Nastia and a Beautiful Matrix
Contest: Codeforces Round 720 (Div. 2)
Difficulty rating: 2700
Tags: binary search, constructive algorithms, dp, greedy

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

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

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

Make a beautiful matrix of minimum size.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.

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

The second line of each test case contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_{k}$$$ ($$$0 \le a_i \le m$$$, $$$a_1 + a_2 + \ldots + a_{k} = m$$$), where $$$a_i$$$ is how many numbers $$$i$$$ you have.

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

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Note that $$$0$$$ 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:

$$$\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 $$$4$$$ numbers.

Example input:
2
3 4
2 0 0 1
15 4
2 4 8 1

Example output:
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

Editorial:
Let's fix $$$n$$$ and will check whether we build a beautiful matrix or not.
Let's define the variable $$$mx$$$ as a maximum element among all elements from the array $$$a$$$. In other words, the amount of the most frequently occurring number we have. Also, define the variable $$$sum$$$ as an amount of numbers we have.
We can single out the $$$2$$$ criteria. These are $$$sum \le n ^ 2 - \lfloor \frac {n} {2} \rfloor ^ 2$$$ and $$$mx \le n \cdot \lceil \frac {n} {2} \rceil$$$. It can be proved by spitting the matrix into disjoint matrices $$$2 \times 2$$$.
Let's construct the structure of the matrix and provide the algorithm of arrangement, that if the previous $$$2$$$ conditions are satisfied, then we always can create the beautiful matrix of $$$n$$$ size. Take a look at the picture:
There are $$$4$$$ types of cells. White cells are empty, blue ones can consist of any number.
Let's fill yellow and red cells in a way that they don't have any common number. We will do it greedily:
Let's fill red cells at first. Let's take numbers $$$x$$$, which is the most frequently occurring, and just try to fill red cells using only it.
If all numbers $$$x$$$ are fully fit there, then we just take a new $$$x$$$ and continue filling cells. If there are elements of color $$$x$$$ that cannot be placed there then we put all such remaining elements in blue cells.
It is always possible to do because the number of blue cells and yellow cells together is $$$n \cdot \lceil \frac {n} {2} \rceil$$$, that is the upper bound of the value $$$mx$$$. In this way, we filled red cells and some blue cells.
The other elements, which haven't been placed yet, can be placed randomly because they won't match(by diagonal) due to the way of filling red cells.