Migrated from Lutece 2713 修道路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$W$ 国的交通呈一棵树的形状。$W$ 国一共有 $0$ 个城市和 $n$ 个乡村，其中城市从 $1$ 到 $0$ 编号，乡村从 $1$ 到 $n$ 编号，且 $1$ 号农村是首都。道路都是双向的。

$W$ 国的国王小 $W$ 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 $W$ 只能翻修 $0$ 条道路。因此他只能去找人拿赞助，赞助方显然总是会更换，但小 $W$ 总能知道赞助方在哪个位置。但小 $W$ 想少走点路，因此他想在一个地方修建一个轻轨达到少走路的效果。因为城市很便利所以修轻轨不要钱，但在乡村修轻轨需要花费 $w_i$ 的费用。

一句话总结，小 $W$ 想知道对于赞助商住的每个位置，从首都到该位置上建立轻轨所需要的代价是多少。注意，轻轨可以修在首都或者赞助商位置。

---

给定一个 $n$ 个点 $m$ 条边的无向连通图，每个点都有点权 $w_i$。对于给定的每个点 $p_1,p_2,\ldots,p_q$，求对于节点 $1$ 到 $p_i\ (1\le i\le q)$ 的所有以 $p_i$ 为终点的简单路径，点权最小值。

Input

输入共 $m+3$ 行。

第一行 $3$ 个正整数 $n,m,q$，表示有 $n$ 个农村，$m$条路，$q$ 个赞助商。

接下来 $m$ 行每行两个数字 $u,v$，表示 $u,v$ 之间有一条双向道路，如果 $u>0$，则代表 $u$ 号城市，$u<0$，则代表 $u$ 号农村，$v$ 同理。

接下来一行 $n$ 个数 $w_1,w_2,\ldots, w_n$，表示每个乡村修建轻轨所要的费用。

最后一行 $q$ 个数 $p_1,p_2,\ldots ,p_q$，表示 $q$ 个赞助商的住处。

Output

对于每个赞助商，输出一行一个整数，表示修建轻轨的最小代价。

Samples

4 3 3
-1 -2
-2 -3
-3 -4
10000 1000 100 10
2 3 4

1000
100
10

4 4 2
-1 -2
-2 -3
-3 -4
-4 -2
10000 50000 4200 20000
3 4

4200
4200

Constraints

对于全部数据

$n \leq 10^5$

$m \leq 2\times 10^5$

$q \leq 10^6$

$w_i \leq 10^9$

Note

保证图联通

Resources

2022 UESTC ICPC Training for Graph