Sum is a Power of Two

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenik and Marichka have a sequence of \(n\) positive integers \(a_i\).

Marichka likes it when the sum of all numbers in the sequence is a power of two.

In one step, Zenik can perform one of the two possible operations:

• Multiply any of the numbers by 2.

• Integer divide by 2 any of the numbers that is strictly greater than 1.

Your task is to help Zenik find any sequence of at most \(2 \cdot 10^5\) operations after which the sum of the numbers in the sequence becomes a power of two.

Input

The first line contains a single integer \(n\) — the size of the sequence.

The next line contains \(n\) integers \(a_i\) — the initial sequence (\(1 \le i \le n\)).

Output

In the first line, output a single non-negative integer \(k\) — the number of operations.

In the next \(k\) lines, output the operations in the order they should be performed, in the following format:

• M \(i\) — multiply the \(i\)-th number by 2.

• D \(i\) — integer divide the \(i\)-th number by 2. At the moment of the operation, \(a_i\) must be strictly greater than 1.

It is guaranteed that an answer exists for the given constraints. If there are multiple correct answers, output any of them.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

\(0 \le k \le 2 \cdot 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 3 4 2	1 D 2

Input (stdin) сopy	Output (stdout) сopy
1 8	0

Input (stdin) сopy	Output (stdout) сopy
3 7 47 4	4 D 1 D 1 M 3 M 3

Notes

In the first example, it is enough to integer divide the second number by 2, after which the sequence becomes [1, 1, 4, 2]. The sum of the numbers in it is equal to \(8 = 2^3\).

In the second example, the sum is already a power of two, so no changes are needed.