CF884E.Binary Matrix

You are given a matrix of size n × m. Each element of the matrix is either 1 or 0. You have to determine the number of connected components consisting of 1's. Two cells belong to the same component if they have a common border, and both elements in these cells are 1's.

Note that the memory limit is unusual!

你将得到一个大小为 $n \times m$ 的矩阵。矩阵中的每个元素均为 $1$ 或 $0$。你需要确定由 $1$ 构成的连通块的数量。若两个格子具有公共边，且这两个格子中的元素均为 $1$，则它们属于同一连通块。

注意：内存限制非常特殊！

The first line contains two numbers n and m (1 ≤ n ≤ 212, 4 ≤ m ≤ 214) — the number of rows and columns, respectively. It is guaranteed that m is divisible by 4.

Then the representation of matrix follows. Each of n next lines contains one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from 0 to 9 or as uppercase Latin letters from A to F). Binary representation of each of these numbers denotes next 4 elements of the matrix in the corresponding row. For example, if the number B is given, then the corresponding elements are 1011, and if the number is 5, then the corresponding elements are 0101.

Elements are not separated by whitespaces.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2^{12}$，$4 \leq m \leq 2^{14}$），分别表示矩阵的行数和列数。保证 $m$ 能被 $4$ 整除。

随后是矩阵的表示。接下来的 $n$ 行中，每行包含 个一位十六进制数字（即这些数字可以表示为数字 $0$ 至 $9$ 或大写拉丁字母 $A$ 至 $F$）。每个十六进制数字的二进制表示对应所在行的接下来 $4$ 个矩阵元素。例如，若给出数字 $B$，则对应元素为 $1011$；若给出数字 $5$，则对应元素为 $0101$。

这些元素之间不以空格分隔。

Print the number of connected components consisting of 1's.

输出由 1 组成的连通分量的数量。

In the first example the matrix is:

0001
1010
1000

It is clear that it has three components.

The second example:

01011111
11100011

It is clear that the number of components is 2.

There are no 1's in the third example, so the answer is 0.

第一个例子中的矩阵是：

0001
1010
1000

显然，它包含三个连通分量。

第二个例子：

01011111
11100011

显然，连通分量的数目为 2。

第三个例子中没有 1，因此答案为 0。