C. Произведение массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. С ним могут производиться следующие операции:

  1. Выбрать позиции $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n, i \ne j$$$), записать произведение $$$a_i \cdot a_j$$$ в ячейку $$$j$$$ и удалить число из позиции $$$i$$$;
  2. Выбрать позицию $$$i$$$ и удалить число из позиции $$$i$$$ (провести такую операцию можно не более одного раза в любой момент времени, не обязательно в самом начале).

После каждой операции в массиве становится ровно на одно число меньше. При этом нумерация элементов сохраняется, но удалённые числа нельзя использовать в последующих операциях.

Ваша задача — произвести $$$n - 1$$$ операцию с этим массивом таким образом, чтобы единственное число, которое останется в этом массиве, было максимально возможным. Так как это число может быть достаточно большим, вместо вывода этого числа вам необходимо вывести любую последовательность действий, приводящую к максимально возможному числу. Прочитайте формат вывода для точного понимания того, что именно нужно выводить.

Входные данные

В первой строке входных данных следует одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве.

Во второй строке входных данных следует $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива.

Выходные данные

Выведите $$$n - 1$$$ строку. В $$$k$$$-й строке должна содержаться одна из двух описанных операций.

Операция первого типа должна выглядеть следующим образом: $$$1~ i_k~ j_k$$$, где $$$1$$$ — тип операции, $$$i_k$$$ и $$$j_k$$$ — индексы выбранных элементов.

Операция второго типа должна выглядеть следующим образом: $$$2~ i_k$$$, где $$$2$$$ — тип операции, $$$i_k$$$ — индекс выбранного элемента. Обратите внимание, что таких операций должно быть не более одной.

Если существует несколько различных последовательностей операций, приводящих к максимальному остающемуся числу, выведите любую из них.

Примеры
Входные данные
5
5 -2 0 1 -3
Выходные данные
2 3
1 1 2
1 2 4
1 4 5
Входные данные
5
5 2 0 4 0
Выходные данные
1 3 5
2 5
1 1 2
1 2 4
Входные данные
2
2 -1
Выходные данные
2 2
Входные данные
4
0 -10 0 0
Выходные данные
1 1 2
1 2 3
1 3 4
Входные данные
4
0 0 0 0
Выходные данные
1 1 2
1 2 3
1 3 4
Примечание

Будем обозначать за X удаленное число в массиве. Рассмотрим все тестовые примеры:

В первом тестовом примере последовательность преобразований массива может выглядеть как: $$$[5, -2, 0, 1, -3] \to [5, -2, X, 1, -3] \to [X, -10, X, 1, -3] \to$$$ $$$[X, X, X, -10, -3] \to [X, X, X, X, 30]$$$. Таким образом, максимально возможный ответ равен $$$30$$$. Обратите внимание, что другие последовательности, приводящие к ответу $$$30$$$, также допустимы.

Во втором тестовом примере последовательность преобразований массива может выглядеть как: $$$[5, 2, 0, 4, 0] \to [5, 2, X, 4, 0] \to [5, 2, X, 4, X] \to [X, 10, X, 4, X] \to$$$ $$$[X, X, X, 40, X]$$$. Также допустима, например, следующая последовательность: 


1 5 3
1 4 2
1 2 1
2 3

Тогда последовательность преобразований массива будет выглядеть как: $$$[5, 2, 0, 4, 0] \to [5, 2, 0, 4, X] \to [5, 8, 0, X, X] \to [40, X, 0, X, X] \to$$$ $$$[40, X, X, X, X]$$$.

В третьем тестовом примере последовательность преобразований массива может выглядеть как: $$$[2, -1] \to [2, X]$$$.

В четвертом тестовом примере последовательность преобразований массива может выглядеть как: $$$[0, -10, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$.

В пятом тестовом примере последовательность преобразований массива может выглядеть как: $$$[0, 0, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$.