시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 168 102 82 67.213%

문제

완전 이진 트리의 각 노드는 계측적인 구조로 이루어져 있다. 루트 노드의 레벨은 0이며, 레벨 1의 두 자식 노드를 가지고 있다. 또, 레벨 1의 자식 노드의 레벨은 2이다.

보통 레벨이 N인 완전 이진 트리는 2N-1개의 노드를 가지고 있다. 레벨이 N-1이 아닌 모든 노드는 자식 노드를 두 개씩 가지고 있다.

1부터 2N-1까지 숫자를 레벨이 N인 완전 이진 트리의 각 노드에 적을 수 있다. 이때, 레벨이 D인 각각의 노드에 대해서 왼쪽 서브트리에 쓰여 있는 숫자의 합과 오른쪽 서브트리에 쓰여 있는 숫자의 합의 차이는 2D라는 조건을 만족해야 한다.

예를 들어, 루트의 왼쪽 서브 트리의 합과 오른쪽 서브 트리의 합의 차이는 1이어야 하며, 레벨이 1인 경우에는 2이어야 한다. 또, 모든 숫자는 한 번씩 사용해야 한다.

N이 주어졌을 때, 문제의 조건에 맞게 완전 이진 트리의 각 노드에 숫자를 정하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 문제의 조건에 맞게 숫자를 채운 완전 이진 트리를 프리오더로 순회한 결과를 출력한다.

예제 입력 1

3

예제 출력 1

3 1 7 5 6 2 4
W3sicHJvYmxlbV9pZCI6IjMwMzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NDRcdWM4MDQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNjQ0XHVjODA0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWFjYzRcdWNlMjFcdWM4MDFcdWM3NzggXHVhZDZjXHVjODcwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjhlOFx1ZDJiOCBcdWIxNzhcdWI0ZGNcdWM3NTggXHViODA4XHViY2E4XHVjNzQwIDBcdWM3NzRcdWJhNzAsIFx1YjgwOFx1YmNhOCAxXHVjNzU4IFx1YjQ1MCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViODA4XHViY2E4IDFcdWM3NTggXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWI4MDhcdWJjYThcdWM3NDAgMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViY2Y0XHVkMWI1IFx1YjgwOFx1YmNhOFx1Yzc3NCBOXHVjNzc4IFx1YzY0NFx1YzgwNCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViMjk0IDI8c3VwPk48XC9zdXA+LTFcdWFjMWNcdWM3NTggXHViMTc4XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjgwOFx1YmNhOFx1Yzc3NCBOLTFcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWI0NTAgXHVhYzFjXHVjNTI5IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDFcdWJkODBcdWQxMzAgMjxzdXA+TjxcL3N1cD4tMVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViODA4XHViY2E4XHVjNzc0IE5cdWM3NzggXHVjNjQ0XHVjODA0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM4MDFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI4MDhcdWJjYThcdWM3NzQgRFx1Yzc3OCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTc4XHViNGRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1YWNmYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNjMjhcdWM3NzRcdWIyOTQgMjxzdXA+RDxcL3N1cD5cdWI3N2NcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjhlOFx1ZDJiOFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjI5NCAxXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHViODA4XHViY2E4XHVjNzc0IDFcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDJcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YzY0NFx1YzgwNCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwMSBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHViODA4XHViY2E4XHVjNzc4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjNDRcdWM2YjQgXHVjNjQ0XHVjODA0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKT0dVUlQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY29tcGxldGUgYmluYXJ5IHRyZWUgaXMgbWFkZSBvZiBub2RlcyBhcnJhbmdlZCBpbiBhIGhpZXJhcmNoaWMgc3RydWN0dXJlLiBPbmUgb2YgdGhlIG5vZGVzIGlzIHRoZSByb290IG5vZGUsIHNhaWQgdG8gYmUgYXQgbGV2ZWwgMC4gVGhlIHJvb3Qgbm9kZSBoYXMgdHdvIGNoaWxkIG5vZGVzLCB3aGljaCBhcmUgYXQgbGV2ZWwgMS4gRWFjaCBvZiB0aG9zZSBoYXMgdHdvIGNoaWxkcmVuIGF0IGxldmVsIDIgZXRjLjxcL3A+XHJcblxyXG48cD5JbiBnZW5lcmFsLCBhIGNvbXBsZXRlIGJpbmFyeSB0cmVlIHdpdGggTiBsZXZlbHMgaGFzIDI8c3VwPk48XC9zdXA+Jm5kYXNoOzEgbm9kZXMsIGVhY2ggb2Ygd2hpY2ggaGFzIHR3byBjaGlsZCBub2RlcywgZXhjZXB0IHRob3NlIGF0IGxldmVsIEwmbmRhc2g7MS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBudW1iZXIgY2FuIGJlIHdyaXR0ZW4gaW50byBlYWNoIG5vZGUuIFdyaXRlIHRoZSBudW1iZXJzIDEgdG8gMjxzdXA+TjxcL3N1cD4mbmRhc2g7MSBpbnRvIGEgY29tcGxldGUgYmluYXJ5IHRyZWUgd2l0aCBOIGxldmVscyBzbyB0aGF0LCBmb3IgZWFjaCBub2RlIGF0IGxldmVsIEQsIHRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiB0aGUgZGlmZmVyZW5jZSBvZiB0aGUgc3VtIG9mIGFsbCBudW1iZXJzIGluIHRoZSBsZWZ0IHN1YnRyZWUgYW5kIHRoZSBzdW0gb2YgYWxsIG51bWJlcnMgaW4gdGhlIHJpZ2h0IHN1YnRyZWUgaXMgMjxzdXA+RDxcL3N1cD4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgc3VtIG9mIHRoZSBsZWZ0IHN1YnRyZWUgb2YgdGhlIHJvb3Qgbm9kZSBtdXN0IGRpZmZlciBmcm9tIHRoZSBzdW0gb2YgdGhlIHJpZ2h0IHN1YnRyZWUgYnkgMS4gVGhlIHN1bXMgb2YgdGhlIGxlZnQgYW5kIHJpZ2h0IHN1YnRyZWVzIG9mIGEgbm9kZSBhdCBsZXZlbCAxIG11c3QgZGlmZmVyIGJ5IDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggbnVtYmVyIG11c3QgYmUgdXNlZCBleGFjdGx5IG9uY2UuIFRoZSBzb2x1dGlvbiBuZWVkIG5vdCBiZSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDE1KSwgdGhlIG51bWJlciBvZiBsZXZlbHMgaW4gdGhlIHRyZWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgMjxzdXA+TjxcL3N1cD4mbmRhc2g7MSBzZXBhcmF0ZWQgYnkgc3BhY2VzIG9uIGEgc2luZ2xlIGxpbmUsIHRoZSBiaW5hcnkgdHJlZSBpbiB0aGUgcHJlb3JkZXIgdHJhdmVyc2FsLiBUaGUgcHJlb3JkZXIgdHJhdmVyc2FsIGZpcnN0IG91dHB1dHMgdGhlIG51bWJlciBpbiB0aGUgcm9vdCBub2RlLCB0aGVuIG91dHB1dHMgdGhlIGxlZnQgc3VidHJlZSAoYWdhaW4gaW4gdGhlIHByZW9yZGVyIHRyYXZlcnNhbCksIHRoZW4gdGhlIHJpZ2h0IHN1YnRyZWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d