Вы обожаете числа, не так ли?) У Насти их много, и она решила поделиться ими с вами! Ну не прелесть?)
Пусть \(a_i\) — это количество чисел, равных \(i\) (\(1 \le i \le k\)), которые у вас есть.
Матрица \(n \times n\) называется красивой, если она содержит все числа, которые у вас есть, а также для каждой подматрицы \(2 \times 2\) исходной матрицы, выполняется:
- Количество занятых ячеек не превышает \(3\);
- Диагонали не содержат одинаковых чисел.
Составьте красивую матрицу минимального размера.
Выходные данные
Для каждого из \(t\) наборов входных данных в первой строке выведите одно целое число \(n\) — размер составленной вами красивой матрицы.
В последующий \(n\) строках выведите по \(n\) целых чисел \(b_{i, j}\) (\(0 \le b_{i, j} \le k\), если позиция пуста, выведите \(b_{i, j} = 0\)) — составленная вами красивая матрица \(b\).
Примечание
Обратите внимание, что \(0\) в этой задаче считается пустой позицией, а не числом.
Возможные ответы для первого набора входных данных:
\(\begin{array}{cc} 1 & 1 \\ 4 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\ 1 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\ 1 & 1 \\ \end{array}\)
Примеры некрасивых матриц для первого набора входных данных:
\(\begin{array}{cc} 1 & 0 \\ 4 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\ 7 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\ 4 & 0 \\ \end{array}\)
Пример некрасивой матрицы для второго набора входных данных:
\(\begin{array}{cc} 3 & 4 & 0 & 2 & 2 \\ 3 & 2 & 3 & 3 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 3 & 3 & 3 \\ \end{array}\)
В данном случае левая верхняя матрица содержит \(4\) числа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 4
2 0 0 1
15 4
2 4 8 1
|
2
4 1
0 1
5
3 0 0 2 2
3 2 3 3 0
0 1 0 4 0
3 0 0 0 0
2 1 3 3 3
|