310818: CF1893D. Colorful Constructive

D. Colorful Constructivetime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

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

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 

题目大意：
你有一些彩色的立方体，第i个立方体颜色为a_i。需要将这些立方体分配到书架上。总共有m个书架，第i个书架可以容纳s_i个立方体。所有书架的容量之和等于立方体的数量。如果书架上有k个立方体，它们的颜色为c_1, c_2, ..., c_k，并且按这个顺序排列，那么我们定义这个书架的“多彩性”为同一颜色的两个立方体之间的最小距离。如果书架上所有立方体颜色都不同，那么“多彩性”被认为是k。对于每个书架，都会给出一个最小要求的“多彩性”d_i。需要分配立方体到书架上，以满足“多彩性”的要求，或者报告无法做到。

输入输出数据格式：
输入：
- 第一行包含一个整数t，表示测试用例的数量。
- 每个测试用例包含四行：
- 第一行包含两个整数n和m，分别表示立方体的数量和书架的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n，表示立方体的颜色。
- 第三行包含m个整数s_1, s_2, ..., s_m，表示每个书架的容量。
- 第四行包含m个整数d_1, d_2, ..., d_m，表示每个书架的最小要求“多彩性”。

输出：
- 对于每个测试用例，如果无法按照要求分配立方体，输出-1。
- 否则，输出m行，每行包含s_i个整数，表示对应书架上的立方体颜色。

请注意，由于这是LaTeX格式，所以上述内容应该按照LaTeX语法进行适当的格式化。题目大意： 你有一些彩色的立方体，第i个立方体颜色为a_i。需要将这些立方体分配到书架上。总共有m个书架，第i个书架可以容纳s_i个立方体。所有书架的容量之和等于立方体的数量。如果书架上有k个立方体，它们的颜色为c_1, c_2, ..., c_k，并且按这个顺序排列，那么我们定义这个书架的“多彩性”为同一颜色的两个立方体之间的最小距离。如果书架上所有立方体颜色都不同，那么“多彩性”被认为是k。对于每个书架，都会给出一个最小要求的“多彩性”d_i。需要分配立方体到书架上，以满足“多彩性”的要求，或者报告无法做到。 输入输出数据格式： 输入： - 第一行包含一个整数t，表示测试用例的数量。 - 每个测试用例包含四行： - 第一行包含两个整数n和m，分别表示立方体的数量和书架的数量。 - 第二行包含n个整数a_1, a_2, ..., a_n，表示立方体的颜色。 - 第三行包含m个整数s_1, s_2, ..., s_m，表示每个书架的容量。 - 第四行包含m个整数d_1, d_2, ..., d_m，表示每个书架的最小要求“多彩性”。 输出： - 对于每个测试用例，如果无法按照要求分配立方体，输出-1。 - 否则，输出m行，每行包含s_i个整数，表示对应书架上的立方体颜色。 请注意，由于这是LaTeX格式，所以上述内容应该按照LaTeX语法进行适当的格式化。