Шел последний день летнего лагеря, как вдруг Вы заблудились в лабиринте по дороге к кампусу Комаба университета Токио. Соревнование только что началось. Ваши товарищи по команде с нетерпением ждут Вас. Вам необходимо выйти из этого лабиринта как можно скорее.
Лабиринт представлен картой на сетке. Изначально каждая ячейка кроме стен и лестниц расположена либо на первом, либо на втором этаже. Некоторые ячейки имеют переключатель, способный передвигать их вверх или вниз (ячейки на первом этаже двигаются на второй этаж, а ячейки со второго этажа на первый).
На каждом шагу Вы можете совершить одно из следующих действий:
Перейти на соседнюю ячейку (включая лестницу) того же этажа где Вы находитесь.
Перейти на другой этаж (если Вы находитесь на ячейке с лестницей).
Использовать переключатель (если Вы находитесь на ячейке с переключателем).
К счастью, Вы только что нашли карту лабиринта. Вычислите наименьшее количество действий, которое достаточно совершить для того чтобы убежать из лабиринта, и прийти туда где Вас ждут члены Вашей команды!
The format of the input is as follows.
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
The first line contains two integers W (3 ≤ W ≤ 50) and H (3 ≤ H ≤ 50). They represent the width and height of the labyrinth, respectively.
The following H lines represent the initial state of the labyrinth. Each of M_ij is one of the following symbols:
'#' representing a wall,
'|' representing stairs,
'_' representing a grid which is initially on the first floor,
'^' representing a grid which is initially on the second floor,
a lowercase letter from 'a' to 'j' representing a switch the grid has, and the grid is initially on the first floor,
an uppercase letter from 'A' to 'J' representing a switch the grid has, and the grid is initially on the second floor,
'%' representing the grid you are initially in (which is initially on the first floor) or
'' representing the exit of the labyrinth (which is initially on the first floor).
The next line contains one integer S (0 ≤ S ≤ 10), and then the following SH lines represent the information of the switches. Each of MS_kij is one of:
'#' if Mij is a '#',
'|' if Mij is a '|',
'*' if the grid is moved by the switch represented by the k-th alphabet letter, or
'.' otherwise.
Note that the grid which contains a switch may be moved by operating the switch. In this case, you will move together with the grid.
You may assume each of the '%' (start) and '' (goal) appears exacyly once, that the map is surround by walls, and that each alphabet in the map is any of the letters from 'A' (or 'a') to S-th alphabet letter.
Print the minimum step to reach the goal in one line. If there is no solution, print "-1".