#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
int data[2][51][51],sy,sx,gy,gx;
int sw[51][51],h,w,num;
string s[51],t;
int dy[]={0,0,-1,1};
int dx[]={-1,1,0,0};
bool used[51][51][1<<10][2];
struct dat{
    int y,x,sw,flo,cost;
    dat(int a,int b,int c,int d,int e){
        y=a;x=b;sw=c;flo=d;cost=e;
    }
};
signed main(){
    memset(data,-1,sizeof(data));
    cin>>w>>h;
    r(i,h)cin>>s[i];
    r(i,h)r(j,w){
        if(s[i][j]=='%')data[0][i][j]=100,sy=i,sx=j;
        if(s[i][j]=='&')data[0][i][j]=100,gy=i,gx=j;
        if(s[i][j]=='_')data[0][i][j]=100;
        if(s[i][j]=='^')data[1][i][j]=100;
        if(s[i][j]=='|')data[0][i][j]=data[1][i][j]=101;
        if(isalpha(s[i][j])){
            if(islower(s[i][j]))data[0][i][j]=(s[i][j]-'a');
            if(isupper(s[i][j]))data[1][i][j]=(s[i][j]-'A');
        }
    }
    cin>>num;
    r(i,num)r(j,h){
        cin>>t;
        r(k,w)if(t[k]=='*')sw[j][k]|=(1<<i);
    }
    queue<dat>q;
    q.push(dat(sy,sx,0,0,0));
    used[sy][sx][0][0]=1;
    while(!q.empty()){
        dat a=q.front();q.pop();
        if(a.y==gy&&a.x==gx){
            cout<<a.cost<<endl;
            return 0;
        }
        int y=a.y;
        int x=a.x;

        // 階段
        if(data[a.flo][y][x]==101){
            if(!used[y][x][a.sw][a.flo^1]){
                used[y][x][a.sw][a.flo^1]=1;
                q.push(dat(y,x,a.sw,a.flo^1,a.cost+1));
            }
        }

        // 移動
        r(i,4){
            int ny=y+dy[i];
            int nx=x+dx[i];
            int A=a.sw;
            int B=sw[ny][nx];
            int C=A&B;
            int D=__builtin_popcount(C)+a.flo;D%=2;
            if(data[D][ny][nx]!=-1){
                //cout<<ny<<' '<<nx<<endl;
                if(!used[ny][nx][a.sw][a.flo]){
                    used[ny][nx][a.sw][a.flo]=1;
                    q.push(dat(ny,nx,a.sw,a.flo,a.cost+1));
                }
            }
        }

        // スイッチ
        if(isalpha(s[y][x])){
            int A=a.sw;
            int B=sw[y][x];
            int C=A&B;
            int D=__builtin_popcount(C)+a.flo;D%=2;
            int E=data[D][y][x];
            int F=0;
            if(islower(s[y][x]))F|=(1<<(s[y][x]-'a'));
            if(isupper(s[y][x]))F|=(1<<(s[y][x]-'A'));
            if(F&B){
                if(!used[y][x][a.sw^F][a.flo^1]){
                    used[y][x][a.sw^F][a.flo^1]=1;
                    q.push(dat(y,x,a.sw^F,a.flo^1,a.cost+1));
                }
            }
            else{
                if(!used[y][x][a.sw^F][a.flo]){
                    used[y][x][a.sw^F][a.flo]=1;
                    q.push(dat(y,x,a.sw^F,a.flo,a.cost+1));
                }
            }
        }
    }
    cout<<-1<<endl;
}
