Двоповерхове підземелля
Настав останній день літнього табору, і ви раптом заблукали в лабіринті на шляху до кампусу Комаба університету Токіо. Змагання вже почалося, і ваші товариші по команді з нетерпінням чекають на вас. Вам потрібно якомога швидше вибратися з цього лабіринту.
Лабіринт представлений у вигляді карти на сітці. Спочатку кожна клітинка, окрім стін і сходів, розташована або на першому, або на другому поверсі. Деякі клітинки мають перемикач, який може переміщати їх вгору або вниз (клітинки на першому поверсі переміщуються на другий поверх, а клітинки з другого поверху на перший).
На кожному кроці ви можете виконати одну з наступних дій:
Перейти на сусідню клітинку (включаючи сходи) того ж поверху, де ви знаходитесь.
Перейти на інший поверх (якщо ви знаходитесь на клітинці зі сходами).
Використати перемикач (якщо ви знаходитесь на клітинці з перемикачем).
На щастя, ви щойно знайшли карту лабіринту. Обчисліть найменшу кількість дій, яку потрібно виконати, щоб вибратися з лабіринту і дістатися до місця, де вас чекають члени вашої команди!
Вхідні дані
Формат вхідних даних наступний.
W H
M_11M_12M_13…M_1W
M_21M_22M_23…M_2W
........
M_H1M_H2M_H3…M_HW
S
MS_111MS_112MS_113…MS_11W
MS_121MS_122MS_123…MS_12W
........
MS_1H1MS_1H2MS_1H3…MS_1HW
MS_211MS_212MS_213…MS_21W
MS_221MS_222MS_223…MS_22W
........
MS_2H1MS_2H2MS_2H3…MS_2HW
MS_S11MS_S12MS_S13…MS_S1W
MS_S21MS_S22MS_S23…MS_S2W
........
MS_SH1MS_SH2MS_SH3…MS_SHW
Перший рядок містить два цілі числа W (3 ≤ W ≤ 50) і H (3 ≤ H ≤ 50) - ширина і висота лабіринту.
Наступні H рядків описують початковий стан лабіринту. Кожне з M_ij є одним з наступних символів:
'#' позначає стіну,
'|' позначає сходи,
'_' позначає клітинку, що знаходиться на першому поверсі,
'^' позначає клітинку, що знаходиться на другому поверсі,
літера нижнього регістру від 'a' до 'j' означає, що в клітинці знаходиться перемикач, клітинка спочатку знаходиться на першому поверсі,
літера верхнього регістру від 'A' до 'J' означає, що в клітинці знаходиться перемикач, клітинка спочатку знаходиться на другому поверсі,
'%' позначає клітинку, в якій ви спочатку знаходитесь (і вона розташована на першому поверсі),
'' позначає клітинку - вихід з лабіринту (яка спочатку на першому поверсі).
Наступний рядок містить значення S (0 ≤ S ≤ 10), а наступні S*H рядків описують інформацію про перемикачі. Кожне MS_kij є одним з:
'#' якщо Mij дорівнює '#',
'|' якщо Mij дорівнює '|',
'*' якщо клітинка переміщується перемикачем, представленим k-ою літерою в алфавіті,
'.' інакше.
Клітинка, що містить перемикач, може бути переміщена зміною стану перемикача. У цьому випадку ви рухаєтеся разом з клітинкою.
Кожен з символів '%' (початок) і '' (ціль) на карті присутній в єдиному екземплярі, карта оточена стінами, на карті присутні тільки літери від 'A' (або 'a') і до S-ої літери в алфавіті.
Вихідні дані
Виведіть найменшу кількість дій, необхідну для досягнення цілі. Якщо рішення не існує, виведіть "-1".