题目描述

通常，人们习惯将所有 $n$ 位二进制串按照字典序排列，例如所有 $2$ 位二进制串按字典序从小到大排列为：00，01，10，11。

格雷码（Gray Code）是一种特殊的 $n$ 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

设 $c_i$ 表示第 $i$ 位作为相邻两个串的不同位的次数。

所有 $2$ 位二进制串按格雷码排列的一个例子为：00，01，11，10。对应的 $c$ 序列为：$c_1=2$，$c_2=2$。

$n$ 位格雷码不止一种，你想求出 $c$ 序列的极差最小的一种。特别的，如果有多种答案，输出任意一种。

输入格式

仅一行一个正整数 $n$，意义见题目描述。

输出格式

仅一行 $2^n$ 个正整数。$\forall 1 \le i < 2^n$，第 $i$ 个正整数表示你构造的第 $i$ 个二进制串和第 $i+1$ 个二进制串不同的位。第 $2^n$ 个正整数表示第一个串与最后一个串不同的位。

样例

样例输入 1

2

样例输出 1

1 2 1 2

样例输入 2

3

样例输出 2

1 3 1 2 1 3 1 2

数据范围与约定

本题采用自定义校验器（Special Judge）评测。

本题共 $25$ 个测试点，每个测试点分值相同。第 $T$ 个测试点满足 $n = T$。

对每个测试点，评分方式如下：

• 如果你输出的方案是 $n$ 位格雷码且 $c$ 序列的极差最小，得到 $100\%$ 的该测试点分数；
• 如果你输出的方案是 $n$ 位格雷码但 $c$ 序列极差并非最小，得到 $20\%$ 的该测试点分数；
• 否则，得到 $0\%$ 的该测试点分数。

提示

本题输出数据较大，请使用较快的输出方式。