#include <bits/stdc++.h>

using namespace std;

namespace {
    int W, H;
    vector<string> M;
    int S;
    vector< vector<string> > MS;
    void input() {
        cin >> W >> H;
        M.clear(); M.resize(H);
        for (int i = 0; i < H; i++) {
            cin >> M[i];
        }
        cin >> S;
        MS.clear(); MS.resize(S);
        for (int i = 0; i < S; i++) {
            MS[i].clear(); MS[i].resize(H);
            for (int j = 0; j < H; j++) {
                cin >> MS[i][j];
            }
        }
    }

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

    string to_s(int n) {
        string ret;
        for (int i = 0; i < S; i++) {
            ret.push_back( (n & (1 << i)) ? '1' : '0' );
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    struct P {
        int y, x, floor;
        int t;
        int bit;
        P() {}
        P(int y, int x, int floor, int bit, int t) : y(y), x(x), floor(floor), t(t), bit(bit) {}
    };
    ostream& operator<<(ostream& os, const P& p) {
        return os << "P[ (" << p.y << "," << p.x << "," << p.floor << ") % " << to_s(p.bit) << " " << p.t << " ]";
    }

    void find_init(P& init) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (M[i][j] == '%') {
                    init.y = i;
                    init.x = j;
                    init.floor = 0;
                    init.bit = 0;
                    return;
                }
            }
        }
    }

    int init_floor(char c) {
        if (c == '_') return 0;
        if (c == '^') return 1;
        if (c == '%') return 0;
        if (c == '&') return 0;
        if (isupper(c)) return 1;
        if (islower(c)) return 0;
        assert(0);
    }

    int cfloor(int y, int x, int bit) {
        char c = M[y][x];
        int f = init_floor(c);
        bool flag = false;
        for (int i = 0; i < S; i++) {
            if ( (bit & (1 << i)) && MS[i][y][x] == '*' ) {
                flag = !flag;
            }
        }
        if (flag) return !f;
        else return f;
    }

    bool blocked(int y, int x, int floor, int bit) {
        char c = M[y][x];
        if (c == '#') return true;
        if (c == '|') return false;
        if (cfloor(y, x, bit) != floor) return true;
        return false;
    }

    bool visited[51][51][2][1 << 10];
    void solve() {
        if (false) {
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    char c;
                    if (M[i][j] == '#') {
                        c = '#';
                    } else if (M[i][j] == '|') {
                        c = '|';
                    } else {
                        c = cfloor(i, j, 0) + '0';
                    }
                    cout << c << " ";
                }
                cout << endl;
            }
        }

        memset(visited, 0, sizeof(visited));
        P init;
        find_init(init);
        queue<P> Q;
        Q.push(init);
        visited[init.y][init.x][init.floor][init.bit] = true;
        bool found = false;
        while (!Q.empty()) {
            P c = Q.front(); Q.pop();
            int y = c.y,
                x = c.x;
            if (M[y][x] == '&') {
                found = true;
                cout << c.t << endl;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i],
                    nx = x + dx[i];
                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;
                if (blocked(ny, nx, c.floor, c.bit)) continue;
                P next(ny, nx, c.floor, c.bit, c.t + 1);
                bool& v = visited[ny][nx][c.floor][c.bit];
                if (v) continue;
                v = true;
                //cout << c << " -> " << next << endl;
                Q.push(next);
            }
            if (isalpha(M[y][x])) {
                char cc = tolower(M[y][x]);
                int s = int(cc - 'a');
                int nbit = c.bit ^ (1 << s);
                bool& v = visited[y][x][c.floor][nbit];
                if (!v) {
                    v = true;
                    int nfloor = c.floor;
                    if (MS[s][y][x] == '*') {
                        nfloor = !c.floor;
                    }
                    Q.push(P(y, x, nfloor, nbit, c.t + 1));
                }
            }
            if ('|' == M[y][x]) {
                bool& v = visited[y][x][!c.floor][c.bit];
                if (!v) {
                    v = true;
                    Q.push(P(y, x, !c.floor, c.bit, c.t + 1));
                }
            }
        }
        if (!found) {
            cout << -1 << endl;
        }
    }
}

int main() {
    input(); solve();
    return 0;
}

Measured memory_bytes: 7368