Background

The artistic youth JYY is very fond of watching opera performances. JYY knows the appearances and names of all the actors, but cannot match them correctly. JYY hopes that one day he will be able to identify exactly who each actor is.

The JSOI opera troupe has $N$ actors and has held $M$ performances. All actors are numbered from $1$ to $N$, and the $i$-th performance involves $K_i$ actors.

JYY has seen photos of all $N$ actors (meaning he knows the appearances of these $N$ actors) and has seen the list of actors (meaning he knows the names of these $N$ actors, assuming no two actors share the same name). He has also carefully observed all $M$ performances: for each performance, JYY knows which actors participated and can distinguish their appearances.

Now, JYY wants to know, after watching these $M$ performances, whether he can match the names and appearances of all the actors.

Input

The first line contains two positive integers $N$ and $M$.

The next $M$ lines each start with an integer $K_i$, followed by $K_i$ distinct integers between $1$ and $N$, representing the IDs of the actors who participated in that performance.

Output

Output a single line containing $N$ integers. The $i$-th integer $a_i$ represents the performance number after which JYY can match the name and appearance of the actor with ID $i$. If JYY still cannot identify the actor after $M$ performances, $a_i$ should be $0$.

Examples

Input 1

5 3
3 1 2 3
3 2 3 1
2 1 3

Output 1

0 3 0 0 0

Note

For the first example, the participants in the first two performances are the same, while the third performance excludes actor 2. By comparing these, JYY can identify actor 2 after the third performance.

Input 2

4 3
1 1
1 3
1 2

Output 2

1 3 2 3

Note

For the second example, each performance allows identifying one actor's appearance, and actor 4 is the only one who never participated in any performance. Since JYY knows the appearances of all actors from the beginning, JYY can also confirm the appearance of actor 4 after the third performance.

Subtasks

For $30\%$ of the data, $N, M, \sum_i K_i \leq 100$;

For $50\%$ of the data, $N, M, \sum_i K_i \leq 1\,000$;

For $100\%$ of the data, $N, M, \sum_i K_i \leq 100\,000$;