Ví dụ:

Input

Output

Có 1 cân đĩa và các quả cân có khối lượng 1, 3, 3^2, 3^3, 3^4, 3^5, 3^6,... (Mỗi mức khối lượng chỉ có 1 quả)

Tìm cách cân vật có khối lượng n.

Input

• Số nguyên dương n (n ≤ ~10^{18}~).

Output

• Dòng đầu ghi ra các quả cân để bên đĩa không có vật cần cân;
• Dòng thứ hai ghi các quả cân để bên đĩa cùng với vật cần cân (nếu có)

Các số trên một dòng ghi theo thứ tự từ nhỏ đến lớn.

Ví dụ:

Input

11

Output

3 9
1

Giải thích:

11 + 1 = 3 + 9

Ví dụ 2:

Input

10

Output

1 9

Ví dụ:

Input

3

Output

4

Không tính các xâu giống nhau

Nguồn

Cho dãy a[1..n]

Đếm số đoạn con của a là dãy số nguyên liên tiếp.

1 ≤ a[i] ≤ n ≤ 10^5

Ví dụ 1:

input

3
1 2 3

Output:

6

Ví dụ 2:

input

3
2 2 1

Output:

4

Nguồn

Có 1 cân đĩa và các quả cân có khối lượng 1, 5, 5^2, 5^3, 5^4, 5^5, 5^6,... (Mỗi mức khối lượng có đúng 2 quả).

Tìm cách cân vật có khối lượng n.

Input

• Số nguyên dương n (n ≤ ~10^{18}~).

Output

• Dòng đầu ghi ra các quả cân để bên đĩa không có vật cần cân;
• Dòng thứ hai ghi các quả cân để bên đĩa cùng với vật cần cân (nếu có)

Các số trên một dòng ghi theo thứ tự từ nhỏ đến lớn.

Ví dụ:

Input

9

Output

5 5
1

Giải thích:

9+1 = 5 + 5

Ví dụ 2:

Input

11

Output

1 5 5

Nguồn