В исследовательских целях, \(n^2\) лабораторий были построены на горе на различных высотах. Давайте пронумеруем их целыми числами от \(1\) до \(n^2\), так что лаборатория с номером \(1\) находится в самом низком месте, лаборатория с номером \(2\) находится во втором по высоте месте, \(\ldots\), лаборатория с номером \(n^2\) находится в самом высоком месте.
Для транспортировки воды между лабораториями, трубы были построены между всеми парами лабораторий. Труба может переместить не больше одной единицы воды в единицу времени из лаборатории с номером \(u\) в лабораторию с номером \(v\), если \(u > v\).
Сейчас необходимо разбить лаборатории на \(n\) групп, каждая группа должна содержать ровно \(n\) лабораторий. Лаборатории из разных групп могут транспортировать воду друг другу. Тогда суммарное количество воды, которое может быть отправлено из группы \(A\) в группу \(B\) равно количеству пар лабораторий (\(u, v\)), таких что лаборатория с номером \(u\) из группы \(A\), лаборатория с номером \(v\) из группы \(B\) и \(u > v\). Давайте обозначим это число за \(f(A,B)\) (то есть \(f(A,B)\) равно суммарному количеству воды, которое может быть отправлено из группы \(A\) в группу \(B\)).
Например, если \(n=3\) и есть \(3\) группы \(X\), \(Y\) и \(Z\): \(X = \{1, 5, 6\}, Y = \{2, 4, 9\}\) и \(Z = \{3, 7, 8\}\). В этом случае значения \(f\) равны:
- \(f(X,Y)=4\) потому что \(5 \rightarrow 2\), \(5 \rightarrow 4\), \(6 \rightarrow 2\), \(6 \rightarrow 4\),
- \(f(X,Z)=2\) потому что \(5 \rightarrow 3\), \(6 \rightarrow 3\),
- \(f(Y,X)=5\) потому что \(2 \rightarrow 1\), \(4 \rightarrow 1\), \(9 \rightarrow 1\), \(9 \rightarrow 5\), \(9 \rightarrow 6\),
- \(f(Y,Z)=4\) потому что \(4 \rightarrow 3\), \(9 \rightarrow 3\), \(9 \rightarrow 7\), \(9 \rightarrow 8\),
- \(f(Z,X)=7\) потому что \(3 \rightarrow 1\), \(7 \rightarrow 1\), \(7 \rightarrow 5\), \(7 \rightarrow 6\), \(8 \rightarrow 1\), \(8 \rightarrow 5\), \(8 \rightarrow 6\),
- \(f(Z,Y)=5\) потому что \(3 \rightarrow 2\), \(7 \rightarrow 2\), \(7 \rightarrow 4\), \(8 \rightarrow 2\), \(8 \rightarrow 4\).
Пожалуйста, разбейте лаборатории на \(n\) групп размера \(n\), так что значение \(\min f(A,B)\) по всем возможным парам групп \(A\) и \(B\) (\(A \neq B\)) было максимально.
Другими словами, разбейте лаборатории на \(n\) групп размера \(n\), таких что минимальное количество воды, которое может быть отправлено из группы \(A\) в группу \(B\) для всех возможных пар групп \(A\) и \(B\) (\(A \neq B\)) было максимально большое.
Обратите внимание, что приведенный в условии пример не демонстрирует оптимальное разбиение на группы, он демонстрирует подсчет значений \(f\) для некоторого разбиения.
Если существует несколько оптимальных разбиений, вы можете найти любое.
Выходные данные
Выведите \(n\) строк:
В \(i\)-й строке выведите \(n\) чисел, которые являются номерами лабораторий, которые составляют \(i\)-ю группу, в любом порядке.
Если существует несколько возможных ответов, максимизирующих минимальное количество воды, которое может быть отправлено из одной группы в другую, разрешается вывести любой.
Примечание
В первом тесте можно разбить \(9\) лабораторий на группы \(\{2, 8, 5\}, \{9, 3, 4\}, \{7, 6, 1\}\).
Из первой группы во вторую можно отправить \(4\) единицы воды (\(8 \rightarrow 3, 8 \rightarrow 4, 5 \rightarrow 3, 5 \rightarrow 4\)).
Из первой группы в третью можно отправить \(5\) единиц воды (\(2 \rightarrow 1, 8 \rightarrow 7, 8 \rightarrow 6, 8 \rightarrow 1, 5 \rightarrow 1\)).
Из второй группы в первую можно отправить \(5\) единиц воды (\(9 \rightarrow 2, 9 \rightarrow 8, 9 \rightarrow 5, 3 \rightarrow 2, 4 \rightarrow 2\)).
Из второй группы в третью можно отправить \(5\) единиц воды (\(9 \rightarrow 7, 9 \rightarrow 6, 9 \rightarrow 1, 3 \rightarrow 1, 4 \rightarrow 1\)).
Из третьей группы в первую можно отправить \(4\) единицы воды (\(7 \rightarrow 2, 7 \rightarrow 5, 6 \rightarrow 2, 6 \rightarrow 5\)).
Из третьей группы во вторую можно отправить \(4\) единицы воды (\(7 \rightarrow 3, 7 \rightarrow 4, 6 \rightarrow 3, 6 \rightarrow 4\)).
Минимальное количество воды, которое можно отправить из какой-то группы в другую равно \(4\). Можно доказать, что при любом другом разбиении на группы нельзя добиться ответа лучше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
2 8 5
9 3 4
7 6 1
|