Năng Lực Bò

Bác John phỏng vấn $N$ con bò và cho mỗi con một điểm "năng lực" từ $1$ đến $C$. Bác nhớ $Q$ cặp $(a_j,h_j)$: con bò thứ $h_j$ là con bò đầu tiên có điểm năng lực lớn hơn nghiêm ngặt tất cả các con bò từ $1$ đến $a_j$.

Cho một dãy điểm năng lực, trong đó một số giá trị đã biết và các giá trị còn lại là $0$ (chưa biết). Hãy tìm dãy nhỏ nhất theo thứ tự từ điển thỏa mãn tất cả các ràng buộc, hoặc trả về $-1$ nếu không tồn tại.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $T$ ($1\le T\le 20$) - số test case.
• Mỗi test case:
  • Dòng 1: ba số nguyên $N$, $Q$, $C$ ($2\le N\le {10}^5$, $1\le Q<N$, $1\le C\le {10}^9$).
  • Dòng 2: $N$ số nguyên $c_1,\dots ,c_N$ ($0\le c_i\le C$), với $0$ là chưa biết.
  • $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a_j$ và $h_j$ ($1\le a_j<h_j\le N$).

Dữ liệu ra

Với mỗi test case, in dãy nhỏ nhất theo thứ tự từ điển thỏa mãn ràng buộc, hoặc -1.

Ràng buộc

• $1\le T\le 20$
• $2\le N\le {10}^5$
• $1\le C\le {10}^9$

Ví dụ