Апокалипсис

문제

На планете Мидав очень близок конец света. Как известно, эта плоская планета, которую можно представить как бесконечную плоскость с декартовыми координатами. На этой планете есть $QQ$ поселений.

В нулевой день на Мидаве случилось заражение. Оно представляет из себя выпуклый многоугольник на $NN$ вершинах. Каждый день площадь заражения меняется неизвестным образом, но для каждого дня c номером $i>0i\; >\; 0$ верно следующее:

1. Если в $ii$-й день заражена любая точка на расстояние $dd$ от исходного многоугольника, то заражены и все остальные точки на расстоянии не большем $dd$ от исходного многоугольника;
2. Пусть $S_{k}S\_\{k\}$ --- площадь заражения в $kk$-й день. Тогда верно $S_i=2\cdot S_{i-1}S\_i\; =\; 2\; \backslash cdot\; S\_\{i-1\}$.

Если какое-то поселение окажется внутри или на границе заражения, то все живые организмы в нём сразу же вымрут. Для каждого поселения планеты Мидав осталось совсем немного времени, поэтому ответьте, какой день (включая и нулевой) окажется для поселения последним.

입력

В первой строке дано целое число $NN$ --- количество точек в многоугольнике заражения нулевого дня $(3\le N\le {10}^5)(3\; \backslash le\; N\; \backslash le\; 10^5)$.

В следующих $NN$ строках даны по два целых числа $c_{xi}c\_\{xi\}$ и $c_{yi}c\_\{yi\}$ --- координаты вершин заражения.

В следующей строке дано целое число $QQ$ --- количество поселений на Мидаве $(1\le Q\le {10}^5)(1\; \backslash le\; Q\; \backslash le\; 10^5)$.

В следующих $QQ$ строках даны по два целых числа $t_{xi}t\_\{xi\}$ и $t_{yi}t\_\{yi\}$ --- координаты каждого из поселений.

Все координаты по модулю не превосходят ${10}^{9}10^9$. Гарантируется, что данный многоугольник выпуклый, а также, что вершины заданы в порядке обхода против часовой стрелки. Гарантируется, что поселения находятся на расстоянии не меньшем ${10}^{-6}10^\{-6\}$ от границы заражения в любой из дней, кроме нулевого.

출력

Выведите $QQ$ целых чисел --- последние дни для поселений в порядке ввода.

힌트

В примере второе поселение будет заражено в нулевой день, так как лежит на границе заражения.

4
1 3
1 1
3 1
3 3
4
2 2
1 2
4 1
6 2

0
0
2
4