eva's balance

프로그램 명: eva_balance

제한시간: 1 초

에바는 20 개의 저울 추를 가지고 있다. 추의 무게는 1 , 3 , 9 , 27 , ... , 3^19 이다.

에바는 물건의 무게를 대칭저울을 사용하여 알고자 한다. 물건의 무게는 1 에서 (3^20 - 1) / 2 이다.

물건을 대칭 저울의 왼쪽 접시에 두고 , 추를 왼쪽 혹은 오른쪽 접시에 두어 대칭을 만들면 물건의 무게를 알수 있다.

물건의 무게 W 가 입력으로 주어진다. ( 1 <= W <= (3^20-1)/2 )

왼쪽 접시의 저울추 , 오른쪽 접시의 저울 추를 공백을 사이에 두고 출력한다. 같은 접시내의 저울추는 오름차순으로 출력하고 콤마(,)로 저울추를 구분한다.

왼쪽 접시에 저울추가 필요하지 않다면 empty 를 출력한다.

입력

9

출력

empty 9

입력

5

출력

1,3 9

입력

20

출력

1,9 3,27

저울 추는 각 한 개씩이고 , 여러가지 경우의 답이 존재하지 않는다.

출처:POJ Monthly--2004.07.18