English · Original
Chinese · Translation
Formal · Original
Vasya passes all exams! Despite expectations, Vasya is not tired, moreover, he is ready for new challenges. However, he does not want to work too hard on difficult problems.
Vasya remembered that he has a not-so-hard puzzle: $m$ colored cubes are placed on a chessboard of size $n \times n$. The fact is that $m \leq n$ and all cubes have distinct colors. Each cube occupies exactly one cell. Also, there is a designated cell for each cube on the board, the puzzle is to place each cube on its place. The cubes are fragile, so in one operation you only can move one cube onto one of four neighboring by side cells, if only it is empty. Vasya wants to be careful, so each operation takes exactly one second.
Vasya used to train hard for VK Cup Final, so he can focus his attention on the puzzle for at most $3$ hours, that is $10800$ seconds. Help Vasya find such a sequence of operations that all cubes will be moved onto their designated places, and Vasya won't lose his attention.
## Input
The first line contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 50$).
Each of the next $m$ lines contains two integers $x_i$, $y_i$ ($1 \leq x_i, y_i \leq n$), the initial positions of the cubes.
The next $m$ lines describe the designated places for the cubes in the same format and order.
It is guaranteed that all initial positions are distinct and all designated places are distinct, however, it is possible that some initial positions coincide with some final positions.
## Output
In the first line print a single integer $k$ ($0 \le k \leq 10800$) — the number of operations Vasya should make.
In each of the next $k$ lines you should describe one operation: print four integers $x_1$, $y_1$, $x_2$, $y_2$, where $x_1, y_1$ is the position of the cube Vasya should move, and $x_2, y_2$ is the new position of the cube. The cells $x_1, y_1$ and $x_2, y_2$ should have a common side, the cell $x_2, y_2$ should be empty before the operation.
We can show that there always exists at least one solution. If there are multiple solutions, print any of them.
[samples]
## Note
In the fourth example the printed sequence of movements (shown on the picture below) is valid, but not shortest. There is a solution in $3$ operations.
<center></center>
[{"iden":"statement","content":"Vasya 通过了所有考试！尽管预期他会疲惫，但他却精力充沛，准备好迎接新的挑战。然而，他并不想在难题上花费太多精力。\n\nVasya 想起他有一个不算太难的谜题：在一张 $n \\times n$ 的棋盘上放置了 $m$ 个彩色立方体。已知 $m lt.eq n$，且所有立方体颜色互不相同。每个立方体占据恰好一个格子。此外，棋盘上为每个立方体都指定了一处目标位置，谜题的目标是将每个立方体移动到其对应的目标位置。立方体很脆弱，因此每次操作只能将一个立方体移动到与其相邻（共享一条边）的空格子上。Vasya 想要谨慎行事，因此每次操作恰好耗时一秒。\n\nVasya 曾为 VK Cup 决赛刻苦训练，因此他最多能集中注意力 $3$ 小时，即 $10800$ 秒。请帮助 Vasya 找到一个操作序列，使得所有立方体都能移动到其目标位置，且 Vasya 不会失去注意力。\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq m lt.eq n lt.eq 50$）。\n\n接下来的 $m$ 行，每行包含两个整数 $x_i$, $y_i$（$1 lt.eq x_i, y_i lt.eq n$），表示立方体的初始位置。\n\n接下来的 $m$ 行以相同的格式和顺序描述每个立方体的目标位置。\n\n保证所有初始位置互不相同，所有目标位置也互不相同，但某些初始位置可能与某些目标位置重合。\n\n第一行输出一个整数 $k$（$0 lt.eq k lt.eq 10800$）——表示 Vasya 应执行的操作次数。\n\n接下来的 $k$ 行，每行描述一次操作：输出四个整数 $x_1$, $y_1$, $x_2$, $y_2$，其中 $x_1, y_1$ 是要移动的立方体的当前位置，$x_2, y_2$ 是其新位置。格子 $x_1, y_1$ 和 $x_2, y_2$ 必须相邻（共享一条边），且 $x_2, y_2$ 在操作前必须为空。\n\n可以证明，至少存在一种可行解。如果有多个解，输出任意一个即可。\n\n在第四个示例中，所打印的操作序列（如下图所示）是合法的，但不是最短的。存在一个只需 $3$ 次操作的解。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$（$1 lt.eq m lt.eq n lt.eq 50$）。接下来的 $m$ 行，每行包含两个整数 $x_i$, $y_i$（$1 lt.eq x_i, y_i lt.eq n$），表示立方体的初始位置。接下来的 $m$ 行以相同的格式和顺序描述每个立方体的目标位置。保证所有初始位置互不相同，所有目标位置也互不相同，但某些初始位置可能与某些目标位置重合。"},{"iden":"output","content":"第一行输出一个整数 $k$（$0 lt.eq k lt.eq 10800$）——表示 Vasya 应执行的操作次数。接下来的 $k$ 行，每行描述一次操作：输出四个整数 $x_1$, $y_1$, $x_2$, $y_2$，其中 $x_1, y_1$ 是要移动的立方体的当前位置，$x_2, y_2$ 是其新位置。格子 $x_1, y_1$ 和 $x_2, y_2$ 必须相邻（共享一条边），且 $x_2, y_2$ 在操作前必须为空。可以证明，至少存在一种可行解。如果有多个解，输出任意一个即可。"},{"iden":"examples","content":"输入\n2 1\n1 1\n2 2\n输出\n2\n1 1 1 2\n1 2 2 2\n\n输入\n2 2\n1 1\n2 2\n1 2\n2 1\n输出\n2\n2 2 2 1\n1 1 1 2\n\n输入\n2 2\n2 1\n2 2\n2 2\n2 1\n输出\n4\n2 1 1 1\n2 2 2 1\n1 1 1 2\n1 2 2 2\n\n输入\n4 3\n2 2\n2 3\n3 3\n3 2\n2 2\n2 3\n输出\n9\n2 2 1 2\n1 2 1 1\n2 3 2 2\n3 3 2 3\n2 2 1 2\n1 1 2 1\n2 1 3 1\n3 1 3 2\n1 2 2 2"},{"iden":"note","content":"在第四个示例中，所打印的操作序列（如下图所示）是合法的，但不是最短的。存在一个只需 $3$ 次操作的解。 "}]}
**Definitions**
Let $ n, m \in \mathbb{Z} $ with $ 1 \le m \le n \le 50 $.
Let $ C = \{c_1, \dots, c_m\} $ be a set of $ m $ distinct colored cubes.
Let $ I = \{(x_i^{\text{init}}, y_i^{\text{init}}) \mid i \in \{1, \dots, m\}\} \subseteq \{1, \dots, n\}^2 $ be the set of initial positions of the cubes.
Let $ F = \{(x_i^{\text{final}}, y_i^{\text{final}}) \mid i \in \{1, \dots, m\}\} \subseteq \{1, \dots, n\}^2 $ be the set of designated (final) positions for the cubes.
Assume $ I $ and $ F $ contain distinct points each, and $ I \cap F $ may be non-empty.
Let $ B = \{1, \dots, n\} \times \{1, \dots, n\} $ be the set of all cells on the $ n \times n $ chessboard.
At any time, let $ P \subseteq B $ be the set of occupied cells (initially $ P = I $).
**Constraints**
1. Each operation moves one cube from a cell $ (x_1, y_1) \in P $ to an adjacent empty cell $ (x_2, y_2) \in B \setminus P $, where $ |x_1 - x_2| + |y_1 - y_2| = 1 $.
2. Each operation takes 1 second; total operations $ k \le 10800 $.
3. After all operations, the set of occupied cells must equal $ F $.
4. For each cube $ c_i $, its final position must be $ (x_i^{\text{final}}, y_i^{\text{final}}) $ — i.e., the mapping from initial to final positions is fixed by input order.
**Objective**
Find a sequence of $ k $ operations $ \{(x_1^{(j)}, y_1^{(j)}, x_2^{(j)}, y_2^{(j)}) \}_{j=1}^k $ such that:
- Each operation satisfies adjacency and emptiness constraints.
- After the $ k $-th operation, every cube $ c_i $ is at $ (x_i^{\text{final}}, y_i^{\text{final}}) $.
- $ 0 \le k \le 10800 $.
API Response (JSON)
{
"problem": {
"name": "B. Colored Cubes",
"description": {
"content": "Vasya passes all exams! Despite expectations, Vasya is not tired, moreover, he is ready for new challenges. However, he does not want to work too hard on difficult problems. Vasya remembered that he ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF951B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vasya passes all exams! Despite expectations, Vasya is not tired, moreover, he is ready for new challenges. However, he does not want to work too hard on difficult problems.\n\nVasya remembered that he ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Vasya 通过了所有考试！尽管预期他会疲惫，但他却精力充沛，准备好迎接新的挑战。然而，他并不想在难题上花费太多精力。\\n\\nVasya 想起他有一个不算太难的谜题：在一张 $n \\\\times n$ 的棋盘上放置了 $m$ 个彩色立方体。已知 $m lt.eq n$，且所有立方体颜色互不相同。每个立方体占据恰好一个格子。此外，棋盘上...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\le m \\le n \\le 50 $. \nLet $ C = \\{c_1, \\dots, c_m\\} $ be a set of $ m $ distinct colored cubes. \nLet $ I = \\{(x_i^{\\text{init}}, y_i^{\\text{in...",
"is_translate": false,
"language": "Formal"
}
]
}