406561: GYM102441 C Partial Sums

You have a matrix $$$A_0$$$, consisting of $$$n$$$ rows and $$$m$$$ columns. Rows and columns are numbered with consecutive natural numbers starting from $$$1$$$. The elements of the matrix are zeros and ones. Denote the element of this matrix at the intersection of the $$$i$$$ row and $$$j$$$ column as $$$A_0[i, j]$$$.

Consider an infinite sequence of matrices $$$A_k$$$. The matrix $$$A_k$$$ ($$$k > 0$$$) also consists of $$$n$$$ rows and $$$m$$$ columns and it is a matrix of partial sums for the matrix $$$A_{k - 1}$$$ modulo $$$2$$$. Formally, this means that $$$$$$ A_k[i, j] = \sum_{1 \le u \le i} \sum_{1 \le v \le j} A_{k - 1}[u, v] \mod 2 $$$$$$

It is required to find a minimum $$$k > 0$$$ such that the matrices $$$A_k$$$ and $$$A_0$$$ are element-wise equal.

The first line of the input data contains two integers $$$n$$$ and $$$m$$$ — the number of rows and columns in the matrix $$$A_0$$$. The following $$$n$$$ lines contain descriptions of the rows of the matrix. Each line consists of $$$m$$$ characters, each character is either $$$0$$$ or $$$1$$$.

$$$$$$1 \le n, m \le 10^6$$$$$$ $$$$$$n \times m \le 10^6$$$$$$

Output the single number $$$k$$$ — the answer to the problem.

1 1
1

1

4 2
00
01
10
11

4