CSES - Aalto Competitive Programming 2024 - wk5 - Wed - 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.

Constraints

  • 1 \leq n \leq 10^{18}

Example 1

Input:

10

Output:

4
MUL
ADD
MUL
END

Example 2

Input:

12

Output:

0