K. Apocalypse
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On the planet Midav, the end of the world is very near. As is known, this flat planet can be represented as an infinite plane with Cartesian coordinates. On this planet, there are $$$Q$$$ settlements.

On day zero, an infection occurred on Midav. It is represented by a convex polygon with $$$N$$$ vertices. Each day, the area of the infection changes in an unknown manner, but for each day with number $$$i \gt 0$$$, the following holds:

  1. If any point is infected on the $$$i$$$-th day at a distance $$$d$$$ from the original polygon, then all other points at a distance no greater than $$$d$$$ from the original polygon are also infected;
  2. Let $$$S_{k}$$$ be the area of the infection on the $$$k$$$-th day. Then it holds that $$$S_i = 2 \cdot S_{i-1}$$$.

If any settlement is located inside or on the boundary of the infection, all living organisms in it will immediately die. For each settlement on the planet Midav, there is very little time left, so answer which day (including day zero) will be the last for the settlement.

Input

The first line contains an integer $$$N$$$ — the number of points in the infection polygon on day zero $$$(3 \le N \le 10^5)$$$.

The next $$$N$$$ lines contain two integers $$$c_{xi}$$$ and $$$c_{yi}$$$ — the coordinates of the vertices of the infection.

The following line contains an integer $$$Q$$$ — the number of settlements on Midav $$$(1 \le Q \le 10^5)$$$.

The next $$$Q$$$ lines contain two integers $$$t_{xi}$$$ and $$$t_{yi}$$$ — the coordinates of each settlement.

All coordinates in absolute value do not exceed $$$10^9$$$. It is guaranteed that the given polygon is convex and that the vertices are given in counter-clockwise order. It is also guaranteed that the settlements are at least $$$10^{-6}$$$ away from the boundary of the infection on any day except day zero.

Output

Output $$$Q$$$ integers — the last days for the settlements in the order of input.

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

In the example, the second settlement will be infected on day zero, as it lies on the boundary of the infection.