在 Luka 的城市里有 $N$ 家餐厅，编号从 $1$ 到 $N$，每家餐厅都有其特色。餐厅老板们也有自己喜欢光顾的餐厅。如果我们向某位餐厅老板询问推荐，他不仅会推荐自己的餐厅，还会推荐他喜欢的餐厅，以及那些餐厅老板所推荐的所有餐厅。

下表展示了一个包含四家餐厅的示例：

Luka 计划按以下方式参观几家餐厅： 第一家餐厅可以任意选择。 之后每一家餐厅的选择方式是：询问当前餐厅的老板获取推荐，并从推荐的餐厅中选择一家他尚未去过的餐厅。 * Luka 可以随时结束参观。

每家餐厅 $A$ 的主菜有两种价格 $X_A$ 和 $Y_A$。进入餐厅时，老板会询问 Luka 是谁推荐他来到这家餐厅的。如果推荐人是餐厅 $B$ 的老板，那么 Luka 需要支付： 如果餐厅 $A$ 的老板推荐了餐厅 $B$，则支付 $X_A$ 库纳； 否则，支付 $Y_A$ 库纳。Luka 在第一家餐厅也支付此金额（注：第一家餐厅视为由“无”推荐，即支付 $Y_A$）。

设 $K$ 为 Luka 可以参观的最多餐厅数量。对于 $1$ 到 $K$ 之间的每个数字 $k$，需要计算 Luka 参观恰好 $k$ 家餐厅所需的最少库纳金额。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示餐厅数量。 接下来的 $N$ 行，每行包含若干整数。 第 $i$ 行的前两个数字是主菜价格 $X_i, Y_i$ ($1 \le X_i, Y_i \le 10000$)，第三个数字 $O_i$ ($0 \le O_i < N$) 是餐厅老板 $i$ 喜欢的餐厅数量。接下来的 $O_i$ 个数字表示他喜欢的餐厅编号；这些编号互不相同且均不等于 $i$。

输出格式

如果 $K$ 是 Luka 可以参观的最多餐厅数量，则需要输出 $K$ 行。第 $k$ 行应输出 Luka 参观恰好 $k$ 家餐厅所需支付的最少库纳金额。

样例

样例输入 1

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

样例输出 1

200 
450 
650 
950

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

样例输出 2

100 
550 
950 
1450 
2150 
3050

说明

第一个测试样例的解释： 参观一家餐厅的最便宜方式是参观餐厅 1 (200 kn)。 参观两家餐厅的最便宜方式是参观餐厅 3 (250 kn)，然后是餐厅 2 (200 kn)。 参观三家餐厅的最便宜方式是参观餐厅 1 (200 kn)，餐厅 3 (250 kn)，最后是餐厅 2 (200 kn)。 参观四家餐厅的最便宜方式是参观餐厅 1 (200 kn)，餐厅 3 (250 kn)，餐厅 2 (200 kn)，最后是餐厅 4 (300 kn)。