/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score: 100 points
Problem Statement
There are N \times M stones on a number line, with M colors labeled 1 through M, and N stones of each color. Here, N is an even number, and M is an odd number. Among the stones of color i, the j-th stone from the left (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) is initially placed at the coordinate (j-1) \times M + i. Stones of the same color are indistinguishable.
You can perform the following operation up to (N+1) \times M times:
Pick two adjacent stones and move them, in the same order, to any unoccupied adjacent positions.
Specifically:
- Choose an integer x such that -10^9 \leq x \leq 10^9-1 and there are stones at both coordinates x and x+1. Let the stone at x be A and the stone at x+1 be B. Remove A and B from the number line.
- Choose an integer y such that -10^9 \leq y \leq 10^9-1 and there are no stones at both coordinates y and y+1. Place A at y and B at y+1.
Your goal is to rearrange the stones to satisfy the following two conditions:
- All stones are part of a single contiguous block. That is, there exists an integer n such that for all integers x satisfying n \leq x \leq n + NM - 1, there is exactly one stone at coordinate x.
- Additionally, the stones are sorted by color in ascending order. Specifically, among the stones of color i, the j-th stone from the left (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) is at coordinate n + (i-1) \times N + (j-1).
Under the constraints of this problem, it can be shown that the goal is always achievable. Output one valid sequence of operations to achieve the goal. You do not need to minimize the number of operations.
Constraints
- 2 \leq N \leq 1000
- 3 \leq M \leq 999
- N is even
- M is odd
Input
The input is given in the following format:
N M
Output
Output the solution in the following format:
K x_1 y_1 x_2 y_2 \vdots x_K y_K
Here, K is the number of operations performed, and x_k, y_k\ (1 \leq k \leq K) represent the values of x and y chosen in the k-th operation.
The output must satisfy the following constraints:
- 0 \leq K \leq (N+1) \times M
- -10^9 \leq x_k, y_k \leq 10^9-1\ (1 \leq k \leq K)
If there are multiple valid solutions, output any one of them.
Sample Input 1
4 3
Sample Output 1
13 3 13 10 3 12 10 6 12 4 6 1 4 13 14 14 14 14 999999999 999999999 -1000000000 9 13 5 9 -1000000000 5
Initially, the stones are placed as follows (. indicates an unoccupied position). The coordinate of the leftmost . is 0, and the coordinate of the rightmost . is 15.
.123123123123...
After the first three operations, the stone arrangement changes as follows:
.123123123123... ↓ .12..2312312331. ↓ .121223123..331. ↓ .12122312333..1.
Finally, the stones are rearranged as follows:
...111122223333.
This arrangement satisfies the conditions of being a single contiguous block and sorted by color. Additionally, the number of operations is at most (N + 1) \times M = 15, so this output is valid.
配点 : 100 点
問題文
数直線上に色 1 から色 M までの M 色の石がそれぞれ N 個ずつ、合計 NM 個の石があります。ここで、N は 偶数 、M は 奇数 です。色 i の石のうち左から j 番目のもの (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) は座標 (j-1) \times M + i に置かれています。同じ色の石同士には区別はありません。
あなたは以下の操作を (N+1)\times M 回まで行うことができます。
2 個並んでいる石を掴み取り、順番を変えずに空いている好きな場所に移す。
より正確には、以下の操作を行う。
- -10^9 ≤ x ≤ 10^9-1 を満たす整数 x であって、座標 x,x+1 の両方に石が置かれているようなものを選ぶ。座標 x に置かれている石を A 、座標 x+1 に置かれている石を B とする。A,B をいったん数直線上から取り除く。
- 次に、-10^9 ≤ y ≤ 10^9-1 を満たす整数 y であって、座標 y,y+1 の両方に石が置かれていないようなものを選ぶ。座標 y に A を、座標 y+1 に B をそれぞれ置く。
あなたの目標は、次の 2 つの条件を満たすように石を配置することです。
- 全ての石は連続した 1 つの塊になっている。すなわち、ある整数 n が存在して、n \le x \le n+NM-1 を満たすすべての整数 x に対して、座標 x に石がちょうど 1 個置かれている。
- さらに、石は色の昇順にソートされている。すなわち、色 i の石のうち左から j 番目のもの (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) は座標 n + (i-1) \times N + (j-1) にある。
この問題の制約下で、目標は必ず達成可能であることが示せます。目標を達成する具体的な操作方法を 1 つ出力してください。操作回数を最小化する必要はないことに注意してください。
制約
- 2 \le N \le 1000
- 3 \le M \le 999
- N は偶数
- M は奇数
入力
入力は以下の形式で与えられる。
N M
出力
答えを以下の形式で出力せよ。
K x_1 y_1 x_2 y_2 \vdots x_K y_K
ここで、K は行う操作の回数であり、x_k, y_k\ (1 ≤ k ≤ K) は k 回目の操作において選ばれた x,y を表す。
出力は以下の制約を満たさなければならない。
- 0 \le K \le (N+1) \times M
- -10^9 \le x_k,y_k \le 10^9-1\ (1 ≤ k ≤ K)
条件を満たす解が複数存在する場合は、どれを出力しても正解とみなされる。
入力例 1
4 3
出力例 1
13 3 13 10 3 12 10 6 12 4 6 1 4 13 14 14 14 14 999999999 999999999 -1000000000 9 13 5 9 -1000000000 5
最初の状態では、以下のように石が置かれています。(. は石が置かれていないことを表します)。左端の . の座標は 0 、右端の . の座標は 15 です。
.123123123123...
最初の 3 回の操作により、石の配置は以下のように変化します。
.123123123123... ↓ .12..2312312331. ↓ .121223123..331. ↓ .12122312333..1.
最終的に、石の配置は以下のようになります。
...111122223333.
この配置は石が 1 つの塊になっていて、色の昇順にソートされています。操作回数も (N + 1) \times M = 15 回以下であるので、この出力は正解となります。