На планете Мидав очень близок конец света. Как известно, эта плоская планета, которую можно представить как бесконечную плоскость с декартовыми координатами. На этой планете есть $$$Q$$$ поселений.
В нулевой день на Мидаве случилось заражение. Оно представляет из себя выпуклый многоугольник на $$$N$$$ вершинах. Каждый день площадь заражения меняется неизвестным образом, но для каждого дня c номером $$$i > 0$$$ верно следующее:
Если какое-то поселение окажется внутри или на границе заражения, то все живые организмы в нём сразу же вымрут. Для каждого поселения планеты Мидав осталось совсем немного времени, поэтому ответьте, какой день (включая и нулевой) окажется для поселения последним.
В первой строке дано целое число $$$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$$$ целых чисел — последние дни для поселений в порядке ввода.
41 31 13 13 342 21 24 16 2
0 0 2 4
В примере второе поселение будет заражено в нулевой день, так как лежит на границе заражения.