Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Робот и подземные толчки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мир представляет собой прямоугольную таблицу с $$$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$$$.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В каждом наборе первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$3 \le n, m \le 10^3$$$) — размеры планеты.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. $$$(j+1)$$$-е целое число в $$$(i+1)$$$-й строке ($$$0 \le i < n, 0 \le j < m$$$) — это $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 1$$$), которое обозначает, есть ли камень в $$$(i,j)$$$ в момент времени $$$0$$$.

Кроме того, гарантируется, что $$$a_{0,0} = 0$$$, и $$$a_{i, m-1} = 0$$$ для $$$0 \le i < n$$$. Другими словами, в начальной позиции RT также нет камня, а в столбце $$$m-1$$$ его также нет.

Сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Выходные данные

Для каждого набора входных данных:

  • Если конечная точка может быть достигнута без столкновения с камнями, выведите одно целое число — минимальное количество времени, которое RT нужно, чтобы добраться до $$$(n-1,m-1)$$$.
  • В противном случае выведите $$$-1$$$.
Примеры
Входные данные
6
4 5
0 1 0 0 0
0 0 1 0 0
1 0 1 1 0
0 0 0 0 0
3 3
0 0 0
1 0 0
0 0 0
5 3
0 0 0
0 0 0
1 0 0
0 0 0
1 0 0
3 7
0 0 1 0 0 1 0
1 0 1 0 1 0 0
0 1 0 0 0 0 0
3 4
0 1 0 0
1 0 0 0
0 1 1 0
5 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
Выходные данные
7
3
3
8
-1
12
Входные данные
6
3 3
0 0 0
0 0 0
0 0 0
4 3
0 1 0
1 0 0
0 1 0
1 0 0
4 3
0 1 0
0 1 0
0 1 0
0 1 0
3 3
0 0 0
1 1 0
0 0 0
3 3
0 1 0
0 0 0
0 1 0
5 5
0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 1 0 0
Выходные данные
3
3
-1
-1
3
8
Примечание

Визуальное объяснение первого теста в примере: