I. 多项全能
每次测试的时间限制：3 秒
每次测试的内存限制：512 兆字节

今年，$Berland$ 是国际大学生多项全能锦标赛的主办国！与两项运动组成的冬季两项类似，多项全能是许多运动的竞赛。今年有 $m$ 个运动项目。此外，有 $n$ 名参赛者。运动编号为 $1$ 到 $m$，参赛者编号为 $1$ 到 $n$。

有些参赛者擅长多项运动。给你一个 $n \times m$ 的二进制矩阵，其中第 $i$ 行的第 $j$ 个字符为 $1$ 表示第 $i$ 个参赛者擅长第 $j$ 项运动，否则为 $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 2m$；$nm \le 2 \cdot 10^6$）—— 参赛者人数和运动项目数。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 的二进制字符串——第 $i$ 个参赛者的技能集。如果第 $j$ 个字符是 $1$，则第 $i$ 个参赛者擅长第 $j$ 项运动；如果是 $0$，则不擅长。

输入的额外约束：对于每一对参赛者，至少存在一项运动，使得其中一人擅长而另一人不擅长。换句话说，所有 $n$ 个二进制字符串是两两不同的。

输出
输出 $m$ 个整数。对于每个 $x$ 从 $1$ 到 $m$，如果比赛从第 $x$ 项运动开始，输出获胜者的编号。

示例

输入

3 5
10010
01100
10101

输出

3 2 3 1 3