**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}