Шел последний день летнего лагеря, как вдруг Вы заблудились в лабиринте по дороге к кампусу Комаба университета Токио. Соревнование только что началось. Ваши товарищи по команде с нетерпением ждут Вас. Вам необходимо выйти из этого лабиринта как можно скорее. Лабиринт представлен картой на сетке. Изначально каждая ячейка кроме стен и лестниц расположена либо на первом, либо на втором этаже. Некоторые ячейки имеют переключатель, способный передвигать их вверх или вниз (ячейки на первом этаже двигаются на второй этаж, а ячейки со второго этажа на первый). На каждом шагу Вы можете совершить одно из следующих действий: \begin{itemize} \item Перейти на соседнюю ячейку (включая лестницу) того же этажа где Вы находитесь. \item Перейти на другой этаж (если Вы находитесь на ячейке с лестницей). \item Использовать переключатель (если Вы находитесь на ячейке с переключателем). \end{itemize} К счастью, Вы только что нашли карту лабиринта. Вычислите наименьшее количество действий, которое достаточно совершить для того чтобы убежать из лабиринта, и прийти туда где Вас ждут члены Вашей команды! \InputFile The format of the input is as follows. \textbf{W H} \textbf{M_11M_12M_13…M_1W} \textbf{M_21M_22M_23…M_2W} \textbf{........} \textbf{M_H1M_H2M_H3…M_HW} \textbf{S} \textbf{MS_111MS_112MS_113…MS_11W} \textbf{MS_121MS_122MS_123…MS_12W} \textbf{........} \textbf{MS_1H1MS_1H2MS_1H3…MS_1HW} \textbf{MS_211MS_212MS_213…MS_21W} \textbf{MS_221MS_222MS_223…MS_22W} \textbf{........} \textbf{MS_2H1MS_2H2MS_2H3…MS_2HW} \textbf{MS_S11MS_S12MS_S13…MS_S1W} \textbf{MS_S21MS_S22MS_S23…MS_S2W} \textbf{........} \textbf{MS_SH1MS_SH2MS_SH3…MS_SHW} The first line contains two integers \textbf{W} (\textbf{3} ≤ \textbf{W} ≤ \textbf{50}) and \textbf{H} (\textbf{3} ≤ \textbf{H} ≤ \textbf{50}). They represent the width and height of the labyrinth, respectively. The following \textbf{H} lines represent the initial state of the labyrinth. Each of \textbf{M_ij} is one of the following symbols: \begin{itemize} \item '#' representing a wall, \item '|' representing stairs, \item '_' representing a grid which is initially on the first floor, \item '^' representing a grid which is initially on the second floor, \item a lowercase letter from 'a' to 'j' representing a switch the grid has, and the grid is initially on the first floor, \item an uppercase letter from 'A' to 'J' representing a switch the grid has, and the grid is initially on the second floor, \item '\%' representing the grid you are initially in (which is initially on the first floor) or \item '&' representing the exit of the labyrinth (which is initially on the first floor). \end{itemize} The next line contains one integer \textbf{S} (\textbf{0} ≤ \textbf{S} ≤ \textbf{10}), and then the following SH lines represent the information of the switches. Each of \textbf{MS_kij} is one of: \begin{itemize} \item '#' if Mij is a '#', \item '|' if Mij is a '|', \item '*' if the grid is moved by the switch represented by the k-th alphabet letter, or \item '.' otherwise. \end{itemize} 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. \OutputFile Print the minimum step to reach the goal in one line. If there is no solution, print "\textbf{-1}".