## IPSC 2000

## Problem H – Colorful Cubes

Bill Games, an excellent programmer, spent Easter with his
grandparents. In their old house he came across wooden cubes - a
child's toy. When he was a child, he used to build castles and towers
and pyramids of these colorful cubes. He started to play with them
again. However, the problem which he tries to solve today is much
more complicated than building a simple pyramid.

Each face of a cube is colored with one color. Bill wants to build a
tower from all cubes he has. This means to stack all the cubes in
one column, one on another. Bill does not want to put the cubes in
arbitrary order - the bottom face of every cube (except the bottom
cube which is lying on the floor) should have the same color as the
top face of the cube below it.

### Input file specification

The first line of the input file consists of two numbers **M** and
**N**. **M** is the number of colors used (colors are numbered
**1...M**) and **N** is the number of cubes (cubes are numbered
**1...N** in the order as they appear on the input).

Next **N** lines represent cubes **1,2,...,N** in this
order. A cube is described by six numbers giving colors of its faces
in the following order: front, back, right, left, bottom, and top
face.

### Output file specification

Given the cubes described in the input file determine how to arrange
them into a tower. Every cube has to be used exactly once. You need
to find only one solution. Assume that the solution exists.

The output file consists of **N** lines. The **i**-th line
contains the description of the cube on the **i**th position in the
tower, counting from bottom. The description of a cube consists of
seven numbers. The first number is the number of the cube (the order
of the cube in the input file) and the following six numbers represent
colors of the faces in the following order: front, back, right, left,
bottom, and top face. Notice that cubes can be rotated.

### Example #1

**Input file:**
6 2
1 2 3 4 5 6
2 1 3 4 5 6

**Output file:**
1 6 5 3 4 1 2
2 6 5 3 4 2 1

### Example #2

**Input file:**
3 3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 1 1 1

**Output file:**
1 1 2 2 2 1 2
3 1 1 1 1 2 3
2 3 3 3 3 3 3