题目描述

强哥现在获取了一张画有 $n$ 行 $m$ 列空白格子的纸。

强哥现在需要在纸上写数字，并且每次会选择在同一行或者同一列写下数字。

如果那个格子之前有数字，会被新写下的数字覆盖。

强哥想要知道他的操作全部完成之后，纸上每一个存在的数字的出现次数。

输入格式

第一行有三个数 $n,m,k$，$k$ 表示操作次数。

然后 $k$ 行，每一行三个数 $T_i,A_i,X_i$。

• $T_i$ 为 $1$ 时，表示强哥是把第 $A_i$ 行里面的每个格子都写下数数字 $X_i$。
• $T_i$ 为 $2$ 时，表示强哥是把第 $A_i$ 列里面的每个格子都写下数数字 $X_i$。

输出格式

每一行有两个数，第一个数是一个出现在纸上的数字，第二个数是这个数字在纸上的出现次数。

若出现的数字有多个，按照数字的大小从小到大地输出。

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

3
0 5
2 4
5 3

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\ n,m,k\ \leq\ 2\ \times\ 10^5$
• $T_i\ \in\ \lbrace\ 1,\ 2\ \rbrace$
• $T_i\ =\ 1$ 时 $1\ \leq\ A_i\ \leq\ n$
• $T_i\ =\ 2$ 时 $1\ \leq\ A_i\ \leq\ m$
• $0\ \leq\ X_i\ \leq\ 2\ \times\ 10^5$