给你一个无向连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。该图的 $$$k$$$ 顶点是特殊的。
您必须定向该图的每条边或使其保持无向。如果你让第 $$$i$$$ 条边不定向,你需要支付 $$$w_i$$$ 硬币,如果你定向它,你就不必支付费用。
如果一个顶点可以沿着图的边从每个特殊顶点到达(如果边是无向的,则可以在两个方向上遍历它),我们称该顶点为饱和顶点。在您定向图的边(可能其中一些边是无向的)后,您会为每个饱和顶点 $$$i$$$ 收到 $$$c_i$$$ 硬币。因此,您的总利润可以计算为 $$$\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$$$,其中 $$$S$$$ 是饱和顶点集,而 $$$U$$$ 是无向边集。
对于每个顶点 $$$i$$$,计算如果必须使顶点 $$$i$$$ 饱和的话可以获得的最大可能利润。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2})$$$, $$$1 \le k \le n$$$)。
第二行包含 $$$k$$$ 成对不同的整数 $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$ ($$$1 \le v_i \le n$$$) — 特殊顶点的索引。
第三行包含 $$$n$$$ 整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^9$$$)。
第四行包含 $$$m$$$ 整数 $$$w_1$$$, $$$w_2$$$, ..., $$$w_m$$$ ($$$0 \le w_i \le 10^9$$$)。
接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条边的端点。
每对顶点之间最多有一条边。
输出
打印 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数是如果必须使顶点 $$$i$$$ 饱和时可以获得的最大利润。
示例
输入 #1
3 2 2 1 3 11 1 5 10 10 1 2 2 3
输出 #1
11 2 5
输入 #2
4 4 4 1 2 3 4 1 5 7 8 100 100 100 100 1 2 2 3 3 4 1 4
输出 #2
21 21 21 21
注意
考虑第一个例子:
- 使顶点 $$$1$$$ 饱和的最佳方法是将边定向为 $$$2 \to 1$$$, $$$3 \to 2$$$; $$$1$$$ 是唯一饱和的顶点,所以答案是 $$$11$$$;
- 使顶点 $$$2$$$ 饱和的最佳方法是让边 $$$1-2$$$ 无向,并将另一条边定向为 $$$3 \to 2$$$; $$$1$$$和$$$2$$$是饱和顶点,离开边$$$1-2$$$无向的成本是$$$10$$$,所以答案是$$$2$$$;
- 使顶点 $$$3$$$ 饱和的最佳方法是将边定向为 $$$2 \to 3$$$, $$$1 \to 2$$$; $$$3$$$ 是唯一饱和的顶点,因此答案是 $$$5$$$。
第二个示例中的最佳操作方案是沿循环引导边:$$$1 \to 2$$$、$$$2 \to 3$$$、$$$3 \to 4$$$ 和 $$$4 \to 1$$$。这样,所有顶点都饱和了。