E. Точно больше
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$$$$^{\text{∗}}$$$ чисел от $$$1$$$ до $$$n$$$.

Для произвольной перестановки $$$q$$$ длины $$$n$$$ будем говорить, что индекс $$$j$$$ доминирует над индексом $$$i$$$ тогда и только тогда, когда выполняются все следующие условия:

  • $$$j \gt i$$$,
  • $$$p_j \gt p_i$$$, и
  • $$$q_j \gt q_i$$$.

Также дан массив $$$d$$$ длины $$$n$$$, где $$$d_i$$$ обозначает количество индексов, доминирующих над индексом $$$i$$$.

Ваша задача — построить перестановку $$$q$$$ чисел от $$$1$$$ до $$$n$$$ такую, что для каждого индекса $$$i$$$ ($$$1 \le i \le n$$$) количество индексов $$$j$$$, доминирующих над $$$i$$$, равно $$$d_i$$$.

Если такая $$$q$$$ существует, выведите любую подходящую. Иначе сообщите, что её не существует.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 5000$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$. Гарантируется, что $$$p$$$ является перестановкой чисел от $$$1$$$ до $$$n$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных:

  • Если построить $$$q$$$ возможно, выведите строку из $$$n$$$ целых чисел $$$q_1, q_2, \ldots, q_n$$$ — подходящую перестановку. Если существует несколько подходящих ответов, можно вывести любой из них.
  • Иначе выведите $$$-1$$$.
Пример
Входные данные
7
3
2 3 1
1 0 0
4
3 4 1 2
2 1 1 0
5
2 3 1 4 5
2 2 1 1 0
1
1
0
5
3 1 4 2 5
1 1 1 1 0
4
3 4 2 1
1 1 1 0
8
7 6 3 1 2 5 4 8
1 1 2 2 2 1 1 0
Выходные данные
1 2 3
-1
2 1 4 3 5
1
2 4 1 3 5
-1
1 2 4 6 5 3 7 8
Примечание

В первом наборе входных данных подходящим ответом является $$$q = [1, 2, 3]$$$:

  • Для $$$i=1$$$ имеем $$$p_1=2$$$ и $$$q_1=1$$$. Индекс $$$j=2$$$ доминирует над $$$i=1$$$, потому что $$$2 \gt 1$$$, $$$p_2=3 \gt p_1$$$, и $$$q_2=2 \gt q_1$$$. Индекс $$$j=3$$$ не доминирует над $$$i=1$$$, потому что $$$p_3=1 \lt p_1$$$. Таким образом, над $$$i=1$$$ доминирует ровно $$$1$$$ индекс, что совпадает с $$$d_1=1$$$.
  • Для $$$i=2$$$ имеем $$$p_2=3$$$ и $$$q_2=2$$$. Единственный больший индекс — это $$$j=3$$$, но $$$p_3=1 \lt p_2$$$, поэтому он не доминирует. Следовательно, над $$$i=2$$$ доминирует $$$0$$$ индексов, что совпадает с $$$d_2=0$$$.
  • Для $$$i=3$$$ нет индексов $$$j \gt 3$$$, поэтому над ним доминирует $$$0$$$ индексов, что совпадает с $$$d_3=0$$$.

Во втором наборе входных данных $$$p = [3, 4, 1, 2]$$$ и $$$d = [2, 1, 1, 0]$$$. Рассмотрим $$$i=2$$$, где $$$p_2=4$$$. Поскольку не существует индекса $$$j \gt 2$$$ с $$$p_j \gt p_2$$$, ни один индекс не может доминировать над $$$i=2$$$. Однако массив $$$d$$$ требует, чтобы $$$d_2=1$$$, что делает построение подходящей перестановки $$$q$$$ невозможным. Следовательно, ответ — -1.