HZNUOJ

Little Sub and Triangles

Tags:   
Time Limit:  2 s      Memory Limit:   256 MB
Submission:1190     AC:189     Score:89.20

Description

Little Sub loves triangles. Now he has a problem for you.

Given n points on the two-dimensional plane, you have to answer many queries. Each query require you to calculate the number of triangles which are formed by three points in the given points set and their area S should satisfy l ≤ S ≤ r.

Specially, to simplify the calculation, even if the formed triangle degenerate to a line or a point which S = 0, we still consider it as a legal triangle.

Input

The first line contains two integer n, q(1 ≤ n ≤ 250, 1 ≤ q ≤ 100000), indicating the total number of points.

All points will be described in the following n lines by giving two integers x,y(−10^7 ≤ x,y ≤ 10^7) as their coordinates.

All queries will be described in the following q lines by giving two integers l, r(0 ≤ l ≤ r ≤ 10^18).

Output

Output the answer in one line for each query.

Samples

input
4 2 0 1 100 100 0 0 1 0 0 50 0 2
output
3 1

Author

CHEN, Jingbang