← 返回题目列表

Codeforces · 1851/E

E. 娜斯佳和魔药

中文机器翻译题面 查看原题

炼金术士 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 已经拥有无限数量的第三类药水;
- 购买第四种药水比购买和混合其他药水更有利可图;
- 第五种药水只能通过购买获得。