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

Надзиратель, охраняющий тюрьму, стоит в начале координат и обладает полем зрения. Известно, что поле зрения надзирателя удовлетворяет следующим условиям:

• Поле зрения ограничено простым многоугольником с $N$ вершинами. Внутренняя область многоугольника, включая его стороны, является полем зрения, а область вне сторон — вне поля зрения.
• Если надзиратель видит определенную точку, он также видит все точки, расположенные ближе к нему в том же направлении. Строго говоря, для любой точки внутри поля зрения весь отрезок, соединяющий эту точку с началом координат, также находится внутри поля зрения.
• Окрестность начала координат всегда видна надзирателю. Строго говоря, существует такое $\varepsilon > 0$, что круг с центром в начале координат и радиусом $\varepsilon$ полностью содержится в поле зрения надзирателя.

$Q$ заключенных, стремясь хоть к какой-то свободе, объединяют усилия, чтобы попытаться выйти за пределы поля зрения надзирателя. Чтобы эффективнее покинуть поле зрения, для всех $2 \leq i \leq Q$ заключенный под номером $i$ перемещается последовательно в зависимости от того, находится ли заключенный под номером $(i-1)$ в поле зрения после своего перемещения:

• Если заключенный $(i-1)$ после перемещения находился внутри поля зрения, заключенный $i$ смотрит в направлении, противоположном направлению на заключенного $(i-1)$, и перемещается на расстояние, равное расстоянию между ними.
• Если заключенный $(i-1)$ после перемещения находился вне поля зрения, заключенный $i$ смотрит в направлении на заключенного $(i-1)$ и перемещается на расстояние, равное половине расстояния между ними. Однако, поскольку находиться в точках, не являющихся целочисленными узлами решетки, неудобно, после перемещения он переходит в ближайший целочисленный узел решетки, который находится ближе всего к началу координат.

Вы, ценящий свободу, получили от информатора данные о поле зрения надзирателя и хотите использовать их, чтобы сообщить заключенным, находятся ли они внутри или вне поля зрения. Напишите программу, которая по заданным начальным позициям заключенных определяет, находится ли каждый заключенный внутри или вне поля зрения после своего перемещения.

Входные данные

В первой строке заданы $N$ и $Q$ ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$).

Со второй строки следуют $N$ строк, содержащих координаты вершин $(x_i, y_i)$ поля зрения в порядке против часовой стрелки. Гарантируется, что заданный многоугольник удовлетворяет условиям задачи ($-10^6 \leq x_i, y_i \leq 10^6$).

Начиная с $(N+2)$-й строки, следуют $Q$ строк, содержащих начальные позиции $(x_j, y_j)$ каждого заключенного ($-10^6 \leq x_j, y_j \leq 10^6$).

Все заданные координаты являются целыми числами.

Выходные данные

Для каждого $i$ от $1$ до $Q$ выведите в $i$-й строке $1$, если $i$-й заключенный находится внутри поля зрения, и $0$ в противном случае.

Примеры

Входные данные 1

3 3
-1 -1
9 -1
-1 9
2 2
-2 3
8 0

Выходные данные 1

1
0
1

Входные данные 2

6 5
0 -2
3 -10
14 -3
5 0
10 10
-5 5
0 0
-2 0
6 4
5 -5
-3 11

Выходные данные 2

1
0
1
0
1