有一个供 $K$ 名玩家参与的棋盘游戏。游戏棋盘由 $N$ 个编号为 $1$ 到 $N$ 的格子和 $M$ 条编号为 $1$ 到 $M$ 的路径组成，其中第 $j$ 条路径（$1 \le j \le M$）双向连接格子 $U_j$ 和 $V_j$。

棋盘上的格子分为两种类型：重激活格子（re-activate cells）和停止格子（stop cells）。 这些信息由一个长度为 $N$ 的字符串 $S$ 给出，其中 $S$ 的第 $i$ 个字符（$1 \le i \le N$）为 '0' 表示格子 $i$ 是重激活格子，为 '1' 表示格子 $i$ 是停止格子。

该棋盘游戏由 $K$ 名编号为 $1$ 到 $K$ 的玩家进行。每名玩家都有自己的棋子，游戏开始时，每名玩家将棋子放置在指定的格子上。起初，玩家 $p$（$1 \le p \le K$）将棋子放置在格子 $X_p$ 上。注意，多名玩家的棋子可以放置在同一个格子上。

游戏按玩家 $1$ 到 $K$ 的顺序轮流进行。玩家 $p$ 完成回合后，轮到玩家 $p+1$（若 $p=K$，则轮到玩家 $1$）。每名玩家在自己的回合内执行以下操作：

1. 选择一个与当前棋子所在格子通过路径相连的格子，并将棋子移动到所选格子。
2. 如果目标格子是重激活格子，则重复步骤 1 并继续当前回合。如果目标格子是停止格子，则结束当前回合。

包括 JOI-Kun 在内的 $K$ 名成员组成的团队代表日本参加此棋盘游戏，他们正在研究合作策略以快速征服游戏。他们目前正在研究以下问题：

为了将玩家 $1$ 的棋子放置在格子 $T$ 上，所有 $K$ 名玩家总共需要的最少移动次数是多少？即使是在回合进行中，只要玩家 $1$ 的棋子被放置在格子 $T$ 上，即视为满足条件。

给定游戏棋盘的信息和每名玩家棋子的初始位置，编写一个程序，计算对于每个 $T = 1, 2, \dots, N$ 的答案。

输入格式

从标准输入读取以下数据：

$N \ M \ K$ $U_1 \ V_1$ $U_2 \ V_2$ $\vdots$ $U_M \ V_M$ $S$ $X_1 \ X_2 \ \dots \ X_K$

输出格式

输出 $N$ 行到标准输出。在第 $T$ 行（$1 \le T \le N$），输出将玩家 $1$ 的棋子放置在格子 $T$ 上所需的最少总移动次数。

数据范围

• $2 \le N \le 50\,000$。
• $1 \le M \le 50\,000$。
• $2 \le K \le 50\,000$。
• $1 \le U_j < V_j \le N$（$1 \le j \le M$）。
• $(U_j, V_j) \neq (U_k, V_k)$（$1 \le j < k \le M$）。
• 通过若干路径，可以从任意格子到达任意其他格子。
• $S$ 是一个长度为 $N$ 的由 '0' 和 '1' 组成的字符串。
• $1 \le X_p \le N$（$1 \le p \le K$）。
• $N, M, K$ 为整数。
• $U_j, V_j$ 为整数（$1 \le j \le M$）。
• $X_p$ 为整数（$1 \le p \le K$）。

子任务

1. (3 分) 没有停止格子。
2. (7 分) 恰好有一个停止格子。
3. (7 分) 恰好有两个停止格子。
4. (19 分) $N \le 3\,000, M \le 3\,000, K \le 3\,000$。
5. (23 分) $K = 2$。
6. (9 分) $K \le 100$。
7. (23 分) $N \le 30\,000, M \le 30\,000, K \le 30\,000$。
8. (9 分) 没有额外限制。

样例

样例输入 1

5 5 2
1 2
2 3
2 4
3 5
4 5
00000
1 5

样例输出 1

0
1
2
2
3

样例输入 2

5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

样例输出 2

0
1
4
4
5

样例输入 3

5 5 2
1 2
2 3
2 4
3 5
4 5
01100
1 5

样例输出 3

0
1
3
3
4

样例输入 4

8 7 5
1 3
5 7
4 6
2 6
2 3
7 8
1 5
10011010
4 6 4 7 1

样例输出 4

4
2
3
0
10
1
17
24

样例输入 5

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

样例输出 5

0
1
4
5
6
7
8
8
4
1
13
9