Cân đĩa là một dụng cụ để cân khối lượng của một vật. Cân gồm \(2\) đĩa đặt cố định ở \(2\) đầu đòn cân, đĩa bên trái chứa vật cần cân, đĩa bên phải chứa các quả cân đối ứng. Khi cân đạt trạng thái cân bằng, khối lượng của vật chính là tổng khối lượng của các quả cân đối ứng. Thông thường, bộ quả cân gồm \(5\) quả với khối lượng lần lượt là \(1, 2, 2, 5\) và \(10\). Tuy nhiên, cư dân ở xứ sở OnlyThree lại dùng đúng \(K+1\) quả cân với khối lượng lần lượt là \(1, 3, 9, …, 3^K\). Khi đó, để xác định khối lượng một vật, các quả cân có thể được đặt lên cả \(2\) đĩa cân. Lúc này, khối lượng của vật được tính bằng tổng các quả cân ở đĩa bên phải trừ tổng các quả cân ở đĩa bên trái.

Ví dụ: khối lượng vật là \(6\) thì trong đĩa bên trái cần thêm thêm quả cân khối lượng \(3\) và đĩa bên phải đặt quả cân khối lượng \(9\) thì cân sẽ đạt trạng thái cân bằng.

Yêu cầu

Với vật có khối lượng \(M\), hãy xác định các quả cân được thêm vào cùng vật cần cân ở đĩa bên trái và các quả cân đặt ở đĩa bên phải để cân đạt trạng thái cân bằng.

Dữ liệu.

Vào từ thiết bị nhập chuẩn số nguyên dương \(M\) (\(M\) có thể rất lớn và không có những chữ số \(0\) ở đầu).

Kết quả

Đưa ra thiết bị xuất chuẩn \(2\) dòng:

• Dòng thứ nhất ghi các số \(s_1, s_2, ...\) \((0 ≤ s_1 < s_2 < …)\) thể hiện các quả cân có khối lượng \(3^{s_1}, 3^{s_2}, ...\) được đặt thêm vào đĩa bên trái cùng với vật cần cân hoặc ghi \(-1\) khi không cần thêm.
• Dòng thứ hai ghi các số \(a_1, a_2, ...\) \((0 ≤ a_1 < a_2 < ...)\) thể hiện các quả cân có khối lượng \(3^{a_1}, 3^{a_2}, ...\) được đặt vào đĩa bên phải.

Ví dụ

Đầu vào

6

Kết quả

1
2

Dữ liệu:

30

Kết quả:

-1
1 3

Subtask

\(30\%\) số test có \(1 \le n \le 100\).

\(30\%\) số test có \(1 \le n \le 10^{18}\).

\(40\%\) số test có \(1 \le n \le 10^{10^5}\).