#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
   
using namespace std;
   
 
#ifdef __GNUC__
template <class T> int popcount(T n);
template <> int popcount(unsigned int n) { return __builtin_popcount(n); }
template <> int popcount(int n) { return __builtin_popcount(n); }
template <> int popcount(unsigned long long n) { return __builtin_popcountll(n); }
template <> int popcount(long long n) { return __builtin_popcountll(n); }
#else
#define __typeof__ decltype
template <class T> int popcount(T n) { return n ? 1 + popcount(n & (n - 1)) : 0; }
#endif
 
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define rforeach(it, c) for (__typeof__((c).rbegin()) it=(c).rbegin(); it != (c).rend(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))
#define COPY(dest, src) memcpy(dest, src, sizeof(dest))
   
template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }
 
template <class T> void sort(vector<T>& c) { sort(c.begin(), c.end()); }
template <class T> void unique(vector<T>& c) { c.erase(unique(c.begin(), c.end()), c.end()); }
template <class T> void sort_unique(vector<T>& c) { sort(c); unique(c); }
 
typedef long long ll;
typedef pair<int, int> pint;
   
template <class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { os << "( " << p.first << ", " << p.second << " )"; return os;  }
  
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
  
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }
   
template <class T> void print(T a, int n, const string& deli = " ", int br = 1) { for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } while (br--) cout << endl; }
template <class T> void print(const T& c, const string& deli = " ", int br = 1) { foreach (it, c) { cout << *it; if (++it != c.end()) cout << deli;--it; } while (br--) cout << endl; }
template <class T> void print2d(T a, int w, int h, int width = -1, int br = 1) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) {    if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
   
template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T, class U> void input(T& a, U& b, int n) { for (int i = 0; i < n; ++i) cin >> a[i] >> b[i]; }
  
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
  
const double PI = acos(-1.0);
const int mod = 1000000007;
 
 
template <class W, class WW>
void push(W& dis, WW& q, int T, int f, int x, int y, int d)
{
    if (d < dis[T][f][y][x])
    {
        dis[T][f][y][x] = d;
        q.push(make_pair(make_pair(T, f), make_pair(x, y)));
    }
}
int main()
{
    int w, h, s;
    char m[52][52];
    char ms[10][52][52];

    cin >> w >> h;
    for (int i = 0; i < h; ++i)
        cin >> m[i];
    cin >> s;
    for (int i = 0; i < s; ++i)
        for (int j = 0; j < h; ++j)
            cin >> ms[i][j];


    int sx, sy;
    static char c[1 << 10][2][52][52];
    CL(c, '#');
    for (int T = 0; T < 1 << s; ++T)
    {
        for (int y = 0; y < h; ++y)
        {
            for (int x = 0; x < w; ++x)
            {
                char p, q;
                p = q = '#';
                if (isalpha(m[y][x]))
                {
                    if (islower((m[y][x])))
                        p = m[y][x];
                    else
                        q = tolower(m[y][x]);
                }
                else  if (m[y][x] == '%')
                {
                    p = '.';
                    sx = x, sy = y;
                }
                else if (m[y][x] == '&')
                    p = '&';
                else if (m[y][x] == '_')
                    p = '.';
                else if (m[y][x] == '^')
                    q = '.';
                else
                    p = q = m[y][x];

                for (int i = 0; i < s; ++i)
                    if (T >> i & 1)
                        if (ms[i][y][x] == '*')
                            swap(p, q);

                c[T][0][y][x] = p;
                c[T][1][y][x] = q;
            }
        }
    }

    const int INF = 1 << 29;
    static int dis[1 << 10][2][52][52];
    for (int T = 0; T < 1 << s; ++T)
        for (int f = 0; f < 2; ++f)
            for (int y = 0; y < h; ++y)
                for (int x = 0; x < w; ++x)
                    dis[T][f][y][x] = INF;

    int res = INF;

    typedef pair<pint, pint> P;
    queue<P> q;
    dis[0][0][sy][sx] = 0;
    q.push(P(pint(0, 0), pint(sx, sy)));
    while (!q.empty())
    {
        P aa = q.front();
        q.pop();

        int T = aa.first.first, f = aa.first.second;
        int x = aa.second.first, y = aa.second.second;


        if (c[T][f][y][x] == '&')
        {
            res = dis[T][f][y][x];
            break;
        }

        int nd = dis[T][f][y][x] + 1;
        char w = c[T][f][y][x];
        if (isalpha(w))
        {
            int k = w - 'a';
            int nT = T ^ (1 << k);
            int nf = c[nT][f][y][x] == '#' ? (f ^ 1) : f;

            push(dis, q, nT, nf, x, y, nd);
        }
        else if (w == '|')
        {
            int nf = f ^ 1;
            push(dis, q, T, nf, x, y, nd);
        }

        for (int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (c[T][f][ny][nx] != '#')
                push(dis, q, T, f, nx, ny, nd);
        }
    }

    if (res == INF)
        res = -1;
    cout << res << endl;
}

Measured memory_bytes: 28964