← 返回题目列表

AtCoder · abc213_c

E. 重新排序卡

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有 HW 卡片排列成矩阵 H 行和 W 列。
对于每个 i=1, \ldots, N,卡位于 A_i从顶部开始的第行和 B_i左起第 列有一个数字 上面写着 i 。另一个 HW-N 卡片上没有写任何内容。

我们将尽可能地对这些卡重复以下两种操作。

  • 如果有一排没有编号的卡片,请取出该排中的所有卡片,并通过向上移动剩余的卡片来填补空白。
  • 如果有一列没有编号的卡片,则移除该列中的所有卡片,并将剩余的卡片向左移动来填补空白。

上述过程结束后,找到每张编号卡的位置。可以证明,这些位置是唯一确定的,与操作执行的顺序无关。

约束

  • 1 \leq H,W \leq 10^9
  • 1 \leq N \leq \min(10^5,HW)
  • 1 \leq A_i \leq H
  • 1 \leq B_i \leq W
  • 所有对 (A_i,B_i) 是不同的。
  • 输入中的所有值都是整数。

输入

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

H W N
A_1 B_1
\vdots
A_N B_N

输出

打印 N 行。

如果在该过程结束后,带有该号码的卡 i 位于 C_i从顶部开始的第行和 D_i左起第 列, i- 第行应包含 C_i 和 D_i 按此顺序,中间有一个空格。


示例输入 1

4 5 2
3 2
2 5

示例输出 1

2 1
1 2

让 * 代表一张上面没有写任何东西的卡片。卡片的初始排列是:

*****
****2
*1***
*****

流程结束后,将进行如下安排:

*2
1*

这里,该卡带有 1 位于 2- 从顶部开始的第 1 行和 1- 从左边算起第 1 列,以及带有 2 位于 1- 从顶部开始的第 1 行 2- 左起第 2 列。


示例输入 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

示例输出 2

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