Двоповерхове підземелля

Вхідні дані

Формат вхідних даних наступний.

$W$ $H$

M_{11}M_{12}M_{13}…M_{1W}

M_{21}M_{22}M_{23}…M_{2W}

$........$

M_{H1}M_{H2}M_{H3}…M_{HW}

$S$

MS_{111}MS_{112}MS_{113}…MS_{11W}

MS_{121}MS_{122}MS_{123}…MS_{12W}

$........$

MS_{1H1}MS_{1H2}MS_{1H3}…MS_{1HW}

MS_{211}MS_{212}MS_{213}…MS_{21W}

MS_{221}MS_{222}MS_{223}…MS_{22W}

$........$

MS_{2H1}MS_{2H2}MS_{2H3}…MS_{2HW}

MS_{S11}MS_{S12}MS_{S13}…MS_{S1W}

MS_{S21}MS_{S22}MS_{S23}…MS_{S2W}

$........$

MS_{SH1}MS_{SH2}MS_{SH3}…MS_{SHW}

Перший рядок містить два цілі числа $W$ (3 \le W \le 50) і $H$ (3 \le H \le 50) - ширина і висота лабіринту.

Наступні $H$ рядків описують початковий стан лабіринту. Кожне з M_{ij} є одним з наступних символів:

• '#' позначає стіну,

• '|' позначає сходи,

• '_' позначає клітинку, що знаходиться на першому поверсі,

• '^' позначає клітинку, що знаходиться на другому поверсі,

• літера нижнього регістру від '$a$' до '$j$' означає, що в клітинці знаходиться перемикач, клітинка спочатку знаходиться на першому поверсі,

• літера верхнього регістру від '$A$' до '$J$' означає, що в клітинці знаходиться перемикач, клітинка спочатку знаходиться на другому поверсі,

• '%' позначає клітинку, в якій ви спочатку знаходитесь (і вона розташована на першому поверсі),

• '&' позначає клітинку - вихід з лабіринту (яка спочатку на першому поверсі).

Наступний рядок містить значення $S$ (0 \le S \le 10), а наступні S \cdot H рядків описують інформацію про перемикачі. Кожне MS_{kij} є одним з:

• '#' якщо M_{ij} дорівнює '#',

• '|' якщо M_{ij} дорівнює '|',

• '*' якщо клітинка переміщується перемикачем, представленим $k$-ою літерою в алфавіті,

• '.' інакше.

Клітинка, що містить перемикач, може бути переміщена зміною стану перемикача. У цьому випадку ви рухаєтеся разом з клітинкою.

Кожен з символів '%' (початок) і '&' (ціль) на карті присутній в єдиному екземплярі, карта оточена стінами, на карті присутні тільки літери від '$A$' (або '$a$') і до $S$-ої літери в алфавіті.

Вихідні дані

Виведіть найменшу кількість дій, необхідну для досягнення цілі. Якщо рішення не існує, виведіть "$-1$".

Приклади