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

Обмеження: 2 сек., 256 МіБ

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

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

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

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

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

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

Обмеження

$1 \le n \le 10^5$,

$1 \le a_i \le 10^9$.

$0 \le k \le 2 \cdot 10^5$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 3 4 2	1 D 2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 8	0

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 7 47 4	4 D 1 D 1 M 3 M 3

Примітки

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

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