영화 포스터

영화 포스터

Hrolleifur는 열렬한 영화 애호가로, 영화와 관련된 온갖 물건을 수집한다. 그가 해 온 수집 활동 중 하나는 영화를 홍보하는 포스터를 모으는 것이다. 그는 각 영화마다 적어도 하나의 포스터를 소장하고 있으며, 그 포스터를 자기 방 벽에 붙인다.

이제 Hrolleifur는 여러 해 동안 포스터를 모아 왔으며, 포스터가 벽을 완전히 덮을 날이 가까워지고 있다. Hrolleifur가 포스터를 붙이고 나면 포스터는 그 자리에 단단히 고정된다. 안타깝게도 Hrolleifur는 포스터를 벽에 붙일 때 항상 충분히 꼼꼼하지는 않았기 때문에, 벽이 아직 완전히 덮이지 않았는데도 일부 포스터가 서로 겹친다.

Hrolleifur의 벽과 모든 포스터는 직사각형이다. Hrolleifur는 포스터가 서로 겹치지 않도록 항상 주의한 것은 아니지만, 포스터의 방향이 올바르도록 하는 데에는 언제나 주의를 기울였다. 따라서 포스터의 위쪽 변은 항상 수평이다.

벽에서 아직 사용되지 않은 영역의 넓이는 얼마인가?

[h!]

예제 2

점수 배점

그룹 | 점수 | 제한

1 | 10 | $1 \leq b, h \leq 200$, $0 \leq n \leq 50$, 어떤 두 포스터도 서로 겹치지 않는다

2 | 15 | $1 \leq b, h \leq 200$, $0 \leq n \leq 50$, 같은 지점에서 최대 두 포스터가 겹친다

3 | 20 | $1 \leq b, h \leq 200$, $1 \leq n \leq 1\,000$

4 | 25 | $1 \leq b, h \leq 2\,000$, $1 \leq n \leq 1\,000$

5 | 25 | $1 \leq n \leq 1\,000$

6 | 5 | 추가 제한 없음

첫째 줄에는 세 정수 $b, h$와 $n$가 주어진다. 여기서 $b$와 $h$는 Hrolleifur의 벽의 너비와 높이이고, $n$는 그가 벽에 붙인 포스터의 수이다. 항상 $1 \leq b,h \leq 10^9$와 $1 \leq n \leq 10^5$가 성립한다. 이어서 각각 네 정수 $0 \leq x_1 < x_2 \leq b$와 $0 \leq y_1 < y_2 \leq h$를 포함하는 $n$개의 줄이 주어진다. 여기서 $x_1$, $x_2$는 포스터의 왼쪽 변과 오른쪽 변에서 벽의 왼쪽 면까지의 거리이고, $y_1$, $y_2$는 포스터의 아래쪽 변과 위쪽 변에서 천장까지의 거리이다. 모든 단위는 센티미터이다.

어떤 포스터로도 덮이지 않은 벽 부분의 넓이를 제곱센티미터 단위의 정수 하나로 출력한다.