Có $Q$ tù nhân bị giam giữ trong một nhà tù trên mặt phẳng tọa độ, nơi được mệnh danh là không thể trốn thoát vì khu vực này là vô tận.

Quản ngục đứng tại gốc tọa độ và có một tầm nhìn nhất định. Tầm nhìn của quản ngục thỏa mãn các điều kiện sau:

• Tầm nhìn của quản ngục được bao quanh bởi một đa giác đơn có $N$ đỉnh. Phần bên trong đa giác (bao gồm cả các cạnh) là khu vực nằm trong tầm nhìn, còn phần bên ngoài (không bao gồm các cạnh) là khu vực nằm ngoài tầm nhìn.
• Nếu quản ngục có thể nhìn thấy một điểm cụ thể, thì quản ngục cũng có thể nhìn thấy các điểm gần hơn theo hướng đó. Nói một cách chính xác, mọi điểm nằm trên đoạn thẳng nối gốc tọa độ với bất kỳ điểm nào bên trong tầm nhìn đều nằm trong tầm nhìn.
• Khu vực xung quanh gốc tọa độ luôn nằm trong tầm nhìn của quản ngục. Nói một cách chính xác, tồn tại một số $\varepsilon > 0$ sao cho hình tròn tâm tại gốc tọa độ với bán kính $\varepsilon$ nằm hoàn toàn trong tầm nhìn của quản ngục.

$Q$ tù nhân bị giam trong nhà tù này đang hợp sức để cố gắng thoát khỏi tầm nhìn của quản ngục nhằm giành lấy chút tự do. Để thoát khỏi tầm nhìn một cách hiệu quả hơn, với mọi $2 \leq i \leq N$, tù nhân thứ $i$ sẽ di chuyển theo thứ tự dựa trên việc tù nhân thứ $(i-1)$ có nằm trong tầm nhìn hay không:

• Nếu tù nhân thứ $(i-1)$ nằm trong tầm nhìn sau khi di chuyển, tù nhân thứ $i$ sẽ nhìn theo hướng ngược lại với hướng của tù nhân thứ $(i-1)$ và di chuyển một khoảng bằng khoảng cách giữa hai người.
• Nếu tù nhân thứ $(i-1)$ nằm ngoài tầm nhìn sau khi di chuyển, tù nhân thứ $i$ sẽ nhìn theo hướng của tù nhân thứ $(i-1)$ và di chuyển một khoảng bằng một nửa khoảng cách giữa hai người. Tuy nhiên, vì các điểm không phải là điểm lưới nguyên gây khó chịu khi đứng lâu, sau khi di chuyển, tù nhân sẽ di chuyển đến điểm lưới nguyên gần nhất và gần gốc tọa độ nhất.

Là một người coi trọng tự do, bạn đã thu thập được thông tin về tầm nhìn của quản ngục và muốn sử dụng nó để thông báo cho các tù nhân biết liệu họ đang ở trong hay ngoài tầm nhìn. Với vị trí ban đầu của các tù nhân, hãy viết chương trình xác định xem sau khi di chuyển, mỗi tù nhân nằm trong hay ngoài tầm nhìn.

Dữ liệu vào

Dòng đầu tiên chứa $N$ và $Q$. ($3 \leq N \leq 100\,000; 1 \leq Q \leq 100\,000$)

$N$ dòng tiếp theo, mỗi dòng chứa tọa độ $(x_i, y_i)$ của các đỉnh của đa giác tầm nhìn theo thứ tự ngược chiều kim đồng hồ. Đa giác được cho đảm bảo thỏa mãn các điều kiện của bài toán. ($-10^6 \leq x_i, y_i \leq 10^6$)

$Q$ dòng tiếp theo, mỗi dòng chứa vị trí ban đầu $(x_j, y_j)$ của mỗi tù nhân. ($-10^6 \leq x_j, y_j \leq 10^6$)

Tất cả các tọa độ được cho đều là số nguyên.

Dữ liệu ra

Từ $i=1$ đến $i=Q$, in ra 1 trên dòng thứ $i$ nếu tù nhân thứ $i$ nằm trong tầm nhìn, ngược lại in ra 0.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
0
1

Dữ liệu vào 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

Dữ liệu ra 2

1
0
1
0
1