AT_arc231_f [ARC231F] 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.

The input is given from Standard Input in the following format: > $ 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.

### Sample Explanation 1 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.