G. Christopher Robin is Learning Object-oriented Programming
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Every object has its scalar value and its references list, possibly empty. The order of references in the list does matter. One can illustrate objects as follows:

Let us explain the picture. The left object has 50 as its scalar value. Its references list has three objects with scalar values 20, 30 and 40 (their references lists are empty); the right object has 120 as its scalar value and has references to the left object (illustrated as an embedded object) and an object with scalar value 30.

Two objects are equal if their illustrations are indistinguishable. Please note that objects may have circular references causing inability to illustrate the object on paper due to infinite embedding, but such illustrations are still virtually comparable.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of objects.

The following $$$n$$$ lines describe objects. Each description starts with an integer $$$s$$$ ($$$0 \leq s \leq 10^5$$$) — the scalar value of the object. Number $$$s$$$ is followed by an integer $$$m$$$ ($$$0 \leq m \leq 10$$$) and $$$m$$$ numbers forming the list of references. Each reference is a number of some object. Objects are numbered from $$$1$$$ to $$$n$$$ in the order they are given in the input.

Output

Output exactly $$$n$$$ lines.

On the $$$i$$$-th line output a positive integer — class number of the $$$i$$$-th object. Equal objects should belong to the same class, different objects should have different class numbers. The class numbers can be any integers from $$$1$$$ to $$$2^{63} - 1$$$, inclusive.

Example
Input
8
50 3 3 4 5
120 2 1 4
20 0
30 0
40 0
50 3 3 4 5
120 2 6 4
120 2 4 6
Output
10
12
3
4
5
10
12
11