무한한 영역이 감옥이기 때문에 절대로 탈옥할 수 없어 악명 높은 좌표평면 감옥에 $Q$명의 죄수가 갇혀 있다.

감옥을 감시하는 교도관은 원점에 서 있으며, 죄수들을 볼 수 있는 시야가 있다. 교도관의 시야는 다음 조건을 만족함이 알려져 있다.

• 교도관의 시야는 꼭짓점이 $N$개인 단순다각형으로 둘러싸여 있으며, 단순다각형의 선분을 포함한 내부는 시야 내부, 선분을 제외한 외부는 시야 외부이다.
• 교도관이 특정 지점을 볼 수 있다면, 그 방향으로 그보다 더 가까운 곳도 볼 수 있다. 엄밀히 말해, 시야 내부의 임의의 점과 원점을 잇는 선분 위의 모든 점은 시야 내부에 있다.
• 원점 주변은 교도관이 언제나 볼 수 있다. 엄밀히 말해, 원점을 중심으로 하고 반지름이 $\varepsilon$인 원이 교도관의 시야에 포함되는 $\varepsilon > 0$이 존재한다.

이 감옥에 갇힌 $Q$명의 죄수들이, 조금의 자유라도 쟁취하기 위해 힘을 모아 교도관의 시야에서 벗어나기 위해 시도하고 있다. 시야를 더욱 효과적으로 벗어나기 위해, 모든 $2 \leq i \leq N$에 대해 $i$번 죄수가 $(i-1)$번 죄수가 시야 내에 있는지 여부에 따라 다음과 같이 순서대로 움직인다.

• $(i-1)$번 죄수가 이동한 후 시야 내부에 있었다면, $i$번 죄수는 $(i-1)$번 죄수가 있는 방향의 반대 방향을 본 뒤 둘 사이의 거리만큼 이동한다.
• $(i-1)$번 죄수가 이동한 후 시야 외부에 있었다면, $i$번 죄수는 $(i-1)$번 죄수가 있는 방향을 바라본 뒤, 둘 사이 거리의 절반만큼 이동한다. 단, 정수 격자점이 아닌 점은 오래 있기 불편하게 설계되었으므로, 이동한 후 가장 가까운 정수 격자점 중 원점과 가장 가까운 점으로 이동한다.

자유를 중시하는 당신이 교도관의 시야 정보를 소식통으로부터 입수했고, 이를 이용해서 죄수들에게 시야 안에 있는지 밖에 있는지를 알려주고자 한다. 현재 죄수들의 위치가 주어지면, 이동 후 각 죄수가 시야 내부에 있는지 외부에 있는지를 판별하는 프로그램을 작성하여라.

Input

첫째 줄에 $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$)

주어지는 모든 좌표는 정수이다.

Output

$i=1$부터 $i=Q$까지 차례대로, $i$번째 줄에는 $i$번째 죄수가 시야 내부에 있다면 1, 아니면 0을 출력한다.

Examples

Input 1

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

Output 1

1
0
1

Input 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

Output 2

1
0
1
0
1