Stacking Cubes

Interview

Time limit1sMemory limit128 MB

Summary

Given a stacking pattern as non-increasing rows with non-increasing columns, print its left and right rotations as corner stackings.

Level: Medium6 of 10
Topics: Array, Implementation, Simulation, Matrix
Solved: No attempts yet

Problem

Consider the following pattern of positive integers:

3 3 1
3 1
2

Each row is left-justified and is no longer than the row above it. Reading each row from left to right the numbers are non-increasing, and reading each column from top to bottom the numbers are also non-increasing. We call such an arrangement a stacking pattern (SP), because it describes a way of stacking unit cubes into the corner of a room.

Put the top row against one wall and the left column against the other wall. Each number in the SP is then a bird's-eye view of how many cubes are stacked vertically at that position. The pattern above represents this corner stacking:

We call the wall behind the top row the right wall and the wall behind the left column the left wall. Here is another SP together with the stacking it represents:

6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1

If you tip a corner stacking so that its left wall becomes the floor (and the old floor becomes the right wall), you again get a valid corner stacking; call this the left rotation. Likewise, tipping it so that the right wall becomes the floor (and the old floor becomes the left wall) is the right rotation.

For example, the left and right rotations of the first pattern are:

Left rotation:

3 2 1
2 1 1
2 1

Right rotation:

3 3 2
2 1 1
1

You can check that both the left and right rotations of the second pattern are identical to the original.

Input

The input contains several problem instances. Each instance begins with a positive integer $n$ ( $n \le 11$ ), the number of rows in the stacking pattern. A value of $n = 0$ marks the end of the input.

The $n$ rows of the pattern then follow, one per line. Within a line the entries are separated by single spaces and the line ends with a trailing $0$ ; this $0$ is only a delimiter and is not part of the pattern. Every pattern entry is a positive integer at most $20$ , each row contains at least one entry, and no row has more than $20$ entries.

Output

For each stacking pattern, output its left rotation followed by its right rotation, in that order. Print the rows left-justified, with entries separated by single spaces. Separate the left rotation from the right rotation with one blank line, and separate the output of different problem instances with two blank lines.

Examples1

Example 1

Input

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

Expected output

3 2 1
2 1 1
2 1

3 3 2
2 1 1
1


6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1

6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1