CF200A Cinema

Berland 首都有该国唯一的一家电影院。此外，它只有一个放映厅。这个厅被分为 $n$ 行，每行有 $m$ 个座位。 有 $k$ 个人排队买票，每个人都想为自己买一张票。在售票开始前，每个人都找到了他认为最合适的座位，并记住了这个座位的坐标对 $(x_{i},y_{i})$，其中 $x_{i}$ 是行号，$y_{i}$ 是该行的座位号。 可能有些人选择了同一个位置，那么当某人发现他心仪的座位已经被别人买走时，他会在影厅中剩余的座位里选择另一个。他们的选择依据如下逻辑：假设他最初想要购买 $(x_{1},y_{1})$ 这个座位，那么当他来到售票处时，会选择一个空座 $(x_{2},y_{2})$，使得以下条件依次满足： - $|x_{1}-x_{2}|+|y_{1}-y_{2}|$ 的值最小； - 如果有多个座位满足第一个条件，那么在这些座位中选择 $x_{2}$ 最小的； - 如果还是不唯一，那么在这些座位中选择 $y_{2}$ 最小的。 你的任务是，对于队列中的每个人，找出他最终买到的座位坐标。

输入的第一行包含三个整数 $n,m,k$（$1 \leq n, m \leq 2000$，$1 \leq k \leq \min(n \cdot m, 10^5)$），表示影厅的行数、每行的座位数和排队的人数。接下来的 $k$ 行，每行包含两个整数 $x_{i},y_{i}$（$1 \leq x_{i} \leq n$，$1 \leq y_{i} \leq m$），表示每个人最想选择的座位坐标。每行的数字用空格隔开。坐标对的排列顺序即为人们排队的顺序，从队头（第一位）到队尾（第 $k$ 位）。

输出 $k$ 行，每行两个整数。在第 $i$ 行输出 $x_{i},y_{i}$，表示排在队列第 $i$ 的人最终买到的座位坐标。

由 ChatGPT 5 翻译