Имеется пустая матрица \(M\) размера \(n\times m\).
Экзамен закончился, и Daniel хотел бы заняться головоломками. Он собирается заполнить матрицу \(M\) перестановками длины \(m\). То есть каждая строка \(M\) должна быть перестановкой длины \(m^\dagger\).
Определим значение \(i\)-го столбца в \(M\) как \(v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger\). Поскольку Daniel любит разнообразие, то красота \(M\) равна \(s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)\).
Вы должны помочь Daniel заполнить матрицу \(M\) и максимизировать её красоту.
\(^\dagger\) Перестановка длины \(m\) — это массив, состоящий из \(m\) различных целых чисел от \(0\) до \(m-1\), расположенных в произвольном порядке. Например, \([1,2,0,4,3]\) является перестановкой, но \([0,1,1]\) не является перестановкой (\(1\) встречается в массиве дважды), и \([0,1,3]\) также не является перестановкой (\(m-1=2\), но в массиве есть \(3\)).
\(^\ddagger\) \(\operatorname{MEX}\) массива — это наименьшее неотрицательное целое число, не принадлежащее массиву. Например, \(\operatorname{MEX}(2,2,1)=0\), так как \(0\) не принадлежит массиву, и \(\operatorname{MEX}(0,3,1,2)=4\), так как \(0\), \(1\), \(2\) и \(3\) в массиве есть, а \(4\) нет.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число — максимальную красоту \(M\).
Затем выведите матрицу \(M\) размера \(n\times m\) — матрицу, которую вы нашли.
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных:
- \(v_1=\operatorname{MEX}(1,0,1,0)=2\);
- \(v_2=\operatorname{MEX}(0,2,0,2)=1\);
- \(v_3=\operatorname{MEX}(2,1,2,1)=0\).
Таким образом, \(s=\operatorname{MEX}(2,1,0)=3\).
Можно доказать, что \(3\) является максимально возможной красотой \(M\).
Во втором наборе входных данных при любой перестановке \(s=2\).
В третьем наборе входных данных:
- \(v_1=\operatorname{MEX}(3,5,1,4,4,2)=0\);
- \(v_2=\operatorname{MEX}(0,2,3,1,2,4)=5\);
- \(v_3=\operatorname{MEX}(1,1,2,3,5,0)=4\);
- \(v_4=\operatorname{MEX}(4,0,4,2,3,5)=1\);
- \(v_5=\operatorname{MEX}(2,4,5,5,0,1)=3\);
- \(v_6=\operatorname{MEX}(5,3,0,0,1,3)=2\).
Таким образом, \(s=\operatorname{MEX}(0,5,4,1,3,2)=6\).