Problem Description

Express the positive integer $ N $ as a sum or difference of distinct powers of $ 3 $.

Formally, construct a sequence $ A $ that satisfies all the following conditions:

• Let the length of $ A $ be $ M $, then $1 \leq M \leq 100$
• $\sum_{i=1}^{M} A_i = N$
• $|A_i| \leq 10^{18}$
• For each $ i $ ( $1 \leq i \leq M$ ), $ |A_i| $ is a power of $ 3 $. That is, it can be expressed as $ |A_i| = 3^x $ for some non-negative integer $ x $.
• $|A_i| \neq |A_j|$ ( $i \neq j$ )

Under the constraints of this problem, the existence of such a sequence $ A $ is guaranteed.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the sequence $ A $ that satisfies the conditions in the problem in the following format. Here, $ M $ represents the length of $ A $.

$ M $ $ A_1 $ $ A_2 $ $\ldots$ $ A_M $

If there are multiple sequences $ A $ that satisfy the conditions, you may output any one of them.

Sample Input and Output

Sample Input #1

6

Sample Output #1

2
9 -3

Sample Input #2

9193

Sample Output #2

9
2187 27 1 -243 3 9 -81 6561 729

Sample Input #3

10120190919012

Sample Output #3

16
-1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609

Notes/Hints

Constraints

• $1 \leq N \leq 10^{15}$
• $ N $ is an integer

Sample Explanation 1

Both $ 9 $ and $ 3 $ are powers of $ 3 $, and $ 9 + (-3) = 6 $, so this output satisfies the conditions in the problem.

Sample Explanation 3

The input may exceed the range of a 32-bit integer type.

见题面 Input 部分

见题面 Output 部分