Phản vật chất antimatter là một khái niệm hấp dẫn trong vật lý và khoa học viễn tưởng. Các nhà tin học tưởng tượng về một thế giới máy tính hoạt động với hệ cơ số âm, cụ thể là cơ số ~-2~.

Trong hệ cơ số ~-2~, một số nguyên ~x~ được biểu diễn dưới dạng: ~x = \sum_{i=0}^{n-1} a_i \cdot (-2)^i~, trong đó mỗi ~a_i~ là ~0~ hoặc ~1~, và bit cao nhất thỏa ~a_{n-1} \ne 0~.

Ví dụ: ~3 = 111_{-2}~.

Yêu cầu

Cho số nguyên ~x~, hãy xác định:

• ~n~ — độ dài nhỏ nhất của dãy bit biểu diễn ~x~ trong cơ số ~-2~,
• và chính dãy bit ~a_0, a_1, \dots, a_{n-1}~ (theo thứ tự từ bit thấp đến bit cao).

Dữ liệu

Một dòng chứa số nguyên ~x~ với ~-10^{18} \le x \le 10^{18}~.

Kết quả

• Dòng 1: in ra số nguyên ~n~.
• Dòng 2: in ra ~n~ số nguyên ~a_0, a_1, \dots, a_{n-1}~ — các bit của biểu diễn ~x~ trong cơ số ~-2~.

Ví dụ

Ví dụ 1

Input

3

Output

3
1 1 1

Giải thích

Ví dụ 1

Ta có: ~1\cdot(-2)^0 + 1\cdot(-2)^1 + 1\cdot(-2)^2 = 1 - 2 + 4 = 3~, nên ~3 = 111_{-2}~, và dãy bit in theo thứ tự ~a_0, a_1, a_2~ là ~1\ 1\ 1~.

Ràng buộc và chấm điểm

Ràng buộc

~-10^{18} \le x \le 10^{18}~.