103464: [Atcoder]ABC346 E - Paint

Problem Statement

There is a grid with $H$ rows and $W$ columns. Initially, all cells are painted with color $0$.

You will perform the following operations in the order $i = 1, 2, \ldots, M$.

• If $T_i = 1$, repaint all cells in the $A_i$-th row with color $X_i$.

• If $T_i = 2$, repaint all cells in the $A_i$-th column with color $X_i$.

After all operations are completed, for each color $i$ that exists on the grid, find the number of cells that are painted with color $i$.

Constraints

• $1 \leq H, W, M \leq 2 \times 10^5$
• $T_i \in \lbrace 1, 2 \rbrace$
• $1 \leq A_i \leq H$ for each $i$ such that $T_i = 1$,
• $1 \leq A_i \leq W$ for each $i$ such that $T_i = 2$.
• $0 \leq X_i \leq 2 \times 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Let $K$ be the number of distinct integers $i$ such that there are cells painted with color $i$. Print $K + 1$ lines.

The first line should contain the value of $K$.

The second and subsequent lines should contain, for each color $i$ that exists on the grid, the color number $i$ and the number of cells painted with that color.

Specifically, the $(i + 1)$-th line $(1 \leq i \leq K)$ should contain the color number $c_i$ and the number of cells $x_i$ painted with color $c_i$, in this order, separated by a space.

Here, print the color numbers in ascending order. That is, ensure that $c_1 < c_2 < \ldots < c_K$. Note also that $x_i > 0$ is required.

Sample Input 1

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

Sample Output 1

3
0 5
2 4
5 3

The operations will change the colors of the cells in the grid as follows:

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

Eventually, there are five cells painted with color $0$, four with color $2$, and three with color $5$.

Sample Input 2

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

Sample Output 2

1
10000 1

Sample Input 3

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

Sample Output 3

5
6 5
7 5
8 5
9 5
10 5

问题描述

有一个$H$行$W$列的网格。最初，所有的单元格都被涂成颜色$0$。

你将按照顺序执行以下操作：$i = 1, 2, \ldots, M$。

• 如果$T_i = 1$，将第$A_i$行的所有单元格涂成颜色$X_i$。

• 如果$T_i = 2$，将第$A_i$列的所有单元格涂成颜色$X_i$。

完成所有操作后，对于网格中存在的每个颜色$i$，找出涂成颜色$i$的单元格数量。

限制条件

• $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$
• 所有的输入值都是整数。

输入

输入通过标准输入以以下格式给出：

$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 < c_2 < \ldots < c_K$。注意还要求$x_i > 0$。

样例输入1

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

样例输出1

3
0 5
2 4
5 3

操作将改变网格中单元格的颜色如下：

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

最终，有五个单元格涂成颜色$0$，四个涂成颜色$2$，三个涂成颜色$5$。

样例输入2

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

样例输出2

1
10000 1

样例输入3

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

样例输出3

5
6 5
7 5
8 5
9 5
10 5