{"raw_statement":[{"iden":"statement","content":"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.\n\n**Note that the memory limit is unusual!**"},{"iden":"input","content":"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.\n\nThen 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_.\n\nElements are not separated by whitespaces."},{"iden":"output","content":"Print the number of connected components consisting of 1's."},{"iden":"examples","content":"Input\n\n3 4\n1\nA\n8\n\nOutput\n\n3\n\nInput\n\n2 8\n5F\nE3\n\nOutput\n\n2\n\nInput\n\n1 4\n0\n\nOutput\n\n0"},{"iden":"note","content":"In the first example the matrix is:\n\n0001\n1010\n1000\n\nIt is clear that it has three components.\n\nThe second example:\n\n01011111\n11100011\n\nIt is clear that the number of components is 2.\n\nThere are no 1's in the third example, so the answer is 0."}],"translated_statement":[{"iden":"statement","content":"给定一个大小为 $n × m$ 的矩阵。矩阵的每个元素要么是 1，要么是 0。你需要计算由 1 组成的连通分量的数量。如果两个单元格有公共边，且这两个单元格中的元素均为 1，则它们属于同一个分量。\n\n*注意：内存限制非常特殊！*\n\n第一行包含两个数 $n$ 和 $m$（$1 ≤ n ≤ 212$，$4 ≤ m ≤ 214$），分别表示行数和列数。保证 $m$ 能被 4 整除。\n\n接下来是矩阵的表示形式。接下来的 $n$ 行中，每行包含一个十六进制数字（即这些数字可以表示为数字 $0$ 到 $9$ 或大写拉丁字母 $A$ 到 $F$）。每个数字的二进制表示对应该行中接下来的 $4$ 个矩阵元素。例如，如果给出数字 $B$，则对应的元素为 _1011_；如果给出数字 $5$，则对应的元素为 _0101_。\n\n元素之间没有空格分隔。\n\n请输出由 1 组成的连通分量的数量。\n\n第一个例子中，矩阵为：\n\n显然它有三个分量。\n\n第二个例子：\n\n显然分量的数量是 2。\n\n第三个例子中没有 1，因此答案为 0。\n\n"},{"iden":"input","content":"第一行包含两个数 $n$ 和 $m$（$1 ≤ n ≤ 212$，$4 ≤ m ≤ 214$），分别表示行数和列数。保证 $m$ 能被 4 整除。接下来是矩阵的表示形式。接下来的 $n$ 行中，每行包含一个十六进制数字（即这些数字可以表示为数字 $0$ 到 $9$ 或大写拉丁字母 $A$ 到 $F$）。每个数字的二进制表示对应该行中接下来的 $4$ 个矩阵元素。例如，如果给出数字 $B$，则对应的元素为 _1011_；如果给出数字 $5$，则对应的元素为 _0101_。元素之间没有空格分隔。"},{"iden":"output","content":"请输出由 1 组成的连通分量的数量。 "},{"iden":"examples","content":"输入3 41A8输出3输入2 85FE3输出2输入1 40输出0"},{"iden":"note","content":"在第一个例子中，矩阵为： 000110101000显然它有三个分量。第二个例子： 0101111111100011显然分量的数量是 2。第三个例子中没有 1，因此答案为 0。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n, m \\in \\mathbb{N} $ with $ 1 \\leq n \\leq 2^{12} $, $ 4 \\leq m \\leq 2^{14} $, and $ 4 \\mid m $.\n\nLet $ A \\in \\{0,1\\}^{n \\times m} $ be a binary matrix, where each row $ i \\in \\{1, \\dots, n\\} $ is encoded as $ \\frac{m}{4} $ hexadecimal digits. Each hexadecimal digit $ h \\in \\{0,1,\\dots,9,A,\\dots,F\\} $ corresponds to a 4-bit binary string $ b_1b_2b_3b_4 \\in \\{0,1\\}^4 $, such that $ h = \\sum_{j=1}^4 b_j \\cdot 2^{4-j} $, and these bits fill columns $ 4k+1 $ to $ 4k+4 $ of row $ i $, for $ k = 0, \\dots, \\frac{m}{4}-1 $.\n\nDefine the adjacency relation: two cells $ (i,j) $ and $ (i',j') $ are adjacent if $ |i - i'| + |j - j'| = 1 $ and $ A_{i,j} = A_{i',j'} = 1 $.\n\nA connected component is a maximal set of cells $ S \\subseteq \\{1,\\dots,n\\} \\times \\{1,\\dots,m\\} $ such that for every pair $ (i,j), (i',j') \\in S $, there exists a path of adjacent cells within $ S $ connecting them, and $ A_{p,q} = 1 $ for all $ (p,q) \\in S $.\n\n**Objective:** Compute the number of connected components of 1's in $ A $.","simple_statement":null,"has_page_source":false}