题目描述

炼金术士 Nastya 喜欢混合药剂。总共有 $n$ 种药剂，第 $i$ 种药剂可以花费 $c_i$ 枚金币直接购买。

每种药剂至多可以通过一种方式由其他若干种药剂混合而成。混合过程中用到的药剂会被消耗。此外，没有任何一种药剂能够通过一次或多次混合过程从自身得到。

作为经验丰富的炼金术士，Nastya 已经无限拥有 $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$）—— 药剂的总种类数以及 Nastya 已经拥有的药剂种类数。

第二行包含 $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$）—— Nastya 已经无限拥有的药剂的编号。

接下来有 $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$ 个整数 —— Nastya 为了获得每种药剂所需花费的最少金币数。

样例

样例 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 

样例解释（第一个样例的第一个测试用例）

最优方案如下：

• 第一种药剂：通过购买并混合第 $2$、$4$、$5$ 种药剂来获得；
• 第二种药剂：只能通过购买获得；
• 第三种药剂：Nastya 已经无限拥有；
• 第四种药剂：直接购买比购买材料再混合更划算；
• 第五种药剂：只能通过购买获得。