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

Обмеження: 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\).

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