{"raw_statement":[{"iden":"statement","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 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.\n\nVasya 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."},{"iden":"input","content":"The first line contains two integers $n$ and $m$ ($1 \\leq m \\leq n \\leq 50$).\n\nEach 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.\n\nThe next $m$ lines describe the designated places for the cubes in the same format and order.\n\nIt 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."},{"iden":"output","content":"In the first line print a single integer $k$ ($0 \\le k \\leq 10800$) — the number of operations Vasya should make.\n\nIn 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.\n\nWe can show that there always exists at least one solution. If there are multiple solutions, print any of them."},{"iden":"examples","content":"Input\n\n2 1\n1 1\n2 2\n\nOutput\n\n2\n1 1 1 2\n1 2 2 2\n\nInput\n\n2 2\n1 1\n2 2\n1 2\n2 1\n\nOutput\n\n2\n2 2 2 1\n1 1 1 2\n\nInput\n\n2 2\n2 1\n2 2\n2 2\n2 1\n\nOutput\n\n4\n2 1 1 1\n2 2 2 1\n1 1 1 2\n1 2 2 2\n\nInput\n\n4 3\n2 2\n2 3\n3 3\n3 2\n2 2\n2 3\n\nOutput\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":"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.\n\n<center>![image](https://espresso.codeforces.com/65c819604d89b503e01b7193dac4402bed917d36.png)</center>"}],"translated_statement":[{"iden":"statement","content":"Vasya 通过了所有考试！尽管有预期，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$ 次操作的解。"}],"sample_group":[],"show_order":[],"formal_statement":"**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{init}}) \\mid i \\in \\{1, \\dots, m\\} \\} \\subseteq \\{1, \\dots, n\\}^2 $ be the set of initial positions of the cubes.  \nLet $ 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.  \nAssume $ I $ and $ F $ consist of distinct points (no duplicates within each set).  \n\nLet $ B = \\{1, \\dots, n\\} \\times \\{1, \\dots, n\\} $ be the set of all cells on the $ n \\times n $ chessboard.  \nLet $ E_t \\subseteq B $ denote the set of empty cells at time $ t $; initially, $ E_0 = B \\setminus I $.  \n\n**Constraints**  \n1. $ |I| = |F| = m $, and $ I \\cap F $ may be non-empty.  \n2. Each operation moves one cube from a cell $ (x_1, y_1) $ to an adjacent (sharing a side) empty cell $ (x_2, y_2) $.  \n3. Each operation takes exactly 1 second.  \n4. Total number of operations $ k \\le 10800 $.  \n5. Final configuration must satisfy: for each cube $ c_i $, it occupies position $ (x_i^{\\text{final}}, y_i^{\\text{final}}) $.  \n\n**Objective**  \nFind a sequence of $ k $ operations $ \\{(x_1^{(t)}, y_1^{(t)}, x_2^{(t)}, y_2^{(t)}) \\}_{t=1}^k $ such that:  \n- For each $ t \\in \\{1, \\dots, k\\} $:  \n  - $ (x_1^{(t)}, y_1^{(t)}) $ contains a cube at time $ t-1 $,  \n  - $ (x_2^{(t)}, y_2^{(t)}) \\in E_{t-1} $,  \n  - $ |x_1^{(t)} - x_2^{(t)}| + |y_1^{(t)} - y_2^{(t)}| = 1 $ (Manhattan-adjacent),  \n- After $ k $ operations, the cube originally at $ (x_i^{\\text{init}}, y_i^{\\text{init}}) $ is at $ (x_i^{\\text{final}}, y_i^{\\text{final}}) $ for all $ i \\in \\{1, \\dots, m\\} $.  \n- $ 0 \\le k \\le 10800 $.  \n\nOutput $ k $ and the sequence of operations.","simple_statement":null,"has_page_source":false}