Rectangular Fibonacci Spiral#12370
We call the rectangular Fibonacci spiral an infinite broken line on the coordinate plane, consisting of segments parallel to the coordinate axes.
Each spiral is defined by a starting point and is constructed as follows.
Let f_1 = 1,\quad f_2 = 1,\quad f_i = f_{i-1} + f_{i-2} \quad (i \ge 3) — the Fibonacci numbers.
The directions of the segments repeat cyclically in the following order: (1,0), (0,1), (-1,0), (0,-1).
We denote these directions by the arrays dx = [1, 0, -1, 0], \qquad dy = [0, 1, 0, -1].
Let the spiral start at the point P_0 = (X_0, Y_0) = (x, y).
For each i \ge 1, we define:
X_i = X_{i-1} + f_i \cdot dx_{(i-1) \bmod 4}
Y_i = Y_{i-1} + f_i \cdot dy_{(i-1) \bmod 4}
Then the -th segment of the spiral is the segment between the points P_{i-1} = (X_{i-1}, Y_{i-1}) \quad \text{and} \quad P_i = (X_i, Y_i). The spiral continues infinitely.
An example of such a spiral
Given points (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) where such spirals start.
Also given are queries. Each query contains a point .
For each query, you need to determine how many spirals pass through this point.
A point is considered to belong to a spiral if it lies on at least one of its segments (including the endpoints).
In the first line, there is one integer (1 \le n \le 2 \cdot 10^5) — the number of spirals.
In the next lines, there are two integers x_i, y_i (|x_i| , |y_i| \le 10^9) — the starting points of the spirals.
In the next line, there is one integer (1 \le q \le 2 \cdot 10^5) — the number of queries.
In the next lines, there are two integers (|x| , |y| \le 10^7) — the query points.
For each query, output one integer — the number of spirals that pass through the corresponding point.
Example 1
Example 2
For the second test case:
For the first query, the point is passed by spirals numbered 1,2,3,4.
For the second query, the point is passed by spirals numbered .
For the third query, the point is passed by spirals numbered .
For the fourth query, the point is passed by spiral number .
Subtask ( points) : (n \le 10)
Subtask ( points) : (|x_i| , |y_i| , |x| , |y| \le 5)
Subtask ( points) : (q = 1)
Subtask ( points) : (n,q \le 2000)
Subtask ( points) : No additional constraints