Национальная библиотека Франции — одна из крупнейших библиотек в мире. Но не только уникальное содержание библиотечных фондов привлекает туда туристов. Многие из них посещают библиотеку для того, чтобы воспользоваться бесплатной Wi-Fi сетью.

Здание библиотеки представляет собой поле N × M клеток. Клетки бывают трех типов:

1) препятствие — обозначается символом '#';

2) коридор — обозначается символом '.';

3) комната — обозначается номером от 1-го до 5-ти, в зависимости от назначения (номера могут повторяться).

Посетители могут проходить между соседними по четырем сторонам клетками, но не могут пройти в клетку с препятствием.

Покрытие сети Wi-Fi в библиотеке достаточно слабое, поэтому в комнатах и коридорах помещения часто можно увидеть посетителей с гаджетами, которые ходят по зданию библиотеки в поисках места с хорошим приёмом сигнала.

Однажды турист с друзьями пришёл в библиотеку, чтобы воспользоваться бесплатным Интернетом и после продолжительных поисков обнаружил место с хорошим приёмом Wi-Fi. В силу плохого знания французского языка точно определить своё местоположение в здании библиотеки турист не смог. Тем не менее он решил рассказать своим друзьям об этом месте и отправился на их поиски. Чтобы впоследствии легко вернуться обратно, он решил записать, сколько клеток и в каком направлении он прошёл. Также он решил записывать последовательность A номеров комнат, в которые приходил, но к этой задаче отнесся не очень внимательно и, возможно, пропустил номера некоторых пройденных комнат. Пока турист разыскивал друзей, наступило время закрытия библиотеки, и он был вынужден отправиться домой.

На следующий день турист вновь пришёл в библиотеку. Получив на входе схему библиотеки, он решил по вчерашним заметкам найти клетку, с которой он вчера отправился на поиски друзей.

Искомая клетка должна удовлетворять следующим критериям:

1. Если начать движение из клетки и перемещаться строго в соответствии с записями, то ни в какой момент времени не окажешься за пределами библиотеки или в клетке с препятствием.

2. Если при движении в соответствии с записями выписать последовательность B номеров посещаемых комнат, то записанная ранее туристом последовательность A будет являться подпоследовательностью B.

Вам необходимо определить, сколько клеток в библиотеке подходят туристу. Учтите, что турист мог ошибиться в записях, и в этом случае искомой клетки не существует.