#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
double EPS=1e-10;
double EQ(double a,double b){
    return abs(a-b)<EPS;
}
void fast_stream(){
  std::ios_base::sync_with_stdio(0);
}
template<class T>
string IntToString(T num){
  string res;stringstream ss;ss<<num;
  return ss.str();
}
ll StringToInt(string &str){
  ll res=0;
  for(int i=0;i<(int)str.size();i++)
    res=(res*10+str[i]-'0');
  return res;
}

int W,H,S;
char field[101][101];
char event[11][101][101];
int moves[1<<10][51][51];

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

int d[51][51][1<<10][2];

typedef pair<pii,pair<int,int> > Sit;
int sy,sx,gy,gx;


int main(){
  cin>>W>>H;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>field[i][j];
      if(field[i][j]=='%'){
	sy=i;sx=j;
	field[i][j]='.';
      }
      else if(field[i][j]=='&'){
	gy=i;gx=j;
	field[i][j]='.';
      }
      else if((field[i][j]>='A'&&field[i][j]<='Z')||(field[i][j]>='a'&&field[i][j]<='z')){
	char ch=field[i][j];
	if(ch>='a'&&ch<='z')ch=ch-'a'+'A';
      }
    }
  }
  cin>>S;
  for(int k=0;k<S;k++)
    for(int i=0;i<H;i++)
      for(int j=0;j<W;j++)
	cin>>event[k][i][j];
  for(int i=1;i<(1<<S);i++){
    for(int j=0;j<10;j++){
      if((i>>j)&1){
	for(int k=0;k<H;k++){
	  for(int l=0;l<W;l++){
	    if(event[j][k][l]=='*'){
	      moves[i][k][l]=moves[i&~(1<<j)][k][l]^1;
	    }
	    else
	      moves[i][k][l]=moves[i&~(1<<j)][k][l];
	  }
	}
      }
    }
  }
  queue<Sit> q;
  q.push(make_pair(pii(sy,sx),make_pair(0,0)));
  memset(d,-1,sizeof(d));
  d[sy][sx][0][0]=0;
  while(q.size()){
    pair<pii,pii> p=q.front();q.pop();
    const int cy=p.first.first,cx=p.first.second;
    const int mask=p.second.first,rank=p.second.second;
    const int ccost=d[cy][cx][mask][rank];
    if(field[cy][cx]=='|'){
      int nrank=rank^1;
      if(d[cy][cx][mask][nrank]<0){
	d[cy][cx][mask][nrank]=ccost+1;
	q.push(Sit(pii(cy,cx),pii(mask,nrank)));
      }
    }
    if(field[cy][cx]>='A'&&field[cy][cx]<='Z'){
      const int ch=field[cy][cx]-'A';
      int nmask=mask;
      if(!((nmask>>ch)&1))nmask|=(1<<ch);
      else nmask&=~(1<<ch);
      int nrank=rank;
      if(moves[nmask][cy][cx]!=moves[mask][cy][cx])nrank^=1;
      if(d[cy][cx][nmask][nrank]<0){
	d[cy][cx][nmask][nrank]=ccost+1;
	q.push(Sit(pii(cy,cx),pii(nmask,nrank)));
      }
    }
    else if(field[cy][cx]>='a'&&field[cy][cx]<='z'){
      int ch=field[cy][cx]-'a';
      int nmask=mask;
      if(!((nmask>>ch)&1))
	nmask|=(1<<ch);
      else
	nmask&=~(1<<ch);
      int nrank=rank;
      if(moves[nmask][cy][cx]!=moves[mask][cy][cx])nrank^=1;
      if(d[cy][cx][nmask][nrank]<0){
	d[cy][cx][nmask][nrank]=ccost+1;
	q.push(Sit(pii(cy,cx),pii(nmask,nrank)));
      }
    }
    for(int i=0;i<4;i++){
      const int ny=cy+dy[i];
      const int nx=cx+dx[i];
      if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#'&&d[ny][nx][mask][rank]<0){
	if((field[ny][nx]=='_'||(field[ny][nx]>='a'&&field[ny][nx]<='z'))&&!(moves[mask][ny][nx]^rank)){
	  d[ny][nx][mask][rank]=ccost+1;
	  q.push(Sit(pii(ny,nx),pii(mask,rank)));
	}
	else if((field[ny][nx]=='^'||(field[ny][nx]>='A'&&field[ny][nx]<='Z'))&&(moves[mask][ny][nx]^rank)){
	  d[ny][nx][mask][rank]=ccost+1;
	  q.push(Sit(pii(ny,nx),pii(mask,rank)));
	}
	else if(field[ny][nx]=='|'){
	  d[ny][nx][mask][rank]=ccost+1;
	  q.push(Sit(pii(ny,nx),pii(mask,rank)));
	}
	else if(field[ny][nx]=='.'&&!(moves[mask][ny][nx]^rank)){
	  d[ny][nx][mask][rank]=ccost+1;
	  q.push(Sit(pii(ny,nx),pii(mask,rank)));
	}
      }
    }
  }
  const int INF=1<<30;
  int res=INF;
  for(int i=0;i<(1<<10);i++){
    int a=moves[i][gy][gx];
    if(d[gy][gx][i][a]!=-1)
      res=min(res,d[gy][gx][i][a]);
  }
  if(res==INF)cout<<-1<<endl;
  else cout<<res<<endl;
  
  return 0;
}

Measured memory_bytes: 33056