Перемістити на кубику
На прямокутній карті з сіткою 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), які вказують на кількість рядків і стовпців карти відповідно. Наступні W рядків описують карту. j-й символ i-го рядка вказує на інструкцію квадрата, що розташований на i-му рядку (зверху) і j-му стовпці (зліва).
Потім наступні 6 рядків описують рядки на кожній грані куба. Всі ці рядки не порожні і коротші за 12 символів (включно). Крім того, вони складаються лише з великих літер алфавіту або цифр. Грані, на яких написані рядки, наведені як рисунок 1. Спочатку куб розміщено на стартовому квадраті в напрямку, коли грань № 1 звернена вгору, а верхній напрямок грані № 1 спрямований до верхнього рядка карти.
Рисунок 1. розгортка куба
Останні два рядки містять по два цілі числа, які вказують на номер рядка і номер стовпця стартового квадрата і цільового квадрата в цьому порядку. Ви можете припустити, що стартовий квадрат і цільовий квадрат завжди різні.
Вихідні дані
Виведіть лексикографічно мінімальний рядок в одному рядку. Якщо шляху немає, виведіть "no" в одному рядку. Якщо ви можете зробити лексикографічно мінімальний рядок нескінченно довгим, виведіть "infinite" в одному рядку.