- 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 3MUL
: multiply X by 2END
: 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.
Constraints
- 1 \leq n \leq 10^{18}
Example 1
Input:
10
Output:
4 MUL ADD MUL END
Example 2
Input:
12
Output:
0