#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
char field[50][50];
int s[50][50];
bool diff[10][50][50];
bool used[50][50][2][2048];
 
struct state{
    int y,x,f,sw;
    int step;
    state(int y, int x, int f, int sw, int step)
        :y(y),x(x),f(f),sw(sw),step(step){}
    state(){}
};
 
int main(){
    memset(s, -1, sizeof(s));
    memset(diff, 0, sizeof(diff));
    memset(used, 0, sizeof(used));
    int w,h;
    cin >> w >> h;
    int sy,sx,gy,gx;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> field[i][j];
            if('a'<=field[i][j] && field[i][j]<='z'){
                s[i][j] = field[i][j] -'a';
                field[i][j] = '_';
            }
            if('A'<=field[i][j] && field[i][j]<='Z'){
                s[i][j] = field[i][j] -'A';
                field[i][j] = '^';
            }
            if(field[i][j] == '%'){
                sy = i;
                sx = j;
                field[i][j] = '_';
            }
            if(field[i][j] == '&'){
                gy = i;
                gx = j;
                field[i][j] = '_';
            }
        }
    }
 
    int m;
    cin >> m;
    for(int r=0; r<m; r++){
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                char c;
                cin >> c;
                if(c == '*') diff[r][i][j] = true;
            }
        }
    }
 
    queue<state> wait;
    wait.push(state(sy,sx,0,0,0));
    used[sy][sx][0][0] = true;
    int ans = -1;
    while(!wait.empty()){
        state curr = wait.front();
        int y = curr.y;
        int x = curr.x;
        int f = curr.f;
        int sw = curr.sw;
        int step = curr.step;
        wait.pop();
        if(y == gy && x == gx){
            ans = step;
            break;
        }
        if(field[y][x] == '|'){
            if(!used[y][x][1-f][sw]){
                used[y][x][1-f][sw] = true;
                wait.push(state(y, x, 1-f, sw, step+1));
            }
        }
        if(s[y][x] != -1){
            int nsw = sw ^ (1<<s[y][x]);
            int nf = f ^ diff[s[y][x]][y][x];
            if(!used[y][x][nf][nsw]){
                used[y][x][nf][nsw] = true;
                wait.push(state(y, x, nf, nsw, step+1));
            }
        }
        for(int i=0; i<4; i++){
            int ny = y +dy[i];
            int nx = x +dx[i];
            if(field[ny][nx] == '#') continue;
            if(field[ny][nx] == '|'){
                if(!used[ny][nx][f][sw]){
                    used[ny][nx][f][sw] = true;
                    wait.push(state(ny, nx, f, sw, step+1));
                }
                continue;
            }
            int nf = (field[ny][nx] == '_')? 0: 1;
            for(int j=0; j<m; j++){
                if((sw & 1<<j) != 0){
                    nf ^= diff[j][ny][nx];
                }
            }
            if(f != nf) continue;
            if(!used[ny][nx][nf][sw]){
                used[ny][nx][nf][sw] = true;
                wait.push(state(ny, nx, nf, sw, step+1));
            }
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 13740