CF1893D Colorful Constructive

你有 $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 \leq i \leq k - x)$ 满足 $c_i = c_{i+x}$。 对于每个架子，给定了最小要求的多彩度，即给定了 $d_1, d_2, \ldots, d_m$，表示第 $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$ 个架子上依次放置的立方体颜色。

由 ChatGPT 4.1 翻译