Пусть \(a\) — матрица размера \(r \times c\), в каждой ячейке которой записано положительное целое число (эти числа не обязательно различны). Строки матрицы пронумерованы от \(1\) до \(r\), а столбцы — от \(1\) до \(c\). Мы можем построить массив \(b\), состоящий из \(r + c\) целых чисел, следующим образом: для каждого \(i \in [1, r]\) обозначим за \(b_i\) наибольший общий делитель всех чисел в \(i\)-й строке, а для каждого \(j \in [1, c]\) обозначим за \(b_{r+j}\) наибольший общий делитель всех чисел в \(j\)-м столбце.
Назовем матрицу разнообразной, если все \(r + c\) чисел \(b_k\) (\(k \in [1, r + c]\)) попарно различны.
Назовем модулем матрицы максимальное число среди \(b_k\).
Например, рассмотрим следующую матрицу:
\(\begin{pmatrix} 2 & 9 & 7\\ 4 & 144 & 84 \end{pmatrix}\) Построим массив \(b\):
- \(b_1\) — наибольший общий делитель \(2\), \(9\) и \(7\), он равен \(1\);
- \(b_2\) — наибольший общий делитель \(4\), \(144\) и \(84\), он равен \(4\);
- \(b_3\) — наибольший общий делитель \(2\) и \(4\), он равен \(2\);
- \(b_4\) — наибольший общий делитель \(9\) и \(144\), он равен \(9\);
- \(b_5\) — наибольший общий делитель \(7\) и \(84\), он равен \(7\).
Итак, \(b = [1, 4, 2, 9, 7]\). Все значения в этом массиве различны, поэтому матрица является разнообразной. Модулем матрицы является число \(9\).
Для заданных \(r\) и \(c\) найдите разнообразную матрицу с минимально возможным модулем. Если таких матриц несколько, найдите любую из них. Если решения нет, выведите единственное целое число \(0\).
Выходные данные
Если решения нет, выведите одно целое число \(0\).
Иначе выведите \(r\) строк. В \(i\)-й строке выведите \(c\) целых чисел, разделенных пробелами, \(j\)-е из которых равно \(a_{i,j}\) — положительному целому числу на пересечении \(i\)-й строки и \(j\)-го столбца в разнообразной матрице с минимальным модулем.
Для всех элементов матрицы должно соблюдаться условие \(1 \leq a_{i,j} \leq 10^9\). Можно показать, что если решение существует, существует и решение, удовлетворяющее этим ограничениям (с тем же самым минимально возможным модулем).
Примечание
В первом примере НОДы в строках равны \(b_1 = 4\) и \(b_2 = 1\), а НОДы в столбцах равны \(b_3 = 2\) и \(b_4 = 3\). Все НОДы различны, а максимальный из них равен \(4\). Так как все НОДы должны быть различны и не могут быть меньше \(1\), не существует разнообразных матриц \(2 \times 2\) с модулем меньше \(4\).
Во втором примере независимо от значения \(a_{1,1}\) условие \(b_1 = b_2\) будет всегда соблюдаться, поэтому разнообразных матриц не существует.