#ABC213C. 卡牌重编号

卡牌重编号

AT_abc213_c [ABC213C] Reorder Cards

题目描述

\hspace{15pt}有一个 hh 行 ww 列的网格,每个格子中放着一张卡片,因此共有 h×wh \times w 张卡片。其中只有 nn 张卡片写了数字:对于 i=1,2,…,ni = 1, 2, \dots, n,从上往下数第 aia_i 行、从左往右数第 bib_i 列的卡片上写有数字 ii,其余 h×w−nh \times w - n 张卡片上什么都没有写。

\hspace{15pt}接下来重复执行下面两种操作,直到两种操作都无法执行:

∙ \hspace{23pt}\bullet\,若存在一整行都没有写数字的卡片,则删去这一行,并把下方的卡片整体向上平移,使网格不留空隙;

∙ \hspace{23pt}\bullet\,若存在一整列都没有写数字的卡片,则删去这一列,并把右侧的卡片整体向左平移,使网格不留空隙。

\hspace{15pt}每一步可以任选一种当前可执行的操作进行,执行次数不限。可以证明,无论以什么顺序执行这些操作,最终每张写了数字的卡片所在的位置都是唯一确定的。

\hspace{15pt}请求出操作结束后,每张写了数字的卡片所在的行号和列号。

输入格式

\hspace{15pt}第一行输入三个整数 $h, w, n \left(1 \leqq h, w \leqq 10^9;\ 1 \leqq n \leqq \min\left(10^5, h \times w\right)\right)$ 分别代表网格的行数、列数和写了数字的卡片数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq h;\ 1 \leqq b_i \leqq w\right)$ 代表写有数字 ii 的卡片位于从上往下数第 aia_i 行、从左往右数第 bib_i 列。

\hspace{15pt}保证所有 (ai,bi)(a_i, b_i) 两两不同。

输出格式

\hspace{15pt}输出 nn 行。第 ii 行输出两个整数 ci,dic_i, d_i,相邻两个整数之间用一个空格隔开,代表操作结束后写有数字 ii 的卡片位于从上往下数第 cic_i 行、从左往右数第 did_i 列。

测试样例

4 5 2
3 2
2 5
2 1
1 2

样例 1 解释

\hspace{15pt}初始时写有数字 11 的卡片位于第 33 行第 22 列,写有数字 22 的卡片位于第 22 行第 55 列。

∙ \hspace{23pt}\bullet\,含卡片的行只有第 22 行和第 33 行,删去其余空行后,原第 22 行成为新第 11 行,原第 33 行成为新第 22 行;

∙ \hspace{23pt}\bullet\,含卡片的列只有第 22 列和第 55 列,删去其余空列后,原第 22 列成为新第 11 列,原第 55 列成为新第 22 列。

\hspace{15pt}因此写有数字 11 的卡片最终位于第 22 行第 11 列,写有数字 22 的卡片最终位于第 11 行第 22 列,与输出一致。

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10