史莱姆国有 $N$ 家餐厅，编号依次是 $1$ 到 $N$ 。每家餐厅的老板会有喜欢的几家餐厅（也可能没有）。如果你向某家餐厅的老板寻求建议，它会推荐如下的餐厅：

• 它自己的餐厅
• 它喜欢的餐厅
• 它喜欢的餐厅的老板喜欢的餐厅
• 它喜欢的餐厅的老板喜欢的餐厅的老板喜欢的餐厅
• …依次类推…

换言之，如果将餐厅看成点，“老板喜欢某家餐厅”的关系看成有向边，一家餐厅的老板会推荐的所有餐厅即为从该餐厅出发能到达的所有点。

好吃来到史莱姆国品尝美食。他决定按照如下规则拜访餐厅：

第一家餐厅可以任意选择。 此后每次选择餐厅时，必须从上一家餐厅的老板推荐的餐厅中选择。 好吃不会去此前已经去过的餐厅。 好吃可以在任意时刻结束这一流程。 每家餐厅的菜品有两种定价 $X_i$ 和 $Y_i$ 。当好吃到达餐厅 $i$ 时，老板会询问他去的上一家餐厅 $j$ 。如果好吃尚没有去过其它餐厅，或者餐厅 $j$ 不会被餐厅 $i$ 的老板推荐，好吃需要支付 $Y_i$ ；否则，即如果餐厅 $j$ 在餐厅 $i$ 的老板的推荐列表中，好吃需要支付 $X_i$ 。

设好吃最多能访问 $M$ 家餐厅。对每个 $1$ 到 $M$ 中的 $K$ ，好吃想知道，如果他恰好访问了 $K$ 家餐厅，至少需要花费多少钱。

输入格式

第一行，一个正整数 $N$ 。

接下来 $N$ 行，每行首先输入两个正整数 $X_i$ 和 $Y_i$ ，然后输入一个非负整数 $F_i$ ，代表餐厅 $i$ 的老板喜欢的餐厅数量；接下来 $F_i$ 个正整数，表示餐厅 $i$ 喜欢的餐厅编号。保证这些餐厅互不相同且不为 $i$ 。

输出格式

输出 $M$ 行，第 $K$ 行代表好吃恰好访问 $K$ 家餐厅的最小花费。

样例1

4
100 200 1 2
200 300 1 3
200 250 2 2 4
200 300 0

200
450
650
950

1号餐厅的老板推荐所有餐厅，2,3号餐厅的老板推荐2,3,4号餐厅，4号餐厅的老板只推荐他自己的餐厅。$K=1,2,3,4$ 时的最佳路线分别为 1, 1->3, 1->3->2, 1->3->2->4。

样例2

9
100 100 0
300 400 1 4
350 500 1 2
550 600 3 7 3 2
900 300 2 7 6
250 400 1 5
900 900 2 9 8
400 500 1 9
500 400 0

100
550
950
1450
2150
3050

样例3&4

见下发文件。

数据范围

保证 $1\le N\le 500,1\le X_i,Y_i\le 10^4$ 。