$Q$ 名囚犯被关押在一个臭名昭著的坐标平面监狱中，由于监狱是一个无限大的区域，他们永远无法越狱。

看守监狱的狱警站在原点，拥有一定的视野。已知狱警的视野满足以下条件：

• 狱警的视野由一个具有 $N$ 个顶点的简单多边形包围，包含多边形边线在内的内部区域为视野内，不包含边线的外部区域为视野外。
• 如果狱警能看到某个点，那么在该方向上比该点更近的点也能看到。严格来说，连接视野内任意点与原点的线段上的所有点都在视野内。
• 原点周围始终在狱警的视野内。严格来说，存在一个 $\varepsilon > 0$，使得以原点为中心、半径为 $\varepsilon$ 的圆包含在狱警的视野内。

被关押的 $Q$ 名囚犯为了争取哪怕一丝自由，正齐心协力试图逃离狱警的视野。为了更有效地逃离视野，对于所有 $2 \leq i \leq N$，第 $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$ 到 $i=Q$ 依次输出，第 $i$ 行输出第 $i$ 位囚犯移动后是否在视野内，如果在视野内则输出 1，否则输出 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