有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1\le j\le M$）双向连接着单元格 $U_j$ 和 $V_j$。

棋盘上有两种类型的单元格：激活单元格和停止单元格。

这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1\le i\le N$）是 '0' 表示单元格 $i$ 是激活单元格，是 '1' 表示单元格 $i$ 是停止单元格。

这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1\le p\le K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。

游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p+1$ 开始回合（如果 $p=K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作：

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

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

为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。

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

输入格式

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

• $N$ $M$ $K$
• $U_1$ $V_1$
• $U_2$ $V_2$
• ...
• $U_M$ $V_M$
• $S$
• $X_1,X_2,...,X_K$

输出格式

输出 $N$ 行。在第 $T$ 行（$1\le T\le N$）上，输出 $K$ 个玩家将玩家 1 的棋子放在单元格 $T$ 上所需的最小总移动次数。

样例 #1

样例输入 #1

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

样例输出 #1

0
1
2
2
3

样例解释 1

由于玩家 $1$ 的棋子从单元格 $1$ 开始，所以 $T=1$ 的答案是 $0$。

对于 $T=2$，在第一步中，玩家 $1$ 可以将他的棋子从单元格 $1$ 移动到单元格 $2$。因此，$T=2$ 的答案是 $1$。

对于 $T=3$，他们可以通过以下 $2$ 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

• 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个激活单元格，因此玩家 $1$ 的回合继续。
• 在第二步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $1$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T=3$ 的答案是 $2$。

类似地，可以验证 $T=4$ 的答案为 $2$，$T=5$ 的答案为 $3$。

这个样例输入满足子任务 $1,4,5,6,7,8$ 的约束。

样例 #2

样例输入 #2

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

样例输出 #2

0
1
4
4
5

样例解释 2

对于 $T=3$，他们可以通过以下 4 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

• 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $2$。
• 在第二步中，玩家 $2$ 将他的棋子从单元格 $5$ 移动到单元格 $3$。由于单元格 $3$ 是一个激活单元格，玩家 $2$ 的回合继续。
• 在第三步中，玩家 $2$ 将他的棋子从单元格 $3$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $1$。
• 在第四步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $3$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T=3$ 的答案是 $4$。

这个样例输入满足子任务 $2,4,5,6,7,8$ 的约束。

样例 #3

样例输入 #3

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

样例输出 #3

0
1
3
3
4

样例 #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

样例输入 #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

样例解释 3

这个样例输入满足子任务 $3,4,5,6,7,8$ 的约束。

样例解释 4

这个样例输入满足子任务 $4,6,7,8$ 的约束。

样例解释 5

这个样例输入满足子任务 $4,6,7,8$ 的约束。

约束条件

• $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)$，$(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 分) 没有额外的约束。