Bell Ringing

Method ringing is a way of ringing church bells, common in England. Suppose there are $n$ bells with $n$ different pitches. The bell highest in pitch gets number 1, the second highest gets number 2, and so on. Ringing all $n$ bells in some order, each of them exactly once, gives one row. For $n = 6$, the orders 1, 2, 3, 4, 5, 6 and 6, 3, 2, 4, 1, 5 are two different rows.

A performance is ideal when every possible row appears in it exactly once. Physics limits which rows can follow each other. A bell that has been rung carries considerable inertia, and the ringer can speed up or slow down its cycle only a little. Therefore the position of each bell can change by at most one between two consecutive rows.

The figure below shows a performance that respects the inertia of the bells but is not ideal. The trajectory of bell 1 is drawn in blue and the trajectory of bell 2 is drawn in brown.

Given $n$, print an ideal performance whose first row is 1, 2, ..., $n$.

The first and only line contains an integer $n$ ($1 \le n \le 8$).

Many ideal performances exist for the same $n$, so exactly one of them is accepted, defined as follows.

• For $n = 1$ the sequence is the single row 1.
• Let $R_1, R_2, \dots, R_{(n-1)!}$ be the sequence for $n - 1$. Build the sequence for $n$ by replacing each $R_i$, in order, with $n$ rows: insert bell $n$ into each of the $n$ possible positions of $R_i$. When $i$ is odd, go from the rightmost position to the leftmost one. When $i$ is even, go from the leftmost position to the rightmost one.

Print the $n!$ rows of that sequence, one row per line. Separate the $n$ numbers of a row with single spaces.