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 > 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 · 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.

The first line contains an integer N — the number of points in the infection polygon on day zero (3 ≤ N ≤ 10⁵).

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 ≤ Q ≤ 10⁵).

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⁹. 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⁻⁶ away from the boundary of the infection on any day except day zero.

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

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