#include<iostream>
#include<cctype>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cassert>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<28)
#define MAX 51
#define X first
#define Y second
using namespace std;

typedef pair<int,int> ii;

struct P
{
  int x,y,state,cost;
  bool floor;
  P(int x=inf,int y=inf,int state=inf,int cost=inf,bool floor=false):x(x),y(y),state(state),cost(cost),floor(floor){}
  bool operator < (const P& a)const
  {
    return cost > a.cost;
  }
};

int W,H,S;
char G[MAX][MAX];//初期状態のグリッド
vector<int> swt[MAX][MAX];//swt[y][x] := (x,y)に影響を与えるスイッチ
int mincost[2][(1<<10)][MAX][MAX];
ii st;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

bool getFloor(char c)//false -> 1, true -> 2
{
  if(c == '_' || c == '&' || c == '%' || (isalpha(c) && islower(c)))return false;
  if(c == '^' || (isalpha(c) && isupper(c)))return true;

  return true;//stair
}

void compute()
{
  priority_queue<P> Q;
  Q.push(P(st.X,st.Y,0,0,0));//int x | int y | int state | int cost | bool floor
  mincost[0][0][st.Y][st.X] = 0;

  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();

      int x = p.x, y = p.y, state = p.state, cost = p.cost;
      bool floor = p.floor;

      bitset<10> sta(state);
      //cout << "(" << x << "," << y << ") " << sta << " cost = " << cost << " floor : " << (floor?"2":"1") << endl;

      if(G[y][x] == '&')
	{
	  cout << p.cost << endl;
	  return;
	}

      rep(i,4)
	{
	  int nx = x + dx[i];
	  int ny = y + dy[i];
	  if(!( 0 <= nx && nx < W && 0 <= ny && ny < H))continue;
	  if(G[ny][nx] == '#')continue;

	  char nc = G[ny][nx];
	  bool nfloor = getFloor(nc);
	  int cnt = 0;

	  rep(j,swt[ny][nx].size())
	    if((state>>swt[ny][nx][j]) & 1)cnt++;

	  if(cnt%2)nfloor = !nfloor;
	  
	  if(nc == '|')//stair
	    {
	      //same floor
	      if(mincost[floor][state][ny][nx] > cost + 1)
		{
		  mincost[floor][state][ny][nx] = cost + 1;	      
		  Q.push(P(nx,ny,state,cost+1,floor));
		}

	      //move down
	      if(mincost[!floor][state][ny][nx] > cost + 2)
		{	      
		  mincost[!floor][state][ny][nx] = cost + 2;
		  Q.push(P(nx,ny,state,cost+2,!floor));
		}

	      continue;
	    }

	  if(floor != nfloor)continue;
	  
	  if(isalpha(nc))//switch
	    {
	      
	      //dont use
	      if(mincost[floor][state][ny][nx] > cost + 1)
		{
		  mincost[floor][state][ny][nx] = cost + 1;
		  Q.push(P(nx,ny,state,cost+1,floor));
		}
	      
	      //use that
	      nc = tolower(nc);
	      int index = nc - 'a';
	      int nstate = state ^ (1<<index);
	      rep(j,swt[ny][nx].size())
		if(index == swt[ny][nx][j])
		  {
		    nfloor = !nfloor;
		    break;
		  }

	      if(mincost[nfloor][nstate][ny][nx] > cost + 2)
		{
		  mincost[nfloor][nstate][ny][nx] = cost + 2;
		  Q.push(P(nx,ny,nstate,cost+2,nfloor));
		}

	      continue;
	    }
	  
	  	    
	  //other
	  if(mincost[floor][state][ny][nx] > cost + 1)
	    {
	      mincost[floor][state][ny][nx] = cost + 1;
	      Q.push(P(nx,ny,state,cost+1,floor));
	    }
	  
	}

    }

  cout << -1 << endl;

}

void init()
{
  rep(i,H)rep(j,W)swt[i][j].clear();
  rep(l,2)rep(i,(1<<10))rep(j,H)rep(k,W)mincost[l][i][j][k] = inf;
}

int main()
{

  while(cin >> W >> H)
    { 
      init();
      rep(i,H)rep(j,W)
	{
	  cin >> G[i][j];
	  if(G[i][j] == '%')st = ii(j,i);
	}

      cin >> S;
      rep(s,S)
	{
	  char c;
	  rep(y,H)rep(x,W)
	    {
	      cin >> c;
	      if(c == '*')swt[y][x].push_back(s);
	    }
	}
	
      compute();

    }
  return 0;
}





  /*
  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();
      if(G[p.y][p.x] == '&')
	{
	  cout << p.cost << endl;
	  return;
	}

      bool floor = p.floor;
      int cnt = 0;
      rep(i,swt[p.y][p.x].size())
	if((p.state>>swt[p.y][p.x][i]) & 1)cnt++;
      if(cnt%2)floor = !floor;
	
      rep(i,4)
	{
	  int nx = p.x + dx[i];
	  int ny = p.y + dy[i];
	  if(!(0 <= nx && nx < W && 0 <= ny && ny < H))continue;
	  if(G[ny][nx] == '#')continue;
	  bool nfloor = getFloor(G[ny][nx]);
	  cnt = 0;
	  rep(j,swt[ny][nx].size())
	    if((p.state>>swt[ny][nx][j]) & 1)cnt++;
	  if(cnt%2)nfloor = !nfloor;

	  if(isalpha(G[ny][nx]))
	    {
	      if(nfloor != floor)continue;
	      if(mincost[p.state][ny][nx] > p.cost+1)
		{
		  mincost[p.state][ny][nx] = p.cost+1;
		  Q.push(P(nx,ny,p.state,p.cost+1,nfloor));
		}
	      char c = tolower(G[ny][nx]);
	      int nstate = p.state ^ (1<<(c-'a'));
	      if(mincost[nstate][ny][nx] > p.cost+2)
		{
		  mincost[nstate][ny][nx] = p.cost+2;
		  Q.push(P(nx,ny,nstate,p.cost+2));
		}
	    }
	  else if(G[ny][nx] == '|')
	    {
	      if(mincost[p.state][ny][nx] > p.cost+1)
		{
		  mincost[p.state][ny][nx] = p.cost+1;
		  Q.push(P(nx,ny,p.state,p.cost+1));
		}


	    }
	  else
	    {
	      if(nfloor != floor)continue;

	    }
	}
    }
  */

Measured memory_bytes: 23512