#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef complex<ld> Point;
const ll mod = 1000000007;
const ld INF = 1e+30;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int n, m;

char mp[1024][2][50][50];
char ch[10][50][50];
struct status {
	int i, j, x, y;
	bool operator<(const status &s)const {
		if (i != s.i)return i < s.i;
		if (j != s.j)return j < s.j;
		if (x != s.x)return x < s.x;
		return y < s.y;
	}
};
bool used[1024][2][50][50];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
void solve() {
	cin >> m >> n;
	int sx, sy,gx,gy;
	rep(i, n) {
		rep(j, m) {
			char t; cin >> t;
			if (t == '#' || t == '|') {
				rep(k, 2) {
					mp[0][k][i][j] = t;
				}
			}
			else if (t == '_') {
				mp[0][0][i][j] = '.';
				mp[0][1][i][j] = '#';
			}
			else if (t == '^') {
				mp[0][0][i][j] = '#';
				mp[0][1][i][j] = '.';
			}
			else if ('a' <= t && t <= 'z') {
				mp[0][0][i][j] = '0'+(t-'a');
				mp[0][1][i][j] = '#';
			}
			else if ('A' <= t && t <= 'Z') {
				mp[0][0][i][j] = '#';
				mp[0][1][i][j] = '0'+(t-'A');
			}
			else if (t == '%') {
				sx = i, sy = j;
				mp[0][0][i][j] = '.';
				mp[0][1][i][j] = '#';
			}
			else if (t == '&') {
				gx = i, gy = j;
				mp[0][0][i][j] = '.';
				mp[0][1][i][j] = '#';
			}
		}
	}
	int s; cin >> s;
	rep(i, s) {
		rep(j, n) {
			rep(k, m) {
				cin >> ch[i][j][k];
			}
		}
	}
	rep(i, (1 << s)) {
		rep(j, 2) {
			rep(k, n) {
				rep(l, m) {
					mp[i][j][k][l] = mp[0][j][k][l];
				}
			}
		}
		rep(j, s) {
			if (i&(1 << j)) {
				rep(k, n) {
					rep(l, m) {
						if (ch[j][k][l] == '*') {
							swap(mp[i][0][k][l], mp[i][1][k][l]);
						}
					}
				}
			}
		}
	}
	int tmp = 0;
	queue<status> q; q.push({ 0,0,sx,sy });
	used[0][0][sx][sy] = true;
	int ans = -1;
	while (!q.empty()) {
		int len = q.size();
		//cout << tmp << endl;
		rep(aa, len) {
			status v = q.front(); q.pop();
			//cout << v.i << " " << v.j << " " << v.x << " " << v.y << endl;
			int x = v.x, y = v.y;
			if (x == gx && y == gy) {
				ans = tmp;
				while (!q.empty())q.pop();
				break;
			}
			char memo = mp[v.i][v.j][x][y];
			if (memo == '|') {
				if (!used[v.i][v.j ^ 1][x][y]) {
					used[v.i][v.j ^ 1][x][y] = true;
					q.push({ v.i,v.j ^ 1,x,y });
				}
			}
			if ('0' <= memo && memo <= '9') {
				int u = memo - '0';
				int ni = v.i ^ (1 << u);
				int nj = v.j;
				if (mp[ni][v.j][x][y] == '#') {
					nj ^= 1;
				}
				if (!used[ni][nj][x][y]) {
					used[ni][nj][x][y] = true;
					q.push({ ni,nj,x,y });
				}
			}
			rep(j, 4) {
				int nx = x + dx[j], ny = y + dy[j];
				if (mp[v.i][v.j][nx][ny] != '#') {
					if (!used[v.i][v.j][nx][ny]) {
						used[v.i][v.j][nx][ny] = true;
						q.push({ v.i,v.j,nx,ny });
					}
				}
			}
		}
		tmp++;
	}
	cout << ans << endl;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 13728