CF200A.Cinema

The capital of Berland has the only movie theater in the country. Besides, it consists of only one room. The room is divided into n rows, each row consists of m seats.

There are k people lined up to the box office, each person wants to buy exactly one ticket for his own entertainment. Before the box office started selling tickets, each person found the seat that seemed best for him and remembered it as a pair of coordinates (x__i, y__i), where x__i is the row number, and y__i is the seat number in this row.

It is possible that some people have chosen the same place, then when some people see their favorite seat taken in the plan of empty seats in the theater, they choose and buy a ticket to another place. Each of them has the following logic: let's assume that he originally wanted to buy a ticket to seat (_x_1, _y_1), then when he comes to the box office, he chooses such empty seat (_x_2, _y_2), which satisfies the following conditions:

• the value of |_x_1 - _x_2| + |_y_1 - _y_2| is minimum
• if the choice is not unique, then among the seats that satisfy the first condition, this person selects the one for which the value of _x_2 is minimum
• if the choice is still not unique, among the seats that satisfy the first and second conditions, this person selects the one for which the value of _y_2 is minimum

Your task is to find the coordinates of a seat for each person.

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$ 值最小者。

你的任务是为每个人确定其最终购得的座位坐标。

The first input line contains three integers n, m, k (1 ≤ n, m ≤ 2000, 1 ≤ k ≤ min(n·m, 105) — the number of rows in the room, the number of seats in each row and the number of people in the line, correspondingly. Each of the next k lines contains two integers x__i, y__i (1 ≤ x__i ≤ n, 1 ≤ y__i ≤ m) — the coordinates of the seat each person has chosen. Numbers on the same line are separated by a space. The pairs of coordinates are located in the order, in which people stand in the line, starting from the head (the first person in the line who stands in front of the box office) to the tail (the last person in the line).

第一行输入包含三个整数 $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$），表示第 $i$ 个人所选择的座位坐标。同一行中的数字以空格分隔。这些坐标对按人员在队列中的顺序给出，从队首（站在售票窗口前的第一人）到队尾（队列中的最后一人）。

Print k lines, each containing a pair of integers. Print on the i-th line x__i, y__i — the coordinates of the seat, for which the person who stands i-th in the line will buy the ticket.

输出 k 行，每行包含一对整数。在第 i 行输出 x__i, y__i —— 表示队列中第 i 位的人将购买的座位坐标。