炼金术士 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
输出 #1
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
输出 #2
0 0 0 0 0 2 0 0 0 0 0 0 0 0
注意
在第一个样本的第一个测试用例中,最优的是:
- 通过购买并混合 $$$2$$$、$$$4$$$ 和 $$$5$$$ 获得第一种药水;
- 第二种药水只能通过购买获得;
- Nastya 已经拥有无限数量的第三类药水;
- 购买第四种药水比购买和混合其他药水更有利可图;
- 第五种药水只能通过购买获得。