In Luka's city, there are $N$ restaurants labeled with numbers from 1 to $N$, and there is something for everyone. Restaurant owners also have their own favorite restaurants that they enjoy visiting. If we ask a restaurant owner for a recommendation, they will, in addition to their own restaurant, recommend their favorite restaurants, as well as all the restaurants that would be recommended by their owners.

The table below shows an example with four restaurants:

Luka plans to visit several restaurants in the following way: The first restaurant will be chosen arbitrarily. Each subsequent restaurant will be chosen by asking the owner of the current restaurant for a recommendation, and then choosing one from the recommended restaurants that he has not yet visited. * Luka can finish his tour of restaurants at any time.

Each restaurant $A$ has two prices $X_A$ and $Y_A$ for the main menu. Upon entering a restaurant, the owner will ask Luka who recommended his restaurant to him. If that person is the owner of restaurant $B$, then Luka will pay: $X_A$ kuna, if the owner of restaurant $A$ recommends restaurant $B$, $Y_A$ kuna, otherwise. Luka also pays this amount at the first restaurant.

Let $K$ be the maximum number of restaurants Luka can visit in this way. For every number $k$ between 1 and $K$, it is necessary to calculate the minimum number of kuna Luka needs if he wants to visit exactly $k$ restaurants.

Input

The first line contains an integer $N$ ($1 \le N \le 1000$), the number of restaurants. In each of the following $N$ lines, there are several integers. The first two numbers in the $i$-th line are the prices of the main menu $X_i, Y_i$ ($1 \le X_i, Y_i \le 10000$), while the third number is $O_i$ ($0 \le O_i < N$), the number of restaurants favorite to the owner of restaurant $i$. The remaining $O_i$ numbers represent the labels of their favorite restaurants; these labels are mutually distinct and none of them is equal to $i$.

Output

If $K$ is the maximum number of restaurants Luka can visit, then it is necessary to print $K$ lines. In the $k$-th line, it is necessary to print the minimum number of kuna Luka must pay to visit exactly $k$ restaurants.

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

Note

Explanation of the first test example: The cheapest way to visit one restaurant is to visit restaurant 1 (200 kn). The cheapest way to visit two restaurants is to visit restaurant 3 (250 kn), and then restaurant 2 (200 kn). The cheapest way to visit three restaurants is to visit restaurant 1 (200 kn), restaurant 3 (250 kn), and finally restaurant 2 (200 kn). The cheapest way to visit four restaurants is to visit restaurant 1 (200 kn), restaurant 3 (250 kn), restaurant 2 (200 kn), and finally restaurant 4 (300 kn).