e-olymp
Competitions

Topological sort

Sections in Makhovniki

Little Peter loves computers and wants to learn programming. In the small town of Makhovniki, where he lives, there is a network of programming sections on a wide variety of subjects. When Peter went to sign up, he saw a large list of n sections. Peter wants to be a comprehensively developed person, so he was going to learn in all these sections. But when he was going to sign up for all the classes at once, it turned out that everything was not so simple. First of all, at one time it is allowed to study only in one of these n sections. Secondly, some teachers put forward input requirements for the knowledge of students, consisting in the knowledge of the courses of some other sections!

Peter wants to become a great programmer, so such trifles do not stop him. Indeed, all he needs is just to make up the correct order for visiting sections, in order to meet all the input requirements - this is a very simple task, accessible even to a very inexperienced programmer.

Before sitting down to make up the order of visiting the sections, Peter carefully read the conditions of study and found another important point. It turns out that in order to attract schoolchildren, in all sections there is a system of encouraging pupils with candies. This means that at the end of the next round, the student is given several boxes of chocolates, more and more with each passing section. On the other hand, in each section the number of candies in a box is different, depending on the complexity of the course. More specifically - for passing the i-th section, if this section goes in the general list with the number j, the student is given as much ni-1 * j candies - such generous people are programmers. Peter decided to combine the useful with the pleasant - now he wants to choose such an order of visiting sections so that to get as many candies as possible, however this task is no longer within his power. Help the future great man find such an order.

Input

The first line contains an integer n (1n100 000) - the number of sections in Makhovniki. The following n lines contain descriptions of the input requirements for the sections, in the order in which they appear in the general list. The i-th line first contains an integer ki (0kin - 1) - the number of sections where you need to learn before signing up to the i-th section, and then ki numbers of these sections. The sum ki does not exceed 200 000. It is guaranteed that it is possible to visit all these sections in a certain order, without violating the conditions of the visit.

Output

Print n space separated numbers - the order in which Peter needs to attend the sections in order to eat as many candies as possible.

Explanation to the sample

By visiting the sections in the specified order, Peter will receive 60 * 2 + 61 * 1 + 62 * 3 + 63 * 5 + 64 * 4 + 65 * 6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 candies.

prb4861.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
Output example #1
2 1 3 5 4 6
Source 2013 Moscow city informatics olympiad for 6-9 classes, Moscow, February 3, Problem E