아포칼립스

기 행성 미다브는 세계의 종말이 가까이 와 있다. 이 행성은 데카르트 좌표계를 갖춘 무한한 평면으로 볼 수 있는 평평한 행성이다. 미다브에는 $Q$개의 정착지가 있다.

0일째에 미다브에서 감염이 발생했다. 감염 범위는 꼭짓점이 $N$개인 볼록 다각형이다. 감염 범위는 매일 알 수 없는 방식으로 변하지만, $i > 0$인 모든 날 $i$에 대해 다음이 성립한다.

1. $i$일째에 원래 다각형으로부터 거리 $d$에 있는 점이 감염되었다면, 원래 다각형으로부터 거리가 $d$ 이하인 다른 모든 점도 감염된다.
2. $S_k$를 $k$일째의 감염 면적이라 하자. 그러면 $S_i = 2 \cdot S_{i-1}$이다.

정착지가 감염 범위의 내부나 경계에 놓이면, 그곳의 모든 생명체는 즉시 멸종한다. 각 정착지에 남은 시간이 얼마 없으므로, 정착지마다 마지막 날(0일째 포함)을 구하라.

첫 줄에 정수 $N$이 주어진다. 0일째 감염 다각형의 꼭짓점 개수이다 $(3 \le N \le 10^5)$.

다음 $N$개 줄에는 꼭짓점의 좌표 $c_{xi}$와 $c_{yi}$가 각각 주어진다.

다음 줄에는 정수 $Q$가 주어진다. 미다브의 정착지 개수이다 $(1 \le Q \le 10^5)$.

다음 $Q$개 줄에는 정착지의 좌표 $t_{xi}$와 $t_{yi}$가 각각 주어진다.

모든 좌표의 절댓값은 $10^9$ 이하이다. 주어진 다각형은 볼록하며, 꼭짓점은 반시계 방향 순서로 주어진다. 0일째를 제외한 모든 날에, 각 정착지는 감염 범위의 경계로부터 $10^{-6}$ 이상 떨어져 있다.

$Q$개의 정수를 출력한다. 입력 순서대로 각 정착지의 마지막 날이다.

예시에서 두 번째 정착지는 경계 위에 있으므로 0일째에 감염된다.