건축가

N개의 나무 좌표와 꼭짓점이 12개 이하인 Q개의 축 정렬 다각형이 주어질 때, 각 다각형 내부(경계 포함)에 있는 나무의 수를 센다.

보통6기하배열완전 탐색구현아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

마티야는 주택을 짓는 회사에 취직했다. 매일 여러 고객이 특정 필지에 건물을 올리고 싶다며 주문을 넣는다. 마티야가 할 일은 그 필지 안에 있는 나무를 모두 베는 것이다. 주문을 다 모으면 먼저 필지마다 그 안에 나무가 몇 그루 있는지 세야 한다. 아직 아무것도 베지 않은 현재 상태를 기준으로 세고, 필지 경계선 위에 있는 나무도 안에 있는 것으로 센다.

평면에 놓인 모든 나무의 위치와 고객이 관심을 둔 필지의 정보가 주어진다. 나무 한 그루의 크기는 무시한다. 각 필지는 꼭짓점이 KK개인 다각형이고, 모든 변은 가로 또는 세로다. 한 필지의 변끼리는 절대 서로 만나지 않지만, 서로 다른 필지는 겹칠 수 있다.

입력

첫째 줄에 평면에 있는 나무의 수 NN이 주어진다 (1N1000001 \le N \le 100\,000). 다음 NN개의 줄에는 나무 한 그루의 좌표를 나타내는 정수 XX, YY가 주어진다 (X,Y100000|X|, |Y| \le 100\,000). 좌표가 같은 나무는 없다.

다음 줄에 고객 주문의 수 QQ가 주어진다 (1Q10001 \le Q \le 1\,000). 이어서 주문을 설명하는 2Q2Q개의 줄이 온다. 주문 하나는 두 줄로 이루어진다. 첫 줄에는 필지를 나타내는 다각형의 꼭짓점 수 KK가 주어지고 (4K124 \le K \le 12), 둘째 줄에는 그 필지의 꼭짓점 좌표를 순서대로 짝지어 나열한 정수 2K2K개가 주어진다. 필지 꼭짓점의 좌표도 절댓값이 100000100\,000 이하다.

꼭짓점은 반시계 방향으로 주어진다. 이웃한 두 변은 항상 하나가 가로, 다른 하나가 세로다.

출력

QQ개의 줄을 출력한다. 고객 주문마다 해당 필지에 있는 나무의 수를 한 줄에 하나씩 출력한다. 출력의 AA번째 줄은 입력의 AA번째 주문에 대응해야 한다.