패턴 칠하기

시간 제한2초메모리 제한64 MB

요약

최대 N개의 직사각형 칠하기 연산이 세 가지 주기적 패턴 중 하나로 수행될 때 검게 칠해진 격자 칸 수를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 누적 합, 해시맵, 정렬
정답자: 아직 제출이 없습니다

문제

루카스에게 매우 큰 격자가 있습니다. 처음에는 모든 칸이 흰색입니다. 그에게는 왼쪽부터 순서대로 1번부터 3번까지 번호가 매겨진 세 가지 패턴이 있습니다.

XXXX    X.X.    X.X.
....    X.X.    .X.X
XXXX    X.X.    X.X.
....    X.X.    .X.X

각 패턴은 주기적이며 임의의 크기의 직사각형을 채우도록 확장할 수 있습니다. 루카스는 격자를 $N$ 번 칠합니다. 매번 축에 평행한 직사각형 하나와 패턴 하나를 고른 뒤, 그 패턴에 따라 직사각형 내부의 칸을 검은색으로 칠합니다(패턴의 X는 해당 칸을 검게 칠하고, .은 그대로 둡니다). 패턴은 그 왼쪽 위 모서리가 직사각형의 왼쪽 위 모서리, 즉 $x$ 좌표가 가장 작고 $y$ 좌표가 가장 큰 격자점과 일치하도록 놓입니다.

칠한 영역이 겹칠 때는 OR 규칙을 따릅니다. 즉, 어떤 칸은 한 번이라도 검게 칠해졌다면 검은색입니다. 예를 들어, 같은 $4 \times 4$ 직사각형에 패턴 1을 칠한 다음 패턴 3을 칠하면 다음과 같이 됩니다.

XXXX
.X.X
XXXX
.X.X

$N$ 번의 작업을 모두 마친 뒤, 검은 칸의 개수를 구하세요.

입력

첫째 줄에 정수 $N$ ( $0 \le N \le 100000$ )이 주어집니다. 이어지는 $N$ 개의 줄에는 각각 다섯 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ , $p$ 가 주어집니다. 여기서 $(x_1, y_1)$ 과 $(x_2, y_2)$ 는 직사각형의 마주 보는 두 꼭짓점(격자점)이고, $p$ ( $1 \le p \le 3$ )는 패턴 번호입니다. 모든 좌표의 절댓값은 $10^9$ 이하이며, 모든 직사각형의 가로와 세로 길이는 각각 1 이상입니다.

출력

모든 작업을 마친 뒤 검은 칸의 개수를 정수 하나로 출력하세요.

예제1

예제 1
입력
```
3
0 0 3 2 3
1 4 4 1 1
2 3 6 0 2
```
예상 출력
```
13
```