Có rất nhiều cách để phân tích một số nguyên dương thành tổng của các số là luỹ thừa của ~3~.

Ví dụ: Phân tích ~13~:

• ~13 = 9 + 3 + 1~
• ~13 = 3 + 3 + 3 + 3 + 1~
• ~13 = 3 + 3 + 3 + 1 + 1 + 1 + 1~
• ~...~

Yêu cầu

Cho số nguyên dương ~n~. Tìm ra dãy ngắn nhất có tổng bằng ~n~ chỉ chứa các số là luỹ thừa của 3.

Input

Một dòng duy nhất chứa một số nguyên dương ~n~ ~(1≤n≤10^{18})~.

Output

Gồm 1 dòng duy nhất chứa dãy số thoả mãn yêu cầu đề bài theo thứ tự giảm dần.

Sample Input

2

Sample Output

1 1

Sample Input 2

13

Sample Output 2

9 3 1

Sample Input 3

25

Sample Output 3

9 9 3 3 1