ebala

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


struct State{
    int x, y, z, mask;
    State(){
        x=0,y=0,z=0,mask=0;
    }
    State(int xx, int yy, int zz, int mm){
        x = xx;
        y = yy;
        z = zz;
        mask = mm;
    }
};

//////////////////////


const int sz = 1<<23;
int n,m,s;
int depth[sz];
bool exist[sz];
string M[50];
string G[10][50];
vector< vector<int> > change_mask;
vector<vector<int> > change_coordinates;

//////////////////////

int id(State & st){
    return (st.mask) + (st.x << 10) + (st.y << 16) + (st.z << 22);
}

int id(int x, int y, int z, int mask){
    return (mask) + (x << 10) + (y << 16) + (z << 22);
}

const string is_switch = "ABCDEFGHIJabcdefghij";

bool can_go(State & from, State & to){
    if(!exist[id(from)] || !exist[id(to)]) return false;
    if(__builtin_popcount(abs(from.mask - to.mask))>1) return false;
    if(from.mask == to.mask) {
        int delta = abs(from.x - to.x) + abs(from.y - to.y) + abs(from.z - to.z);
       if(delta!=1) return false;
        return true;
    } else {
        int delta_not_z = abs(from.x - to.x) + abs(from.y - to.y);
        if(delta_not_z > 0)
            return false;
        if(from.z != to.z)
            if(is_switch.find(M[from.x][from.y]) == -1)
                return false;

        return true;
    }
}

int check_bit(int & val, int & bit){
    return ((val>>bit)&1);
}

int check_coor(int & x, int & y, int & z){
   return x>=0&&y>=0&&z>=0&&x<=n&&y<=m&&z<=1;
}

const string upper_string = "ABCDEFGHIJ^";

char is_upper(char c){
    return upper_string.find(c) != -1;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>M[i];
    }
    cin>>s;
    for(int g=0;g<s;g++){
        for(int i=0;i<n;i++){
            cin>>G[g][i];
        }
    }

    for(int i=0;i<s;i++){
        change_mask.push_back({0,0,0,i});
        change_mask.push_back({0,0,-1,i});
        change_mask.push_back({0,0,1,i});
    }
    change_coordinates.push_back({ 1, 0, 0});
    change_coordinates.push_back({-1, 0, 0});
    change_coordinates.push_back({ 0, 1, 0});
    change_coordinates.push_back({ 0,-1, 0});
    change_coordinates.push_back({ 0, 0, 1});
    change_coordinates.push_back({ 0, 0,-1});

    memset(exist, 0, sizeof exist);

    for(int mask=0;mask<(1<<s);mask++){
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                if(M[x][y]=='#') continue;
                for(int z=0;z<2;z++){
                    if(M[x][y]=='|'){
                        exist[id(x,y,z,mask)] = 1;
                    }
                }
        if(M[x][y] == '|') continue;
                int z = is_upper(M[x][y]);
                for(int bit=0;bit<s;bit++){
                    if(check_bit(mask, bit)){
                        if(G[bit][x][y] == '*'){
                            z ^=1;
                        }
                    }
                }
                exist[id(x,y,z,mask)] = 1;
            }
        }
    }

    int start_x, start_y, finish_x, finish_y;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(M[i][j] == '%'){
                start_x = i;
                start_y = j;
            }
            if(M[i][j] == '&'){
                finish_x = i;
                finish_y = j;
            }
        }
    }

    State start = State(start_x, start_y, 0, 0);

    queue<State> q;
    q.push(start);

    memset(depth, 0x3f, sizeof depth);
    depth[id(start_x, start_y, 0, 0)] = 0;
    int cur_x,cur_y,cur_z,cur_mask,nxt_x,nxt_y,nxt_z,nxt_mask, delta_mask, bit;
    while(q.size()){
        State cur = q.front();
        q.pop();

        cur_x = cur.x;
        cur_y = cur.y;
        cur_z = cur.z;
        cur_mask = cur.mask;


        for(auto & v : change_mask){
           nxt_x = cur_x;
            nxt_y = cur_y;
            nxt_z = cur_z + v[2];
            bit = v[3];
            if(!check_coor(nxt_x, nxt_y, nxt_z)) continue;
            nxt_mask = (cur_mask | (1<<v[3]));
            delta_mask = (abs(nxt_mask - cur_mask));
            if(M[cur_x][cur_y] - 'a' != bit && M[cur_x][cur_y] - 'A' != bit) continue;
            State nxt_state = State(nxt_x, nxt_y, nxt_z, nxt_mask);
            if(can_go(cur, nxt_state)){
                if(depth[id(cur)] + 1 < depth[id(nxt_state)]){
                    depth[id(nxt_state)] = depth[id(cur)] + 1;
                    q.push(nxt_state);
                }
            }
        }

        for(auto & v : change_mask){
            nxt_x = cur_x;
            nxt_y = cur_y;
            nxt_z = cur_z + v[2];
            if(!check_coor(nxt_x, nxt_y, nxt_z)) continue;
            nxt_mask = (cur_mask & ((1<<s)-1-(1<<v[3])));

            delta_mask = (abs(nxt_mask - cur_mask));
            bit = 0;
            while((1<<bit) < delta_mask) ++bit;
            if(M[cur_x][cur_y] - 'a' != bit && M[cur_x][cur_y] - 'A' != bit) continue;

            State nxt_state = State(nxt_x, nxt_y, nxt_z, nxt_mask);
            if(can_go(cur, nxt_state)){
                if(depth[id(cur)] + 1 < depth[id(nxt_state)]){
                    depth[id(nxt_state)] = depth[id(cur)] + 1;
                    q.push(nxt_state);
                }
            }
        }

        for(auto & v : change_coordinates){
            nxt_x = cur_x + v[0];
            nxt_y = cur_y + v[1];
            nxt_z = cur_z + v[2];
            if(!check_coor(nxt_x, nxt_y, nxt_z)) continue;
            nxt_mask = cur_mask;
            State nxt_state = State(nxt_x, nxt_y, nxt_z, nxt_mask);
            if(can_go(cur, nxt_state)){
                if(depth[id(cur)] + 1 < depth[id(nxt_state)]){
                    depth[id(nxt_state)] = depth[id(cur)] + 1;
                    q.push(nxt_state);
                }
            }
        }
    }
    int ans = depth[0];
    for(int mask = 0; mask < (1<<s); mask++){
        for(int z=0;z<2;z++){
            ans = min(ans, depth[id(finish_x, finish_y, z, mask)]);
        }
    }
    if(ans == depth[0]){
        cout<<-1<<endl;
    }
    else{
        cout<<ans<<endl;
    }
    return 0;
}