Задан массив \(a\), состоящий из \(n\) целых чисел. С ним могут производиться следующие операции:
- Выбрать позиции \(i\) и \(j\) (\(1 \le i, j \le n, i \ne j\)), записать произведение \(a_i \cdot a_j\) в ячейку \(j\) и удалить число из позиции \(i\);
- Выбрать позицию \(i\) и удалить число из позиции \(i\) (провести такую операцию можно не более одного раза в любой момент времени, не обязательно в самом начале).
После каждой операции в массиве становится ровно на одно число меньше. При этом нумерация элементов сохраняется, но удалённые числа нельзя использовать в последующих операциях.
Ваша задача — произвести \(n - 1\) операцию с этим массивом таким образом, чтобы единственное число, которое останется в этом массиве, было максимально возможным. Так как это число может быть достаточно большим, вместо вывода этого числа вам необходимо вывести любую последовательность действий, приводящую к максимально возможному числу. Прочитайте формат вывода для точного понимания того, что именно нужно выводить.
Выходные данные
Выведите \(n - 1\) строку. В \(k\)-й строке должна содержаться одна из двух описанных операций.
Операция первого типа должна выглядеть следующим образом: \(1~ i_k~ j_k\), где \(1\) — тип операции, \(i_k\) и \(j_k\) — индексы выбранных элементов.
Операция второго типа должна выглядеть следующим образом: \(2~ i_k\), где \(2\) — тип операции, \(i_k\) — индекс выбранного элемента. Обратите внимание, что таких операций должно быть не более одной.
Если существует несколько различных последовательностей операций, приводящих к максимальному остающемуся числу, выведите любую из них.
Примечание
Будем обозначать за 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]\).