/*
*Rainto96
*Beijing University of Posts and Telecommunications School of Software Engineering
*http://blog.csdn.net/u011775691
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <climits>
using namespace std;
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define VINT vector<int>
#define PII pair<int,int>
#define MP(x,y) make_pair((x),(y))
#define ll long long
#define ull unsigned ll
#define MEM0(x)  memset(x,0,sizeof(x))
#define MEM(x,val) memset((x),val,sizeof(x))
#define scan(x) scanf("%d",&(x))
#define scan2(x,y) scanf("%d%d",&(x),&(y))
#define scan3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define scan4(x,y,z,k) scanf("%d%d%d%d",&(x),&(y),&(z),&(k))
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
using namespace std;
int n,m,s;//m hang n lie
int c[55][55][1111];//
char g[55][55];
char sg[11][55][55];
int sx,sy;
struct Info{
        int x,y,up,sta,step;
};
int dir[4][2]={-1,0,0,1,1,0,0,-1};
bool vis[52][52][2][1100];//
void bfs(){
        queue<Info> que;
        que.push((Info){sx,sy,0,0,0});
        vis[sx][sy][0][0] = true;
        bool flag= false;
        while(!que.empty()){
                Info now = que.front() ; que.pop();
                int x = now.x, y=now.y, up=now.up, sta=now.sta, step=now.step;
                //if(g[x][y]!='|' && c[x][y][sta] != up) continue;
                //cerr<<x<<" "<<y<<" "<<up<<endl;
                if(g[x][y] == '&'){
                        flag=true;
                        printf("%d\n",step);
                        break;
                }
                if(g[x][y] == '|'){
                        if(!vis[x][y][up^1][sta]){
                                vis[x][y][up^1][sta] = true;
                                que.push((Info){x,y,up^1,sta,step+1});
                        }
                }
                if(isalpha(g[x][y])){
                        int id;
                        if(g[x][y] >='A' && g[x][y] <= 'Z')  id=g[x][y] - 'A';
                        else id = g[x][y] -'a';
                        int nup = c[x][y][sta^(1<<id)];
                        if(!vis[x][y][nup][sta^(1<<id)]){
                                vis[x][y][nup][sta^(1<<id)] = true;
                                que.push((Info){x,y,nup,sta^(1<<id),step+1} );
                        }
                }
                for(int i=0;i<4;i++){
                        int nx = x + dir[i][0] , ny = y + dir[i][1];
                        if(nx<0 || nx>=m || ny<0 || ny>=n || g[nx][ny] == '#') continue;
                        if(g[nx][ny]!='|' && c[nx][ny][sta] != up) continue;
                        if(!vis[nx][ny][up][sta]){
                                vis[nx][ny][up][sta] = true;
                                que.push((Info){nx,ny,up,sta,step+1});
                        }
                }
        }
        if(!flag) puts("-1");
}
int main(){
	#ifndef ONLINE_JUDGE
		//freopen("C:/OJ/in.txt","r",stdin);
	#endif
	while(scan2(n,m)==2){
                MEM0(vis);
                MEM0(c);
                for(int i=0;i<m;i++) {
                        scanf("%s",g[i]);
                        for(int j=0;j<n;j++){
                                if(g[i][j] == '%') sx=i , sy=j;
                        }
                }
                scan(s);
                for(int i=0;i<s;i++){
                        for(int j=0;j<m;j++) scanf("%s",sg[i][j]);
                }
                for(int i=0;i<m;i++){
                        for(int j=0;j<n;j++){
                                if(g[i][j] == '#' || g[i][j] == '|') continue;
                                for(int k=0;k<(1<<s);k++){
                                        bool state = false;
                                        for(int p=0;p<s;p++){
                                                if(k&(1<<p)){
                                                        if(sg[p][i][j] =='*')
                                                        state ^= 1;
                                                }
                                        }
                                        c[i][j][k] = state ^ (g[i][j]=='^' || (g[i][j]>='A' && g[i][j]<='Z'));
                                }
                        }
                }
                bfs();
	}
        return 0;
}

Measured memory_bytes: 20988