AND path

Once Andriy took part in a programming competition. The first prize was a valuable bag of candies. However, no matter how hard he tried to solve the last problem, he could not, so he turns to you for help.

You are given a matrix of size $n\times m$, where the intersection of the $i$-th row and $j$-th column is an element $a_{i,j}$. Rows are numbered from top to bottom from $1$ to $n$, and columns from left to right from $1$ to $m$. The upper left cell has coordinates $(1;1)$. You need to find the maximum value of the bitwise AND of the numbers on the path from the upper left to the lower right cell of the matrix, if you can only move to the right or down (if they exist).

The symbol AND denotes the bitwise AND. The bitwise AND operation between two numbers $a$ and $b$ is defined on pairs of corresponding bits of the numbers: if both bits are equal to $1$, then the bit in the answer at this position is equal to $1$, otherwise — $0$. For example, $6$ AND $3$ = $0110$ AND $0011$ = $0010$ = $2$.

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 10^3$) — the number of rows and columns, respectively.

The next $n$ lines contain $m$ integers $a_{i,j}$ ($0\le a_{i,j}<2^{60}$) — the values of the matrix elements.

Output

Output one integer — the maximum value of the AND of elements on the path from the upper left to the lower right cell of the matrix.

Examples

Note

More about bitwise AND: http://bit.ly/3Whf2l6

Explanation for the first example:

There are two paths from the upper left cell to the lower right:

$(1;1)$, $(1;2)$, $(2;2)$ — The elements in these positions have values $7$, $3$, and $2$, respectively. $7$ AND $3$ AND $2$ = 2.

$(1;1)$, $(2;1)$, $(2;2)$ — The elements in these positions have values $7$, $4$, and $2$, respectively. $7$ AND $4$ AND $2$ = 0.

Explanation for the second example:

One of the possible paths is the path with the numbers highlighted in red. $15$ AND $13$ AND $14$ AND $31$ AND $31$ AND $4$ AND $12$ = 4.

Binary matrix in the second example

Scoring

Solutions that work correctly for $n\times m\le 25$ will receive at least $15$ points.

Solutions that work correctly for $a_{i,j}\le 32$ will receive at least $15$ points.