Description

$n$ opaque rectangles of different colors are placed on a sheet of white paper with width $a$ and height $b$. Their edges are parallel to the edges of the paper, and all rectangles are placed inside the paper.

Now they are overlapped. After overlapping, various colored regions of different shapes will appear. You need to find the area of each color.

The coordinates of the lower-left corner of the paper are the origin $(0,0)$, and the coordinate axes are parallel to the edges of the paper.

Input Format

The input has a total of $n+1$ lines.

The first line contains three integers $a,b,n$.

Lines $2$ to $n+1$ each contain five integers $llx,lly,urx,ury,color$, representing the coordinates of the lower-left corner and upper-right corner of a rectangle, and its color index. Note: Color $1$ is the same as the color of the bottom white paper.

Output Format

Output a summary of every visible color and its total area. Each line should contain the color index and the area. Even if the regions of a color are not connected, you should still output the total area. Output the results in increasing order of $color$, and do not output colors with zero visible area.

20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

1 91
2 84
3 187
4 38

Hint

Explanation for Sample Input/Output 1

After all layers have covered the paper, the areas of the colors are $91,84,187,38$, respectively.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 10^3$, $1 \leq a,b \leq 10^4$, $1 \leq llx,lly,urx,ury \leq a,b$, $1 \leq color \leq n+1$.

Translated by ChatGPT 5