Colored Cubes
Contest: Codeforces Round 505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 2700
Tags: constructive algorithms, implementation, matrices

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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
2 1
1 1
2 2

Example output:
2
1 1 1 2
1 2 2 2

Example input:
2 2
1 1
2 2
1 2
2 1

Example output:
2
2 2 2 1
1 1 1 2

Editorial:
We're gonna show how to turn an arbitrary arrangement of cubes into the arrangement where $$$i$$$-th cube is located at $$$(i, i)$$$ (we call such an arrangement basic) in no more than $$$2*n^{2}$$$ operations. For simplicity, we imply that we have exactly $$$n$$$ cubes where $$$n$$$ is even.
Say we have some arrangement where $$$i$$$-th cube occupies some cell $$$(x_i, y_i)$$$. On the first step, we turn it into the arrangement where all cubes have distinct $$$x$$$ coordinates. In order to do this, we sort cubes in ascending order of their $$$x$$$ coordinates $$$x$$$ (with ties broken arbitrarily) . If cube $$$i$$$ is at position $$$j$$$ in the sorted list, we say that its desired coordinates are $$$(j, y_i)$$$. It's easy to check that such choice always allows to move at least one cube from its current position to the desired one through the $$$y = y_i$$$ line. If we perform this operation $$$n$$$ times, we'll move all cubes to their desired positions. In addition, the maximum number of operations will occur if all the cubes were initially located on the line $$$x = 1$$$ or $$$x = n$$$, and in this case the number of operations will be equal to $$$0 + 1 + ... + (n-1)$$$ < $$$n^{2}/2$$$.
The formal proof of this inequality can be given using the induction principle. Indeed, the base ($$$n = 1$$$) is obvious. Now let the statement be true for all $$$k \leq n$$$. Let's prove that if the number of cubes (and the size of the board) changes from $$$n$$$ to $$$(n+1)$$$, the upper limit of the number of operations increases by no more than $$$n$$$. Consider the cube $$$i$$$ with maximum $$$x$$$ coordinate which we have to move to $$$x_i = n$$$. If initially $$$x_i$$$ is less than $$$n$$$, we move this cube to the desired position in no more than $$$n$$$ operations, and other $$$n$$$ cubes have coordinates $$$x_j \leq n$$$ which implies the upper limit of $$$n*(n-1)/2$$$ operations by definition. But if $$$x_i$$$ is initially $$$n$$$, we don't have to move it whereas each of the remaining $$$n$$$ cubes requires one more additional (i.e $$$n$$$ total) operation since we added only one diagonal. In total we'll make a total of $$$n + n*(n-1)/2 = n*(n+1)/2$$$ operations.
Now all $$$x$$$ coordinates are distinct and that means that nothing restricts us from changing their $$$y$$$ coordinates. Let's move the cubes in such a way that $$$i$$$-th cube ends at position $$$y_i = i$$$. One cube can be processed in no more than $$$min(i-1, n-i)$$$ operations. According to this, we need at most $$$(n-1) + (n-2) + ... + n/2 + n/2 + ... + (n-1) = 2*((n/2)*(n/2 + n - 1)/2) = 3*n*(n-2)/4 \leq 3*n^{2}/4$$$ operations in total. Now we obtain an arrangement where all $$$y$$$ coordinates are also distinct. If we apply the same operation to cubes' $$$x$$$ coordinates, we will end up with $$$i$$$-th cube at position $$$(i, i)$$$. This requires no more than $$$n^{2}/2 + 2*(3*n^{2}/4) = 2*n^{2}$$$ operations.
Now we can switch any arrangement to the basic one. Let's get the list of operations for turning the initial position to basic and the final position to basic. Now it's sufficient to reverse one of the lists and concatenate these actions. This yields no more than $$$4*n^{2} \leq 10000$$$ operations in total.
Note that this estimate is quite rough; however, this is enough under given constraints.