AT_arc231_f.Two Unbalanced Subtrees

You are given a positive integer $N$.

There is a perfect binary tree with $2^N - 1$ vertices. The vertices are numbered from $1$ to $2^N - 1$.

Vertex $1$ is the root, and for each vertex $i$ ($1 \leq i < 2^{N - 1}$), vertex $i$ has vertex $2i$ and vertex $2i + 1$ as its children.

Among the ways to write an integer between $1$ and $2^N - 1$, inclusive, on each vertex (where the $2^N - 1$ written integers must be pairwise distinct) such that the following condition is satisfied, find one that minimizes the integer written on vertex $1$.

• For each vertex $i$ ($1 \leq i < 2^{N - 1}$), the integer written on vertex $i$ is the absolute difference between the sum of the integers written on the vertices of the subtree rooted at vertex $2i$ and the sum of the integers written on the vertices of the subtree rooted at vertex $2i+1$.

It can be proved that, under the constraints of this problem, a way of writing integers satisfying the condition always exists.

给定一个正整数 $N$。

存在一棵含 $2^N - 1$ 个顶点的完美二叉树。这些顶点编号为 $1$ 至 $2^N - 1$。

顶点 $1$ 是根节点；对每个顶点 $i$（$1 \leq i < 2^{N - 1}$），顶点 $i$ 的左右子节点分别为顶点 $2i$ 和顶点 $2i + 1$。

在所有满足如下条件的填数方案中（即：将 $1$ 到 $2^N - 1$（含端点）之间的整数分别填入各顶点，且这 $2^N - 1$ 个整数两两不同），找出一种使得顶点 $1$ 上所填整数最小的方案。

• 对每个顶点 $i$（$1 \leq i < 2^{N - 1}$），顶点 $i$ 上所填整数等于以顶点 $2i$ 为根的子树中所有顶点所填整数之和，与以顶点 $2i+1$ 为根的子树中所有顶点所填整数之和的绝对差值。

可以证明，在本题约束下，总存在满足该条件的填数方案。

The input is given from Standard Input in the following format:

$N$

输入从标准输入中按以下格式给出：

$N$

Let $P_i$ be the integer written on vertex $i$ ($1 \leq i \leq 2^N - 1$), and output in the following format:

$P_1$ $P_2$ $\cdots$ $P_{2^N - 1}$

$(P_1, P_2, \cdots, P_{2^N - 1})$ must be a permutation of $(1, 2, \cdots, 2^N - 1)$. If there are multiple ways of writing satisfying the condition that minimize the integer written on vertex $1$, any of them will be considered correct.

设顶点 $i$（$1 \leq i \leq 2^N - 1$）上所写的整数为 $P_i$，并按如下格式输出：

$P_1$ $P_2$ $\cdots$ $P_{2^N - 1}$

$(P_1, P_2, \cdots, P_{2^N - 1})$ 必须是 $(1, 2, \cdots, 2^N - 1)$ 的一个排列。若存在多种满足条件的写法，且均使顶点 $1$ 上所写的整数最小，则其中任意一种均视为正确。

Sample 1 Explanation:
It can be verified as follows that this way of writing satisfies the condition. Also, the integer written on vertex $1$ is clearly minimized.

• $i = 1$: The sum of the integers written on the vertices of the subtree rooted at vertex $2$ is $2$, the sum of the integers written on the vertices of the subtree rooted at vertex $3$ is $3$, and $∣2 − 3∣ = 1$.

The way of writing $2, 3, 1$ on vertices $1, 2, 3$, respectively, satisfies the condition, but the integer written on vertex $1$ is not the minimum, so it will be judged as incorrect.

Constraints

• $2 \leq N \leq 18$
• All input values are integers.

样例 1 解释：
可以验证，如下所示的赋值方式满足题目条件。此外，顶点 $1$ 上所写的整数显然最小。

• $i = 1$：以顶点 $2$ 为根的子树中各顶点上所写整数之和为 $2$，以顶点 $3$ 为根的子树中各顶点上所写整数之和为 $3$，且 $|2 - 3| = 1$。

在顶点 $1, 2, 3$ 上分别写入 $2, 3, 1$ 的方式虽满足条件，但顶点 $1$ 上所写的整数并非最小，因此会被判定为错误。

限制条件

• $2 \leq N \leq 18$
• 所有输入值均为整数。