Сума — степінь двійки

Limits: 2 sec., 256 MiB

У Зеника і Марічки є послідовність із \(n\) натуральних чисел \(a_i\).

Марічці подобається, коли сума усіх чисел послідовності є степенем двійки.

Зеник може за один крок виконати одну із двох можливих операцій:

• Помножити довільне із чисел на 2.

• Поділити націло на 2 довільне із чисел, яке є більшим за 1.

Ваше завдання — допомогти Зенику знайти довільну послідовність із не більше ніж \(2 \cdot 10^5\) операцій, після виконання яких сума чисел послідовності стане степенем двійки.

Input

У першому рядку задано одне ціле число \(n\) — розмір послідовності.

У наступному рядку задано \(n\) цілих чисел \(a_i\) — початкова послідовність (\(1 \le i \le n\)).

Output

У першому рядку виведіть одне ціле невід’ємне число \(k\) — кількість операцій.

У наступних \(k\) рядках виведіть операції в тому порядку, в якому їх слід виконувати, у наступному форматі:

• M \(i\) — помножити \(i\)-те число на 2.

• D \(i\) — поділити націло на 2 \(i\)-те число. На момент виконання операції \(a_i\) повинно бути більше за 1.

Гарантовано, що відповідь існує для заданих обмежень. Якщо правильних відповідей декілька — виведіть будь-яку із них.

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

У першому прикладі достатньо поділити націло на 2 друге число, після цього послідовність стане [1, 1, 4, 2]. Сума чисел у ній рівна \(8 = 2^3\).

У другому прикладі сума вже є степенем двійки, отже можна не виконувати змін.