#include <bits/stdc++.h>
using namespace std;
// #define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
// const int inf = 1ll << 60;
const int inf = 1e9;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int H, W, S;
int sx, sy, gx, gy;
vector<string> board;
vector<vector<string>> switches;
int d[50][50][2][1 << 10];

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

int whichFloor(int x, int y, int bit) {
    int f = 0;
    if (board[x][y] == '^' || isupper(board[x][y])) f = 1;
    rep(s, S) {
        if (((bit >> s) & 1) && switches[s][x][y] == '*') {
            f ^= 1;
        }
    }
    return f;
}

bool cango(int f, int nx, int ny, int bit) {
    if (board[nx][ny] == '|') return true;
    if (board[nx][ny] == '#') return false;
    return f == whichFloor(nx, ny, bit);
}

int bfs() {
    using State = tuple<int, int, int, int>; // x, y, f, bit
    queue<State> que;
    que.emplace(sx, sy, 0, 0);
    rep(i, H) rep(j, W) rep(f, 2) rep(bit, 1 << S) d[i][j][f][bit] = inf;
    d[sx][sy][0][0] = 0;

    auto update = [&](int x, int y, int f, int bit, int cost) {
        if (d[x][y][f][bit] != inf) return;
        d[x][y][f][bit] = cost + 1;
        que.emplace(x, y, f, bit);
    };

    while (!que.empty()) {
        int x, y, f, bit;
        tie(x, y, f, bit) = que.front(); que.pop();
        int cost = d[x][y][f][bit];

        // output(x, y, f, bit, cost);

        if (x == gx && y == gy) {
            return cost;
        }

        rep(k, 4) {
            int nx = x + dx[k], ny = y + dy[k];
            if (cango(f, nx, ny, bit)) {
                update(nx, ny, f, bit, cost);
            }
        }

        if (board[x][y] == '|') {
            update(x, y, f^1, bit, cost);
        }

        if (isalpha(board[x][y]) && f == whichFloor(x, y, bit)) {
            int id_switch = (isupper(board[x][y]) ? board[x][y] - 'A' : board[x][y] - 'a');
            int nbit = bit ^ (1 << id_switch);
            int nf = f;
            if (switches[id_switch][x][y] == '*') {
                nf ^= 1;
            }
            update(x, y, nf, nbit, cost);
        }


    }

    return -1;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> W >> H;
    board.resize(H);
    rep(i, H) {
        cin >> board[i];
        rep(j, W) {
            if (board[i][j] == '%') {
                sx = i; sy = j;
            } else if (board[i][j] == '&') {
                gx = i; gy = j;
            }
        }
    }
    cin >> S;
    switches.resize(S, vector<string>(H));
    rep(s, S) {
        rep(i, H) cin >> switches[s][i];
    }

    cout << bfs() << endl;
}

Measured memory_bytes: 23540