A11440. 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!

The first line contains two numbers $n$ and $m$ ( $1<=n<=2^{12}$ , $4<=m<=2^{14}$ ) — 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.

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

In the first example the matrix is:

<br></br>0001<br></br>1010<br></br>1000<br></br>It is clear that it has three components.

The second example:

<br></br>01011111<br></br>11100011<br></br>It is clear that the number of components is 2.

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