题目描述

Yuki 给出了一个长度为 $n$ 的正整数序列 $f_1, \ldots, f_n$，保证对每个 $i$ 都有 $1 \leq f_i \leq i$。她想要请你构造一个 $n$ 阶方阵 $A$，满足：

• 对任意 $1 \leq i, j \leq n$，都有 $0 \leq A_{i,j} \leq n$；
• 对任意 $1 \leq i \leq n$，$\text{mex}(A_{i,1}, A_{i,2}, \ldots, A_{i,n}) = \text{mex}(A_{1,i}, A_{2,i}, \ldots, A_{n,i}) = f_i$。 可以证明，对任意合法的 $f_1, \ldots, f_n$，一定有解。

输入格式

本题中每个测试点有许多组数据。第一行仅包含一个整数 $t$ ($1 \leq t \leq 2 \cdot 10^4$)，表示测试数据组数。每组测试数据的格式如下：

第一行，一个整数 $n$ ($1 \leq n \leq 1414$)，表示给定的序列长度。

第二行，n 个整数 $f_1, \ldots, f_n$ ($1 \leq f_i \leq i$)，描述给定的序列。

保证所有测试数据中，$n^2$ 的总和不超过 $2 \cdot 10^6$。

输出格式

对于每组测试数据，输出共 $n$ 行，第 $i$ 行包含 $[0, n]$ 内的 $n$ 个非负整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,n}$。

3
3
1 1 2
5
1 1 3 2 5
4
1 2 1 3

0 2 0
0 0 0
0 0 1
3 2 0 0 4
0 0 2 0 3
2 4 1 0 2
0 0 1 1 0
2 0 4 3 1
2 0 2 2
0 1 0 1
2 3 0 0
0 0 2 1

解释 #1

对于第一组数据，$f = [1, 1, 2]$，一个合法的方阵为：

$$A = \begin{bmatrix} 0 & 2 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

对于第一行，$\text{mex}([0, 2, 0]) = 1 = f_1$，这是因为 $0$ 在 $[0,2,0]$ 内出现，而 $1$ 没有，因此 $1$为最小的未出现的非负整数；对于第一列，同理地，$\text{mex}([0, 0, 0]) = 1 = f_1$，容易验证该矩阵也满足其它限制。

• 行列 $b_1, \ldots, b_m$ 的 $\text{mex}$ 值为最小的非负整数 $z$，满足 $z$ 不在该行列中出现。