贝尔兰是今年国际大学生全能比赛的主办国!与冬季两项是两项运动的比赛类似,全能是多种运动的比赛。今年,有 $$$m$$$ 体育项目。此外,该活动还有 $$$n$$$ 参与者。运动项目编号从$$$1$$$到$$$m$$$,参与者编号从$$$1$$$到$$$n$$$。
一些参与者精通多种运动。给定一个二进制矩阵 $$$n \times m$$$,如果第 $$$i$$$ 个参与者擅长第 $$$j$$$ 项运动,则第 $$$i$$$ 行的第 $$$j$$$ 个字符为 1,否则为 0。还已知,对于每对参与者,至少存在一项运动,使得其中一个擅长该运动,而另一个则不擅长。
比赛项目顺序在开幕式上确定。从历史上看,这是由全能的随机数生成器完成的。滚动从 $$$1$$$ 到 $$$m$$$ 的随机数 $$$x$$$。然后,比赛从运动项目 $$$x$$$ 开始,然后进行运动项目 $$$(x \bmod m + 1)$$$,然后进行运动项目 $$$((x + 1) \bmod m + 1)$$$,依此类推。
每项运动的进行如下。如果所有剩余的参赛者(所有尚未被淘汰的参赛者)都不擅长该项目,则每个人都会进入下一项项目。否则,所有熟练的参赛者将进入下一项比赛,所有不熟练的参赛者将被淘汰出局。一旦比赛中只剩下一名参赛者,比赛就会结束,该参赛者将被宣布为获胜者。
作为比赛的组织者,你事先很好奇比赛可能出现的结果(不是说你要随机掷骰子,你怎么可能会这样想……)。对于每项运动 $$$x$$$,如果比赛以运动 $$$x$$$ 开始,则打印获胜者的索引。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 10^6$$$; $$$n \le 2^m$$$; $$$nm \le 2 \cdot 10^6$$$) – 分别是参与者人数和运动项目数量。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含一个二进制字符串,该字符串恰好由 $$$m$$$ 个字符 0 或 1 组成 - 第 $$$i$$$ 个参与者的技能组。如果第 $$$j$$$ 个字符为 1,则第 $$$i$$$ 个参与者擅长第 $$$j$$$ 项运动。如果为 0,则第 $$$i$$$ 参与者不擅长第 $$$j$$$ 运动。
对输入的附加约束:对于每对参与者,至少存在一项运动,其中一个人擅长该运动,而另一个则不擅长。换句话说,所有 $$$n$$$ 二进制字符串都是两两不同的。
输出
打印 $$$m$$$ 整数。对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$x$$$,如果比赛以 $$$x$$$ 运动开始,则打印获胜者的索引。
示例
输入 #1
3 5 10010 01100 10101
输出 #1
3 2 3 1 3