시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 (추가 시간 없음) 512 MB 68 11 10 20.000%

문제

농부 John의 목장은 특이하게 생겼다. 볼록 다각형을 이루는 N개의 말뚝이 있고, 각 말뚝 쌍에 대해 두 말뚝을 선분으로 잇는 밧줄이 존재한다. 이 밧줄은 높이가 상당해서 소들이 넘어 다니기 어렵다.

소 Alice와 Bessie는 서로의 가장 친한 친구이다. 하지만 농부 John이 그들을 떨어뜨려 놓았기 때문에 현재는 멀리 위치해 있다.

위 그림은 N=4일때의 한 예를 그림으로 나타낸 것이다. 총 6개의 밧줄이 존재한다.

Alice는 Bessie가 있는 곳으로 놀러 가려고 한다. 하지만 밧줄을 넘는 것은 쉽지 않기 때문에, 넘는 밧줄의 개수를 최소로 하여 가려고 한다.

위 그림의 경우, 밧줄을 2번 넘어서 가는 것이 최적임을 알 수 있다.

농부 John이 두 소의 위치를 자주 바꾸기 때문에, Q개의 위치 쌍에 대해 각각의 경우 넘어야 하는 밧줄의 최소 개수를 구하고자 한다. Alice와 Bessie를 도와 문제를 해결해주자.

두 개 이상의 밧줄이 교차하는 점을 통해 넘어가는 것은 한꺼번에 넘은 것으로 인정되지 않는다. 예를 들어 3개 밧줄이 교차하는 점을 통해 한꺼번에 넘어도 3번으로 센다. 또한, 같은 밧줄을 여러 번 넘는 것은 여러 번 센다.

입력

첫 번째 줄에 말뚝의 수 N(3 ≤ N ≤ 5,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 2개의 정수 x와 y가 주어진다. 이는 말뚝들의 좌표를 나타낸다. 말뚝의 정보는 반시계방향 순서대로 주어진다.

N+2번째 줄에 쿼리의 개수 Q(1 ≤ Q ≤ 10,000)가 주어진다. N+3번째 줄부터 Q개의 줄에는 4개의 정수 x1, y1, x2, y2가 주어진다. (x1, y1)은 Alice의 좌표를, (x2, y2)은 Bessie의 좌표를 나타낸다.

주어지는 모든 좌표의 절댓값은 108 이하이다.

N개의 말뚝은 내각이 180도 미만인 볼록 다각형을 이루고 있으며, 주어지는 소들의 위치는 밧줄 위에 있지 않다. 또한, 각 쿼리에 대해 N개의 말뚝 및 두 소의 좌표는 서로 다르다.

출력

쿼리가 주어진 순서대로 Q개의 줄에 걸쳐 각 줄에 그 쿼리에 대한 답을 출력한다.

예제 입력 1

4
-5 -5
5 -5
5 5
-5 5
3
0 2 0 -2
2 0 -2 0
6 0 0 -6

예제 출력 1

2
2
0