#abc247c. [abc247_c]1 2 1 3 1 2 1

[abc247_c]1 2 1 3 1 2 1

题目描述

我们定义序列 SnS_n 如下。

  • S1S_1 是长度为 11 的序列,只包含一个 11
  • SnS_nnn 是大于或等于 22 的整数)是通过将 Sn1S_{n-1}nnSn1S_{n-1} 依次拼接而得到的序列。

例如,S2S_2S3S_3 定义如下。

  • S2S_2 是按顺序将 S1S_122S1S_1 拼接而成的,因此它是 1,2,11,2,1
  • S3S_3 是按顺序将 S2S_233S2S_2 拼接而成的,因此它是 1,2,1,3,1,2,11,2,1,3,1,2,1

给定 NN,打印完整的序列 SNS_N

约束条件

  • NN 是一个整数。
  • 1N161 \leq N \leq 16

输入

输入以以下格式从标准输入获得:

NN

输出

以空格分隔的形式打印 SNS_N


示例输入 1

2

示例输出 1

1 2 1

根据题目描述,S2S_21,2,11,2,1


示例输入 2

1

示例输出 2

1

示例输入 3

4

示例输出 3

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

S4S_4 按顺序将 S3S_344S3S_3 拼接而成。