G. Выбираем направления
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный связный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. $$$k$$$ вершин этого графа — особенные.

Вы должны ориентировать каждое ребро графа (или оставить некоторые ребра неориентированными за дополнительную плату). Вы можете оставить $$$i$$$-е ребро неориентированным, заплатив $$$w_i$$$ монет, или бесплатно ориентировать его.

Назовем вершину насыщенной, если она достижима из всех особенных вершин по ребрам графа (если ребро осталось неориентированным, по нему можно ходить в любом направлении). После того, как вы выберете направления для ребер графа (возможно, оставив некоторые неориентированными), вы получите $$$c_i$$$ монет за каждую насыщенную вершину $$$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$$$ насыщенной.

Примеры
Входные данные
3 2 2
1 3
11 1 5
10 10
1 2
2 3
Выходные данные
11 2 5
Входные данные
4 4 4
1 2 3 4
1 5 7 8
100 100 100 100
1 2
2 3
3 4
1 4
Выходные данные
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$$$. Таким образом, все вершины будут насыщенными.