Description

布尔可满足性问题（SAT）问题的定义如下：

有 $n$ 个变量 $x_1,\dots,x_n$，每个变量可以取值 0（假）或 1（真），每个变量有正文字 $x_i$ 与负文字 $\bar{x_i}$ 两种形式。其中正文字 $x_i$ 的值与变量相同，负文字 $\bar{x_i}$ 的值与变量相反。

一个子句为若干个文字相析取，即 $C_i=x_{a_{i,1}}\vee \dots \vee x_{a_{i,p}}\vee \bar{x}_{b_{i,1}}\vee \dots \vee \bar{x}_{b_{i,q}},1\leq a_{i,j},b_{i,k} \leq n$。这些文字中有任意一个文字的取值为 1，则该子句的值为 1；反之若所有文字的取值都为 0，则该子句的值为 0。

一个合取范式（CNF）为 $m$ 个子句 $C_1,\dots,C_m$ 相合取，即 $C=C_1\wedge \dots \wedge C_m$。若所有子句的取值为 1，则该 CNF 的值为 1；反之若任意一个子句的取值为 0，则该 CNF 的值为 0。

SAT 问题即给出一个 CNF，问存不存在一种对变量的赋值，使该 CNF 的值为 1。

Bob Wang 知道要找到一组让所有子句都为真的变量赋值是一件很困难的事情，因此对于给出的 CNF $C_1\wedge \dots \wedge C_m$，Bob Wang 只需要找出一种变量赋值，使得至少 $\lceil \frac{m}{2} \rceil$ 个子句的赋值为 1。可以证明满足要求的赋值一定存在。

Input

第一行两个整数 $n,m$（$1\leq n,m\leq 10^6$），表示变量个数以及子句个数。

接下来 $m$ 组数据，描述子句。

对于第 $i$ 个子句，第一行一个整数 $c_i$（$1\leq c_i\leq 10^6$），表示文字的数量。接下来 $c_i$ 行，每行两个整数 $x,y$，描述该子句包含的文字。其中 $x$ 表示变量编号，$y=1$ 表示正文字 $x$，$y=0$ 表示负文字 $\bar{x}$。

保证 $\sum_{i=1}^{m}c_i\leq 10^6$。

Output

一行 $n$ 个整数，表示变量的赋值。其中 $x_i=1$ 表示第 $i$ 个变量赋值为 1，$x_i=0$ 表示第 $i$ 个变量赋值为 0。输出使至少 $\lceil \frac{m}{2} \rceil$ 个子句的赋值为 1 的任意一组赋值即可。

Samples

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

0 1 0 1

Note

样例表示的子句为 $C_1=x_1$，$C_2=x_2$，$C_3=\bar{x_3}$，$C_4=x_4$，$C_5=x_1\vee x_3$，容易证明 $x_1=0,x_2=1,x_3=0,x_4=1$ 是符合题意的一组赋值。

Resources

The 23rd UESTC Programming Contest Preliminary