UOI 终于考完了,现在你要以标准的宇宙通用语请获奖选手上台领奖。
现在邀请的这一批选手一共有 $n$ 个“人”。更准确地说,他们是一群脑回路几乎相同的外星蜜蜂,故而在比赛中取得了完全相同的分数。
宇宙通用语非常强大,一共有 $m$ 种符号。用这种语言表达每只外星蜜蜂的名字要么只需要一个符号,要么只需要两个符号。
你需要给这一批选手编写一份由他们所有人名字组成的获奖名单,再按顺序念出来。你可以做如下调整:
- 你可以调整这 $n$ 个名字的排列顺序;
- 由于外星蜜蜂的特殊文化,所有两个符号的名字无论你顺着念还是倒着念,指代的都是同一只蜜蜂。所以名单中每个两个符号的名字你既可以按顺序写也可以按逆序写。
- 可能存在名字相同的多只蜜蜂,但你仍然要读这个名字多次。
为了避免倾向性,你希望最后把名字顺次连起来是个回文串。也就是说,你要让名字串起来后的符号序列从左到右读和从右往左读没有区别。
测试数据保证有解。
输入格式
第一行两个正整数 $n,m$,分别表示选手个数和符号数。选手从 $1 \ldots 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\%$ 的数据,$1\leq n,m\leq 5\times 10^5$。令 $L=\sum_{i=1}^{n} l_i$。
子任务编号 | $n,m\le$ | 特殊性质 | 分值 |
---|---|---|---|
$1$ | $10$ | 无 | $15$ |
$2$ | $20$ | $20$ | |
$3$ | $5\times 10^5$ | $l_i=2$ | $10$ |
$4$ | $3000$ | 无 | $15$ |
$5$ | $5\times 10^5$ | $L$ 为偶数 | |
$6$ | $L$ 为奇数 | ||
$7$ | 无 | $10$ |
时间限制:$\texttt{2s}$
空间限制:$\texttt{512MB}$