Problem Statement

A kingdom has $N$ towns, numbered from $1$ to $N$. In town $i$ ( $i = 1, 2, \ldots, N$ ) there are $X_i$ houses, and at this point all that is known is that $0 \leq X_i < 2^{30}$. The king of this country wants to know how many houses there are in each town.

One day, $M$ travelers visited this country. The $j$-th traveler ( $j = 1, 2, \ldots, M$ ) went around $A_j$ of the towns in the kingdom, whose numbers were $B_{j1}, B_{j2}, \ldots, B_{jA_j}$. When leaving the kingdom, each traveler $j$ reported the following 2 things to the king.

• The number of towns they went around, $A_j$, and their numbers $B_{j1}, B_{j2}, \ldots, B_{jA_j}$.
• The value $Y_j$, the total XOR of the numbers of houses over the $A_j$ towns they went around. That is, $$Y_j = X_{B_{j1}} \oplus X_{B_{j2}} \oplus \cdots \oplus X_{B_{jA_j}}$$

The king decided to determine the numbers of houses $X_1, X_2, \ldots, X_N$ of the towns based on the reports of the $M$ travelers.

However, some of the travelers may have made false reports.

If there exists a tuple of values $X_1, X_2, \ldots, X_N$ consistent with all the reports of the $M$ travelers, output one such tuple. Otherwise (if the travelers' reports are contradictory), output $-1$.

Input

$N$ $M$
$A_1$
$B_{11}$ $B_{12}$ $\ldots$ $B_{1A_1}$
$Y_1$
$A_2$
$B_{21}$ $B_{22}$ $\ldots$ $B_{2A_2}$
$Y_2$
$\vdots$
$A_M$
$B_{M1}$ $B_{M2}$ $\ldots$ $B_{MA_M}$
$Y_M$

Constraints:

• All inputs are integers.
• $1 \leq N \leq 50$
• $1 \leq M \leq 10^4$
• For each $j = 1, 2, \ldots, M$:
  • $1 \leq A_j \leq N$
  • $1 \leq B_{j1} < B_{j2} < \cdots < B_{jA_j} \leq N$
  • $0 \leq Y_i < 2^{30}$

Output

If there is no contradiction, output, separated by newlines,

$X_1$
$X_2$
$\vdots$
$X_N$

If there is a contradiction, output

-1

Sample

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

2
1
4

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

-1