Painting Patterns

Time limit2sMemory limit64 MB

Summary

Count grid cells painted black by up to N rectangle operations, each applying one of three periodic patterns under OR overlap.

Level: Hard8 of 10
Topics: Geometry, Prefix sum, Hash map, Sorting
Solved: No attempts yet

Problem

Lukas has a very large grid. Initially every cell is white. He has three patterns, numbered 1 to 3 (from left to right):

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

Each pattern is periodic and can be extended to fill a rectangle of any size. Lukas paints the grid $N$ times. Each time he chooses an axis-aligned rectangle and one pattern, then paints the cells inside the rectangle black according to that pattern (an X in the pattern paints the cell black, a . leaves it unchanged). The pattern is anchored so that its top-left corner coincides with the top-left corner of the rectangle: the grid point with the smallest $x$ coordinate and the largest $y$ coordinate.

When painted areas overlap, the OR rule applies: a cell is black if it was painted black by at least one operation. For example, applying pattern 1 and then pattern 3 to the same $4 \times 4$ rectangle yields:

XXXX
.X.X
XXXX
.X.X

After all $N$ operations, compute the number of black cells.

Input

The first line contains an integer $N$ ( $0 \le N \le 100000$ ). Each of the next $N$ lines contains five integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , $p$ , where $(x_1, y_1)$ and $(x_2, y_2)$ are two opposite corners of the rectangle (given as grid points), and $p$ ( $1 \le p \le 3$ ) is the pattern number. All coordinates have absolute value at most $10^9$ , and every rectangle is at least one unit wide and one unit tall.

Output

Print a single integer: the number of black cells after all operations.

Examples1

Example 1
Input
```
3
0 0 3 2 3
1 4 4 1 1
2 3 6 0 2
```
Expected output
```
13
```