카우엠페턴시

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

요약

잊어버린 점수를 채워 각 (a, h) 쌍에서 소 h가 1번부터 a번 소를 처음으로 넘어서게 하면서, 사전순으로 가장 작은 점수열을 구합니다. 조건을 만족하는 수열이 없으면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 배열, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Farmer John은 소 무리를 이끌 새 리더를 뽑고 있다. 이를 위해 그 자리에 지원한 소 $N$ 마리( $2 \leq N \leq 10^5$ )와 면접을 봤다. $i$ 번째 후보와 면접을 마친 뒤, 그 후보에게 1 이상 $C$ 이하의 정수 "cowmpetency" 점수 $c_i$ 를 매겼다( $1 \leq C \leq 10^9$ ). 이 점수는 리더십 능력과 상관관계가 있다.

소를 너무 많이 면접했기 때문에 Farmer John은 모든 소의 점수를 기억하지 못한다. 하지만 $Q$ 개( $1 \leq Q < N$ )의 수 쌍 $(a_j, h_j)$ 는 기억한다. 여기서 소 $h_j$ 는 1번부터 $a_j$ 번 소까지 어느 소보다도 엄격하게 큰 점수를 가진 첫 번째 소다( $1 \leq a_j < h_j \leq N$ ).

이제 Farmer John은 수열 $c_1, \dots, c_N$ ( $c_i = 0$ 은 $i$ 번 소의 점수를 잊었다는 뜻이다)과 $Q$ 개의 $(a_j, h_j)$ 쌍을 알려준다. 이 정보와 일치하는 점수 수열 중 사전순으로 가장 작은 수열을 구하라. 그런 수열이 없다면 그 사실을 판정하라. 두 수열이 처음으로 다른 소에서 더 작은 점수를 가진 수열이 사전순으로 더 작다.

입력

첫 줄에 독립된 테스트 케이스의 개수 $T$ ( $1 \leq T \leq 20$ )가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

$N$ , $Q$ , $C$ 가 적힌 한 줄.
수열 $c_1, \dots, c_N$ ( $0 \leq c_i \leq C$ )이 적힌 한 줄.
$Q$ 개의 줄에 각각 쌍 $(a_j, h_j)$ 가 적힌다. 한 테스트 케이스 안의 모든 $a_j$ 는 서로 다르다.

모든 테스트 케이스의 $N$ 합은 $3 \cdot 10^5$ 을 넘지 않는다.

출력

각 테스트 케이스마다 정보와 일치하는 사전순 최소 점수 수열을 한 줄에 출력한다. 그런 수열이 없으면 $-1$ 을 출력한다.

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