C - 1 2 1 3 1 2 1 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

列 S_n を次のように定義します。

  • S_1 は 1 つの 1 からなる長さ 1 の列である。
  • S_n (n は 2 以上の整数) は S_{n-1}, n, S_{n-1} をこの順につなげた列である。

たとえば S_2,S_3 は次のような列です。

  • S_2 は S_1, 2, S_1 をこの順につなげた列なので 1,2,1 である。
  • S_3 は S_2, 3, S_2 をこの順につなげた列なので 1,2,1,3,1,2,1 である。

N が与えられるので、列 S_N をすべて出力してください。

制約

  • N は整数
  • 1 \leq N \leq 16

入力

入力は以下の形式で標準入力から与えられる。

N

出力

S_N を空白区切りで出力せよ。

入力例 1

2

出力例 1

1 2 1

問題文の説明にある通り、S_2 は 1,2,1 となります。

入力例 2

1

出力例 2

1

入力例 3

4

出力例 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

S_4 は S_3,4,S_3 をこの順につなげた列です。

Score : 300 points

Problem Statement

We define sequences S_n as follows.

  • S_1 is a sequence of length 1 containing a single 1.
  • S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

  • S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
  • S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

  • N is an integer.
  • 1 \leq N \leq 16

Input

Input is given from Standard Input in the following format:

N

Output

Print S_N, with spaces in between.

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
  • S_4 is a concatenation of S_3, 4, and S_3, in this order.