Мир представляет собой прямоугольную таблицу с $$$n$$$ строками и $$$m$$$ столбцами. Строки нумеруются $$$0, 1, \ldots, n-1$$$, а столбцы нумеруются $$$0, 1, \ldots, m-1$$$. В этом мире столбцы циклические (т.е. верхние и нижние ячейки в каждом столбце смежны). Ячейка в $$$i$$$-й строке и $$$j$$$-м столбце ($$$0 \le i < n, 0 \le j < m$$$) обозначается как $$$(i,j)$$$.

В момент времени $$$0$$$ ячейка $$$(i,j)$$$ (где $$$0 \le i < n, 0 \le j < m$$$) содержит либо камень, либо ничего. Состояние ячейки $$$(i,j)$$$ можно описать с помощью целого числа $$$a_{i,j}$$$:

• Если $$$a_{i,j} = 1$$$, в $$$(i,j)$$$ есть камень.
• Если $$$a_{i,j} = 0$$$, в $$$(i,j)$$$ ничего нет.

В результате подземных толчков от землетрясения, столбцы следуют за движениями тектонических плит: каждый столбец циклически двигается вверх со скоростью $$$1$$$ ячейка за единицу времени. Формально, для некоторых $$$0 \le i < n, 0 \le j < m$$$, если в данный момент времени в $$$(i,j)$$$ есть камень, он переместится из $$$(i, j)$$$ в $$$(i - 1, j)$$$ (или в $$$(n - 1, j)$$$, если $$$i=0$$$).

Робот по имени RT изначально находится в позиции $$$(0,0)$$$. Ему нужно добраться до $$$(n-1,m-1)$$$ для проведения операции спасения от землетрясения (в правый нижний угол поля). Подземные толчки не изменяют положения робота, они только изменяют положение камней в мире.

Пусть текущее положение RT имеет координаты $$$(x,y)$$$ ($$$0 \le x < n, 0 \le y < m$$$), он может выполнить следующие операции:

• Перейти на одну ячейку циклически вверх, т.е. из $$$(x,y)$$$ в $$$((x+n-1) \bmod n, y)$$$ за $$$1$$$ единицу времени.
• Перейти на одну ячейку циклически вниз, т.е. из $$$(x,y)$$$ в $$$((x+1) \bmod n, y)$$$ за $$$1$$$ единицу времени.
• Перейти на одну ячейку вправо, т.е. из $$$(x,y)$$$ в $$$(x, y+1)$$$ за $$$1$$$ единицу времени. (RT может выполнить эту операцию только если $$$y < m-1$$$.)

Обратите внимание, что RT не может ни двигаться влево с помощью этих операций, ни оставаться на месте.

К сожалению, RT взорвется при столкновении с камнем. Поэтому, когда RT находится в $$$(x,y)$$$ и есть камень в $$$((x+1) \bmod n, y)$$$ или $$$((x+2) \bmod n, y)$$$, RT не может двигаться вниз, иначе он столкнется с камнем.

Аналогично, если $$$y+1 < m$$$ и есть камень в $$$((x+1) \bmod n, y+1)$$$, RT не может двигаться вправо, иначе он столкнется с камнем.

Стоит отметить, что если на клетках $$$(x \bmod n, y+1)$$$ и $$$((x+1) \bmod n, y)$$$ находится камень, RT всё равно может безопасно перейти вправо.

Найдите минимальное количество времени, которое RT нужно, чтобы добраться до $$$(n-1,m-1)$$$ без столкновения с камнями. Если это невозможно, выведите $$$-1$$$.