Informatica Online Judge

  Shaping Regions [0292 / 0124]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 16


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

N개의 다양한 색상을 가지는 불투명한 사각형들이 가로 A, 세로 B 크기의 흰색 직사각형 보드 위에 놓여있다. 이 사각형들은 흰색 직사각형 보드의 모든 변과 평행하게 배치된다.

보드 위의 모든 사각형이 불투명하기 때문에 다른 사각형에 덮혀있는 사각형의 부분은 위에서 볼 수 없다.

보드위에 놓일 사각형의 정보가 주어질 때, 최종적으로 보여지는 사각형들의 넓이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 보드의 크기 A, B, 그리고 보드에 놓일 사각형의 수 N이 주어진다.
(단, A, B는 10,000이하의 자연수, N은 1,000이하의 자연수이다.)

두 번째 줄부터 N+1번째 줄까지는 놓일 사각형의 왼쪽아래 좌표 x, y와 오른쪽 위 좌표 x, y 그리고 색깔 C가 공백으로 구분되어 입력된다.
(1 <= C <= 2500)

Output

각 사각형의 색깔별로 오름차순으로 색의 번호와 넓이를 출력한다. 보이지 않는 색에 대해서는 출력하지 않는다.

IO Example

입력
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

* 설명 : 위 입력대로 사각형을 쌓으면 다음과 같이 된다. 모든 영역의 크기를 구해보면 출력결과와 같다.
11111111111111111111
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11111111441111111111
11111111441111111111

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]