A. Angle Beats
time limit per test
4.0 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given $$$n$$$ points $$$P_1, P_2, \cdots, P_n$$$ on 2D plane and $$$q$$$ queries. In $$$i$$$-th query, a point $$$A_i$$$ is given, and you should determine the number of tuples $$$(u, v)$$$ that $$$1 \le u < v \le n$$$ and $$$A_i, P_u, P_v$$$ form a non-degenerate right-angled triangle.

Input

The first line contains two positive integers $$$n,q~(2\le n \le 2\,000, 1\le q \le 2\,000)$$$, denoting the number of given points and the number of queries.

Next $$$n$$$ lines each contains two integers $$$x_i, y_i~(|x_i|,|y_i| \le 10^9)$$$, denoting a given point $$$P_i$$$.

Next $$$q$$$ lines each contains two integers $$$x_i, y_i~(|x_i|,|y_i| \le 10^9)$$$, denoting a query point $$$A_i$$$.

It is guaranteed that the input $$$n+q$$$ points are all pairwise distinct.

Output

Output $$$q$$$ lines each contains a non-negative integer, denoting the answer to corresponding query.

Example
Input
4 2
0 1
1 0
0 -1
-1 0
0 0
1 1
Output
4
3
Note

For query $$$(0,0)$$$, the 4 right-angled triangles are

  • $$$\{(0,0),(0,1),(1,0)\}$$$
  • $$$\{(0,0),(0,1),(-1,0)\}$$$
  • $$$\{(0,0),(0,-1),(1,0)\}$$$
  • $$$\{(0,0),(0,-1),(-1,0)\}$$$

For query $$$(1,1)$$$, the 3 right-angled triangles are

  • $$$\{(1,1),(0,1),(1,0)\}$$$
  • $$$\{(1,1),(0,1),(0,-1)\}$$$
  • $$$\{(1,1),(1,0),(-1,0)\}$$$