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.

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 the answer in one line for each query.