Lexicographically Minimal Cow Leadership Scores

Farmer John is hiring a new leader for his herd of cows. He interviewed \(N\) cows (\(2 \le N \le 10^5\)) and assigned each cow a leadership score \(c_i\) in the range \(1\) to \(C\) (\(1 \le C \le 10^9\)). Unfortunately, he forgot some of the scores; the forgotten scores are recorded as \(0\) in the sequence \(c_1, c_2, \ldots, c_N\).

In addition, Farmer John remembers \(Q\) pairs \((a_j, h_j)\) (with \(1 \le Q < N\)) with the following property: for each pair \((a, h)\), the cow numbered \(h\) is the first cow after the prefix consisting of cows \(1\) to \(a\) whose leadership score is strictly greater than the scores of all cows in positions \(1\) to \(a\). In other words, if we let \(M = \max\{c_1, c_2, \ldots, c_a\}\), then the conditions for each pair \((a, h)\) are: \[ \forall i,\; (a < i M. \]

Your task is to reconstruct a sequence of scores that is consistent with the given information. For cows with forgotten scores (denoted by 0), you should assign values in \([1, C]\) such that the final sequence is lexicographically smallest among all valid sequences. A sequence \(X\) is lexicographically smaller than a sequence \(Y\) if at the first index where they differ, the value in \(X\) is smaller than the corresponding value in \(Y\). If no valid sequence exists, output -1.

The input consists of \(T\) test cases. It is guaranteed that the sum of all \(N\) over the test cases does not exceed \(3 \cdot 10^5\).

inputFormat

The input begins with an integer \(T\) (\(1 \le T \le 20\)), the number of test cases. Each test case has the following format:

N Q C
c1 c2 ... cN
 a1 h1
 a2 h2
 ...
 aQ hQ

Here, \(N\) is the number of cows, \(Q\) is the number of remembered pairs, and \(C\) is the maximum possible score. For the sequence \(c_1, c_2, \ldots, c_N\), a value of 0 indicates that Farmer John forgot the score for that cow.

outputFormat

For each test case, output one line. If a valid sequence exists, output the lexicographically smallest sequence of \(N\) scores (separated by spaces) that is consistent with the given conditions. Otherwise, output -1.

sample

3
5 1 10
0 0 0 0 0
2 3
4 2 5
1 0 5 0
1 3
2 4
3 1 3
0 2 0
1 3

1 1 2 1 1
1 1 5 2
-1