#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Data
{
public:
    int z, y, x, s;
    Data(int z0, int y0, int x0, int s0){
        z = z0;
        y = y0;
        x = x0;
        s = s0;
    }
    int toInt(){
        return ((z * 50 + y) * 50 + x) * 1024 + s;
    }
};

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

int main()
{
    int h, w;
    cin >> w >> h;

    vector<string> m(h, string(w, ' '));
    int sy, sx;
    for(int i=0; i<h; ++i){
        for(int j=0; j<w; ++j){
            cin >> m[i][j];
            if(m[i][j] == '%'){
                sy = i;
                sx = j;
            }
        }
    }

    int sn;
    cin >> sn;
    vector<vector<string> > ms(10, vector<string>(h, string(w, ' ')));
    for(int i=0; i<sn; ++i){
        for(int j=0; j<h; ++j){
            cin >> ms[i][j];
        }
    }

    vector<bool> dp(2*50*50*1024, false);
    dp[Data(0, sy, sx, 0).toInt()] = true;
    queue<Data> q;
    q.push(Data(0, sy, sx, 0));

    int ret = 0;
    while(!q.empty()){
        int n = q.size();
        while(--n >= 0){
            int z = q.front().z;
            int y = q.front().y;
            int x = q.front().x;
            int s = q.front().s;
            q.pop();

            if(m[y][x] == '&'){
                cout << ret << endl;
                return 0;
            }if(m[y][x] == '|'){
                Data d(z^1, y, x, s);
                if(!dp[d.toInt()]){
                    dp[d.toInt()] = true;
                    q.push(d);
                }
            }else if(isalpha(m[y][x])){
                int s2 = s;
                s2 ^= 1 << (tolower(m[y][x]) - 'a');
                int z2 = z;
                if(ms[tolower(m[y][x]) - 'a'][y][x] == '*')
                    z2 ^= 1;
                Data d(z2, y, x, s2);
                if(!dp[d.toInt()]){
                    dp[d.toInt()] = true;
                    q.push(d);
                }
            }

            for(int i=0; i<4; ++i){
                int y2 = y + dy[i];
                int x2 = x + dx[i];
                if(m[y2][x2] == '#')
                    continue;

                int z2 = z;
                if(m[y2][x2] != '|'){
                    z2 = 0;
                    if(m[y2][x2] == '^' || isupper(m[y2][x2]))
                        z2 = 1;

                    bitset<10> bs(s);
                    for(int j=0; j<10; ++j){
                        if(bs[j] && ms[j][y2][x2] == '*')
                            z2 ^= 1;
                    }

                    if(z != z2)
                        continue;
                }

                Data d(z2, y2, x2, s);
                if(!dp[d.toInt()]){
                    dp[d.toInt()] = true;
                    q.push(d);
                }
            }
        }
        ++ ret;
    }

    cout << -1 << endl;
    return 0;
}