평형저울을 이용하여 물건의 무게를 재려고 한다. 물건의 무게는 \(1,000\)g 이하이며, 다음과 같은 7개의 추가 하나씩 준비되어 있다.

\(1\text{g}, 3\text{g}, 9\text{g}, 27\text{g}, 81\text{g}, 243\text{g}, 729\text{g}\)

물건은 항상 저울의 왼쪽 접시에 놓는다. 각각의 추는 사용하지 않거나, 물건과 같은 왼쪽 접시에 놓거나, 오른쪽 접시에 놓을 수 있다. 하나의 추를 두 번 이상 사용할 수는 없다.

예를 들어 25g인 물건은 물건과 3g 추를 왼쪽 접시에 놓고, 1g 추와 27g 추를 오른쪽 접시에 놓으면 무게가 같아진다.

\(25+3=1+27\)

물건의 무게가 주어졌을 때 저울이 평형을 이루도록 양쪽 접시에 놓을 추를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 물건의 무게를 나타내는 정수 \(n\)이 주어진다. 무게의 단위는 g이다.

출력

한 줄에 다음 순서로 정수들을 공백으로 구분하여 출력한다.

1. 물건의 무게 \(n\)
2. 왼쪽 접시에 놓는 추들을 가벼운 순서대로 출력
3. 두 접시의 목록을 구분하는 0
4. 오른쪽 접시에 놓는 추들을 가벼운 순서대로 출력

왼쪽 접시에 놓는 추가 없다면 \(n\) 바로 다음에 0을 출력한다. 0은 추가 아니라 두 접시의 목록을 구분하기 위한 값이다.

제한 사항

• \(1 \le n \le 1,000\)

예제 입력 1

25

예제 출력 1

25 3 0 1 27

예제 설명 1

물건과 3g 추를 왼쪽 접시에 놓고, 1g 추와 27g 추를 오른쪽 접시에 놓으면 \(25+3=1+27\)이므로 평형을 이룬다.

예제 입력 2

5

예제 출력 2

5 1 3 0 9

예제 설명 2

물건과 1g, 3g 추를 왼쪽 접시에 놓고, 9g 추를 오른쪽 접시에 놓으면 \(5+1+3=9\)이므로 평형을 이룬다.