Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Blocks and Sensors

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPolycarp plays a well-known computer game (we won't mention its name). Every object in this game consists of three-dimensional blocks — axis-aligned cubes of size $$$1 \times 1 \times 1$$$. These blocks are unaffected by gravity, so they can float in the air without support. The blocks are placed in cells of size $$$1 \times 1 \times 1$$$; each cell either contains exactly one block or is empty. Each cell is represented by its coordinates $$$(x, y, z)$$$ (the cell with these coordinates is a cube with opposite corners in $$$(x, y, z)$$$ and $$$(x + 1, y + 1, z + 1)$$$) and its contents $$$a_{x, y, z}$$$; if the cell is empty, then $$$a_{x, y, z} = 0$$$, otherwise $$$a_{x, y, z}$$$ is equal to the type of the block placed in it (the types are integers from $$$1$$$ to $$$2 \cdot 10^5$$$).

Polycarp has built a large structure consisting of blocks. This structure can be enclosed in an axis-aligned rectangular parallelepiped of size $$$n \times m \times k$$$, containing all cells $$$(x, y, z)$$$ such that $$$x \in [1, n]$$$, $$$y \in [1, m]$$$, and $$$z \in [1, k]$$$. After that, Polycarp has installed $$$2nm + 2nk + 2mk$$$ sensors around this parallelepiped. A sensor is a special block that sends a ray in some direction and shows the type of the first block that was hit by this ray (except for other sensors). The sensors installed by Polycarp are adjacent to the borders of the parallelepiped, and the rays sent by them are parallel to one of the coordinate axes and directed inside the parallelepiped. More formally, the sensors can be divided into $$$6$$$ types:

- there are $$$mk$$$ sensors of the first type; each such sensor is installed in $$$(0, y, z)$$$, where $$$y \in [1, m]$$$ and $$$z \in [1, k]$$$, and it sends a ray that is parallel to the $$$Ox$$$ axis and has the same direction;
- there are $$$mk$$$ sensors of the second type; each such sensor is installed in $$$(n + 1, y, z)$$$, where $$$y \in [1, m]$$$ and $$$z \in [1, k]$$$, and it sends a ray that is parallel to the $$$Ox$$$ axis and has the opposite direction;
- there are $$$nk$$$ sensors of the third type; each such sensor is installed in $$$(x, 0, z)$$$, where $$$x \in [1, n]$$$ and $$$z \in [1, k]$$$, and it sends a ray that is parallel to the $$$Oy$$$ axis and has the same direction;
- there are $$$nk$$$ sensors of the fourth type; each such sensor is installed in $$$(x, m + 1, z)$$$, where $$$x \in [1, n]$$$ and $$$z \in [1, k]$$$, and it sends a ray that is parallel to the $$$Oy$$$ axis and has the opposite direction;
- there are $$$nm$$$ sensors of the fifth type; each such sensor is installed in $$$(x, y, 0)$$$, where $$$x \in [1, n]$$$ and $$$y \in [1, m]$$$, and it sends a ray that is parallel to the $$$Oz$$$ axis and has the same direction;
- finally, there are $$$nm$$$ sensors of the sixth type; each such sensor is installed in $$$(x, y, k + 1)$$$, where $$$x \in [1, n]$$$ and $$$y \in [1, m]$$$, and it sends a ray that is parallel to the $$$Oz$$$ axis and has the opposite direction.

Polycarp has invited his friend Monocarp to play with him. Of course, as soon as Monocarp saw a large parallelepiped bounded by sensor blocks, he began to wonder what was inside of it. Polycarp didn't want to tell Monocarp the exact shape of the figure, so he provided Monocarp with the data from all sensors and told him to try guessing the contents of the parallelepiped by himself.

After some hours of thinking, Monocarp has no clue about what's inside the sensor-bounded space. But he does not want to give up, so he decided to ask for help. Can you write a program that will analyze the sensor data and construct any figure that is consistent with it?

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^5$$$, $$$nmk \le 2 \cdot 10^5$$$) — the dimensions of the parallelepiped.

Then the sensor data follows. For each sensor, its data is either $$$0$$$, if the ray emitted from it reaches the opposite sensor (there are no blocks in between), or an integer from $$$1$$$ to $$$2 \cdot 10^5$$$ denoting the type of the first block hit by the ray. The data is divided into $$$6$$$ sections (one for each type of sensors), each consecutive pair of sections is separated by a blank line, and the first section is separated by a blank line from the first line of the input.

The first section consists of $$$m$$$ lines containing $$$k$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(0, i, j)$$$.

The second section consists of $$$m$$$ lines containing $$$k$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(n + 1, i, j)$$$.

The third section consists of $$$n$$$ lines containing $$$k$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(i, 0, j)$$$.

The fourth section consists of $$$n$$$ lines containing $$$k$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(i, m + 1, j)$$$.

The fifth section consists of $$$n$$$ lines containing $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(i, j, 0)$$$.

Finally, the sixth section consists of $$$n$$$ lines containing $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is the data from the sensor installed in $$$(i, j, k + 1)$$$.

Output

If the information from the input is inconsistent, print one integer $$$-1$$$.

Otherwise, print the figure inside the parallelepiped as follows. The output should consist of $$$nmk$$$ integers: $$$a_{1, 1, 1}$$$, $$$a_{1, 1, 2}$$$, ..., $$$a_{1, 1, k}$$$, $$$a_{1, 2, 1}$$$, ..., $$$a_{1, 2, k}$$$, ..., $$$a_{1, m, k}$$$, $$$a_{2, 1, 1}$$$, ..., $$$a_{n, m, k}$$$, where $$$a_{i, j, k}$$$ is the type of the block in $$$(i, j, k)$$$, or $$$0$$$ if there is no block there. If there are multiple figures consistent with sensor data, describe any of them.

For your convenience, the sample output is formatted as follows: there are $$$n$$$ separate sections for blocks having $$$x = 1$$$, $$$x = 2$$$, ..., $$$x = n$$$; each section consists of $$$m$$$ lines containing $$$k$$$ integers each. Note that this type of output is acceptable, but you may print the integers with any other formatting instead (even all integers on the same line), only their order matters.

Examples

Input

4 3 2 1 4 3 2 6 5 1 4 3 2 6 7 1 4 1 4 0 0 0 7 6 5 6 5 0 0 0 7 1 3 6 1 3 6 0 0 0 0 0 7 4 3 5 4 2 5 0 0 0 0 0 7

Output

1 4 3 0 6 5 1 4 3 2 6 5 0 0 0 0 0 0 0 0 0 0 0 7

Input

1 1 1 0 0 0 0 0 0

Output

0

Input

1 1 1 0 0 1337 0 0 0

Output

-1

Input

1 1 1 1337 1337 1337 1337 1337 1337

Output

1337

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2022 08:43:48 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|