Connected Cubes
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 3100
Tags: constructive algorithms, games

There are $$$n \cdot m$$$ unit cubes currently in positions $$$(1, 1, 1)$$$ through $$$(n, m, 1)$$$. Each of these cubes is one of $$$k$$$ colors. You want to add additional cubes at any integer coordinates such that the subset of cubes of each color is connected, where two cubes are considered connected if they share a face.

In other words, for every pair of cubes of the same color $$$c$$$, it should be possible to travel from one to the other, moving only through cubes of color $$$c$$$ that share a face.

The existing cubes are currently in the corner of a room. There are colorless cubes completely filling the planes $$$x = 0$$$, $$$y = 0$$$, and $$$z = 0$$$, preventing you from placing additional cubes there or at any negative coordinates.

Find a solution that uses at most $$$4 \cdot 10^5$$$ additional cubes (not including the cubes that are currently present), or determine that there is no solution. It can be shown that under the given constraints, if there is a solution, there is one using at most $$$4 \cdot 10^5$$$ additional cubes.

Input format:
The first line of the input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n, m, k \le 50$$$) — the number of rows and columns of cubes, and the number of colors, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th of these is $$$a_{ij}$$$ ($$$1 \le a_{ij} \le k$$$) — the color of the cube at position $$$(i, j, 1)$$$. For every color from $$$1$$$ to $$$k$$$, it is guaranteed that there is at least one cube in the input of that color.

Output format:
If there is no solution, print a single integer $$$-1$$$.

Otherwise, the first line of output should contain a single integer $$$p$$$ ($$$0 \le p \le 4 \cdot 10^5$$$) — the number of additional cubes you will add.

The next $$$p$$$ lines should contain four integers $$$x$$$, $$$y$$$, $$$z$$$ and $$$c$$$ ($$$1 \le x, y, z \le 10^6$$$, $$$1 \le c \le k$$$) — indicating that you are adding a cube with color $$$c$$$ at position $$$(x, y, z)$$$.

No two cubes in the output should have the same coordinates, and no cube in the output should have the same coordinates as any cube in the input.

If there are multiple solutions, print any.

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

Note:
The image in the statement corresponds to the first example case, with $$$\text{red} = 1$$$, $$$\text{blue} = 2$$$, $$$\text{green} = 3$$$.

Example input:
3 4 3
3 2 3 1
1 1 1 1
1 3 3 2

Example output:
13
1 1 2 3
1 3 2 3
2 1 2 3
2 2 2 3
2 3 2 3
3 3 2 3
1 2 2 2
1 2 3 2
1 3 3 2
1 4 3 2
2 4 3 2
3 4 3 2
3 4 2 2

Example input:
2 2 2
2 1
1 2

Example output:
9
1 3 1 1
2 3 1 1
3 1 1 1
3 2 1 1
3 3 1 1
1 1 2 2
1 2 2 2
2 1 2 2
2 2 2 2

Editorial:
We can show that a solution always exists. This example with $$$n=3$$$, $$$m=5$$$, $$$k=4$$$ will demonstrate the construction we will use:
First, extend each of the even columns up by $$$n+k-1$$$ spaces, keeping all cubes in a given vertical column the same color:
Then, for the odd columns, do something similar, except we use the bottom $$$n-1$$$ rows to "bend" them around so the tops point out to the right:
After that, extend each of these new "bent" rows (each of which corresponds to an input cube in an odd column) to the right by $$$k$$$:
Now, each initial cube in the $$$n$$$ by $$$m$$$ grid corresponds to one of these extended rows or columns, each of which is a connected group. Fill in the remaining columns between the even columns with $$$k$$$ rows each. The $$$i$$$-th of these should be color $$$i$$$.
Now do the same for the odd columns:
At this point, each cell of a given color is connected to at least one of the rows/columns we added in the last two steps. Now, we want to connect all of those by color. Start by adding these $$$k$$$ rows:
Followed by these $$$k-1$$$ rows:
Once again, at this point, each cube of a given color is connected to one of the rows of that color we added in the last two steps. So the last remaining step is to connect them:
Now, all cubes of each color are connected.
This construction uses exactly $$$(n+k)^2m - (k-1)^2(m-1) - nm$$$ additional cubes. Since $$$n, m, k \le 50$$$, this is at most $$$379,851$$$, which fits within the bounds of the problem.
Complexity: $$$O((n+k)^2 m)$$$