Двухэтажное подземелье
Шел последний день летнего лагеря, как вдруг Вы заблудились в лабиринте по дороге к кампусу Комаба университета Токио. Соревнование только что началось. Ваши товарищи по команде с нетерпением ждут Вас. Вам необходимо выйти из этого лабиринта как можно скорее.
Лабиринт представлен картой на сетке. Изначально каждая ячейка кроме стен и лестниц расположена либо на первом, либо на втором этаже. Некоторые ячейки имеют переключатель, способный передвигать их вверх или вниз (ячейки на первом этаже двигаются на второй этаж, а ячейки со второго этажа на первый).
На каждом шагу Вы можете совершить одно из следующих действий:
Перейти на соседнюю ячейку (включая лестницу) того же этажа где Вы находитесь.
Перейти на другой этаж (если Вы находитесь на ячейке с лестницей).
Использовать переключатель (если Вы находитесь на ячейке с переключателем).
К счастью, Вы только что нашли карту лабиринта. Вычислите наименьшее количество действий, которое достаточно совершить для того чтобы убежать из лабиринта, и прийти туда где Вас ждут члены Вашей команды!
Входные данные
Формат входных данных следующий.
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".