Calculator

Time limit1sMemory limit256 MB

Summary

Starting from X=0, reach a given N by pressing +2, -2, *2, /2 (floor) at most 99 times while X stays in [0, 2^63-1], or report that it is impossible.

Level: Hard9 of 10
Topics: Binary search, Math, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Seungju is building a calculator for a homework assignment.

The calculator is unfinished, so it does not have many features.

The calculator holds a single integer X and has 4 buttons in total. The buttons work as follows.

[+] : adds 2 to X.
[-] : subtracts 2 from X.
[*] : multiplies X by 2.
[/] : divides X by 2, discarding the remainder.

If pressing a button makes X negative or greater than $2^{63}-1$ , the calculator explodes.

Seungju wants to test whether the calculator works properly.

Starting from X = 0, given an integer N, press the buttons so that X becomes N without making the calculator explode.

Input

The first line gives an integer N (1 ≤ N ≤ $10^{13}$ ).

Output

On the first line, print the number of button presses K (0 ≤ K ≤ 99). The number of presses does not have to be minimal, but it must not exceed 99.

If no way exists to reach N within 99 presses, print only "-1" on the first line and nothing else.

On the second line, print the buttons in the order they are pressed, separated by spaces. Each button must be one of "[+]", "[-]", "[*]", "[/]". How each button works is described in the statement.

If several ways exist, print any one of them.

Hint

Note that X can exceed the range of a 32-bit integer during the calculation.

In C/C++, using the long long type is recommended, and in Java, the long type.

Examples2

Example 1
Input
```
14
```
Expected output
```
5
[+] [*] [*] [*] [-]
```
Example 2
Input
```
1
```
Expected output
```
4
[+] [*] [-] [/]
```