E. Настя и зелья
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алхимик Настя очень любит смешивать зелья. Всего алхимии известно $$$n$$$ видов зелий, одно зелье вида $$$i$$$ можно купить за $$$c_i$$$ монет.

Любой вид зелий можно получить не более чем одним способом, путём смешивания из нескольких других. Зелья, которые используются в смешивании при этом потратятся. Причём ни одно зелье нельзя получить из самого себя путём одного или нескольких смешиваний.

Как опытный алхимик, Настя имеет зелья $$$k$$$ видов $$$p_1, p_2, \dots, p_k$$$ в неограниченных количествах, но не знает какое захочет получить следующим. Чтобы определиться, она просит вас для всех $$$1 \le i \le n$$$ узнать, какое минимальное число монет нужно потратить, чтобы следующим получить зелье вида $$$i$$$.

Входные данные

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов.

В первой строке набора содержится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$) — количество видов зелий всего и количество видов зелий, которые есть у Насти.

Во второй строке набора содержатся $$$n$$$ чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) – стоимости покупки зелий.

В третьей строке набора содержатся $$$k$$$ различных целых чисел $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_i \le n$$$) — номера зелий, которые уже есть у Насти в неограниченных количествах.

Далее следуют $$$n$$$ строк, описывающих способы получения зелий смешиванием.

Каждая строка начинается с числа $$$m_i$$$ ($$$0 \le m_i < n$$$) — количество зелий, необходимое для смешивания зелья вида $$$i$$$ ($$$1 \le i \le n$$$).

Дальше строка содержит $$$m_i$$$ различных целых чисел $$$e_1, e_2, \dots, e_{m_i}$$$ ($$$1 \le e_j \le n$$$, $$$e_j \ne i$$$) — номера зелий необходимых для смешивания зелья вида $$$i$$$. Если этот список пуст, то зелье вида $$$i$$$ можно только купить.

Гарантируется, что ни одно зелье нельзя получить из самого себя путём одного или нескольких смешиваний.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Аналогично гарантируется, что сумма значений $$$m_i$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ чисел — минимальное число монет, которое нужно потратить, чтобы получить зелье каждого вида.

Примеры
Входные данные
4
5 1
30 8 3 5 10
3
3 2 4 5
0 
0 
2 3 5
0 
3 2
5 143 3
1 3
1 2
0 
2 1 2
5 1
5 4 1 3 4
2
2 4 5
3 3 5 4
2 1 4
1 5
0 
4 2
1 1 5 4
2 4
3 2 4 3
0 
2 2 4
1 2
Выходные данные
23 8 0 5 10 
0 143 0 
5 0 1 3 4 
0 0 0 0
Входные данные
3
6 3
5 5 4 5 2 2
3 4 5
2 2 5
1 5
3 4 1 6
4 2 6 1 5
0 
0 
6 2
1 4 4 1 5 2
3 6
4 6 3 4 5
4 6 5 3 4
0 
1 5
1 6
0 
2 1
4 3
1
0 
1 1
Выходные данные
0 0 0 0 0 2 
0 0 0 0 0 0 
0 0
Примечание

В первом наборе первого примера оптимально:

  • Получить зелье первого типа купив и смешав $$$2$$$, $$$4$$$ и $$$5$$$;
  • зелье второго типа можно получить только купив его;
  • у Насти уже есть неограниченное число зелий третьего типа;
  • зелье четвертого типа выгоднее купить, чем купить и смешать другие зелья;
  • зелье пятого типа можно получить только купив его;