시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 80 41 40 51.948%

문제

다음과 같이 모든 음이 아닌 3의 제곱수가 들어있는 집합이 있다.

S = {1, 3, 9, 27, 81, ...}

S의 모든 부분집합을 구한 뒤, 이 집합을 가지고 있는 원소값의 합으로 오름차순 정렬했을 때, n번째 집합을 구하는 프로그램을 작성하시오.

입력

입력을 여러 개의 줄로 이루어져 있고, 각 줄에는 n이 주어진다. n은 19자리를 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0이 있다. 

출력

각 입력에 대해서, n번째 집합을 예제 출력 형식과 같게 출력한다.

예제 입력 1

1
7
14
783
1125900981634049
0

예제 출력 1

{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
W3sicHJvYmxlbV9pZCI6IjQzMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIzXHVjNzU4IFx1YzgxY1x1YWNmMSIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViYWE4XHViNGUwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgM1x1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMThcdWFjMDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFMgPSB7MSwgMywgOSwgMjcsIDgxLCAuLi59PFwvcD5cclxuXHJcbjxwPlxyXG5cdFNcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NWMgXHViNGE0LCBcdWM3NzQgXHVjOWQxXHVkNTY5XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNmQwXHVjMThjXHVhYzEyXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjODE1XHViODJjXHVkNTg4XHVjNzQ0IFx1YjU0Yywgblx1YmM4OFx1YzlmOCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1Yzc0MCAxOVx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBuXHViYzg4XHVjOWY4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1IFx1ZDYxNVx1YzJkZFx1YWNmYyBcdWFjMTlcdWFjOGMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzMTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaHJlZSBwb3dlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIHRoZSBzZXQgb2YgYWxsIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIHBvd2VycyBvZiAzLjxcL3A+XHJcblxyXG48cD5TID0geyAxLCAzLCA5LCAyNywgODEsIC4uLiB9PFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSBzZXF1ZW5jZSBvZiBhbGwgc3Vic2V0cyBvZiBTIG9yZGVyZWQgYnkgdGhlIHZhbHVlIG9mIHRoZSBzdW0gb2YgdGhlaXIgZWxlbWVudHMuIFRoZSBxdWVzdGlvbiBpcyBzaW1wbGU6IGZpbmQgdGhlIHNldCBhdCB0aGUgbi10aCBwb3NpdGlvbiBpbiB0aGUgc2VxdWVuY2UgYW5kIHByaW50IGl0IGluIGluY3JlYXNpbmcgb3JkZXIgb2YgaXRzIGVsZW1lbnRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgbnVtYmVyIG4sIHdoaWNoIGlzIGEgcG9zaXRpdmUgaW50ZWdlciB3aXRoIG5vIG1vcmUgdGhhbiAxOSBkaWdpdHMuIFRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgMCBhbmQgaXQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbGluZSBvZiBpbnB1dCwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgZGlzcGxheWluZyB0aGUgbi10aCBzZXQgYXMgZGVzY3JpYmVkIGFib3ZlLCBpbiB0aGUgZm9ybWF0IHVzZWQgaW4gdGhlIHNhbXBsZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d