Cowmpetency

문제

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed $NN$ ($2\le N\le {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 10^5$) cows for the position. After interviewing the $ii$th candidate, he assigned the candidate an integer "cowmpetency" score $c_{i}c\_i$ ranging from $11$ to $CC$ inclusive ($1\le C\le {10}^{9}1\; \backslash leq\; C\; \backslash leq\; 10^9$) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John does not remember all of their cowmpetency scores. However, he does remembers $QQ$ () pairs of numbers $(a_j,h_j)(a\_j,\; h\_j)$ where cow $h_{j}h\_j$ was the first cow with a strictly greater cowmpetency score than cows $11$ through $a_{j}a\_j$ (so ).

Farmer John now tells you the sequence $c_1,\dots ,c_{N}c\_1,\; \backslash dots,\; c\_N$ (where $c_i=0c\_i\; =\; 0$ means that he has forgotten cow $ii$'s cowmpetency score) and the $QQ$ pairs of $(a_j,h_j)(a\_j,\; h\_j)$. Help him determine the lexicographically smallest sequence of cowmpetency scores consistent with this information, or that no such sequence exists! A sequence of scores is lexicographically smaller than another sequence of scores if it assigns a smaller score to the first cow at which the two sequences differ.

Each input contains $TT$ $(1\le T\le 20)(1\; \backslash leq\; T\; \backslash leq\; 20)$ independent test cases. The sum of $NN$ across all test cases is guaranteed to not exceed $3\cdot {10}^{5}3\; \backslash cdot\; 10^5$.

입력

The first line contains $TT$, the number of independent test cases. Each test case is described as follows:

1. First, a line containing $NN$, $QQ$, and $CC$.
2. Next, a line containing the sequence $c_1,\dots ,c_{N}c\_1,\; \backslash dots,\; c\_N$ $(0\le c_i\le C)(0\; \backslash leq\; c\_i\; \backslash leq\; C)$.
3. Finally, $QQ$ lines each containing a pair $(a_j,h_j)(a\_j,\; h\_j)$. It is guaranteed that all $a_{j}a\_j$ within a test case are distinct.

출력

For each test case, output a single line containing the lexicographically smallest sequence of cowmpetency scores consistent with what Farmer John remembers, or $-1-1$ if such a sequence does not exist.

1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

1 2 2 3 4 4 1

5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9

1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1