UOI 终于考完了，现在你要以标准的宇宙通用语请获奖选手上台领奖。

现在邀请的这一批选手一共有 $n$ 个“人”。更准确地说，他们是一群脑回路几乎相同的外星蜜蜂，故而在比赛中取得了完全相同的分数。

宇宙通用语非常强大，一共有 $m$ 种符号。用这种语言表达每只外星蜜蜂的名字要么只需要一个符号，要么只需要两个符号。

你需要给这一批选手编写一份由他们所有人名字组成的获奖名单，再按顺序念出来。你可以做如下调整：

1. 你可以调整这 $n$ 个名字的排列顺序；
2. 由于外星蜜蜂的特殊文化，所有两个符号的名字无论你顺着念还是倒着念，指代的都是同一只蜜蜂。所以名单中每个两个符号的名字你既可以按顺序写也可以按逆序写。
3. 可能存在名字相同的多只蜜蜂，但你仍然要读这个名字多次。

为了避免倾向性，你希望最后把名字顺次连起来是个回文串。也就是说，你要让名字串起来后的符号序列从左到右读和从右往左读没有区别。

测试数据保证有解。

输入格式

第一行两个正整数 $n,m$，分别表示选手个数和符号数。选手从 $1\dots n$ 编号。

接下来 $n$ 行，第 $i$ 行先输入一个正整数 $l_i\in \{1,2\}$ 表示 $i$ 号选手的名字长度，下面 $l_i$ 个 $1\sim m$ 间的整数，表示第 $i$ 个人的名字。

输出格式

第一行输出由 $n$ 个 $1\sim n$ 的整数组成的排列，第 $i$ 个为 $p_i$，表示最后名单的第 $i$ 个选手是 $p_i$ 号选手。

下一行输出 $n$ 个 $01$ 整数，第 $i$ 个为 $0$ 表示 $p_i$ 号选手的名字正着写（与输入顺序一致），为 $1$ 表示倒着写。

注意，如果 $p_i$ 号选手名字长度为 $1$，你可以随便输出 $0$ 或 $1$。如果有多种合法的获奖名单，你可以任意输出一个。

样例一

input

4 2
2 1 1
2 1 2
1 1
1 2

output

4 1 3 2 
0 1 0 0 

explanation

样例一输出对应的回文串是 $211112$。

样例二

input

2 2
1 1
2 1 2

output

1 2 
0 1 

explanation

样例二输出对应的回文串是 $121$。

样例三

见附加文件中 ex_namelist3.in 与 ex_namelist3.out，该组样例满足子任务 5 的性质。

样例四

见附加文件中 ex_namelist4.in 与 ex_namelist4.out，该组样例满足子任务 6 的性质。

样例五

见附加文件中 ex_namelist5.in 与 ex_namelist5.out，该组样例满足子任务 5 的性质。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le n,m\le 5\times {10}^5$。令 $L=\sum _{i=1}^n{l}_i$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$