Colorful Constructive
Contest: Codeforces Round 908 (Div. 1)
Difficulty rating: 2600
Tags: constructive algorithms, data structures, greedy

You have $$$n$$$ colored cubes, the $$$i$$$-th cube has color $$$a_i$$$.

You need to distribute all the cubes on shelves. There are a total of $$$m$$$ shelves, the $$$i$$$-th shelf can hold $$$s_i$$$ cubes. Also, $$$s_1 + s_2 + \ldots + s_m = n$$$.

Suppose on a shelf of size $$$k$$$ there are cubes of colors $$$c_1, c_2, \ldots, c_k$$$, in this order. Then we define the colorfulness of the shelf as the minimum distance between two different cubes of the same color on the shelf. If all the cubes on the shelf have different colors, then the colorfulness is considered to be equal to the size of the shelf, that is, the number $$$k$$$.

More formally, the colorfulness of $$$c_1, c_2, \ldots, c_k$$$ is defined as follows:

- If all the colors $$$c_1, c_2, \ldots, c_k$$$ are different, the colorfulness is considered to be $$$k$$$.
- Otherwise, the colorfulness is considered to be the smallest integer $$$x \geq 1$$$ such that there exists an index $$$i$$$ $$$(1 \le i \le k - x)$$$ such that $$$c_i = c_{i+x}$$$.

For each shelf, you are given the minimum required colorfulness, that is, you are given numbers $$$d_1, d_2, \ldots, d_m$$$, which mean that shelf $$$i$$$ must have a colorfulness $$$\geq d_i$$$ for all $$$i$$$.

Distribute the available cubes among the shelves to ensure the required colorfulness, or report that it is impossible.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ $$$(1 \leq m \leq n \leq 2 \cdot 10^5)$$$ — the number of cubes and the number of shelves to distribute them to.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — the colors of the cubes.

The third line of each test case contains $$$m$$$ integers $$$s_1, s_2, \ldots, s_m$$$ $$$(1 \leq s_i \leq n)$$$ — the sizes of the shelves. It's guaranteed, that $$$s_1 + \ldots + s_m = n$$$.

The fourth line of each test case contains $$$m$$$ integers $$$d_1, d_2, \ldots, d_m$$$ $$$(1 \leq d_i \leq s_i)$$$ — the minimum required colorfulness of the shelves.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if it is impossible to distribute the cubes on the shelves satisfying all the requirements, output a single number $$$-1$$$. Otherwise, output $$$m$$$ lines, where the $$$i$$$-th line should contain $$$s_i$$$ numbers representing the colors of the cubes on the $$$i$$$-th shelf, in the appropriate order.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
6
10 3
1 1 1 1 2 2 2 3 3 4
6 2 2
4 1 1
8 2
7 7 7 7 8 8 8 8
4 4
2 2
5 1
5 4 3 2 1
5
3
7 3
1 2 2 2 2 3 4
1 2 4
1 2 4
12 7
6 6 6 6 6 6 6 6 6 7 8 9
2 2 2 2 2 1 1
1 2 2 2 1 1 1
20 2
11 20 15 6 8 18 12 16 8 20 10 12 3 12 20 11 15 8 17 17
8 12
3 5

Example output:
1 3 4 2 1 3 
1 1 
2 2 
8 7 8 7 
8 7 8 7 
2 4 5 3 1 
-1
6 6 
7 6 
8 6 
9 6 
6 6 
6 
6 
12 17 20 15 8 20 16 11 
15 20 17 12 10 8 3 18 12 11 8 6

Editorial:
Let's try to come up with a condition equivalent to "A set of cubes $$$a_1, \ldots, a_n$$$ can be distributed on a shelf of size $$$n$$$ such that the colorfulness of the shelf is $$$\geq d$$$" in such a way that this condition can be conveniently combined for $$$m$$$ shelves.
Let's find the necessary condition (the condition that must be satisfied) if the set of cubes $$$a_1 \ldots a_n$$$ can be correctly placed on a shelf with parameters $$$(n, d)$$$. In such an arrangement, every $$$\leq d$$$ adjacent cubes must have different colors. This means that we can divide the shelf into subsegments as follows: $$$(a_1, \ldots, a_d), (a_{d+1}, \ldots, a_{2d}), \ldots, (a_{d \cdot (\lfloor \frac{n}{d} \rfloor - 1) + 1}, \ldots, a_{d \cdot \lfloor \frac{n}{d} \rfloor}), (a_{d \cdot \lfloor \frac{n}{d} \rfloor + 1}, \ldots, a_{n})$$$ such that the colors of all cubes in each subsegment are different. From this, the necessary condition follows: "The set of cubes $$$a_1, \ldots, a_n$$$ can be divided into $$$\lfloor \frac{n}{d} \rfloor$$$ groups of size $$$d$$$, as well as a group of size $$$n \mod d$$$, such that the colors of all cubes in each group are different."
It turns out that this same condition is also sufficient! We will show this by presenting a way to place all the cubes from the "$$$\lfloor \frac{n}{d} \rfloor$$$ groups of size $$$d$$$, and the group of size $$$n \mod d$$$ (where the colors of all cubes in each group are different)" on a shelf of size $$$n$$$ such that the colorfulness of the shelf is $$$\geq d$$$.
How to do it: place the cubes from the group of size $$$n \mod d$$$ in the first positions. Then consider the groups of size $$$d$$$ in any order. Place the cubes whose colors are already present in the previously placed array at the same indices as in the previous array, at a distance of $$$d$$$, and place the rest of the cubes however you like. It is easy to see that in this construction, the distance between any two identical colors is at least $$$d$$$.
Example for understanding: let $$$d = 3$$$ and the given groups be: $$$[1, 2, 3], [3, 4, 5], [1, 3, 4], [1, 2]$$$. Then we proceed as follows: first, place $$$[1, 2]$$$. Then we want to add the group $$$[1, 2, 3]$$$: $$$[1, 2, ?, ?, ?]$$$. The elements $$$1$$$ and $$$2$$$ were present in the previous array, so we place them at a distance of $$$d = 3$$$ from the previous occurrences: $$$[1, 2, ?, 1, 2]$$$. Fill in the remaining element: $$$[1, 2, 3, 1, 2]$$$. Now append $$$[3, 4, 5]$$$: $$$[1, 2, 3, 1, 2, ?, ?, ?]$$$. The element $$$3$$$ is present in the previous array, so we place it: $$$[1, 2, 3, 1, 2, 3, ?, ?]$$$. Fill in the remaining elements in any order: $$$[1, 2, 3, 1, 2, 3, 4, 5]$$$. After that, append the group $$$[1, 3, 4]$$$ and obtain the final arrangement: $$$[1, 2, 3, 1, 2, 3, 4, 5, 3, 4, 1]$$$. The colorfulness is $$$\geq 3$$$.
What to do with this information now? If we replace the conditions for all $$$m$$$ shelves with equivalent ones, we get: "The cubes can be placed on shelves $$$(s_1, d_1), \ldots, (s_m, d_m)$$$" is equivalent to "The cubes can be divided into groups of sizes $$$[\underbrace{d_1, \ldots, d_1}_{\lfloor \frac{s_1}{d_1} \rfloor}, s_1\mod d_1, \ldots, \underbrace{d_m, \ldots, d_m}_{\lfloor \frac{s_m}{d_m} \rfloor}, s_m \mod d_m]$$$, such that all colors are different in each group."
Thus, we have reduced the problem to a simpler one: given $$$a_1, \ldots, a_n$$$ and a set $$$w_1, \ldots, w_k$$$ with a sum of $$$n$$$. We need to divide the numbers $$$a_1, \ldots, a_n$$$ into arrays of sizes $$$w_1, \ldots, w_k$$$ such that all numbers in each array are different.
This problem can be solved using a simple greedy algorithm. Let $$$[a_1, \ldots, a_n]$$$ consist of $$$cnt_1$$$ copies of element $$$b_1$$$, $$$cnt_2$$$ copies of element $$$b_2$$$, ..., $$$cnt_t$$$ copies of element $$$b_t$$$ ($$$\sum cnt_i = n$$$). Then we consider the elements $$$b_1, \ldots, b_t$$$ in any order and place all copies of the current element in arrays of the largest length. If there are fewer arrays with non-zero length remaining than $$$cnt_i$$$, there is no solution. After adding, the length of the arrays in which the number was added decreases by $$$1$$$. It is easy to see that if we obtain a solution, then the numbers in all arrays will indeed be different. This solution can be easily implemented using std::set.
The correctness of the greedy algorithm follows from the fact that if there are two arrays of lengths $$$n_1 > n_2$$$ consisting of different numbers, then in the array of length $$$n_1$$$, there must be some number that is not present in the array of length $$$n_2$$$, so any number from the array of length $$$n_2$$$ can be swapped with someone from the array of length $$$n_1$$$ to maintain the property that the numbers in both arrays are different. From this, it follows that if we have some solution to the problem and a fixed element, we can obtain a solution in which this fixed element is only present in the largest arrays, which proves our solution.
Second solution:
Ultra Greedy Algorithm. We go through shelves and places on the shelf, and at each moment we place a cube of a color that occurs the most times among the remaining cubes, naturally excluding colors that would break the condition of having different colors (i.e., excluding colors other than the {$$$\max(0, d_i - 1)$$$} colors of the previous cubes on this shelf). The proof of why this solution works will remain behind the scenes.