#P1521E. Nastia and a Beautiful Matrix

    ID: 5908 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>binary searchconstructive algorithmsdpgreedy*2700

Nastia and a Beautiful Matrix

No submission language available for this problem.

Description

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 aia_i be how many numbers ii (1ik1 \le i \le k) you have.

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

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

Make a beautiful matrix of minimum size.

The first line contains a single integer tt (1t100001 \le t \le 10\,000) — the number of test cases.

The first line of each test case contains 22 integers mm and kk (1m,k1051 \le m, k \le 10^5) — how many numbers Nastia gave you and the length of the array aa, respectively.

The second line of each test case contains kk integers a1,a2,,aka_1, a_2, \ldots, a_{k} (0aim0 \le a_i \le m, a1+a2++ak=ma_1 + a_2 + \ldots + a_{k} = m), where aia_i is how many numbers ii you have.

It's guaranteed that the sum of mm and kk in one test doesn't exceed 21052 \cdot 10^5.

For each tt test case print a single integer nn — the size of the beautiful matrix.

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

Input

The first line contains a single integer tt (1t100001 \le t \le 10\,000) — the number of test cases.

The first line of each test case contains 22 integers mm and kk (1m,k1051 \le m, k \le 10^5) — how many numbers Nastia gave you and the length of the array aa, respectively.

The second line of each test case contains kk integers a1,a2,,aka_1, a_2, \ldots, a_{k} (0aim0 \le a_i \le m, a1+a2++ak=ma_1 + a_2 + \ldots + a_{k} = m), where aia_i is how many numbers ii you have.

It's guaranteed that the sum of mm and kk in one test doesn't exceed 21052 \cdot 10^5.

Output

For each tt test case print a single integer nn — the size of the beautiful matrix.

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

Samples

Sample Input 1

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

Sample Output 1

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 00 in this problem represents a blank, not a number.

Examples of possible answers for the first test case:

$\begin{array}{cc} 1 & 1 \\ 4 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\ 1 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\ 1 & 1 \\ \end{array}$

Examples of not beautiful matrices for the first test case:

$\begin{array}{cc} 1 & 0 \\ 4 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\ 7 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\ 4 & 0 \\ \end{array}$

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

3402232330010003000021333\begin{array}{cc} 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 44 numbers.