Артур и Мера в поисках трезубца попали в запутанные катакомбы. Хорошо, что у Меры с собой есть карта. Из карты стало ясно, что комнаты в катакомбах имеют одинаковый размер и расположены в $$$n$$$ рядов по $$$m$$$ комнат в каждом. При этом комнаты, смежные по стороне, соединены проходами. Более того, с помощью своих суперсил Артур может проходить из комнат $$$n$$$-го ряда не только в комнаты $$$(n-1)$$$-го ряда, но и первого. То же самое касается и комнат из $$$m$$$-го столбца. Формально из любой комнаты с координатами ($$$i$$$, $$$j$$$) существует четыре перехода в комнаты с координатами:

1. ($$$i + 1$$$, $$$j$$$), если $$$i \lt n$$$, и ($$$1$$$, $$$j$$$) иначе.
2. ($$$i - 1$$$, $$$j$$$), если $$$i \gt 1$$$, и ($$$n$$$, $$$j$$$) иначе.
3. ($$$i$$$, $$$j + 1$$$), если $$$j \lt m$$$, и ($$$i$$$, $$$1$$$) иначе.
4. ($$$i$$$, $$$j - 1$$$), если $$$j \gt 1$$$, и ($$$i$$$, $$$m$$$) иначе.

Изначально Мера и Артур находятся в комнате ($$$1$$$, $$$1$$$). В некоторых комнатах спрятаны подсказки о местонахождении трезубца. Такие комнаты на плане помечены символом «X». Героям нужно собрать их все, чтобы продолжить поиски. К сожалению, не все так просто. Расстоянием между двумя комнатами будем считать сумму абсолютных разностей их координат. Таким образом, расстояние между комнатами ($$$i_1$$$, $$$j_1$$$) и ($$$i_2$$$, $$$j_2$$$) можно вычислить по формуле $$$|i_1-i_2| + |j_1 - j_2|$$$.

Поиски подсказок осложнены тем, что комната с подсказкой откроется только тогда, когда собраны все подсказки из комнат со строго меньшим расстоянием до комнаты с координатами ($$$1$$$, $$$1$$$). То есть, если подсказки есть в комнатах ($$$1$$$, $$$2$$$) и ($$$2$$$, $$$3$$$), войти во вторую комнату можно только если первая комната уже была посещена.

Мера просит вас написать программу, которая составит маршрут по катакомбам таким образом, чтобы собрать все подсказки. Помогите героям!

Эта задача состоит из двух подзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.