Торгуя на своей любимой бирже, трейдер Василий вдруг понял, что нашел в ней уязвимость. С помощью этой уязвимости он может менять некоторые значения служебных переменных в свою пользу. Чтобы навести суеты, он решил поменять все значения служебных переменных \(a_1, a_2, \ldots, a_n\) на \(-a_1, -a_2, \ldots, -a_n\). По непонятной причине, количество служебных переменных — всегда четное число.
Василий понимает, что каждым своим действием он будет привлекать все больше внимания службы безопасности, поэтому количество его действий не должно превышать \(5\,000\), а также после каждой операции ни одна из переменных по модулю не должна превышать \(10^{18}\). Василий может совершать два типа действий для двух выбранных переменных с индексами \(i\) и \(j\), где \(i < j\):
- Выполнить присваивание \(a_i = a_i + a_j\)
- Выполнить присваивание \(a_j = a_j - a_i\)
Василий просит вас разработать стратегию, приводящую все служебные переменные к требуемым значениям.
Выходные данные
Для каждого набора входных данных выведите ответ в следующем формате:
Первая строка вывода должна содержать количество действий \(k\), которое совершит стратегия. Обратите внимание, что вам не требуется минимизировать \(k\). Должно выполняться неравенство \(k \le 5\,000\).
Следующие \(k\) строк должны содержать действия в формате «type i j», где «type» равен «1», если стратегии нужно выполнить присваивание первого типа, и «2» — если стратегии нужно выполнить присваивание второго типа. Обратите внимание, что должно выполняться \(i < j\).
Можно показать, что ответ всегда существует.
Примечание
В первом тестовом примере одной из возможных последовательностей операций может быть следующая:
- «2 1 2». Значения переменных после применения операции: [1, 0, 1, 1]
- «2 1 2». Значения переменных после применения операции: [1, -1, 1, 1]
- «2 1 3». Значения переменных после применения операции: [1, -1, 0, 1]
- «2 1 3». Значения переменных после применения операции: [1, -1, -1, 1]
- «2 1 4». Значения переменных после применения операции: [1, -1, -1, 0]
- «2 1 4». Значения переменных после применения операции: [1, -1, -1, -1]
- «1 1 2». Значения переменных после применения операции: [0, -1, -1, -1]
- «1 1 2». Значения переменных после применения операции: [-1, -1, -1, -1]
Во втором тестовом примере одной из возможных последовательностей операций может быть следующая:
- «2 1 4». Значения переменных после применения операции: [4, 3, 1, -2]
- «1 2 4». Значения переменных после применения операции: [4, 1, 1, -2]
- «1 2 4». Значения переменных после применения операции: [4, -1, 1, -2]
- «1 2 4». Значения переменных после применения операции: [4, -3, 1, -2]
- «1 3 4». Значения переменных после применения операции: [4, -3, -1, -2]
- «1 1 2». Значения переменных после применения операции: [1, -3, -1, -2]
- «1 1 2». Значения переменных после применения операции: [-2, -3, -1, -2]
- «1 1 4». Значения переменных после применения операции: [-4, -3, -1, -2]
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
1 1 1 1
4
4 3 1 2
|
8
2 1 2
2 1 2
2 1 3
2 1 3
2 1 4
2 1 4
1 1 2
1 1 2
8
2 1 4
1 2 4
1 2 4
1 2 4
1 3 4
1 1 2
1 1 2
1 1 4
|