E. Галзуу Жо

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жо Интернэтэд гэмтсэн байна. Одоо тэр өөрийн замд тааралдсан бүхнийг устгаж, байшингийн эргэн тойрныг сүйрүүлж байна.

Жогийн байшин $n$ давхартай ба давхар бүрт $m$ нүднүүдийн хэсэг байгаа. Нүд бүр хоосон эсвэл тоосго юмуу бетон хана агуулна (энэ гурвын аль нэг нь байна). Мөн давхар бүрийн зүүн болон баруун тал бетонон ханаар хүрээлэгдсэн гэж үзнэ.

Одоо Жо $n$-дүгээр давхрын эхний нүдэнд байгаа ба зүүнээс баруун тийш тоолно. Хугацааны агшин бүрт Жо зүүн тийшээ эсвэл баруун тийшээ харсан байна (энэ хоёр чиглэлийн аль нэг рүү). Эхлээд тэр баруун тийш харсан байгаа.

Жо тодорхой алгоритмаар хөдөлдөг. Секунд бүрт тэр дараах үйлдлүүдийн нэгийг хийдэг:

  • Хэрвээ Жогийн доор байгаа нүд хоосон бол тэр доошоо унана. Ингэснээр тэр зогсож байсан нүднээсээ хөдөлж, өөрийн харж буй чиглэлээ хадгалж үлдэнэ.
  • Эсрэг тохиолдолд өөрийн харж буй чиглэлийн дараагийн нүдэнд шилжинэ.
    • Хэрвээ энэ нүд хоосон бол Жо энэ нүдэнд ирж, мөн чиглэлээ хадгалж үлдэнэ.
    • Хэрвээ энэ нүд тоосго бол Жо духаараа тоосгыг нураагаад (ингээд нүд хоосон болно), өөрийн харж буй чиглэлээ өөрчилнө (эсрэг чиглэлд).
    • Хэрвээ энэ нүд бетон бол Жо зүгээр л чиглэлээ эсрэг чиглэлд болгож өөрчилнө. Бетон ханыг хэдэн ч удаа духаараа мөргөсөн хана нурахгүй.

Жо нэгдүгээр давхрын аль нэг нүдэнд хүрвэл тайвширна.

Доорх зурагт байшин доторх Жогийн хөдөлгөөнийг жишээ болгож харуулав.

Жо тайвширахад хэдэн секунд хэрэгтэйг тодорхойл.

Оролт

Эхний мөрөнд $n$ ба $m$ ($2 ≤ n ≤ 100$, $1 ≤ m ≤ 10^{4}$) хоёр бүхэл тоо байна.

Дараагийн $n$ мөрүүдэд Жогийн байшингийн тодорхойлолт байна. Эдгээр мөрүүдийн $i$-р мөр байшингийн $(n - i + 1)$-р давхрын тодорхойлолтыг агуулна. Мөр бүр $m$ ширхэг тэмдэгтээс бүрдэх ба "$.$" бол хоосон нүд, "$+$" бол тоосгон хана, "#" бол бетон хана байна гэсэн үг.

$n$-дүгээр давхрын эхний нүд үргэлж хоосон байна.

Гаралт

Нэг тоо хэвлэнэ. Энэ нь Жо нэгдүгээр давхарт хүрэхэд хэрэгтэй секундын тоо юм. Хэрвээ тэр нэгдүгээр давхарт хүрэх боломжгүй бол "$Never$" гэсэн үг хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 5
..+.#
#+..+
+.#+.
Гаралт
14
Оролт
4 10
...+.##+.+
+#++..+++#
++.#++++..
.+##.++#.+
Гаралт
42
Оролт
2 2
..
++
Гаралт
Never
Сэтгэгдлүүдийг ачааллаж байна...