AT_arc221_d [ARC221D] 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.

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

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