식탁

시간 제한5초메모리 제한512 MB

요약
서로 겹치지 않는 직사각형 장애물들이 있는 직사각형 탁자에서, 각 쿼리 직사각형을 장애물과 겹치지 않게 놓을 수 있는 정수 위치의 수를 센다.
난이도

보통10점 중 7점

유형
누적 합, 행렬, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

클레망틴 드뵈프는 고급 식당에 놓을 새 식탁을 사려고 한다. 그가 고른 모델에는 넓고 섬세한 장식이 여러 개 달려 있다. 다만 이 장식 때문에 접시를 내고 치우는 동선이 흐트러지면 곤란하다.

장식이 덮은 자리는 평평하지 않아서 접시를 올릴 수 없다. 클레망틴은 접시마다 장식과 겹치지 않는 안전한 자리가 몇 군데인지 알고 싶다.

식탁은 가로 길이가 XX이고 세로 길이가 YY인 직사각형이며, 단위는 밀리미터다. 식탁의 한 꼭짓점을 원점으로 두고 가로 방향을 xx축, 세로 방향을 yy축으로 잡는다. 식탁 위에는 장식 NN개가 놓여 있다. 각 장식은 변이 식탁의 변과 평행한 직사각형이고 위치가 고정되어 있다. 장식끼리 겹치지는 않지만 서로 맞닿을 수는 있다.

접시도 변이 식탁의 변과 평행한 직사각형이고, 놓는 방향이 미리 정해져 있어서 돌려 놓을 수 없다. 종업원은 밀리미터 단위로 정확히 놓으므로 접시의 좌표는 항상 정수다. 가로 ww, 세로 hh인 접시를 (a,b)(a, b)에 놓으면 (a,b)(a, b)와 (a+w,b+h)(a + w, b + h) 사이의 직사각형을 차지하며, aa와 bb는 0≤a≤X−w0 \le a \le X - w와 0≤b≤Y−h0 \le b \le Y - h를 만족하는 정수다. 접시는 어떤 장식과도 겹치면 안 되지만, 장식의 변에 닿는 것은 괜찮다.

접시 DD개 각각에 대해 안전하게 놓을 수 있는 정수 위치가 몇 개인지 세어라. 식탁에는 한 번에 접시 하나만 올리므로 접시끼리 겹치는 경우는 생각하지 않고, 접시마다 따로 세면 된다.

입력

첫째 줄에 정수 XX, YY, NN, DD가 공백으로 구분되어 주어진다.

다음 NN개 줄에는 장식 하나의 좌표가 정수 xx, x′x', yy, y′y'로 주어진다. 0≤x<x′≤X0 \le x < x' \le X이고 0≤y<y′≤Y0 \le y < y' \le Y이며, 이 장식은 (x,y)(x, y)와 (x′,y′)(x', y') 사이의 직사각형을 차지한다.

그다음 DD개 줄에는 접시 하나의 가로 길이 xx와 세로 길이 yy가 정수로 주어진다. 0<x≤X0 < x \le X이고 0<y≤Y0 < y \le Y이다.

제한

  • 1≤X,Y≤20001 \le X, Y \le 2000
  • 0≤N≤1 000 0000 \le N \le 1\,000\,000
  • 1≤D≤100 0001 \le D \le 100\,000

출력

DD개 줄을 출력한다. ii번째 줄에는 ii번째 접시를 장식과 겹치지 않게 놓을 수 있는 정수 위치의 개수를 출력한다.

그림

첫 번째 예제의 식탁이다. 검은 칸은 장식이 덮은 자리이고, 왼쪽 아래 꼭짓점이 (0,0)(0, 0)이며 오른쪽으로 갈수록 xx가, 위로 갈수록 yy가 커진다.

예제2

  1. 예제 1

    입력
    7 5 3 9
1 2 0 1
5 7 2 5
0 1 2 4
7 1
3 5
5 3
2 2
3 3
4 4
4 5
6 2
1 1
    예상 출력
    1
1
0
13
5
1
0
0
26

  2. 예제 2

    입력
    2 2 1 2
0 2 0 2
1 1
2 2
    예상 출력
    0
0