涂色

题目描述

有一个 $H$ 行 $W$ 列的网格。初始时,所有格子都涂有颜色 $0$。

接下来按 $i = 1, 2, \ldots, M$ 的顺序执行以下操作:

如果 $T_i = 1$,将第 $A_i$ 行的所有格子重新涂成颜色 $X_i$。

如果 $T_i = 2$,将第 $A_i$ 列的所有格子重新涂成颜色 $X_i$。

所有操作结束后,对于网格上存在的每一种颜色 $i$,求涂有颜色 $i$ 的格子数。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$ $M$
$T_1$ $A_1$ $X_1$
$T_2$ $A_2$ $X_2$
$\vdots$
$T_M$ $A_M$ $X_M$

输出格式

设 $K$ 为满足「存在涂有颜色 $i$ 的格子」的不同整数 $i$ 的个数。输出 $K + 1$ 行。

第一行输出 $K$ 的值。

第二行及之后的行,对于网格上存在的每一种颜色 $i$,输出颜色编号 $i$ 和涂有该颜色的格子数。

具体来说,第 $(i + 1)$ 行 $(1 \leq i \leq K)$ 输出颜色编号 $c_i$ 和涂有颜色 $c_i$ 的格子数 $x_i$,以空格分隔,按此顺序。

这里,颜色编号要按升序输出。即保证 $c_1 \lt c_2 \lt \ldots \lt c_K$。另外注意 $x_i \gt 0$。

样例

3 4 4
1 2 5
2 4 0
1 3 3
1 3 2

3
0 5
2 4
5 3

操作对网格中格子颜色的改变如下:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

最终,有 5 个格子涂有颜色 0,4 个格子涂有颜色 2,3 个格子涂有颜色 5。

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

1
10000 1

5 5 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
2 2 7
2 3 8
2 4 9
2 5 10

5
6 5
7 5
8 5
9 5
10 5

数据范围

• $1 \leq H, W, M \leq 2 \times 10^5$
• $T_i \in \lbrace 1, 2 \rbrace$
• 对于满足 $T_i = 1$ 的每个 $i$,有 $1 \leq A_i \leq H$
• 对于满足 $T_i = 2$ 的每个 $i$,有 $1 \leq A_i \leq W$
• $0 \leq X_i \leq 2 \times 10^5$
• 所有输入值均为整数。