Alice 和 Bob 决定来玩一个类 SG 的博弈游戏，为了增加乐趣，他们决定在一张有环的图上玩，但这样游戏可能永远无法结束，因此他们又增加了一个额外限制，具体规则如下：

1. 游戏在一张给定的 $n$ 个点 $m$ 条边的可能有重边，保证无自环的有向图 $G$ 上进行。游戏过程中双方只能操作一个特定的棋子，且该棋子任意时刻都必须放在 $G$ 的某个节点上，初始该棋子位于节点 $s$。此外，图上每个节点 $u$ 均被指定了一种颜色 $a_u$。
2. 游戏会进行不超过 $k$ 回合，第 $i$ 回合会有指定的颜色限制 $b_i$。奇数回合的操作由 Alice 执行，偶数回合的操作由 Bob 执行，如果第 $k$ 回合的操作方顺利进行了操作，那么认为他/她取得了胜利，游戏结束。
3. 对于第 $i$ 回合，操作方需要对棋子进行至少一次，不超过 $n$ 次移动。一次移动可以描述为：若棋子当前位于节点 $u$，且 $G$ 中存在 $u \to v$ 的有向边，将棋子移动到节点 $v$。但要求在操作方进行完所有移动后，棋子停在的节点 $u$ 必须满足 $a_u=b_i$。如果当前操作方无法通过这样的一系列移动使棋子停在某个 $a_u=b_i$ 的点 $u$，认为当前操作方失败，游戏立刻结束。否则，游戏进入下一回合。
4. Alice 和 Bob 都绝顶聪明。

但 Alice 不喜欢输，所以她决定在游戏开始前偷偷修改 $b$ 序列，即她在游戏开始前可以进行一次特殊操作：选定 $0 \le r < k$，然后删掉 $b$ 序列的前 $r$ 个元素，然后 Alice 和 Bob 使用修改后的 $b$ 序列继续游戏，修改后 $b$ 序列长度变为 $k-r$，当然新游戏的回合上限也变为 $k-r$。但删掉太多元素可能太明显了，于是如果 Alice 可以通过选择不同的 $r$ 来执行特殊操作，使得她在接下来的游戏中必胜，她一定会选择最小的 $r$。

现在 Alice 想问问你，对于 $\forall 1 \le i \le n$，若 $s=i$，Alice 是否有策略必胜？如果有，Alice 在一开始进行特殊操作时，能够使她接下来有必胜策略的最小 $r$ 是多少？如果 Alice 无策略必胜，输出 -1，否则输出最小的使得 Alice 有策略必胜的 $r$。

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_1 \sim a_n$。

第三行 $k$ 个整数 $b_1 \sim b_k$。

接下来 $m$ 行，每行两个整数 $u,v$。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示 $s=i$ 时的答案。

样例数据

input

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

output

1 1 -1

input

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 0 -1 3 -1 -1 0 -1 -1 -1

input

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

0 0 -1 0 7 7 0

input

2 1 2
1 1
1 1
1 2

output

0 -1

子任务

A 性质：给出的有向边 $u \to v$ 满足 $u < v$。

B 性质：$\forall 1 \le i \le k,b_i=i$。

Subtask1($10\%$)：$n,m,k \le 100$。

Subtask2($10\%$)：$n,m,k \le 3000$。

Subtask3($30\%$)：$n,k \le 10^6,m \le 2.2 \times 10^6$，满足 AB 特殊限制。

Subtask4($25\%$)：$n,k \le 10^6,m \le 2.2 \times 10^6$，满足 B 特殊限制。

Subtask5($25\%$)：$n,k \le 10^6,m \le 2.2 \times 10^6$。

对于所有数据，$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$。