Перемещение на кубике
На прямоугольной карте с сеткой размером H на W находится куб. На карте выделены два особых квадрата: начальный и целевой. Изначально куб расположен на начальном квадрате. Ваша задача — перекатывать куб, чтобы доставить его на целевой квадрат. Перекатывание куба означает выбор одного из четырех ребер, которые касаются карты, и толкание куба в этом направлении, не отрывая ребро от карты. Таким образом, куб можно перемещать в одном из четырех направлений.
Направления, в которых можно перекатывать куб, зависят от каждого квадрата. На каждом квадрате указана инструкция в виде одного из следующих символов:
'+' — все направления
'|' — только вертикально
'-' — только горизонтально
'<' — только влево
'>' — только вправо
'^' — только вверх
'v' — только вниз
'.' — никуда
Независимо от инструкций, куб нельзя перекатывать за пределы карты.
На каждой грани куба написана строка. Ваша задача — вывести строку, которая соединяет строки, написанные на верхней грани, видимой во время перекатывания от начального квадрата до целевого. Если существует несколько путей, ведущих куб к целевому квадрату, выберите минимальную строку в лексикографическом порядке.
Учтите, что могут быть случаи, когда путь от начального до целевого квадрата не существует, или случаи, когда лексикографически минимальная строка может быть бесконечно длинной.
Входные данные
Формат входных данных следующий:
H W
C_11 ... C_1W
...
C_H1 ... C_HW
T_1
...
T_6
R_S C_S
R_D C_D
Первая строка входных данных содержит два целых числа H (1 ≤ H ≤ 12) и W (1 ≤ W ≤ 12), которые указывают количество рядков и столбцов карты соответственно. Следующие H строк описывают карту. j-й символ i-й строки указывает инструкцию квадрата, который находится на i-м рядке (сверху) и j-м столбце (слева).
Затем следующие 6 строк описывают строки на каждой грани куба. Все эти строки не пусты и короче 12 символов (включительно). Они состоят только из заглавных букв алфавита или цифр. Грани, на которых написаны строки, даны как рисунок 1. Изначально куб размещен на начальном квадрате так, что грань № 1 обращена вверх, а верхнее направление грани № 1 направлено к верхнему рядку карты.
Рисунок 1. развертка куба
Последние две строки содержат по два целых числа, которые указывают номер рядка и номер столбца начального квадрата и целевого квадрата в этом порядке. Можно предположить, что начальный квадрат и целевой квадрат всегда разные.
Выходные данные
Выведите лексикографически минимальную строку в строке. Если пути нет, выведите "no". Если можно сделать лексикографически минимальную строку бесконечно длинной, выведите "infinite".