Вокруг круглого стола сидят \(n\) игроков, пронумерованных от \(1\) до \(n\). Игрок номер \((i+1)\) сидит справа от \(i\)-го игрока для всех \(1 \le i < n\), а \(1\)-й игрок сидит справа от \(n\)-го.
У них есть \(n^2\) карт, на каждой из которых написано одно целое число от \(1\) до \(n\). Для каждого числа от \(1\) до \(n\) есть ровно \(n\) с этим числом.
Изначально все карты некоторым образом распределены между игроками, причем у каждого ровно \(n\) карт. За один шаг каждый игрок выбирает одну из своих карт и передает ее игроку справа. Все игроки выполняют свой шаг одновременно.
Игрок \(i\) называется готовым, если на всех его картах написано число \(i\). Цель игроков — достичь конфигурации, где все игроки готовы. Найдите способ сделать это за не более чем \((n^2-n)\) шагов. Вам не нужно минимизировать число шагов.
Выходные данные
В первой строке выведите целое число \(k\) (\(0\le k\le (n^2-n)\)) — количество шагов в вашем решении.
Далее выведите \(k\) строк. В \(i\)-й из них выведите \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1\le d_j\le n\)), где \(d_j\) равно числу, написанному на карте, которую \(j\)-й игрок передает на \(i\)-м шаге игроку, сидящему справа от него.
Можно показать, что в данных ограничениях ответ всегда существует. Если существует несколько решений, выведите любое.
Примечание
В первом примере если первый игрок передает карту с числом \(2\), а второй игрок передает карту с числом \(1\), то у первого игрока будет две карты с числом \(1\), а у второго — две карты с числом \(2\). Значит после этого шага оба игрока готовы.
Во втором примере можно также сделать \(0\) шагов. Обратите внимание, что не нужно минимизировать число шагов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
1 2
|
1
2 1
|
|
2
|
3
1 1 1
2 2 2
3 3 3
|
6
1 2 3
3 1 2
2 3 1
1 2 3
3 1 2
2 3 1
|