题目描述

花国的餐厅有 $n$ 个，作为美食家的你希望用最少的钱 $f_i$ 吃到花城的 $i$ 个餐厅。

这里第 $i$ 个餐厅老板有若干个喜欢的餐厅 $v_1,v_2,\cdots,v_{d_i}$，当然这里不包括自己。

第 $u$ 个餐厅的老板会推荐第 $v$ 个餐厅当且仅当：存在一个序列 $a_1,a_2,\cdots, a_k, a_1=u,a_k=v, \forall 1 \le i < k$, 第 $a_i$ 个餐厅的老板 喜欢 第 $a_{i+1}$ 个餐厅。

对于你在花国的旅程，会经过以下事件。

1. 你可以从任意餐厅开始你的旅程
2. 当你到达一个餐厅 $i$，如果你持有这个餐厅老板推荐的店的用餐记录，你必须支付 $x_i$ 块钱，否则需要支付 $y_i$ 块钱。
3. 当你在餐厅 $i$ 支付后并餐过后，你会获得一个来自第 $i$ 个店的用餐记录，并且你去往的下一个餐厅必须是当前老板推荐的没去过的餐厅。
4. 你可以在在任意餐厅用餐后终止旅程。

令 $K$ 表示你最多可以吃到多少个餐厅，求 $f_1, f_2, \cdots, f_K$，表示吃到了 $i$ 个餐厅的最小花费。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，输入 $x_i,y_i,d_i,v_1,v_2,\cdots,v_{d_i}$，表示这个餐厅的两种价钱，老板喜欢的餐厅个数，以及它们的编号。

输出格式

输出 $K$ 行，每行一个数表示 $f_i$。

样例数据

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

样例 3

见下发文件中的 ex_trip3.in/ex_trip3.ans。

子任务

请注意，本题的满分为 75 分。

对于所有数据：保证 $1\le n \le 1000,1\le x_i,y_i\le 10^4,0\le d_i < n$。