Cowmpetency

시간 제한2초메모리 제한1024 MB

요약

일부만 알려진 점수 배열과 '소 h가 1번부터 a번 소보다 처음으로 큰 점수를 가진다'는 제약이 주어질 때, 이를 만족하는 사전순 최소 배열을 구하거나 불가능함을 판정한다.

난이도: 어려움10점 중 8점
유형: 그리디, 배열, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed $N$ ( $2 \leq N \leq 10^5$ ) cows for the position. After interviewing the $i$ th candidate, he assigned the candidate an integer "cowmpetency" score $c\_i$ ranging from $1$ to $C$ inclusive ( $1 \leq C \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 $Q$ ( $1 \leq Q < N$ ) pairs of numbers $(a\_j, h\_j)$ where cow $h\_j$ was the first cow with a strictly greater cowmpetency score than cows $1$ through $a\_j$ (so $1 \leq a\_j < h\_j \leq N$ ).

Farmer John now tells you the sequence $c\_1, \dots, c\_N$ (where $c\_i = 0$ means that he has forgotten cow $i$ 's cowmpetency score) and the $Q$ pairs of $(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 $T$ $(1 \leq T \leq 20)$ independent test cases. The sum of $N$ across all test cases is guaranteed to not exceed $3 \cdot 10^5$ .

입력

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

First, a line containing $N$ , $Q$ , and $C$ .
Next, a line containing the sequence $c\_1, \dots, c\_N$ $(0 \leq c\_i \leq C)$ .
Finally, $Q$ lines each containing a pair $(a\_j, h\_j)$ . It is guaranteed that all $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$ if such a sequence does not exist.

예제2

예제 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

예제 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

예상 출력

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