У Нины есть матрица \(a\) размера \(n\times n\), заполненная нулями. \(j\)-й элемент \(i\)-й строки матрицы \(a\) обозначается как \(a_{i, j}\).
Она может выполнять операции двух типов с этой матрицей:
- Операция типа \(1\): выбрать целое число \(i\) от \(1\) до \(n\) и перестановку \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\). Присвоить \(a_{i, j}:=p_j\) для всех \(1 \le j \le n\) одновременно.
- Операция типа \(2\): выбрать целое число \(i\) от \(1\) до \(n\) и перестановку \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\). Присвоить \(a_{j, i}:=p_j\) для всех \(1 \le j \le n\) одновременно.
Нина хочет максимизировать сумму всех чисел в матрице \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}\). Она просит вас найти способ выполнить операции так, чтобы эта сумма была максимальной. Поскольку она не хочет выполнять слишком много операций, вы должны предоставить решение с не более чем \(2n\) операциями.
Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных на первой строке выведите два целых числа \(s\) и \(m\) (\(0\leq m\leq 2n\)) — максимальную сумму чисел в матрице и количество операций в вашем решении.
В \(k\)-й из следующих \(m\) строк выведите описание \(k\)-й операции:
- целое число \(c\) (\(c \in \{1, 2\}\)) — тип \(k\)-й операции;
- целое число \(i\) (\(1 \le i \le n\)) — строка или столбец, к которому применяется \(k\)-я операция;
- перестановка \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\) — перестановка, используемая в \(k\)-й операции.
Обратите внимание, что вам не нужно минимизировать количество использованных операций, вам просто нужно использовать не более чем \(2n\) операций. Можно показать, что максимальная возможная сумма всегда может быть получена не более чем за \(2n\) операций.
Примечание
В первом наборе входных данных максимальная сумма \(s=1\) может быть получена за \(1\) операцию присвоением \(a_{1, 1}:=1\).
Во втором наборе входных данных максимальная сумма \(s=7\) может быть получена за \(3\) операции следующим образом:
Можно показать, что невозможно сделать сумму чисел в матрице большей \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
2
|
1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2
|