CSES - Datatähti Open 2017 - Program
  • Time limit: 0.50 s
  • Memory limit: 512 MB
Uolevi has developed a new programming language, that only contains one variable $X$. Initially, the value of $X$ is $1$. In addition, there are three commands:
  • ADD: increase $X$ by 3
  • MUL: multiply $X$ by 2
  • END: print $X$ and stop the program
Your task is to find the shortest program that prints a given number $n$, or state that no such program exists.

Input

The only input line contains an integer $n$.

Output

If a program exists, you should first output the number of commands in it, and after that, each command in a separate line. If there are several possible programs, you can output any of them.

If a program doesn't exist, you should only print $0$.

Example 1

Input:
10

Output:
4
MUL
ADD
MUL
END


Example 2

Input:
12

Output:
0

Subtask 1 (21 points)
  • $1 \le n \le 100$
Subtask 2 (37 points)
  • $1 \le n \le 10^6$
Subtask 3 (42 points)
  • $1 \le n \le 10^{18}$