Problem Description

Farmer John is hiring a new herd leader for his cows. He has interviewed \( N \) (\( 2 \le N \le 10^5 \)) cows for the position. After interviewing the \( i \)-th candidate cow, he assigns her an integer "competency" score \( c_i \) within the range \( 1 \) to \( C \) (\( 1 \le C \le 10^9 \)), related to her leadership abilities.

Since Farmer John interviewed so many cows, he doesn't remember all the competency scores. However, he does remember \( Q \) (\( 1 \le Q < N \)) pairs of numbers \( (a_j, h_j) \), where cow \( h_j \) is the first cow with a strictly higher competency score than cows \( 1 \) to \( a_j \) (thus \( 1 \le a_j < h_j \le N \)).

Farmer John now tells you the sequence \( c_1, \ldots, c_N \) (where \( c_i = 0 \) indicates he forgot the competency score of cow \( i \)) and the \( Q \) pairs \( (a_j, h_j) \). Help him find the lexicographically smallest sequence of competency scores consistent with this information, or determine that no such sequence exists! A score sequence is lexicographically smaller than another if it assigns a smaller score to the cow at the first position where the two sequences differ.

Each test case contains \( T \) (\( 1 \le T \le 20 \)) independent test cases. The input guarantees that the sum of \( N \) over all test cases does not exceed \( 3 \cdot 10^5 \).

Input Format

The first line of the input contains \( T \), the number of independent test cases. Each test case is described as follows:

1. The first line contains \( N \), \( Q \), and \( C \).
2. The second line contains the sequence \( c_1, \ldots, c_N \) (\( 0 \le c_i \le C \)).
3. The last \( Q \) lines, each containing a pair \( (a_j, h_j) \). The input guarantees that all \( a_j \) within the same test case are distinct.

Output Format

For each test case, output a line containing the lexicographically smallest competency score sequence consistent with Farmer John's memory, or output \( -1 \) if no such sequence exists.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1 2 2 3 4 4 1

Input Sample #2

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

Output Sample #2

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

Notes/Hints

Sample Explanation 1

We can see that the given output satisfies all the pairs Farmer John remembers.

• \( \max(c_1) = 1 \), \( c_2 = 2 \) and \( 1 < 2 \), so the first pair is satisfied.
• \( \max(c_1, c_2, c_3) = 2 \), \( c_4 = 3 \) and \( 2 < 3 \), so the second pair is satisfied.
• \( \max(c_1, c_2, c_3, c_4) = 3 \), \( c_5 = 4 \) and \( 3 < 4 \), so the third pair is satisfied.

There are some other sequences consistent with Farmer John's memory, such as

\( 1 \ 2 \ 2 \ 3 \ 5 \ 4 \ 1 \)
\( 1 \ 2 \ 2 \ 3 \ 4 \ 4 \ 5 \)

However, none of these sequences are lexicographically smaller than the given output.

Sample Explanation 2

In test case 3, since \( C = 1 \), the only possible sequence is

\( 1 \ 1 \)

However, in this case, cow 2's score is not higher than cow 1's, so we cannot satisfy the condition.

In test case 5, \( a_1 \) and \( h_1 \) tell us that cow 6 is the first cow with a score strictly higher than cows 1 to 4. Therefore, the highest score among cows 1 to 6 is cow 6, which is 5. Since cow 7's score is 7, cow 7 is the first cow with a score higher than cows 1 to 6. Therefore, the second statement "cow 9 is the first cow with a score higher than cows 1 to 6" cannot hold.

Test Case Properties

• Test case 3: \( N \le 10 \) and \( Q, C \le 4 \).
• Test cases 4-8: \( N \le 1000 \).
• Test cases 9-12: No additional restrictions.

见题面 Input 部分

见题面 Output 部分