Вася написал в тетради некоторую перестановку \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\), то есть для всех \(1 \leq i \leq n\) выполнено \(1 \leq p_i \leq n\), и все \(p_1, p_2, \ldots, p_n\) различны. После этого он записал \(n\) значений \(next_1, next_2, \ldots, next_n\). Значение \(next_i\) равно минимальному индексу \(i < j \leq n\), такому что \(p_j > p_i\). Если такого \(j\) не существует, то определим значение как \(next_i = n + 1\).
Вечером Вася шел домой из школы, и из-за дождя тетрадь намокла. Теперь некоторые написанные числа невозможно разобрать. Перестановка, а также некоторые значения \(next_i\) полностью утеряны! Если для какого-то \(i\) значение \(next_i\) теперь неизвестно, то скажем, что \(next_i = -1\).
Вам даны значения \(next_1, next_2, \ldots, next_n\) (возможно, некоторые числа теперь равны \(-1\)). Помогите Васе найти любую такую перестановку \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\), что он может записать её в тетрадь, и все значения \(next_i\), не равные \(-1\), будут посчитаны правильно.
Выходные данные
Выведите \(T\) строк, в \(i\)-й ответ на \(i\)-й тестовый случай.
Если таких перестановок \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\), которые мог выписать Вася не существует, то выведите единственное число \(-1\).
Иначе выведите \(n\) различных целых чисел \(p_1, p_2, \ldots, p_n\), разделённых пробелами (\(1 \leq p_i \leq n\)). Все определённые значения \(next_i\), не равные \(-1\), должны быть вычислены верно из перестановки \(p_1, p_2, \ldots, p_n\) по определению из условия задачи. Если существует несколько таких перестановок, найдите любую.
Примечание
В первом тестовом случае для перестановки \(p = [1, 2, 3]\) получится \(next = [2, 3, 4]\), так как каждый элемент перестановки меньше следующего. Можно заметить, что это единственная подходящая перестановка.
Во третьем тестовом случае подойдет любая перестановка, так как все значения \(next_i\) неизвестны.
В четвертом тестовом случае не существует ни одной подходящей перестановки, поэтому ответ \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5
|
1 2 3
2 1
2 1 3
-1
1
3 2 1 4
|