$Q$ prisonniers sont enfermés dans une prison située sur un plan cartésien, tristement célèbre car il est impossible de s'en échapper, la zone étant infinie.

Le gardien de prison se tient à l'origine et possède un champ de vision. On sait que le champ de vision du gardien satisfait aux conditions suivantes :

• Le champ de vision est délimité par un polygone simple à $N$ sommets. L'intérieur du polygone, y compris ses segments, constitue l'intérieur du champ de vision, tandis que l'extérieur du polygone, à l'exclusion des segments, constitue l'extérieur du champ de vision.
• Si le gardien peut voir un point spécifique, il peut également voir tout point situé plus près dans cette direction. Plus précisément, pour tout point à l'intérieur du champ de vision, tous les points situés sur le segment reliant ce point à l'origine sont également à l'intérieur du champ de vision.
• Le voisinage de l'origine est toujours visible par le gardien. Plus précisément, il existe un $\varepsilon > 0$ tel que le disque centré à l'origine de rayon $\varepsilon$ est inclus dans le champ de vision du gardien.

Les $Q$ prisonniers enfermés dans cette prison unissent leurs forces pour tenter d'échapper au champ de vision du gardien afin de gagner un peu de liberté. Pour s'échapper plus efficacement, pour tout $2 \leq i \leq N$, le prisonnier $i$ se déplace successivement en fonction de la position du prisonnier $(i-1)$ par rapport au champ de vision :

• Si le prisonnier $(i-1)$ est à l'intérieur du champ de vision après son déplacement, le prisonnier $i$ regarde dans la direction opposée à celle du prisonnier $(i-1)$ et se déplace d'une distance égale à la distance entre eux.
• Si le prisonnier $(i-1)$ est à l'extérieur du champ de vision après son déplacement, le prisonnier $i$ regarde dans la direction du prisonnier $(i-1)$ et se déplace d'une distance égale à la moitié de la distance entre eux. Cependant, comme il est inconfortable de rester sur des points qui ne sont pas des points de la grille entière, après le déplacement, il se déplace vers le point de la grille entière le plus proche, et en cas d'égalité, vers celui le plus proche de l'origine.

En tant que partisan de la liberté, vous avez obtenu les informations sur le champ de vision du gardien et souhaitez informer les prisonniers s'ils se trouvent à l'intérieur ou à l'extérieur du champ de vision. Étant donné les positions initiales des prisonniers, écrivez un programme qui détermine si chaque prisonnier se trouve à l'intérieur ou à l'extérieur du champ de vision après son déplacement.

Entrée

La première ligne contient $N$ et $Q$. ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$)

À partir de la deuxième ligne, $N$ lignes donnent les coordonnées $(x_i, y_i)$ des sommets du champ de vision dans le sens inverse des aiguilles d'une montre. Il est garanti que le polygone donné satisfait aux conditions du problème. ($-10^6 \leq x_i, y_i \leq 10^6$)

À partir de la $(N+2)$-ième ligne, $Q$ lignes donnent les positions initiales $(x_j, y_j)$ de chaque prisonnier. ($-10^6 \leq x_j, y_j \leq 10^6$)

Toutes les coordonnées données sont des entiers.

Sortie

De $i=1$ à $i=Q$, affichez sur la $i$-ième ligne 1 si le $i$-ième prisonnier est à l'intérieur du champ de vision, et 0 sinon.

Exemples

Entrée 1

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

Sortie 1

1
0
1

Entrée 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

Sortie 2

1
0
1
0
1