#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

#define fprintf(...) void(0)

const int INF = 1 << 28;
int board[1 << 10][55][55];
int switch_loc[15][55][55], switch_map[15][55][55], switch_id[55][55];
int dist[1 << 10][55][55][2];

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

int get_alph(char c) {
    if('a' <= c && c <= 'z') return c - 'a';
    return c - 'A';
}

int get_swid(int id) {
    static const int shift_sw = 2;
    return shift_sw + id;
}

int dec_swid(int id) {
    static const int shift_sw = 2;
    return id - shift_sw;
}

struct Elem {
    int state, x, y, f, cost;
};

const int WALL   = -1;
const int STAIR  = -2;
const int FIRST  = 0;
const int SECOND = 1;

int W, H;
int main() {
    memset(switch_id, -1, sizeof(switch_id));
    fill(dist[0][0][0], dist[1 << 10][0][0], INF);
    scanf("%d%d", &W, &H);

    int sx, sy, gx, gy;
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            char chr; scanf(" %c", &chr);

            if(chr == '%') {
                sx = i, sy = j;
                board[0][i][j] = FIRST;
            }
            else if(chr == '&') {
                gx = i, gy = j;
                board[0][i][j] = FIRST;
            }
            else if(chr == '#') {
                board[0][i][j] = WALL;
            }
            else if(chr == '|') {
                board[0][i][j] = STAIR;
            }
            else if(chr == '_') {
                board[0][i][j] = FIRST;
            }
            else if(chr == '^') {
                board[0][i][j] = SECOND;
            }
            else {
                int alph = get_alph(chr);
                switch_loc[alph][i][j] = true;
                switch_id[i][j] = alph;
                if(islower(chr)) {
                    board[0][i][j] = FIRST;
                }
                else {
                    board[0][i][j] = SECOND;
                }
            }
        }
    }

    int S; scanf("%d", &S);
    for(int id=0; id<S; id++) {
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                char chr; scanf(" %c", &chr);
                if(chr == '*') {
                    switch_map[id][i][j] = true;
                }
            }
        }
    }

    for(int bit=0; bit<(1<<S); bit++) {
        int mod2[55][55] = {};
        for(int id=0; id<S; id++) {
            if(bit >> id & 1) {
                for(int i=0; i<H; i++) {
                    for(int j=0; j<W; j++) {
                        if(switch_map[id][i][j]) mod2[i][j] ^= 1;
                    }
                }
            }
        }

        fprintf(stderr, "bit = %d\n", bit);
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                int num = board[0][i][j];
                if(num == WALL || num == STAIR) {
                    board[bit][i][j] = num;
                }
                else {
                    board[bit][i][j] = num ^ mod2[i][j];
                }
                fprintf(stderr, "%2d ", board[bit][i][j]);
            }
            fprintf(stderr, "\n");
        }
    }

    queue<Elem> que;
    dist[0][sx][sy][0] = 0;

    // state, x, y, f, cost
    que.push(Elem{0, sx, sy, 0, 0});

    int ans = INF;
    while(que.size()) {
        Elem cur = que.front(); que.pop();
        int x = cur.x, y = cur.y, f = cur.f, bit = cur.state, cost = cur.cost;

        if(x == gx && y == gy) {
            ans = min(ans, cost);
        }
        if(cost > dist[bit][x][y][f]) continue;

        // printf("x = %d, y = %d, bit = %d, step = %d, floor = %d\n", x, y, bit, cost, f);

        // move
        for(int k=0; k<4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if(board[bit][nx][ny] == WALL) continue;

            // move
            if(board[bit][nx][ny] == f || board[bit][nx][ny] == STAIR) {
                if(dist[bit][nx][ny][f] > cost + 1) {
                    dist[bit][nx][ny][f] = cost + 1;
                    que.push(Elem{bit, nx, ny, f, cost + 1});
                }
            }

            // stair
            if(board[bit][nx][ny] == STAIR) {
                if(dist[bit][nx][ny][f^1] > cost + 2) {
                    dist[bit][nx][ny][f^1] = cost + 2;
                    que.push(Elem{bit, nx, ny, f^1, cost + 2});
                }
            }
        }

        // switch
        if(switch_id[x][y] >= 0) {
            int id = switch_id[x][y];
            int nbit = bit ^ (1 << id);

            int nf = board[nbit][x][y];
            if(dist[nbit][x][y][nf] > cost + 1) {
                dist[nbit][x][y][nf] = cost + 1;
                que.push(Elem{nbit, x, y, nf, cost + 1});
            }
        }
    }

    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}


Measured memory_bytes: 39920