AT_arc221_d.Two Balanced Subtrees

You are given a positive integer $N$.

There is a complete binary tree with $2^N-1$ vertices. The vertices are numbered $1$ through $2^N-1$.

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

Find one way to write an integer between $1$ and $2^N-1$, inclusive, on the vertices (where all $2^N-1$ written integers are distinct) such that the following condition is satisfied.

• For each $i\ (1\leq i\lt 2^{N-1})$, 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$ is $1$.

It can be proved that there always exists a way to write the integers satisfying the condition under the constraints of this problem.

给定一个正整数 $N$。

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

顶点 $1$ 为根节点；对每个 $i\ (1\leq i\lt 2^{N-1})$，顶点 $i$ 的两个子节点分别为顶点 $2i$ 和 $2i+1$。

请给出一种方案：将 $1$ 到 $2^N-1$（含端点）之间的整数填入各顶点（所有 $2^N-1$ 个填入的整数互不相同），使得满足如下条件：

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

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

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

$N$

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

$N$

Let $P_i$ be the integer written on vertex $i$. Output:

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

$(P_1,P_2,\ldots,P_{2^N-1})$ must be a permutation of $(1,2,\ldots,2^N-1)$.

If there are multiple valid ways to write the integers, any of them will be accepted.

设顶点 $i$ 上写的整数为 $P_i$。输出：

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

$(P_1,P_2,\ldots,P_{2^N-1})$ 必须是 $(1,2,\ldots,2^N-1)$ 的一个排列。

若存在多种合法的填数方式，输出任意一种即可。

Sample 1 Explanation:
We can verify that this assignment satisfies the condition, as follows.

• $i=1$: The sum of the integers written on the vertices of the subtree rooted at vertex $2$ is $14$, the sum of the integers written on the vertices of the subtree rooted at vertex $3$ is $13$, and $|14-13|=1$.
• $i=2$: The sum of the integers written on the vertices of the subtree rooted at vertex $4$ is $3$, the sum of the integers written on the vertices of the subtree rooted at vertex $5$ is $4$, and $|3-4|=1$.
• $i=3$: The sum of the integers written on the vertices of the subtree rooted at vertex $6$ is $5$, the sum of the integers written on the vertices of the subtree rooted at vertex $7$ is $6$, and $|5-6|=1$.

Constraints

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

样例 1 解释：
我们可以验证该赋值满足题目条件，具体如下：

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

限制条件

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