완전 이진 트리

완전 이진 트리는 계층적인 구조를 가진다. 루트 노드의 레벨은 0이고, 루트의 두 자식은 레벨 1이다. 일반적으로 어떤 노드의 레벨이 D라면 그 자식의 레벨은 D + 1이다.

레벨이 N인 완전 이진 트리는 모든 잎이 레벨 N - 1에 있으며, 전체 노드 수는 2^N - 1개이다. 레벨이 N - 1이 아닌 모든 노드는 왼쪽 자식과 오른쪽 자식을 하나씩 가진다.

1부터 2^N - 1까지의 정수를 각 노드에 하나씩 적어야 한다. 모든 정수는 정확히 한 번씩 사용해야 한다. 또한 레벨이 D인 모든 내부 노드에 대해, 왼쪽 서브트리에 적힌 수의 합과 오른쪽 서브트리에 적힌 수의 합의 차이의 절댓값은 2^D이어야 한다.

예를 들어 루트에서는 두 서브트리 합의 차이가 1이어야 하고, 레벨 1의 내부 노드에서는 차이가 2이어야 한다.

N이 주어졌을 때 조건을 만족하도록 완전 이진 트리의 각 노드에 수를 적고, 그 결과를 출력하시오.

첫째 줄에 트리의 레벨 N이 주어진다. (1 <= N <= 15)

조건을 만족하도록 수를 적은 완전 이진 트리를 전위 순회한 결과를 첫째 줄에 출력한다. 답이 여러 가지라면 그중 아무 것이나 출력해도 된다.