Вам задана квадратная матрица, состоящая из n строк и n столбцов. Будем считать, что строки пронумерованы целыми числами от 1 до n сверху вниз, а столбцы пронумерованы целыми числами от 1 до n слева направо. Некоторые клетки матрицы (всего n - 1 клеток) содержат единицы, остальные клетки — нули. Разрешается производить над матрицей следующие операции:
- Обменять местами i-ую и j-ую строки матрицы;
- Обменять местами i-ый и j-ый столбцы матрицы.
Требуется при помощи данных операций привести матрицу к такому виду, чтобы все единицы стояли в клетках, лежащих ниже главной диагонали. Клетка матрицы, находящаяся на пересечении i-ой строки и j-ого столбца, лежит ниже главной диагонали, если i > j.
Выходные данные
Выведите описание действий, которые нужно произвести, чтобы получить матрицу с единицами ниже главной диагонали, в следующем формате.
В первой строке нужно вывести целое неотрицательное число m (m ≤ 105) — количество необходимых действий. Далее в каждой из следующих m строк выведите через пробел три целых числа t, i, j (1 ≤ t ≤ 2, 1 ≤ i, j ≤ n, i ≠ j), где t = 1, если нужно произвести обмен строк, t = 2, если нужно произвести обмен столбцов, а i и j обозначают, соответственно, номера строк или столбцов.
Обратите внимание, что минимизировать количество операций не требуется, однако их число не должно превышать 105. Если существует несколько решений, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
2
2 1 2
1 1 2
|
|
2
|
3
3 1
1 3
|
3
2 2 3
1 1 3
1 1 2
|
|
3
|
3
2 1
3 2
|
0
|