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

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

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

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

В первой строке дано целое число N — количество точек в многоугольнике заражения нулевого дня (3 ≤ N ≤ 10⁵).

В следующих N строках даны по два целых числа c_xi и c_yi — координаты вершин заражения.

В следующей строке дано целое число Q — количество поселений на Мидаве (1 ≤ Q ≤ 10⁵).

В следующих Q строках даны по два целых числа t_xi и t_yi — координаты каждого из поселений.

Все координаты по модулю не превосходят 10⁹. Гарантируется, что данный многоугольник выпуклый, а также что вершины заданы в порядке обхода против часовой стрелки. Гарантируется, что поселения находятся на расстоянии не меньшем 10⁻⁶ от границы заражения в любой из дней, кроме нулевого.

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

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