AND-шлях

Одного разу Андрій брав участь в олімпіаді з програмування. За перше місце був дуже цінний приз — мішок з цукерками. Проте, скільки б він не намагався розв'язувати останню задачу, в нього нічого не виходило, саме тому він звертається по допомогу до Вас.

Вам дана матриця розмірами $n\times m$, де на перетині $i$-того рядка та $j$-того стовпчика знаходиться елемент $a_{i,j}$. Рядки нумеруються зверху вниз від $1$ до $n$, а стовпчики зліва направо від $1$ до $m$. Ліва верхня клітинка має координати $(1;1)$. Треба знайти максимальне значення побітового AND чисел на шляху він лівої верхньої до правої нижньої клітинки матриці, якщо можна ходити тільки у праву або нижню клітинку (якщо вони існують).

Через AND позначено побітове І. Операція побітового І між двома числами $a$ і $b$ визначається на парах відповідних бітів чисел: якщо обидва біти дорівнюють $1$, то у відповіді біт на цій позиції дорівнює $1$, інакше — $0$. Наприклад, $6$ AND $3$ = $0110$ AND $0011$ = $0010$ = $2$.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ($1\le n,m\le 10^3$) — кількість рядків та стовпчиків відповідно.

Наступні $n$ рядків містять $m$ цілих чисел $a_{i,j}$ ($0\le a_{i,j}<2^{60}$) — значення елементів матриці.

Вихідні дані

Виведіть одне ціле число — максимальне значення AND елементів на шляху від лівої верхньої до правої нижньої клітинки матриці.

Приклади

Примітка

Детальніше про побітове І: http://bit.ly/3Whf2l6

Пояснення до першого прикладу:

З лівої верхньої клітинки до правої нижньої існують два шляхи:

$(1;1)$, $(1;2)$, $(2;2)$ — елементи на цих позиціях мають значення $7$, $3$ та $2$ відповідно. $7$ AND $3$ AND $2$ = 2.

$(1;1)$, $(2;1)$, $(2;2)$ — елементи на цих позиціях мають значення $7$, $4$ та $2$ відповідно. $7$ AND $4$ AND $2$ = 0.

Пояснення до другого прикладу:

Одним з можливих шляхів є шлях з виділених червоним чисел. $15$ AND $13$ AND $14$ AND $31$ AND $31$ AND $4$ AND $12$ = 4.

Двійкова матриця з другого прикладу

Оцінювання

Рішення, які правильно працюють при $n\times m\le 25$ набиратимуть принаймні $15$ балів.

Рішення, які правильно працюють при $a_{i,j}\le 32$ набиратимуть принаймні $15$ балів.