시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 134 87 67 68.367%

문제

완전 이진 트리의 각 노드는 계측적인 구조로 이루어져 있다. 루트 노드의 레벨은 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+TjxcL3N1cD4tMVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViODA4XHViY2E4XHVjNzc0IE5cdWM3NzggXHVjNjQ0XHVjODA0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM4MDFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViODA4XHViY2E4XHVjNzc0IERcdWM3NzggXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjE3OFx1YjRkY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IDI8c3VwPkQ8XC9zdXA+XHViNzdjXHViMjk0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWI4ZThcdWQyYjhcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNjMjhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YjgwOFx1YmNhOFx1Yzc3NCAxXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAyXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM1MjkgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM2NDRcdWM4MDQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNWQwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MTVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc3OCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTUpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzQ0XHVjNmI0IFx1YzY0NFx1YzgwNCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDUwNFx1YjlhY1x1YzYyNFx1YjM1NFx1Yjg1YyBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSk9HVVJUIiwiZGVzY3JpcHRpb24iOiI8cD5BIGNvbXBsZXRlIGJpbmFyeSB0cmVlIGlzIG1hZGUgb2Ygbm9kZXMgYXJyYW5nZWQgaW4gYSBoaWVyYXJjaGljIHN0cnVjdHVyZS4gT25lIG9mIHRoZSBub2RlcyBpcyB0aGUgcm9vdCBub2RlLCBzYWlkIHRvIGJlIGF0IGxldmVsIDAuIFRoZSByb290IG5vZGUgaGFzIHR3byBjaGlsZCBub2Rlcywgd2hpY2ggYXJlIGF0IGxldmVsIDEuIEVhY2ggb2YgdGhvc2UgaGFzIHR3byBjaGlsZHJlbiBhdCBsZXZlbCAyIGV0Yy48XC9wPlxyXG5cclxuPHA+SW4gZ2VuZXJhbCwgYSBjb21wbGV0ZSBiaW5hcnkgdHJlZSB3aXRoIE4gbGV2ZWxzIGhhcyAyPHN1cD5OPFwvc3VwPiZuZGFzaDsxIG5vZGVzLCBlYWNoIG9mIHdoaWNoIGhhcyB0d28gY2hpbGQgbm9kZXMsIGV4Y2VwdCB0aG9zZSBhdCBsZXZlbCBMJm5kYXNoOzEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgbnVtYmVyIGNhbiBiZSB3cml0dGVuIGludG8gZWFjaCBub2RlLiBXcml0ZSB0aGUgbnVtYmVycyAxIHRvIDI8c3VwPk48XC9zdXA+Jm5kYXNoOzEgaW50byBhIGNvbXBsZXRlIGJpbmFyeSB0cmVlIHdpdGggTiBsZXZlbHMgc28gdGhhdCwgZm9yIGVhY2ggbm9kZSBhdCBsZXZlbCBELCB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlIHN1bSBvZiBhbGwgbnVtYmVycyBpbiB0aGUgbGVmdCBzdWJ0cmVlIGFuZCB0aGUgc3VtIG9mIGFsbCBudW1iZXJzIGluIHRoZSByaWdodCBzdWJ0cmVlIGlzIDI8c3VwPkQ8XC9zdXA+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIHN1bSBvZiB0aGUgbGVmdCBzdWJ0cmVlIG9mIHRoZSByb290IG5vZGUgbXVzdCBkaWZmZXIgZnJvbSB0aGUgc3VtIG9mIHRoZSByaWdodCBzdWJ0cmVlIGJ5IDEuIFRoZSBzdW1zIG9mIHRoZSBsZWZ0IGFuZCByaWdodCBzdWJ0cmVlcyBvZiBhIG5vZGUgYXQgbGV2ZWwgMSBtdXN0IGRpZmZlciBieSAyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG51bWJlciBtdXN0IGJlIHVzZWQgZXhhY3RseSBvbmNlLiBUaGUgc29sdXRpb24gbmVlZCBub3QgYmUgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxNSksIHRoZSBudW1iZXIgb2YgbGV2ZWxzIGluIHRoZSB0cmVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIDI8c3VwPk48XC9zdXA+Jm5kYXNoOzEgc2VwYXJhdGVkIGJ5IHNwYWNlcyBvbiBhIHNpbmdsZSBsaW5lLCB0aGUgYmluYXJ5IHRyZWUgaW4gdGhlIHByZW9yZGVyIHRyYXZlcnNhbC4gVGhlIHByZW9yZGVyIHRyYXZlcnNhbCBmaXJzdCBvdXRwdXRzIHRoZSBudW1iZXIgaW4gdGhlIHJvb3Qgbm9kZSwgdGhlbiBvdXRwdXRzIHRoZSBsZWZ0IHN1YnRyZWUgKGFnYWluIGluIHRoZSBwcmVvcmRlciB0cmF2ZXJzYWwpLCB0aGVuIHRoZSByaWdodCBzdWJ0cmVlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==