#include <iostream>
#include <cstring>
#include <queue>
#include <cctype>
using namespace std;

struct State {
    int row, col, mask, floor, cost;
    State(int row, int col, int mask, int floor, int cost) :
        row(row), col(col), mask(mask), floor(floor), cost(cost) {}
};

const int MAX_W = 51;
const int MAX_H = 51;
const int MAX_S = 11;

bool valid[MAX_H][MAX_W][1 << MAX_S][2];
int cost[MAX_H][MAX_W][1 << MAX_S][2];

string m[MAX_H], ms[MAX_S][MAX_H];

int w, h, s;

int dr[4] = {1, 0, -1, 0},
    dc[4] = {0, 1, 0, -1};

bool can_move(int r, int c) {
    return true;
}

void push_with_test(queue<State>& que, int nrow, int ncol, int nmask, int nfloor, int ncost) {
    int& ref_cost = cost[nrow][ncol][nmask][nfloor];
    if (valid[nrow][ncol][nmask][nfloor] && ref_cost == -1) {
        ref_cost = ncost;
        que.push(State(nrow, ncol, nmask, nfloor, ref_cost));
    }
}

int bfs(int start_r, int start_c) {
    queue<State> que;
    memset(cost, -1, sizeof(cost));

    cost[start_r][start_c][0][0] = 0;
    que.push(State(start_r, start_c, 0, 0, cost[start_r][start_c][0][0]));

    while (!que.empty()) {
        State state = que.front(); que.pop();

        if (m[state.row][state.col] == '&') {
            return state.cost;
        }

        // ??£??\????????????????§????
        for (int i = 0; i < 4; i++) {
            int nrow = state.row + dr[i],
                ncol = state.col + dc[i],
                nmask = state.mask,
                nfloor = state.floor,
                ncost = state.cost + 1;
            push_with_test(que, nrow, ncol, nmask, nfloor, ncost);
        }

        // ?????????????????????????????????????????´??????
        if (m[state.row][state.col] == '|') {
            int nrow = state.row,
                ncol = state.col,
                nmask = state.mask,
                nfloor = (state.floor + 1) % 2,
                ncost = state.cost + 1;
            push_with_test(que, nrow, ncol, nmask, nfloor, ncost);
        }
        // ?????????????????????????????????????????????????????????
        if (isalpha(m[state.row][state.col])) {
            char alpha = m[state.row][state.col];
            int alpha_i = isupper(alpha) ? (alpha - 'A') : (alpha - 'a'),
                nrow = state.row,
                ncol = state.col,
                nmask = state.mask ^ (1 << alpha_i),
                nfloor = ms[alpha_i][state.row][state.col] == '*' ? (state.floor + 1) % 2 :
                                                                    state.floor,
                ncost = state.cost + 1;
            push_with_test(que, nrow, ncol, nmask, nfloor, ncost);
        }
    }

    return -1;
}

int main() {
    cin >> w >> h;
    
    int start_r, start_c;
    for (int r = 0; r < h; r++) {
        cin >> m[r];
        for (int c = 0; c < w; c++) {
            if (m[r][c] == '%') {
                start_r = r;
                start_c = c;
                break;
            }
        }
    }

    cin >> s;
    for (int s_i = 0; s_i < s; s_i++) {
        for (int r = 0; r < h; r++) {
            cin >> ms[s_i][r];
        }
    }

    // valid????????????
    for (int r = 0; r < h; r++) {
        for (int c = 0; c < w; c++) {
            for (int mask = 0; mask < (1 << s); mask++) {
                if (m[r][c] == '#') {
                    continue;
                } else if (m[r][c] == '|') {
                    valid[r][c][mask][0] = valid[r][c][mask][1] = true;
                    continue;
                }

                int init_floor = (isupper(m[r][c]) || m[r][c] == '^') ? 1 : 0,
                    move = 0;
                for (int s_i = 0; s_i < s; s_i++) {
                    if (((mask >> s_i) & 1) && ms[s_i][r][c] == '*') {
                        move++;
                    }
                }
                valid[r][c][mask][(init_floor + move) % 2] = true;
            }
        }
    }

    cout << bfs(start_r, start_c) << endl;

    return 0;
}

Measured memory_bytes: 54692