W nieskończonym więzieniu, z którego ucieczka jest niemożliwa, w układzie współrzędnych uwięzionych jest $Q$ więźniów.

Strażnik pilnujący więzienia stoi w punkcie $(0, 0)$ i posiada określone pole widzenia. Wiadomo, że pole widzenia strażnika spełnia następujące warunki:

• Pole widzenia jest ograniczone wielokątem prostym o $N$ wierzchołkach. Wnętrze wielokąta wraz z jego krawędziami stanowi pole widzenia, natomiast obszar poza krawędziami znajduje się poza polem widzenia.
• Jeśli strażnik widzi dany punkt, widzi również wszystkie punkty znajdujące się bliżej niego w tym samym kierunku. Ściślej mówiąc, dla dowolnego punktu wewnątrz pola widzenia, każdy punkt leżący na odcinku łączącym ten punkt z początkiem układu współrzędnych również znajduje się wewnątrz pola widzenia.
• Otoczenie początku układu współrzędnych jest zawsze widoczne dla strażnika. Ściślej mówiąc, istnieje takie $\varepsilon > 0$, że koło o środku w $(0, 0)$ i promieniu $\varepsilon$ jest zawarte w polu widzenia strażnika.

$Q$ więźniów uwięzionych w tym więzieniu próbuje wydostać się z pola widzenia strażnika. Aby skuteczniej uciec, dla każdego $2 \leq i \leq N$, więzień $i$ porusza się w zależności od tego, czy więzień $(i-1)$ znajduje się wewnątrz pola widzenia, zgodnie z następującymi zasadami:

• Jeśli po ruchu więźnia $(i-1)$ znajdował się on wewnątrz pola widzenia, więzień $i$ patrzy w kierunku przeciwnym do więźnia $(i-1)$ i przesuwa się o odległość równą odległości między nimi.
• Jeśli po ruchu więźnia $(i-1)$ znajdował się on poza polem widzenia, więzień $i$ patrzy w kierunku więźnia $(i-1)$ i przesuwa się o połowę odległości między nimi. Ponieważ przebywanie w punktach niebędących punktami kratowymi jest niewygodne, po ruchu więzień przesuwa się do najbliższego punktu kratowego, a w przypadku kilku takich punktów – do tego, który znajduje się najbliżej początku układu współrzędnych.

Jako osoba ceniąca wolność, zdobyłeś informacje o polu widzenia strażnika i chcesz poinformować więźniów, czy znajdują się wewnątrz, czy poza nim. Mając dane początkowe pozycje więźniów, napisz program, który określi, czy po wykonaniu ruchu każdy więzień znajduje się wewnątrz, czy poza polem widzenia.

Wejście

W pierwszej linii podano $N$ oraz $Q$ ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$).

W kolejnych $N$ liniach podano współrzędne wierzchołków wielokąta pola widzenia $(x_i, y_i)$ w kolejności przeciwną do ruchu wskazówek zegara. Gwarantuje się, że podany wielokąt spełnia warunki zadania ($-10^6 \leq x_i, y_i \leq 10^6$).

W kolejnych $Q$ liniach podano początkowe pozycje więźniów $(x_j, y_j)$ ($-10^6 \leq x_j, y_j \leq 10^6$).

Wszystkie podane współrzędne są liczbami całkowitymi.

Wyjście

Dla każdego więźnia od $i=1$ do $i=Q$, w $i$-tej linii wypisz 1, jeśli więzień znajduje się wewnątrz pola widzenia, lub 0 w przeciwnym przypadku.

Przykład

Wejście 1

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

Wyjście 1

1
0
1

Wejście 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

Wyjście 2

1
0
1
0
1