Alice and Bob decide to play a game similar to an SG game. To make it more interesting, they decide to play on a directed graph with cycles. Since the game might never end, they add an additional constraint. The specific rules are as follows:

1. The game is played on a given directed graph $G$ with $n$ vertices and $m$ edges, which may contain multiple edges but is guaranteed to have no self-loops. During the game, both players operate a single specific piece, which must be placed on one of the vertices of $G$ at any time. Initially, the piece is at vertex $s$. Additionally, each vertex $u$ in the graph is assigned a color $a_u$.
2. The game lasts for at most $k$ rounds, and each round $i$ has a specified color constraint $b_i$. Alice performs the moves in odd-numbered rounds, and Bob performs the moves in even-numbered rounds. If the player whose turn it is in the $k$-th round successfully completes their move, they are declared the winner, and the game ends.
3. In round $i$, the current player must move the piece at least once and at most $n$ times. A single move is defined as follows: if the piece is currently at vertex $u$ and there exists a directed edge $u \to v$ in $G$, the piece can be moved to vertex $v$. After the player completes all their moves, the vertex $u$ where the piece stops must satisfy $a_u = b_i$. If the current player cannot make a sequence of moves such that the piece stops at a vertex $u$ with $a_u = b_i$, the current player loses, and the game ends immediately. Otherwise, the game proceeds to the next round.
4. Alice and Bob are perfectly rational.

Alice does not like to lose, so she decides to secretly modify the sequence $b$ before the game starts. Specifically, she can perform a special operation once: choose $0 \le r < k$, delete the first $r$ elements of the sequence $b$, and then Alice and Bob continue the game using the modified sequence $b$. The length of the modified sequence becomes $k-r$, and the round limit for the new game also becomes $k-r$. However, deleting too many elements might be too obvious, so if Alice can choose different values of $r$ to perform the special operation such that she has a winning strategy in the subsequent game, she will always choose the smallest $r$.

Now, Alice wants to ask you: for every $1 \le i \le n$, if $s=i$, does Alice have a winning strategy? If so, what is the minimum $r$ Alice can choose at the beginning to ensure she has a winning strategy? If Alice does not have a winning strategy, output -1; otherwise, output the minimum $r$ that allows Alice to have a winning strategy.

Input

The first line contains three integers $n, m, k$.

The second line contains $n$ integers $a_1 \sim a_n$.

The third line contains $k$ integers $b_1 \sim b_k$.

The next $m$ lines each contain two integers $u, v$.

Output

A single line containing $n$ integers, where the $i$-th integer represents the answer when $s=i$.

Examples

Input 1

3 3 3
1 2 2 
1 2 3 
1 2
2 3
1 3

Output 1

1 1 -1

Input 2

10 5 9
3 4 3 1 4 4 2 4 1 4 
1 2 3 4 5 6 7 8 9 
1 3
7 10
7 9
4 8
2 7

Output 2

2 0 -1 3 -1 -1 0 -1 -1 -1

Input 3

7 9 10
3 3 3 3 1 4 3 
1 1 4 1 4 4 4 3 4 3 
2 3
2 5
1 7
7 5
6 3
1 7
4 5
5 3
5 3

Output 3

0 0 -1 0 7 7 0

Input 4

2 1 2
1 1
1 1
1 2

Output 4

0 -1

Subtasks

Property A: The given directed edges $u \to v$ satisfy $u < v$.

Property B: $\forall 1 \le i \le k, b_i = i$.

Subtask 1 ($10\%$): $n, m, k \le 100$.

Subtask 2 ($10\%$): $n, m, k \le 3000$.

Subtask 3 ($30\%$): $n, k \le 10^6, m \le 2.2 \times 10^6$, satisfying properties A and B.

Subtask 4 ($25\%$): $n, k \le 10^6, m \le 2.2 \times 10^6$, satisfying property B.

Subtask 5 ($25\%$): $n, k \le 10^6, m \le 2.2 \times 10^6$.

For all data, $m \le 2.2 \times 10^6, n, k \le 10^6, 1 \le a_i, b_i \le n, 1 \le u \neq v \le n$.