Background

cf链接

Description

给你一个正整数 $x$ 。请找出下列条件成立的任意整数数组 $a_0, a_1,...,a_{n-1}$：

• $1 \leq n \leq 32$
• $a_i$ $(0 \leq i \leq n-1)$ 等于 $1、0$ 或 $-1$
• $$x=\sum_{i=0}^{n-1}a_i*2^i$$

• 不存在一个索引 $0 \leq i \leq n-2$，同时存在 $a_i≠0$ 和 $a_{i+1} ≠0$ 的情况。

在问题的限制条件下，总是存在一个有效的数组。

Format

Input

一行包含一个正整数 $x(1 \leq x \leq 2^{30})$。

Output

每个测试用例输出两行。

第一行输出整数 $n(1 \leq n \leq 32)$ -数组 $a_0,a_1,...,a_{n-1}$ 的长度。

第二行，输出数组 $a_0,a_1,...,a_{n-1}$。

如果有多个有效数组，可以输出任意一个。

Samples

1

1
1

14

5
0 -1 0 0 1

Limitation

在第一个测试用例中，一个有效数组是 $[1]$，因为 $(1)*2^0=1$

在第二个测试用例中，一个可能的有效数组是 $[0,-1,0,0,1]$，因为 $(0)*2^0+(-1)*2^1+(0)*2^2+(0)*2^3+(1)*2^4=-2+16=14$