XOR Degree Graph

 MoEngage has given you an array 

D$D$ of length N$N$. Construct a graph with N$N$ vertices such that:

• The graph is connected and does not contain any parallel edges or self-loops;
• Let du$d_u$ be the degree of vertex u$u$ (number of edges incident to u$u$). Then, du≤Du$d_u\le D_u$;
• ⊕Ni=1di=0${\oplus }_{i=1}^N{d}_i=0$. In other words, the bitwise XOR of the degrees of all the vertices is 0$0$.

If multiple such graphs exist, print any.

Input Format

• The first line of input contains one integer T$T$ - the number of test cases you have to process. The descriptions of T$T$ test cases follow.
• The first line contains one integer N$N$ - the size of the array D$D$ and the number of vertices to be present in the graph.
• The second line contains N$N$ integers D1,D2,…,DN$D_1,D_2,\dots ,D_N$ - the elements of the array D$D$.

Output Format

For each test case:

• If it is impossible to construct such a graph, print NO$\mathtt{\text{NO}}$ in a single line.
• Otherwise, print YES$\mathtt{\text{YES}}$ in a single line. Then, in the next N$N$ lines, print the adjacency matrix of the graph.
  The ith$i^{th}$ line should contain a string Ai$A_i$ of length N$N$. The jth$j^{th}$ character of Ai$A_i$ is equal to 1 if there is an edge between the vertices i$i$ and j$j$ and 0 if there is no edge.

Note: The strings YES$\mathtt{\text{YES}}$ and NO$\mathtt{\text{NO}}$ are case-sensitive.

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 2≤N≤2000$2\le N\le 2000$
• 1≤Di<N$1\le D_i<N$
• Sum of N2$N^2$ over all test cases does not exceed 107${10}^7$.

Sample Input 1 

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

Sample Output 1 

YES
0001
0010
0101
1010
NO
NO
YES
01010
10101
01001
10000
01100

Explanation

Test case 1$1$: A possible graph satisfying all the conditions is:

Here, the degrees of the vertices is d=[1,1,2,2]$d=[1,1,2,2]$. Note that, di≤Di$d_i\le D_i$ (1≤i≤4)$(1\le i\le 4)$. Also, the bitwise XOR of the degrees of all vertices is 1⊕1⊕2⊕2=0$1\oplus 1\oplus 2\oplus 2=0$.

Test case 2$2$: There exists no graph that satisfies all the given conditions.

Test case 3$3$: There exists no graph that satisfies all the given conditions.

Test case 4$4$: A possible graph satisfying all the conditions is:

Here, the degrees of the vertices is d=[2,3,2,1,2]$d=[2,3,2,1,2]$. Note that, di≤Di$d_i\le D_i$ (1≤i≤5)$(1\le i\le 5)$. Also, the bitwise XOR of the degrees of all vertices is 2⊕3⊕2⊕1⊕2=0$2\oplus 3\oplus 2\oplus 1\oplus 2=0$.