/*
 * 2447.cc: A Two Floors Dungeon
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_W = 50;
const int MAX_H = 50;
const int MAX_S = 10;
const int SBITS = 1 << MAX_S;

const int INF = 1 << 30;

const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1};

/* typedef */

enum { F_W = -1, F_F = 0, F_ST = 1, F_SW = 2 };

struct Stat {
  int d, x, y, f, sw;
  Stat() {}
  Stat(int _d, int _x, int _y, int _f, int _sw):
    d(_d), x(_x), y(_y), f(_f), sw(_sw) {}
};

/* global variables */

int prtys[SBITS];
int flds[MAX_H][MAX_W], ifs[MAX_H][MAX_W], sws[MAX_H][MAX_W];
int dists[MAX_H][MAX_W][2][SBITS];

/* subroutines */

inline int calc_f(int x, int y, int sw) {
  return ifs[y][x] ^ prtys[sws[y][x] & sw];
}

/* main */

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

  int sx, sy, gx, gy;

  for (int y = 0; y < h; y++) {
    string s;
    cin >> s;
    for (int x = 0; x < w; x++) {
      flds[y][x] = F_F;
      ifs[y][x] = 0;
      switch (s[x]) {
      case '#': flds[y][x] = F_W; break;
      case '|': flds[y][x] = F_ST; break;
      case '_': break;
      case '^': ifs[y][x] = 1; break;
      case '%': sx = x; sy = y; break;
      case '&': gx = x; gy = y; break;
      default:
	if (s[x] >= 'a' && s[x] <= 'j')
	  flds[y][x] = F_SW + s[x] - 'a';
	else if (s[x] >= 'A' && s[x] <= 'J') {
	  flds[y][x] = F_SW + s[x] - 'A';
	  ifs[y][x] = 1;
	}
      }
    }
  }

  int sn;
  cin >> sn;
  int sbits = 1 << sn;

  for (int i = 0, bi = 1; i < sn; i++, bi <<= 1)
    for (int y = 0; y < h; y++) {
      string s;
      cin >> s;
      for (int x = 0; x < w; x++)
	if (s[x] == '*') sws[y][x] |= bi;
    }

  for (int bits = 0; bits < sbits; bits++) {
    prtys[bits] = 0;
    for (int i = 0, bi = 1; i < sn; i++, bi <<= 1)
      if (bits & bi) prtys[bits] ^= 1;
  }
  
  for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
      for (int f = 0; f < 2; f++)
	for (int bits = 0; bits < sbits; bits++)
	  dists[y][x][f][bits] = INF;

  dists[sy][sx][0][0] = 0;

  queue<Stat> q;
  q.push(Stat(0, sx, sy, 0, 0));

  while (! q.empty()) {
    Stat u = q.front(); q.pop();
    if (u.x == gx && u.y == gy) break;

    int vd = u.d + 1;

    // up/down stair
    if (flds[u.y][u.x] == F_ST) {
      int vf = 1 - u.f;
      if (dists[u.y][u.x][vf][u.sw] > vd) {
	dists[u.y][u.x][vf][u.sw] = vd;
	q.push(Stat(vd, u.x, u.y, vf, u.sw));
      }
    }

    // toggle sw
    if (flds[u.y][u.x] >= F_SW) {
      int si = flds[u.y][u.x] - F_SW;
      int vsw = u.sw ^ (1 << si);
      int vf = calc_f(u.x, u.y, vsw);
      if (dists[u.y][u.x][vf][vsw] > vd) {
	dists[u.y][u.x][vf][vsw] = vd;
	q.push(Stat(vd, u.x, u.y, vf, vsw));
      }
    }

    // move to adjacent grid
    for (int di = 0; di < 4; di++) {
      int vx = u.x + dxs[di], vy = u.y + dys[di];
      if (flds[vy][vx] == F_W) continue;
      int vf = (flds[vy][vx] == F_ST) ? u.f : calc_f(vx, vy, u.sw);
      if (vf == u.f && dists[vy][vx][vf][u.sw] > vd) {
	dists[vy][vx][vf][u.sw] = vd;
	q.push(Stat(vd, vx, vy, vf, u.sw));
      }
    }
  }

  int mind = INF;
  for (int f = 0; f < 2; f++)
    for (int bits = 0; bits < sbits; bits++)
      if (mind > dists[gy][gx][f][bits]) mind = dists[gy][gx][f][bits];

  printf("%d\n", (mind >= INF) ? -1 : mind);
  return 0;
}

Measured memory_bytes: 22116