종 울리기

영국을 비롯한 여러 나라의 교회에서는 종 여러 개를 정해진 순서로 울리는 전종(method ringing)을 한다. 음이 서로 다른 종이 $n$개 있고, 음이 가장 높은 종에 1번, 그다음으로 높은 종에 2번, 이런 식으로 번호를 붙인다. 종 $n$개를 각각 정확히 한 번씩 어떤 순서로 울린 것을 한 행이라고 부른다. $n = 6$일 때 1, 2, 3, 4, 5, 6과 6, 3, 2, 4, 1, 5는 서로 다른 두 행이다.

가능한 모든 행이 정확히 한 번씩 나오는 연주를 이상적인 연주라고 한다. 그런데 연속한 두 행 사이에는 물리 법칙에서 오는 제약이 있다. 한 번 울린 종에는 관성이 크게 남아서, 치는 사람이 그 주기를 앞당기거나 늦출 수 있는 폭이 좁다. 그래서 연속한 두 행 사이에서 각 종의 위치는 최대 1만큼만 바꿀 수 있다.

아래 그림은 종의 관성 조건은 지키지만 이상적이지는 않은 연주다. 1번 종이 지나간 자리는 파란 선으로, 2번 종이 지나간 자리는 갈색 선으로 그렸다.

$n$이 주어지면 첫 행이 1, 2, ..., $n$인 이상적인 연주를 출력한다.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 8$).

같은 $n$에 대해 이상적인 연주는 여러 가지가 있으므로, 다음과 같이 정의한 연주 하나만 정답으로 인정한다.

• $n = 1$이면 행은 1 하나뿐이다.
• $n - 1$에 대한 연주를 $R_1, R_2, \dots, R_{(n-1)!}$이라고 하자. $n$에 대한 연주는 각 $R_i$를 순서대로 행 $n$개로 바꾸어 만든다. $R_i$에서 종 $n$을 넣을 수 있는 위치 $n$곳에 하나씩 끼워 넣되, $i$가 홀수면 가장 오른쪽 위치에서 가장 왼쪽 위치까지 차례로 넣고, $i$가 짝수면 가장 왼쪽 위치에서 가장 오른쪽 위치까지 차례로 넣는다.

이렇게 만든 행 $n!$개를 한 줄에 하나씩 출력한다. 한 행에 있는 수 $n$개는 공백 한 칸으로 구분한다.