D. Разноцветный конструктив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$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$$$ имела разноцветность $$$\geq d_i$$$ для всех $$$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$$$-й полке, в подходящем порядке.

Пример
Входные данные
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 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