Масив і часткові суми

Масивом префіксних сум масиву цілих чисел $a$ довжини $n$ називається такий масив $b$ довжини $n$, що $b_i=a_1+a_2+\dots +a_i$.

Масивом суфіксних сум масиву цілих чисел $a$ довжини $n$ називається такий масив $b$ довжини $n$, що $b_i=a_n+a_{n-1}+\dots +a_i$.

Назвемо нормалізацією масиву цілих чисел $a$ довжини $n$ виконання операції присвоєння $a_i\leftarrow \max (\min (a_i,10^{18}),-10^{18})$ для $1\le i\le n$.

Задано масив цілих чисел $a$ довжини $n$.

Дозволяється виконувати операції трьох типів:

1. замінити кожен елемент масиву $a$ на протилежний (виконати операцію присвоєння $a_i\leftarrow (-a_i)$ для $1\le i\le n$);

2. вибрати довільний підвідрізок масиву $a$ та замінити його на масив його префіксних сум, після чого нормалізувати масив $a$;

3. вибрати довільний підвідрізок масиву $a$ та замінити його на масив його суфіксних сум, після чого нормалізувати масив $a$.

Знайдіть найкоротшу послідовність операцій, необхідних для того, щоб усі елементи масиву $a$ стали невід'ємними.

Зверніть увагу, що для деяких блоків тестів дозволяється знайти послідовність операцій, що не є найкоротшою з можливих.

Вхідні дані

У першому рядку задано два цілі числа $n$, $g$ ($1\le n\le 2\cdot 10^5$, $0\le g\le 8$) — довжина масиву та номер блоку тестів відповідно.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($-1\le a_i\le 1$) — елементи масиву.

Вихідні дані

У першому рядку виведіть одне ціле число $m$ — мінімальну кількість операцій, необхідних для того, щоб усі елементи масиву $a$ стали невід'ємними.

У наступних $m$ рядках виведіть опис операцій. Описи операцій першого типу виводіть у форматі «1». Описи операцій другого та третього типів виводіть у форматах «2 l r» та «3 l r» відповідно, де $l$ та $r$ ($1\le l\le r\le n$) позначають ліву та праву межі підвідрізка чергової операції.

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

Приклади

Примітка

У першому прикладі масив $a$ змінюється двічі:

1. після виконання операції третього типу з параметрами $l=1$, $r=3$ масив $a$ стає рівним $[1,1,1,-1,-1,-1,1]$;

2. після виконання операції другого типу з параметрами $l=1$, $r=7$ масив $a$ стає рівним $[1,2,3,2,1,0,1]$.

Оцінювання

Нехай для певного тесту мінімальна кількість операцій, необхідних для того, щоб усі елементи масиву $a$ стали невід'ємними, рівна $m_{ans}$, а ваше рішення використовує $m_{user}$ операцій.

1. ($14$ балів): $m_{ans}\le 1$;

2. ($17$ балів): ваш розв'язок вважатиметься правильним, якщо $m_{user}\le 100$. Можна довести, що завжди існує послідовність не більше ніж з $100$ операцій при заданих обмеженнях;

3. ($18$ балів): ваш розв'язок вважатиметься правильним, якщо $m_{user}\le m_{ans}+3$;

4. ($7$ балів): ваш розв'язок вважатиметься правильним, якщо $m_{user}\le m_{ans}+1$;

5. ($7$ балів): $n\le 3000$; гарантується, що усі найкоротші послідовності операцій містять лише операції другого типу;

6. ($19$ балів): гарантується, що усі найкоротші послідовності операцій містять лише операції другого типу;

7. ($17$ балів): $n\le 3000$;

8. ($1$ бал): без додаткових обмежень.