#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

const int H = 50;
const int W = 50;
const int S = 10;

class State{
public:
   int f, y, x, state, cost;
   State(){}
   State(int state, int f, int y, int x, int cost) : state(state), f(f), y(y), x(x), cost(cost) {}
};

int h, w, s, sx, sy;
char input[H][W];
char data[S][H][W];
int init[H][W];
int data2[(1<<S)][H][W];
bool vis[(1<<S)][2][H][W];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

int solve(){
   fill(vis[0][0][0], vis[(1<<s)][0][0], false);
   State u, v;
   u = State(0, 0, sy, sx, 0);
   queue<State> q;
   q.push(u);
   vis[u.state][u.f][u.y][u.x] = true;
   /*for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	 cout << data2[1][i][j] << ' ';
      }
      cout << endl;
      }*/
   while(!q.empty()){
      u = q.front();
      q.pop();
      //cout << u.state << ' ' << u.f << ' ' << u.y << ' ' << u.x << ' ' << u.cost << endl;
      if(u.f == data2[u.state][u.y][u.x] && input[u.y][u.x] == '&'){
	 return u.cost;
      }
      for(int i=0;i<4;i++){
	 int ny = u.y + dy[i];
	 int nx = u.x + dx[i];
	 if(ny < 0 || ny >= h) continue;
	 if(nx < 0 || nx >= w) continue;
	 if(input[ny][nx] == '#') continue;
	 /*if(u.state == 1 && u.f == 1 && u.y == 3 && u.x == 4 && u.cost == 3){
	    cout << ny << ' ' << nx << endl;
	    }*/
	 if(u.f != data2[u.state][ny][nx] && input[ny][nx] != '|') continue;
	 if(!vis[u.state][u.f][ny][nx]){
	    vis[u.state][u.f][ny][nx] = true;
	    q.push(State(u.state, u.f, ny, nx, u.cost + 1));
	 }
      }
      if(input[u.y][u.x] == '|'){
	 if(!vis[u.state][1-u.f][u.y][u.x]){
	    vis[u.state][1-u.f][u.y][u.x] = true;
	    q.push(State(u.state, 1 - u.f, u.y, u.x, u.cost + 1));
	 }
      }
      if(input[u.y][u.x] >= 'a' && input[u.y][u.x] <= 'j' && u.f == data2[u.state][u.y][u.x]){
	 int tmp = input[u.y][u.x] - 'a';
	 int next = u.state;
	 if((u.state >> tmp) & 1){
	    next &= ~(1<<tmp);
	 }else{
	    next |= (1<<tmp);
	 }
	 v = State(next, u.f, u.y, u.x, u.cost + 1);
	 v.f = data2[next][v.y][v.x];
	 if(!vis[v.state][v.f][v.y][v.x]){
	    vis[v.state][v.f][v.y][v.x] = true;
	    q.push(v);
	 }
      }
      if(input[u.y][u.x] >= 'A' && input[u.y][u.x] <= 'J' && u.f == data2[u.state][u.y][u.x]){
	 int tmp = input[u.y][u.x] - 'A';
	 int next = u.state;
	 if((u.state >> tmp) & 1){
	    next &= ~(1<<tmp);
	 }else{
	    next |= (1<<tmp);
	 }
	 v = State(next, u.f, u.y, u.x, u.cost + 1);
	 v.f = data2[next][v.y][v.x];
	 if(!vis[v.state][v.f][v.y][v.x]){
	    vis[v.state][v.f][v.y][v.x] = true;
	    q.push(v);
	 }
      }
   }
   return -1;
}

main(){
   cin >> w >> h;
   for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	 cin >> input[i][j];
	 if(input[i][j] == '%'){
	    sy = i;
	    sx = j;
	 }
	 init[i][j] = 0;
	 if(input[i][j] == '^') init[i][j] = 1;
	 if(input[i][j] >= 'A' && input[i][j] <= 'J') init[i][j] = 1;
      }
   }
   cin >> s;
   for(int k=0;k<s;k++){
      for(int i=0;i<h;i++){
	 for(int j=0;j<w;j++){
	    cin >> data[k][i][j];
	 }
      }
   }
   for(int k=0;k<(1<<s);k++){
      for(int i=0;i<h;i++){
	 for(int j=0;j<w;j++){
	    data2[k][i][j] = init[i][j];
	    for(int l=0;l<s;l++){
	       if(((k>>l) & 1) && data[l][i][j] == '*') data2[k][i][j] = 1 - data2[k][i][j];
	    }
	 }
      }
   }
   cout << solve() << endl;
}

Measured memory_bytes: 17060