#include<iostream>
#include<cctype>
#include<queue>

using namespace std;

struct State{
  int y,x,t,b,s;
};

int main(){
  int W,H;
  cin>>W>>H;
  char M[50][51];
  int sy,sx;
  for(int i=0;i<H;i++){
    cin>>M[i];
    for(int j=0;j<W;j++){
      if(M[i][j]=='%'){
	sy=i;
	sx=j;
      }
    }
  }
  int S;
  cin>>S;
  char MS[10][50][51];
  for(int i=0;i<S;i++){
    for(int j=0;j<H;j++){
      cin>>MS[i][j];
    }
  }
  queue<State> que;
  que.push({sy,sx,0,0,0});
  static bool p[50][50][1<<10][2];
  while(!que.empty()){
    State cs=que.front();
    if(M[cs.y][cs.x]=='&')break;
    que.pop();
    if(p[cs.y][cs.x][cs.b][cs.s]++)continue;
    for(int i=0;i<4;i++){
      static int d[]={0,-1,0,1,0};
      int ny=cs.y+d[i];
      int nx=cs.x+d[i+1];
      if(M[ny][nx]=='#')continue;
      int is=isupper(M[ny][nx])||M[ny][nx]=='^';
      for(int j=0;j<S;j++){
	is^=cs.b>>j&1&&MS[j][ny][nx]=='*';
      }
      if(is==cs.s||M[ny][nx]=='|'){
	que.push({ny,nx,cs.t+1,cs.b,cs.s});
      }
    }
    if(M[cs.y][cs.x]=='|'){
      que.push({cs.y,cs.x,cs.t+1,cs.b,cs.s^1});
    }
    if(isalpha(M[cs.y][cs.x])){
      int nb=M[cs.y][cs.x]-(isupper(M[cs.y][cs.x])?'A':'a');
      que.push({cs.y,cs.x,cs.t+1,cs.b^1<<nb,cs.s^MS[nb][cs.y][cs.x]=='*'});
    }
  }
  cout<<(que.empty()?-1:que.front().t)<<endl;
}