/*
 * main.cpp
 *
 *  Created on: 2014蟷エ7譛?譌・
 *      Author: whd
 */

#include <cstdio>
#include <cstring>
#include <iostream>

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long big;

const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };

int w, h;
char map[1 << 10][50][50];
int id[50][50];
int s;
char swi[10][50][50];
int sx, sy, tx, ty;
bool vis[1 << 10];
struct state {
	int st, f, x, y;
	state() {
	}
	state(int st, int f, int x, int y) :
			st(st), f(f), x(x), y(y) {
	}
} q[(1 << 10) * 2 * 50 * 50];
int qh, qt;
int d[1 << 10][2][50][50];
int ans;

int main() {
	scanf("%d%d", &w, &h);
	memset(id, -1, sizeof id);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf(" %c", &map[0][i][j]);
			if (map[0][i][j] == '%') {
				sx = i, sy = j;
				map[0][i][j] = '_';
			}
			if (map[0][i][j] == '&') {
				tx = i, ty = j;
				map[0][i][j] = '_';
			}
			if ('a' <= map[0][i][j] && map[0][i][j] <= 'z') {
				id[i][j] = map[0][i][j] - 'a';
				map[0][i][j] = '_';
			}
			if ('A' <= map[0][i][j] && map[0][i][j] <= 'Z') {
				id[i][j] = map[0][i][j] - 'A';
				map[0][i][j] = '^';
			}
		}
	}
	scanf("%d", &s);
	for (int k = 0; k < s; k++) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf(" %c", &swi[k][i][j]);
			}
		}
	}
	vis[0] = true;
	memset(d, -1, sizeof d);
	ans = -1;
	q[qh] = state(0, 0, sx, sy);
	d[0][0][sx][sy] = 0;
	while (qh <= qt) {
		state u = q[qh++], v;
		if ( u.x == tx && u.y == ty) {
			ans = d[u.st][u.f][u.x][u.y];
			break;
		}
//		cout << u.st << " " << u.f << " " << u.x << " " << u.y << " : "
//				<< d[u.st][u.f][u.x][u.y] << endl;
//		for (int i = 0; i < h; i++) {
//			for (int j = 0; j < w; j++) {
//				cout << map[u.st][i][j];
//			}
//			cout << endl;
//		}
		if (map[u.st][u.x][u.y] == '|') {
			v.st = u.st, v.f = u.f ^ 1, v.x = u.x, v.y = u.y;
			if (d[v.st][v.f][v.x][v.y] == -1) {
				d[v.st][v.f][v.x][v.y] = d[u.st][u.f][u.x][u.y] + 1;
				q[++qt] = v;
			}
		}
		if ((map[u.st][u.x][u.y] == '|' && u.f == 0)
				|| map[u.st][u.x][u.y] == '_') {
			for (int dir = 0; dir < 4; dir++) {
				v.st = u.st, v.f = u.f, v.x = u.x + dx[dir], v.y = u.y + dy[dir];
				if ((map[v.st][v.x][v.y] == '|' && v.f == 0)
						|| map[v.st][v.x][v.y] == '_') {
					if (d[v.st][v.f][v.x][v.y] == -1) {
						d[v.st][v.f][v.x][v.y] = d[u.st][u.f][u.x][u.y] + 1;
						q[++qt] = v;
					}
				}
			}
		}
		if ((map[u.st][u.x][u.y] == '|' && u.f == 1)
				|| map[u.st][u.x][u.y] == '^') {
			for (int dir = 0; dir < 4; dir++) {
				v.st = u.st, v.f = u.f, v.x = u.x + dx[dir], v.y = u.y + dy[dir];
				if ((map[v.st][v.x][v.y] == '|' && v.f == 1)
						|| map[v.st][v.x][v.y] == '^') {
					if (d[v.st][v.f][v.x][v.y] == -1) {
						d[v.st][v.f][v.x][v.y] = d[u.st][u.f][u.x][u.y] + 1;
						q[++qt] = v;
					}
				}
			}
		}
		if (id[u.x][u.y] != -1) {
			v.st = u.st ^ (1 << id[u.x][u.y]), v.f = u.f
					^ (swi[id[u.x][u.y]][u.x][u.y] == '*'), v.x = u.x, v.y = u.y;
			if (d[v.st][v.f][v.x][v.y] == -1) {
				d[v.st][v.f][v.x][v.y] = d[u.st][u.f][u.x][u.y] + 1;
				q[++qt] = v;
			}
			if (!vis[v.st]) {
				for (int i = 0; i < h; i++) {
					for (int j = 0; j < w; j++) {
						if (swi[id[u.x][u.y]][i][j] == '*') {
							map[v.st][i][j] = '_' + '^' - map[u.st][i][j];
						} else {
							map[v.st][i][j] = map[u.st][i][j];
						}
					}
				}
			}
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 62768