贝尔兰首都拥有全国唯一的电影院。此外,它仅由一间房间组成。房间分为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