← 返回题目列表

Codeforces · 200/A

A. 电影院

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

贝尔兰首都拥有全国唯一的电影院。此外,它仅由一间房间组成。房间分为n排,每排有m个座位。

有k个人在售票处排队,每个人都想买一张适合自己娱乐的票。在售票处开始售票之前,每个人都找到了最适合自己的座位,并将其记住为一对坐标(xi,yi),其中xi是排号,yi是这一排的座位号。

有可能有些人选择了同一个地方,那么当有些人看到自己喜欢的座位在剧院的空座计划中被占据时,他们就选择并购买了去另一个地方的票。他们每个人都有这样的逻辑:假设他本来想买一张座位(x1,y1)的票,那么当他来到售票处时,他选择了这样一个空座位(x2,y2),满足以下条件:

- |x1 - x2| 的值 + |y1 - y2|是最小值
- 如果选择不唯一,则在满足第一个条件的座位中,此人选择 x2 值最小的座位
- 如果选择仍然不唯一,则在满足第一和第二条件的座位中,此人选择y2值最小的座位

你的任务是找到每个人的座位坐标。

输入

第一输入行包含三个整数 n, m, k (1 ≤ n, m ≤ 2000, 1 ≤ k ≤ min(n·m, 105) — 分别对应房间的行数、每行的座位数和队列中的人数。接下来的 k 行每行包含两个整数 xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) — 同一行上每个人选择的座位的坐标,以空格分隔,坐标对按人们排队的顺序排列,从头(站在售票处前面的第一个人)到尾(最后一个人)。

输出

打印 k 行,每行包含一对整数。在第 i 行打印 xi,yi — 座位坐标,第 i 行的人将购买该座位的票。

示例

输入 #1

3 4 6
1 1
1 1
1 1
1 2
1 3
1 3

输出 #1

1 1
1 2
2 1
1 3
1 4
2 3

输入 #2

4 3 12
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2

输出 #2

2 2
1 2
2 1
2 3
3 2
1 1
1 3
3 1
3 3
4 2
4 1
4 3