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

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$.

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