D. Christmas Children Circle
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$n$$$ children numbered $$$1, 2, \dots, n$$$. They stand in a circle. Each child has a bag with non-empty set of distinct positive integers.

As a part of Christmas celebration, children want to play a game of the following rules:

  1. Each child has to take exactly one integer from her bag.
  2. Each child passes her integer to the next one, so child $$$1$$$ passes her number to child $$$2$$$, child $$$2$$$ passes her number to child $$$3$$$, and so one, child $$$n$$$ passes her number to child $$$1$$$.
  3. Each child puts her newly acquired number back in her bag.
  4. The procedure described above should be performed exactly once. Children win if after they are done with passing integers, each bag contains only distinct integers, i.e. no bag contains the same integer twice.

Help children win the game or find out that this is impossible.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 500\,000$$$), the number of children.

The $$$i$$$-th of the following $$$n$$$ lines contains the description of the $$$i$$$-th child' bag. The first integer of each description is $$$k_i$$$ ($$$1 \leq k_i$$$) — the number of integers in the bag. Then follow $$$k_i$$$ integers $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq 10^{9}$$$), which describe the content of the bag.

The total size of all bags is constrained as $$$\sum k_i \leq 500\,000$$$.

It is guaranteed that all integers in each particular bag are distinct.

Output

If there is no way for children to win the game, print -1 in the only line of the output. Otherwise, print $$$n$$$ integers, $$$x_1, x_2, \dots, x_n$$$, where $$$x_i$$$ is the integer that the $$$i$$$-th child must pull out of her bag and pass to the next child in order to succeed in the game.

Example
Input
3
2 1 4
2 4 3
2 3 1
Output
1 4 1