Апокалипсис
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На планете Мидав очень близок конец света. Как известно, эта плоская планета, которую можно представить как бесконечную плоскость с декартовыми координатами. На этой планете есть $$$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$$$ целых чисел — последние дни для поселений в порядке ввода.

Пример

Входные данные
4
1 3
1 1
3 1
3 3
4
2 2
1 2
4 1
6 2
Выходные данные
0
0
2
4

Примечание

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