시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB111100.000%

문제

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$.

출력

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

제한

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

예제 입력 1

1 1
1

예제 출력 1

1

예제 입력 2

4 2
00
01
10
11

예제 출력 2

4