У вас есть простое число \(n\) и массив из \(n\) целых чисел \(b_1,b_2,\ldots, b_n\), где \(0 \leq b_i < n\) для всех \(1 \le i \leq n\).
Вы должны найти матрицу \(a\) размера \(n \times n\) такую, что выполняются все следующие условия:
- \(0 \le a_{i,j} < n\) для всех \(1 \le i, j \le n\).
- \(a_{r_1, c_1} + a_{r_2, c_2} \not\equiv a_{r_1, c_2} + a_{r_2, c_1} \pmod n\) для всех положительных чисел \(r_1\), \(r_2\), \(c_1\), \(c_2\) таких, что \(1 \le r_1 < r_2 \le n\) и \(1 \le c_1 < c_2 \le n\).
- \(a_{i,i} = b_i\) для всех \(1 \le i \leq n\).
Здесь \(x \not \equiv y \pmod m\) означает, что \(x\) и \(y\) дают разные остатки от деления на \(m\).
Если существуют несколько решений, выведите любое из них. Можно показать, что такая матрица всегда существует при данных ограничениях.
Выходные данные
Выведите \(n\) строк. На \(i\)-й строке выведите \(n\) целых чисел \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}\).
Если существуют несколько решений, выведите любое из них.
Примечание
В первом примере ответ корректный, так как все элементы являются неотрицательными числами меньшими \(n = 2\), и \(a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 2\) (потому что \(a_{1,1}+a_{2,2} = 0 + 0 \equiv 0 \pmod 2\), а \(a_{1,2}+a_{2,1} = 1 + 0 \equiv 1 \pmod 2 \)). Кроме того, значения на главной диагонали равны \(0,0\), как и требовалось.
Во втором примере ответ корректный, так как все элементы являются неотрицательными числами меньшими \(n = 3\), и второе условие выполнено для всех четверок \((r_1, r_2, c_1, c_2)\). Например,
- при \(r_1=1\), \(r_2=2\), \(c_1=1\) и \(c_2=2\), \(a_{1,1}+a_{2,2} \not\equiv a_{1,2}+a_{2,1} \pmod 3\), так как \(a_{1,1}+a_{2,2} = 1 + 1 \equiv 2 \pmod 3\), а \(a_{1,2}+a_{2,1} = 2 + 1 \equiv 0 \pmod 3 \);
- при \(r_1=2\), \(r_2=3\), \(c_1=1\) и \(c_2=3\), \(a_{2,1}+a_{3,3} \not\equiv a_{2,3}+a_{3,1} \pmod 3\), так как \(a_{2,1}+a_{3,3} = 1 + 1 \equiv 2 \pmod 3\), а \(a_{2,3}+a_{3,1} = 0 + 1 \equiv 1 \pmod 3 \).
Кроме того, значения на главной диагонали равны
\(1,1,1\), как и требовалось.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
0 0
|
0 1
0 0
|
|
2
|
3
1 1 1
|
1 2 2
1 1 0
1 0 1
|
|
3
|
5
1 4 1 2 4
|
1 0 1 3 4
1 4 3 1 0
2 4 1 0 2
1 2 2 2 2
2 2 0 1 4
|