Restore Cycles

Input

The first line contains three integers $n$ , $k$ , and $x$ — the length of the array, the number of people, and the number of days, respectively.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\ldots,a_n.

Each of the next $k$ lines contains two integers $s_{i}$ s_i and $c_{i}$ c_i — the initial position of the $i$ -th person and the value of their score after exactly $x$ days, respectively.

All values $s_{i}$ s_i are pairwise distinct.

Output

If there is no permutation $p$ satisfying all the given conditions, output $- 1$ .

Otherwise, output $n$ integers

p_{1}, p_{2}, \dots, p_{n}

p_1,p_2,\ldots,p_n

— any permutation of the numbers from $1$ to $n$ that satisfies all the given conditions.

Examples

Example 1

Loading

Example 2

Loading

Note

In the first example, one can choose the permutation

p = [2, 1, 3, 5, 4] .

p=[2,1,3,5,4].

The first person starts at position $1$ . During three days, they will be at positions $1, 2, 1$ , so their final score will be

max (a_{1}, a_{2}, a_{1}) = max (2, 7, 2) = 7.

\max(a_1,a_2,a_1)=\max(2,7,2)=7.

The second person starts at position $4$ . During three days, they will be at positions $4, 5, 4$ , so their final score will be

max (a_{4}, a_{5}, a_{4}) = max (1, 5, 1) = 5.

\max(a_4,a_5,a_4)=\max(1,5,1)=5.

Thus, the given permutation satisfies all the conditions.

In the second example, the only person starts at position $1$ , where $a_{1} = 2$ a_1=2. After the first day already, their score will become at least $2$ , but the given final score is $1$ . Therefore, no suitable permutation exists, and the answer is $- 1$ .

Scoring

Subtask $1$ ( $20$ points): all values $a_{i}$ a_i are equal.
Subtask $2$ ( $50$ points): $x = n$ x = n.
Subtask $3$ ( $70$ points): $a_{i} \leq 20$ a_i \le 20 for all $1 \leq i \leq n$ 1 \le i \le n.
Subtask $4$ ( $110$ points): No additional constraints.