[SOLUTION !!!] Nastia and a Beautiful Matrix Solution Codeforces 2021

   

Nastia and a Beautiful Matrix Solution Codeforces 2021

SOLUTION

” CLICK HERE “

You like numbers, don't you? Nastia has a lot of numbers and she wants to share them with you! Isn't it amazing?

Let ai$a_i$ be how many numbers i$i$ (1≤i≤k$1\le i\le k$) you have.

An n×n$n\times n$ matrix is called beautiful if it contains all the numbers you have, and for each 2×2$2\times 2$ submatrix of the original matrix is satisfied:

1. The number of occupied cells doesn't exceed 3$3$;
2. The numbers on each diagonal are distinct.

Make a beautiful matrix of minimum size.

Input

The first line contains a single integer t$t$ (1≤t≤10000$1\le t\le 10000$) — the number of test cases.

The first line of each test case contains 2$2$ integers m$m$ and k$k$ (1≤m,k≤105$1\le m,k\le {10}^5$) — how many numbers Nastia gave you and the length of the array a$a$, respectively.

The second line of each test case contains k$k$ integers a1,a2,…,ak$a_1,a_2,\dots ,a_k$ (0≤ai≤m$0\le a_i\le m$, a1+a2+…+ak=m$a_1+a_2+\dots +a_k=m$), where ai$a_i$ is how many numbers i$i$ you have.

It's guaranteed that the sum of m$m$ and k$k$ in one test doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each t$t$ test case print a single integer n$n$ — the size of the beautiful matrix.

In the next n$n$ lines print n$n$ integers bi,j$b_{i,j}$ (0≤bi,j≤k$0\le b_{i,j}\le k$; if position is empty, print bi,j=0$b_{i,j}=0$) — the beautiful matrix b$b$ you made up.

Example

input

Copy

2
3 4
2 0 0 1
15 4
2 4 8 1

output

Copy

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

Note

Note that 0$0$ in this problem represents a blank, not a number.

Examples of possible answers for the first test case:

141011404101$\begin{array}{cc}1& 1\\ 4& 0\end{array}\begin{array}{cc}1& 4\\ 1& 0\end{array}\begin{array}{cc}4& 0\\ 1& 1\end{array}$

Examples of not beautiful matrices for the first test case:

140147111400$\begin{array}{cc}1& 0\\ 4& 1\end{array}\begin{array}{cc}4& 1\\ 7& 1\end{array}\begin{array}{cc}1& 0\\ 4& 0\end{array}$

The example of the not beautiful matrix for the second test case:

3303242101030032300320003$\begin{array}{ccccc}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}$

Everything is okay, except the left-top submatrix contains 4$4$ numbers.

SOLUTION

” CLICK HERE “

   

CODEFORCES

Also Read : Median sort solution codejam 2021

Also Read :Cheating detection solution codejam 2021