Алхимик Настя очень любит смешивать зелья. Всего алхимии известно \(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\) чисел — минимальное число монет, которое нужно потратить, чтобы получить зелье каждого вида.
Примечание
В первом наборе первого примера оптимально:
- Получить зелье первого типа купив и смешав \(2\), \(4\) и \(5\);
- зелье второго типа можно получить только купив его;
- у Насти уже есть неограниченное число зелий третьего типа;
- зелье четвертого типа выгоднее купить, чем купить и смешать другие зелья;
- зелье пятого типа можно получить только купив его;
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|