#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

#define PUSH(r, c, f, m) do{			\
    rs.push(r);					\
    cs.push(c);					\
    fs.push(f); 				\
    ms.push(m); 				\
  }while(0)
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

int W, H, S;
char I[55][55];
bool M[10][55][55];
int  D[2][55][55][1 << 10];

inline bool inside(int r, int c){
  return 0 <= r && r < H && 0 <= c && c < W;
}

inline bool cur_floor(int r, int c, int f, int mask){
  bool ok = f == 0;
  if(I[r][c] == '#') return false;
  if(I[r][c] == '|') return true;
  if(I[r][c] == '^' || isupper(I[r][c])) ok = !ok;
  REP(s, S) if(PARITY(mask >> s) && M[s][r][c]) ok = !ok;
  return ok;
}


int main(){
  memset(D, -1, sizeof(D));
  memset(M, false, sizeof(M));
  
  cin >> W >> H;
  int sr, sc;
  REP(r, H)REP(c, W){
    cin >> I[r][c];
    if(I[r][c] == '%'){
      sr = r;
      sc = c;
    }
  }

  cin >> S;
  char ch;  
  REP(s, S)REP(r, H)REP(c, W){
    cin >> ch;
    M[s][r][c] = ch == '*';
  }

  queue<int> rs, cs, fs, ms;
  rs.push(sr);
  cs.push(sc);
  fs.push(0);
  ms.push(0);
  D[0][sr][sc][0] = 0;
  
  int dr[4] = {0, 1, 0, -1};
  int dc[4] = {-1, 0, 1, 0};

  bool goal = false;
  while(!rs.empty()){
    int r = rs.front(); rs.pop();
    int c = cs.front(); cs.pop();
    int f = fs.front(); fs.pop();
    int mask = ms.front(); ms.pop();
    
    if(I[r][c] == '&' && cur_floor(r, c, f, mask)){
      cout << D[f][r][c][mask] << endl;
      goal = true;
      break;
    }
    
    REP(i, 4){
      int nr = r + dr[i];
      int nc = c + dc[i];
      if(inside(nr, nc) && cur_floor(nr, nc, f, mask) && D[f][nr][nc][mask] ==-1){
	D[f][nr][nc][mask] = D[f][r][c][mask] + 1;
	PUSH(nr, nc, f, mask);
      }
    }

    if(I[r][c] == '|' && D[1 - f][r][c][mask] == -1){
      D[1 - f][r][c][mask] = D[f][r][c][mask] + 1;
      PUSH(r, c, 1 - f, mask);
    }

    if(isalpha(I[r][c]) && cur_floor(r, c, f, mask)){
      int k = isupper(I[r][c]) ? I[r][c] - 'A' : I[r][c] - 'a';
      int nmask = mask ^ (1 << k);
      int nf = cur_floor(r, c, f, nmask) ? f : 1 - f;
      if(D[nf][r][c][nmask] == -1){
	D[nf][r][c][nmask] = D[f][r][c][mask] + 1;
	PUSH(r, c, nf, nmask);
      }
    }
  }
  if(!goal) cout << -1 << endl;
  return 0;
}