这是一个交互式问题。

Polycarp 是一家名为 ¡¡Abacus¿¿ 公司的软件工程师。每天他都需要生成 $N$ 个长度为 $M$ 的二进制字符串。

有一天，Polycarp 感到无聊，决定玩一个游戏：当他生成下一个二进制字符串时，他将其视为二进制表示的数字（该数字可能包含前导零）。然后，他将该数字与之前生成的每个字符串（同样视为数字）相加，并统计有多少次加法的结果无法用 $M$ 位或更少的二进制位表示。

由于 Polycarp 不太擅长二进制加法，他请求你帮助他。

交互

在交互过程开始时，评测程序会向你的程序发送两个正整数 $N$ 和 $M$（$1 \le N \times M \le 10^5$），分别代表 Polycarp 生成的二进制字符串数量和要求的长度。

随后，以下过程重复 $N$ 次：评测程序在新的一行向你的程序发送下一个长度为 $M$ 的二进制字符串，你的程序必须在新的一行输出一个整数，表示该字符串（视为二进制表示的整数）与之前生成的任一字符串相加后，结果超过 $M$ 位二进制位能表示的范围的次数。

当处理完所有 $N$ 个字符串后，你的程序必须以退出代码 0 退出，否则交互过程将导致错误（即使所有答案都是正确的）。

样例

样例输入 1

5 2
01
10
11
00
10

样例输出 1

0
0
2
0
2

样例输入 2

5 3
110
001
101
110
011

样例输出 2

0
0
1
2
3

说明

请记住在每次打印答案后刷新输出缓冲区，例如：

• 对于 Pascal：flush(output);
• 对于 C++：fflush(stdout) 或 cout.flush();
• 对于 Java：System.out.flush();
• 对于 Python：使用 sys 库中的 sys.stdout.flush()；