부분합

$n$개의 행과 $m$개의 열로 이루어진 행렬 $A_0$가 있다. 행과 열은 1부터 시작하는 연속한 자연수로 번호가 매겨진다. 행렬의 각 원소는 0 또는 1이다. $i$번째 행과 $j$번째 열이 만나는 위치의 원소를 $A_0[i, j]$라고 쓰자.

무한한 행렬열 $A_k$를 생각하자. $k > 0$인 행렬 $A_k$도 $n$개의 행과 $m$개의 열로 이루어지며, $A_{k-1}$의 부분합을 2로 나눈 나머지로 이루어진 행렬이다. 즉, 다음과 같다.

$A_k[i, j] = \sum_{1 \le u \le i} \sum_{1 \le v \le j} A_{k-1}[u, v] \mod 2$

$A_k$와 $A_0$가 모든 원소에서 같아지는 최소의 $k > 0$을 구하라.

첫째 줄에 행렬 $A_0$의 행의 수와 열의 수를 나타내는 두 정수 $n$과 $m$이 주어진다. 다음 $n$개의 줄에는 행렬의 각 행이 주어진다. 각 줄은 $m$개의 문자로 이루어지며, 각 문자는 $0$ 또는 $1$이다.

문제의 답인 $k$를 한 줄에 출력한다.

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