← 返回题目列表

Codeforces · 1893/D

D. 多彩建设性

中文机器翻译题面 查看原题

你有 $$$n$$$ 个彩色立方体,第 $$$i$$$ 个立方体的颜色为 $$$a_i$$$。

你需要分发架子上的所有立方体。总共有$$$m$$$个架子,第$$$i$$$个架子可以容纳$$$s_i$$$个立方体。另外,$$$s_1 + s_2 + \ldots + s_m = n$$$。

假设在大小为 $$$k$$$ 的架子上有颜色为 $$$c_1, c_2, \ldots, c_k$$$ 的立方体,按此顺序。然后我们将架子的色彩定义为架子上两个相同颜色的不同立方体之间的最小距离。如果架子上的所有立方体都有不同的颜色,那么色彩度被认为等于架子的大小,即数字$$$k$$$。

更正式地说,$$$c_1, c_2, \ldots, c_k$$$ 的色彩定义如下:

- 如果所有颜色 $$$c_1, c_2, \ldots, c_k$$$ 都不同,则色彩度被认为是 $$$k$$$。
- 否则,色彩度被认为是最小整数 $$$x \geq 1$$$,使得存在索引 $$$i$$$ $$$(1 \le i \le k - x)$$$ 使得 $$$c_i = c_{i+x}$$$。

对于每个架子,都会给出所需的最低色彩度,即给出数字 $$$d_1, d_2, \ldots, d_m$$$,这意味着架子 $$$i$$$ 对于所有 $$$i$$$ 必须具有 $$$\geq d_i$$$ 色彩度。

在架子之间分配可用的立方体以确保所需的色彩,或者报告这是不可能的。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ $$$(1 \leq m \leq n \leq 2 \cdot 10^5)$$$ - 立方体的数量以及将它们分配到的架子的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ - 立方体的颜色。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$s_1, s_2, \ldots, s_m$$$ $$$(1 \leq s_i \leq n)$$$ — 货架的大小。可以保证 $$$s_1 + \ldots + s_m = n$$$。

每个测试用例的第四行包含 $$$m$$$ 整数 $$$d_1, d_2, \ldots, d_m$$$ $$$(1 \leq d_i \leq s_i)$$$ — 货架所需的最低色彩。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果不可能将满足所有要求的立方体分布在货架上,则输出单个数字$$$-1$$$。否则,输出 $$$m$$$ 行,其中第 $$$i$$$ 行应包含 $$$s_i$$$ 数字,以适当的顺序表示第 $$$i$$$ 架上立方体的颜色。

示例

输入 #1

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

输出 #1

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