Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2\le N\le 10^5$）头奶牛来担任该职位。在面试第 $i$ 个候选牛后，他会为候选牛分配一个 $1$ 到 $C$（$1\le C\le 10^9$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。

由于 Farmer John 面试了如此多的奶牛，他没能记得所有奶牛的牲任力分数。然而，他确实记得 $Q$（$1\le Q<N$）对数字 $(a_j,h_j)$，其中奶牛 $h_j$ 是第一头比奶牛 $1$ 到 $a_j$ 拥有严格更高牲任力分数的奶牛（所以 $1\le a_j<h_j\le N$）。

Farmer John 现在告诉你序列 $c_1,\ldots,c_N$
（其中 $c_i=0$ 表示他忘记了奶牛 $i$ 的牲任力分数）和 $Q$ 对 $(a_j,h_j)$。帮助他求出与此信息一致的最小字典序的牲任力分数序列，或者判断不存在这样的序列！如果一个分数序列比另一个分数序列于这两个序列不同的第一个位置上的奶牛分配了更小的分数，则这个分数序列的字典序更小。

每个测试点包含 $T$（$1\le T\le 20$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $3\cdot 10^5$。

输入的第一行包含 $T$，独立的测试用例的数量。每个测试用例描述如下：

1. 第一行包含 $N$，$Q$ 和 $C$。
2. 第二行包含序列 $c_1,\ldots,c_N$（$0\le c_i\le C$）。
3. 最后 $Q$ 行，每行包含一个数对 $(a_j,h_j)$。输入保证同一测试用例内的所有 $a_j$ 各不相同。

对于每个测试用例，输出一行，包含与 Farmer John 记忆一致的最小字典序牲任力分数序列，或者如果这样的序列不存在时输出 $−1$。