给定一个大小为 n × m 的矩阵。矩阵的每个元素要么是 1,要么是 0。您必须确定由 1 组成的连通分量的数量。如果两个单元格具有共同边框,并且这些单元格中的两个元素均为 1,则它们属于同一组件。
注意内存限制不寻常!
输入
第一行包含两个数字 n 和 m (1 ≤ n ≤ 212, 4 ≤ m ≤ 214) — 分别是行数和列数。保证m能被4整除。
那么矩阵的表示如下。接下来的 n 行中的每一行都包含 $$\frac{m}{4}$$ 一位十六进制数字(也就是说,这些数字可以表示为 0 到 9 的数字,也可以表示为 A 到 F 的大写拉丁字母)。每个数字的二进制表示表示相应行中矩阵的接下来 4 个元素。例如,如果给出数字B,那么对应的元素是1011,如果数字是5,那么对应的元素是0101。
元素不以空格分隔。
输出
打印由 1 组成的连接分量的数量。
示例
输入 #1
3 4 1 A 8
输出 #1
3
输入 #2
2 8 5F E3
输出 #2
2
输入 #3
1 4 0
输出 #3
0
注意
在第一个示例中,矩阵为:
很明显,它由三个组成部分组成。
第二个例子:
显然,组件数量为 2。
第三个示例中没有 1,因此答案为 0。