Коала Коа имеет матрицу \(A\) из \(n\) строк и \(m\) столбцов. Элементы этой матрицы — различные целые числа от \(1\) до \(n \cdot m\) (каждое число от \(1\) до \(n \cdot m\) встречается в матрице ровно один раз).
Для любой матрицы \(M\) из \(n\) строк и \(m\) столбцов определим следующее:
- \(i\)-я строка \(M\) определяется как \(R_i(M) = [ M_{i1}, M_{i2}, \ldots, M_{im} ]\) для всех \(i\) (\(1 \le i \le n\)).
- \(j\)-й столбец \(M\) определяется как \(C_j(M) = [ M_{1j}, M_{2j}, \ldots, M_{nj} ]\) для всех \(j\) (\(1 \le j \le m\)).
Коа определяет \(S(A) = (X, Y)\) как спектр \(A\), где \(X\) — множество максимумов в строках \(A\), а \(Y\) — множество максимумов в столбцах \(A\) соответственно.
Более формально:
- \(X = \{ \max(R_1(A)), \max(R_2(A)), \ldots, \max(R_n(A)) \}\)
- \(Y = \{ \max(C_1(A)), \max(C_2(A)), \ldots, \max(C_m(A)) \}\)
Коа просит вас найти некоторую матрицу \(A'\) из \(n\) строк и \(m\) столбцов такую, чтобы каждое число от \(1\) до \(n \cdot m\) встречалось в матрице ровно один раз, и выполнялись следующие условия:
- \(S(A') = S(A)\)
- \(R_i(A')\) является битоническим для всех \(i\) (\(1 \le i \le n\))
- \(C_j(A')\) является битоническим для всех \(j\) (\(1 \le j \le m\)).
Массив
\(t\) (
\(t_1, t_2, \ldots, t_k\)) называется битоническим, если он сначала возрастает, а затем спадает.
Более формально: \(t\) является битоническим, если существует некоторая позиция \(p\) (\(1 \le p \le k\)) такая, что: \(t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k\).
Помогите Коа найти такую матрицу, или определить, что ее не существует.
Выходные данные
Если такой матрицы не существует, в отдельной строке выведите \(-1\).
В противном случае вы должны вывести \(n\) строк, каждая из которых должная состоять из \(m\) целых чисел, разделенных пробелом — описание \(A'\).
\(j\)-е число в \(i\)-й строке обозначает элемент \(A'_{ij}\).
Каждое число от \(1\) до \(n \cdot m\) должно встречаться в \(A'\) ровно один раз, каждая строка и столбец в \(A'\) должны быть битоническими и должно выполняться \(S(A) = S(A')\).
Если ответов несколько, выведите любой.