#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template<typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template<typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
struct Elm {
  int r, c;
  int sw;
  int st;
  int d;
};

bool dp[50][50][1<<10][2];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int w, h;
  cin >> w >> h;
  vector<string> ing(h);
  for(int i=0;i<(h);++i) cin >> ing[i];
  int s;
  cin >> s;
  vector<vector<string>> insw(s, vector<string>(h));
  for(int i=0;i<(s);++i) {
    for(int j=0;j<(h);++j) {
      cin >> insw[i][j];
    }
  }
  vector<vector<vector<bool>>> floor(2, vector<vector<bool>>(h, vector<bool>(w)));
  vector<vector<bool>> stair(h, vector<bool>(w));
  vector<vector<vector<char>>> swval(2, vector<vector<char>>(h, vector<char>(w, -1)));
  vector<vector<vector<bool>>> sw(s, vector<vector<bool>>(h, vector<bool>(w)));
  P st, gl;
  for(int i=0;i<(h);++i) {
    for(int j=0;j<(w);++j) {
      switch (ing[i][j]) {
        case '|':
          floor[0][i][j] = true;
          floor[1][i][j] = true;
          stair[i][j] = true;
          break;
        case '_':
          floor[0][i][j] = true;
          break;
        case '^':
          floor[1][i][j] = true;
          break;
        case '%':
          floor[0][i][j] = true;
          st = {i, j};
          break;
        case '&':
          floor[0][i][j] = true;
          gl = {i, j};
          break;
        default:
          if ('a' <= ing[i][j] && ing[i][j] <= 'j') {
            floor[0][i][j] = true;
            swval[0][i][j] = ing[i][j] - 'a';
          } else if ('A' <= ing[i][j] && ing[i][j] <= 'J') {
            floor[1][i][j] = true;
            swval[1][i][j] = ing[i][j] - 'A';
          }
          break;
      }
    }
  }
  for(int i=0;i<(s);++i) {
    for(int j=0;j<(h);++j) {
      for(int k=0;k<(w);++k) {
        if (insw[i][j][k] == '*') {
          sw[i][j][k] = true;
        }
      }
    }
  }
  ing.clear();
  insw.clear();
  for(int i=0;i<50;++i) {
    for(int j=0;j<50;++j) {
      for(int k=0;k<(1<<10);++k) {
        for(int l=0;l<2;++l) {
          dp[i][j][k][l] = false;
        }
      }
    }
  }
  queue<Elm> que;
  dp[st.first][st.second][0][0] = true;
  que.push({st.first, st.second, 0, 0, 0});
  vi dr = {-1, 1, 0, 0};
  vi dc = {0, 0, -1, 1};
  int ans = -1;
  while(!que.empty()) {
    auto elm = que.front(); que.pop();
    if(elm.r == gl.first && elm.c == gl.second) {
      ans = elm.d;
      break;
    }
    //cout << elm.r << ":" << elm.c << ":" << elm.sw << ":" << elm.st << ":" << elm.d << endl;
    if(stair[elm.r][elm.c]) {
      if(!dp[elm.r][elm.c][elm.sw][!elm.st]) {
        dp[elm.r][elm.c][elm.sw][!elm.st] = true;
        que.push({elm.r, elm.c, elm.sw, !elm.st, elm.d + 1});
      }
    }
    bool st = elm.st;
    for(int i=0;i<(s);++i) {
      if ((1 << i) & elm.sw) st ^= sw[i][elm.r][elm.c];
    }
    int val = swval[st][elm.r][elm.c];
    if(val != -1) {
      if(!dp[elm.r][elm.c][elm.sw ^ (1<<val)][elm.st ^ sw[val][elm.r][elm.c]]) {
        dp[elm.r][elm.c][elm.sw ^ (1<<val)][elm.st ^ sw[val][elm.r][elm.c]] = true;
        que.push({elm.r, elm.c, elm.sw ^ (1<<val), elm.st ^ sw[val][elm.r][elm.c], elm.d + 1});
      }
    }
    for(int i=0;i<(4);++i) {
      int nr = elm.r + dr[i], nc = elm.c + dc[i];
      if(!(0 <= nr && nr < h && 0 <= nc && nc < w)) continue;
      bool nst = elm.st;
      for(int j=0;j<(s);++j) {
        if((1<<j) & elm.sw) nst ^= sw[j][nr][nc];
      }
      if(!floor[nst][nr][nc]) continue;
      if(!dp[nr][nc][elm.sw][elm.st]) {
        dp[nr][nc][elm.sw][elm.st] = true;
        que.push({nr, nc, elm.sw, elm.st, elm.d+1});
      }
    }
  }
  cout << ans << endl;
}




Measured memory_bytes: 8844