There are $n$ restaurants in the Flower Kingdom. As a gourmet, you want to find the minimum cost $f_i$ to dine at $i$ restaurants in Flower City.

Each restaurant owner $i$ has a set of liked restaurants $v_1, v_2, \dots, v_{d_i}$, which does not include the restaurant itself.

The owner of restaurant $u$ recommends restaurant $v$ if and only if there exists a sequence $a_1, a_2, \dots, a_k$ such that $a_1 = u$, $a_k = v$, and for all $1 \le i < k$, the owner of restaurant $a_i$ likes restaurant $a_{i+1}$.

Your journey in the Flower Kingdom consists of the following events:

1. You can start your journey at any restaurant.
2. When you arrive at restaurant $i$, if you possess a dining record from a restaurant recommended by the owner of restaurant $i$, you must pay $x_i$; otherwise, you must pay $y_i$.
3. After you pay and dine at restaurant $i$, you receive a dining record from restaurant $i$. The next restaurant you visit must be a restaurant recommended by the current owner that you have not visited yet.
4. You may terminate your journey after dining at any restaurant.

Let $K$ be the maximum number of restaurants you can dine at. Find $f_1, f_2, \dots, f_K$, where $f_i$ is the minimum cost to dine at $i$ restaurants.

Input

The first line contains a positive integer $n$.

The next $n$ lines each contain $x_i, y_i, d_i, v_1, v_2, \dots, v_{d_i}$, representing the two prices for the restaurant, the number of restaurants the owner likes, and their indices.

Output

Output $K$ lines, each containing a number representing $f_i$.

Examples

Input 1

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

Output 1

200
450
650
950

Input 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

Output 2

100
550
950
1450
2150
3050

Input 3

See ex_trip3.in/ex_trip3.ans in the provided files.

Subtasks

Please note that the total score for this problem is 7 points.

For all data: $1 \le n \le 1000$, $1 \le x_i, y_i \le 10^4$, $0 \le d_i < n$.