감옥

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

교도관은 원점에 서 있으며 시야를 가지고 있다. 교도관의 시야에 대해 다음 조건이 성립함이 알려져 있다.

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

$Q$명의 죄수는 조금의 자유라도 얻으려고 교도관의 시야에서 벗어나고자 한다. 더 효과적으로 벗어나기 위해, 모든 $2\leq i\leq Q$에 대해 $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$개의 줄에 시야를 둘러싸는 다각형이 주어진다. 모든 $1 \leq i \leq N$에 대해 $(i+1)$번째 줄에 $x_i$와 $y_i$가 공백으로 구분되어 주어진다. ($-1\,000\,000\leq x_i,y_i\leq 1\,000\,000$) 이는 다각형의 $i$번째 점이 $(x_i,y_i)$이며, 점들이 반시계 방향으로 주어진다는 뜻이다.

이어지는 $Q$개의 줄에 죄수 정보가 주어진다. 모든 $1 \leq j \leq Q$에 대해 $(N+j+1)$번째 줄에 $u_j$와 $v_j$가 공백으로 구분되어 주어진다. ($-1\,000\,000\leq u_j,v_j\leq 1\,000\,000$) 이는 $j$번 죄수의 처음 위치가 $(u_j,v_j)$라는 뜻이다.

주어지는 모든 좌표는 정수이다. 주어지는 다각형은 문제에서 설명한 시야 조건을 만족한다. 주어지는 다각형의 연속된 세 점은 한 직선 위에 있지 않다.

$Q$개의 줄을 출력한다. 모든 $1 \leq i \leq Q$에 대해 $i$번째 죄수가 시야 내부에 있으면 $1$을, 그렇지 않으면 $0$을 $i$번째 줄에 출력한다.