Về bản chất, hệ cơ số liên quan đến việc biểu diễn một số nguyên dưới dạng tổng các lũy thừa. Hệ số thông dụng và được sử dụng phổ biến hiện nay là hệ thập phân. Ví dụ, số \(1432\) được viết dưới dạng \(1432 = 2 \cdot 10^0 + 3 \cdot 10^1 + 4 \cdot 10^2 + 1 \cdot 10^3\).

Cho trước số nguyên dương \(X\). Bạn cần chỉ ra một dãy số nguyên \(a_1, a_2, \ldots, a_n\) độ dài \(n\) thỏa mãn toàn bộ các điều kiện:

• \(n \leq 20\)
• \(a_i \geq 0\)
• \(3^{a_1} + 3^{a_2} + \cdots + 3^{a_n} = X\)

Input

• Dòng duy nhất chứa số \(X\) (\(1 \leq X \leq 10^5\)).
• Dữ liệu vào đảm bảo luôn tồn tại dãy số nguyên \(a\) hợp lệ.

Output

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\).
• Bạn được điểm nếu \(n\) và dãy \(a\) thỏa mãn các điều kiện, dù có in ra bất kỳ giá trị nào.

Example

13

5
1 1 0 1 1

Scoring

• Subtask 1 (\(20\%\) số điểm): \(X \leq 20\).
• Subtask 2 (\(20\%\) số điểm): tồn tại số nguyên \(a, b \leq 10\) sao cho \(X = 3^a + b\).
• Subtask 3 (\(30\%\) số điểm): tồn tại đáp án với \(n \leq 10\) và \(a_i \leq 4\).
• Subtask 4 (\(30\%\) số điểm): không có ràng buộc gì thêm.