AT_ttpc2024_2_m Colorful Stone Sorting

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 1. 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. > 2. 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

The input is given in the following format: > $ N $ $ M $

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 Explanation 1 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. ### Constraints - $ 2 \leq N \leq 1000 $ - $ 3 \leq M \leq 999 $ - $ N $ is even - $ M $ is odd