AT_2_ttpc2024_2_m.Colorful Stone Sorting

在数轴上有 $M$ 种颜色的石子，每种颜色有 $N$ 个，总共 $NM$ 个石子。其中，$N$ 是偶数，而 $M$ 是奇数。第 $i$ 种颜色的石子中，编号第 $j$ 的石子（$1 \le i \le M, 1 \le j \le N$）放置在坐标 $(j-1) \times M + i$ 上。同一种颜色的石子互相没有区别。

你可以进行以下操作，最多 $(N+1) \times M$ 次：

1. 找到一个整数 $x$，满足 $-10^9 \le x \le 10^9-1$，并且在坐标 $x$ 和 $x+1$ 上都有石子。将坐标 $x$ 处的石子标记为 $A$，坐标 $x+1$ 处的石子标记为 $B$，然后把 $A$ 和 $B$ 从数轴上移除。
2. 找到一个整数 $y$，满足 $-10^9 \le y \le 10^9-1$，并且在坐标 $y$ 和 $y+1$ 上没有石子。将 $A$ 放在坐标 $y$ 处，$B$ 放在坐标 $y+1$ 处。

你的目标是重新排列这些石子，使它们满足以下条件：

• 所有石子组成一个连续的块。也就是说，存在一个整数 $n$，坐标从 $n$ 到 $n+NM-1$ 的每一个位置都有且只有一个石子。
• 石子按颜色从小到大排序。即第 $i$ 种颜色的石子中，编号第 $j$ 的石子（$1 \le i \le M, 1 \le j \le N$）应位于坐标 $n + (i-1) \times N + (j-1)$。

题目的约束条件确保总能实现这个目标。请输出一种具体的操作方法来达成目标，操作次数不必最少。

输入由一行组成：

$N$ $M$

输出应包括以下内容：

$K$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_K$ $y_K$

这里，$K$ 是总操作次数，$x_k$ 和 $y_k$ 表示第 $k$ 次操作中选定的 $x$ 和 $y$。输出必须满足如下限制条件：

• $0 \le K \le (N+1) \times M$
• $-10^9 \le x_k, y_k \le 10^9-1,\ \forall 1 \le k \le K$

如果有多种操作顺序满足要求，输出其中任意一个均可。

数据范围与限制

• $2 \le N \le 1000$，$N$ 为偶数
• $3 \le M \le 999$，$M$ 为奇数

样例解释

初始状态下，石子的排列如下（用 . 表示空位），最左边 . 的坐标是 $0$，最右边 . 的坐标是 $15$：

.123123123123...

前 $3$ 次操作的变化如下所示：

.123123123123...
↓
.12..2312312331.
↓
.121223123..331.
↓
.12122312333..1.

最终，石子的排列变为：

...111122223333.

在这一配置中，所有石子串成一个连续的块，并按颜色排序。操作次数也不超过 $15$ 次，所以该输出是正确的。

本翻译由 AI 自动生成