August 18. Kiev Summer School
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.
The first line contains an integer n (1 ≤ n ≤ 100 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 (0 ≤
ki ≤ n - 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.
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.
6 1 2 0 1 2 3 1 2 5 1 2 4 1 3 4 5
2 1 3 5 4 6