Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bell Ringing

Limits 1s, 512 MB · Custom Checker

Method ringing is used to ring bells in churches, particularly in England. Suppose there are6bells that have6different pitches. We assign the number1to the bell highest in pitch,2tothe second highest, and so on. When the 6 bells are rung in some order—each of them exactly once-it is called a row. For example,1,2,3,4,5,6and6,3,2,4,1,5are two different rows.

An ideal performance contains all possible rows, each played exactly once. Unfortunately,the laws of physics place a limitation on any two consecutive rows; when a bell is rung, it has considerable inertia and the ringer has only a limited ability to accelerate or retard its cycle.Therefore, the position of each bell can change by at most one between two consecutive rows

In the figure, you can see the pattern of a non-ideal performance, where bells only change position by at most one.

This figure shows a non-ideal performance respecting the inertia of bells. The trajectory of bell number 1 is marked with a blue line and trajectory of bell number 2 marked with a brown line.

Given n, the number of bells, output an ideal performance. All possible rows must be present exactly once, and the first row should be 1, 2, …, n.

Input

The first and only line of input contains an integer n (1 ≤ n ≤ 8).

Output

Output an ideal sequence of rows, each on a separate line. The first line should contain the row 1, 2, …, n and each two consecutive lines should be at most 1 step away from each other. Each row should occur exactly once in the output.

Sample

InputOutput
2
1 2
2 1

This NCPC 2015 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NCPC website.


    Discussion
    Statistics

    100% Solution Ratio

    mdvirusEarliest, 1M ago

    mashfiqur404Fastest, 0.1s

    mashfiqur404Lightest, 4.0 MB

    mdvirusShortest, 416B

    Submit

    Login to submit