Фермер Джон нанимает нового вожака стада для своих коров.
Для этого он интервьюирует \(N\) (\(2 \leq N \leq 10^5\)) коров на эту позицию.
После интервью \(i\)-го кандидата он назначает целое число "уровень компетенции"
\(c_i\) от \(1\) дo \(C\) включительно (\(1 \leq C \leq 10^9\)).
Поскольку ФД интервьюировал много коров, он не помнит все \(c_i\).
Однако он помнит \(Q\) (\(1 \leq Q < N\)) пар чисел \((a_j, h_j)\)
где корова \(h_j\) компетенция которой была строго больше,
чем уровень компетенции коров от \(1\) до \(a_j\) (\(1 \leq a_j < h_j \leq N\)).
ФД говорит Вам последовательность \(c_1, \dots, c_N\) (где \(c_i = 0\)
означает, что он забыл уровень компетенции коровы \(i\), и \(Q\) пар \((a_j, h_j)\).
Помогите ему определить лексикографически минимальную
последовательность уровней компетенции, соответствующую этой информации
или указать, что такой последовательности не существует. Последовательность
чисел называется лексикографически меньше другой последовательности
если в ней меньшее число не первой позиции, где эти последовательности
различаются.
Каждый ввод содержит \(T\) \((1 \leq T \leq 20)\) независимых подтестов.
Гарантируется, что сумма \(N\) по всем подтестам не превысит \(3 \cdot 10^5\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\), количество независимых подтестов.
Каждый подтест описывается так:
- Первая строка содержит \(N\), \(Q\), \(C\).
- Следующая строка содержит c1, \dots, cN\( \)(0 \leq ci \leq C)$.
- Каждая из последующих \(Q\) строк содержит пару \((a_j, h_j)\).
Гарантируется что все \(a_j\) в текущем подтесте различны.
ОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите одну строку содержащую
лексикографически минимальную последовательность уровней компетенции,
соответствующую информации, которую помнит ФД, или \(-1\), если
такой последовательности не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5
|
1 2 2 3 4 4 1
|