There are $Q$ prisoners trapped in a notorious coordinate plane prison, from which escape is impossible because the area is infinite.

The prison guard stands at the origin and has a field of vision. The guard's field of vision is known to satisfy the following conditions:

• The guard's field of vision is enclosed by a simple polygon with $N$ vertices. The interior of the polygon, including its edges, is inside the field of vision, while the exterior, excluding the edges, is outside.
• If the guard can see a specific point, they can also see everything closer in that direction. Formally, for any point inside the field of vision, all points on the line segment connecting that point to the origin are also inside the field of vision.
• The area around the origin is always visible to the guard. Formally, there exists an $\varepsilon > 0$ such that a circle centered at the origin with radius $\varepsilon$ is contained within the guard's field of vision.

The $Q$ prisoners trapped in this prison are working together to try and escape the guard's field of vision to gain even a little bit of freedom. To escape the field of vision more effectively, for all $2 \leq i \leq Q$, the $i$-th prisoner moves sequentially based on whether the $(i-1)$-th prisoner is within the field of vision:

• If the $(i-1)$-th prisoner was inside the field of vision after moving, the $i$-th prisoner looks in the opposite direction of the $(i-1)$-th prisoner and moves by the distance between them.
• If the $(i-1)$-th prisoner was outside the field of vision after moving, the $i$-th prisoner looks in the direction of the $(i-1)$-th prisoner and moves by half the distance between them. However, since points that are not integer grid points are uncomfortable to stay in, after moving, the prisoner moves to the nearest integer grid point that is closest to the origin.

You, who value freedom, have obtained information about the guard's field of vision from a source and want to use it to inform the prisoners whether they are inside or outside the field of vision. Given the initial positions of the prisoners, write a program that determines whether each prisoner is inside or outside the field of vision after their move.

Input

The first line contains $N$ and $Q$ ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$).

From the second line, $N$ lines follow, each containing the coordinates $(x_i, y_i)$ of the vertices of the field of vision in counter-clockwise order. The given polygon is guaranteed to satisfy the conditions of the problem. ($-10^6 \leq x_i, y_i \leq 10^6$)

From the $(N+2)$-th line, $Q$ lines follow, each containing the initial position $(x_j, y_j)$ of each prisoner. ($-10^6 \leq x_j, y_j \leq 10^6$)

All given coordinates are integers.

Output

For each $i$ from $1$ to $Q$, output 1 if the $i$-th prisoner is inside the field of vision after moving, and 0 otherwise, on the $i$-th line.

Examples

Input 1

3 3
-1 -1
9 -1
-1 9
2 2
-2 3
8 0

Output 1

1
0
1

Input 2

6 5
0 -2
3 -10
14 -3
5 0
10 10
-5 5
0 0
-2 0
6 4
5 -5
-3 11

Output 2

1
0
1
0
1