Джо обидели в интернете. Теперь он носится по дому, сметая все на своем пути.
Дом Джо состоит из n этажей, каждый этаж представляет собой отрезок из m клеток. В каждой из клеток либо ничего нет (клетка пуста), либо там находится кирпичная, либо бетонная стена (всегда что-то одно из трех). Считается, что каждый из этажей слева и справа огорожен бетонной стеной.
Сейчас Джо находится на n-ом этаже в первой, если считать слева направо, клетке. В каждый момент времени у Джо имеется направление взгляда — вправо или влево (всегда одно направление из двух). Изначально Джо смотрит вправо.
Джо перемещается по определенному алгоритму. Каждую секунду он делает одно из действий:
- Если клетка прямо под Джо пуста, то Джо падает вниз. То есть перемещается в эту клетку, направление взгляда при этом сохраняется.
- Иначе рассматривается соседняя клетка по текущему направлению взгляда.
- Если эта клетка пуста, то Джо перемещается в нее, направление взгляда при этом сохраняется.
- Если в этой клетке находятся кирпичи, то Джо разбивает их своим лбом (клетка становится пустой) и меняет направление своего взгляда на противоположное.
- Если же в этой клетке бетонная стена, то Джо просто меняет направление своего взгляда на противоположное (бетон выдерживает любое количество ударов лбом).
Джо успокаивается достигнув любой клетки первого этажа.
На рисунке ниже показан пример перемещений Джо по дому.
Определите какое количество секунд потребуется Джо для того, чтобы успокоиться.
В первой строке записаны два целых числа n и m (2 ≤ n ≤ 100, 1 ≤ m ≤ 104).
В следующих n строках дано описание дома Джо. В i-ой из этих строк дано описание (n - i + 1)-го этажа дома — строка из m символов: «.» означает пустую клетку, «+» — кирпичи, «#» — бетонную стену.
Гарантируется, что первая клетка n-го этажа пуста.
Выведите единственное число — количество секунд, за которые Джо достигнет первого этажа; или слово «Never» (без кавычек), если этого не произойдет никогда.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3 5
..+.#
#+..+
+.#+.
14
4 10
...+.##+.+
+#++..+++#
++.#++++..
.+##.++#.+
42
2 2
..
++
Never
