30595번 - Апокалипсис 다국어

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

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

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

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

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

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

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

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

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

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

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