#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

vector<vector<int>>field;
vector<vector<bitset<11>>>byswitches;

int memo[50][50][2][2048];

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


bool isup(const int x, const int y, const bitset<11>&bs) {
	bool up = false;
	for (int i = 0; i < 11; ++i) {
		if (bs[i] && byswitches[y][x][i])up = !up;
	}
	return up;
}

bool canmove(const int x, const int y,const int z, const bitset<11>&bs) {
	if (z < 0 || z >= 2)return false;
	if (field[y][x] == 0)return false;
	if (field[y][x] == 1)return true;
	else if (isup(x, y, bs) == z)return true;
	else return false;
}
struct aa {
	int x;
	int y;
	int z;
	bitset<11>bs;
	int time;

};
class Compare {
public:
	//aa?????????????????¶
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};
int sx = 0, sy = 0,gx=0,gy=0;
int dfs() {
	queue<aa>que;
	bitset<11>bs;
	bs[0] = true;
	que.push(aa{ sx,sy,0,bs,0 });
	int ans = -1;
	while (!que.empty()) {
		aa atop(que.front());
		que.pop();
		const int nowx = atop.x;
		const int nowy = atop.y;
		const int nowz = atop.z;
		const bitset<11> nowbs = atop.bs;
		const int nowtime = atop.time;
		if (nowx == gx&&nowy == gy) {
			ans = nowtime;
			break;
		}
		for (int way = 0; way < 6; ++way) {
			const int nextx = nowx + dx[way];
			const int nexty = nowy + dy[way];
			const int nextz = nowz + dz[way];
			const bitset<11> nextbs = nowbs;
			const int nexttime = nowtime + 1;
			if (canmove(nextx, nexty, nextz, nextbs)) {
				if (memo[nextx][nexty][nextz][nextbs.to_ulong()]>nexttime) {
					memo[nextx][nexty][nextz][nextbs.to_ulong()] = nexttime;
					que.push(aa{ nextx,nexty,nextz,nextbs,nexttime });
				}
			}
		}
		{
			if (field[nowy][nowx] >= 3) {
				const int nextx = nowx ;
				const int nexty = nowy ;
				int nextz;
				{
					if (byswitches[nowy][nowx][field[nowy][nowx] - 2]) {
						nextz = !nowz;
					}
					else {
						nextz = nowz;
					}
				}
				bitset<11> nextbs = nowbs;
				const int nexttime = nowtime + 1;
				nextbs[field[nowy][nowx] - 2] = !nextbs[field[nowy][nowx] - 2];
				if (canmove(nextx, nexty, nextz, nextbs)) {
					if (memo[nextx][nexty][nextz][nextbs.to_ulong()]>nexttime) {
						memo[nextx][nexty][nextz][nextbs.to_ulong()] = nexttime;
						que.push(aa{ nextx,nexty,nextz,nextbs,nexttime });
					}
				}
			}
		}
	}
	return ans;
}
int main() {
	for (int i = 0; i < 50; ++i) {
		for (int j = 0; j < 50; ++j) {
			for (int k = 0; k < 2; ++k) {
				for (int l = 0; l < 2048; ++l) {
					memo[i][j][k][l] = 1e9;
				}
			}
		}
	}
	int H, W; cin >> W >> H;
	field = vector<vector<int>>(H, vector<int>(W));
	byswitches = vector<vector<bitset<11>>>(H, vector<bitset<11>>(W));
	for (int i = 0; i < H; ++i) {
		string st; cin >> st;
		for (int j = 0; j < W; ++j) {
			if (st[j] == '#')field[i][j] = 0;
			else if (st[j] == '|')field[i][j] = 1;
			else if (st[j] == '%') {
				sx = j; sy = i;
				field[i][j] = 2;
			}
			else if (st[j] == '&') {
				gx = j; gy = i;
				field[i][j] = 2;
			}
			else if (st[j] == '_') {
				field[i][j] = 2;
			}
			else if (st[j] == '^') {
				field[i][j] = 2;
				byswitches[i][j][0] = true;
			}
			else if(st[j]>='a'&&st[j]<='z'){
				field[i][j] = 3 + st[j] -'a';
			}
			else {
				field[i][j] = 3 + st[j] - 'A';
				byswitches[i][j][0] = true;
			}
		}
	}
	int S; cin >> S;
	for (int s = 0;s < S; ++s) {
		for (int i = 0; i < H; ++i) {
			string st; cin >> st;
			for (int j = 0; j < W; ++j) {
				if (st[j] == '*')byswitches[i][j][s + 1] = true;
			}
		}
	}
	int ans = dfs();
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 44188