無限の領域が監獄であるため決して脱獄できないことで悪名高い座標平面上の監獄に、$Q$人の囚人が閉じ込められている。

監獄を監視する看守は原点に立っており、囚人たちを見渡せる視界を持っている。看守の視界は以下の条件を満たすことが知られている。

• 看守の視界は頂点が $N$ 個の単純多角形で囲まれており、単純多角形の線分を含む内部は視界の内部、線分を除いた外部は視界の外部である。
• 看守がある地点を見ることができるならば、その方向にあるより近い地点も見ることができる。厳密に言えば、視界内部の任意の点と原点を結ぶ線分上のすべての点は視界内部にある。
• 原点の周辺は看守が常に視界に収めている。厳密に言えば、原点を中心とし半径が $\varepsilon$ である円が看守の視界に含まれるような $\varepsilon > 0$ が存在する。

この監獄に閉じ込められた $Q$ 人の囚人たちは、わずかな自由でも勝ち取るために力を合わせ、看守の視界から脱出しようと試みている。視界からより効果的に脱出するため、すべての $2 \leq i \leq N$ について、$i$ 番目の囚人は $(i-1)$ 番目の囚人が視界内にいるかどうかに応じて、以下の順序で移動する。

• $(i-1)$ 番目の囚人が移動した後に視界内部にいた場合、$i$ 番目の囚人は $(i-1)$ 番目の囚人がいる方向の反対方向を向き、両者の距離だけ移動する。
• $(i-1)$ 番目の囚人が移動した後に視界外部にいた場合、$i$ 番目の囚人は $(i-1)$ 番目の囚人がいる方向を向き、両者の距離の半分だけ移動する。ただし、整数格子点ではない点は滞在しにくいため、移動した後に最も近い整数格子点のうち、原点に最も近い点へ移動する。

自由を重んじるあなたは、看守の視界情報を情報源から入手した。これを利用して、囚人たちに彼らが視界の中にいるのか外にいるのかを知らせようとしている。現在の囚人たちの位置が与えられたとき、移動後の各囚人が視界内部にいるか外部にいるかを判定するプログラムを作成せよ。

入力

1行目に $N$ と $Q$ が与えられる。 ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$)

2行目から $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