E. Прямоугольная конгруэнтность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть простое число $$$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$$$ ($$$2 \le n < 350$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i < n$$$) — необходимые значения на главной диагонали матрицы.

Гарантируется, что $$$n$$$ простое.

Выходные данные

Выведите $$$n$$$ строк. На $$$i$$$-й строке выведите $$$n$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$.

Если существуют несколько решений, выведите любое из них.

Примеры
Входные данные
2
0 0
Выходные данные
0 1 
0 0
Входные данные
3
1 1 1
Выходные данные
1 2 2
1 1 0
1 0 1
Входные данные
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
Примечание

В первом примере ответ корректный, так как все элементы являются неотрицательными числами меньшими $$$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$$$, как и требовалось.