#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<string>
#define sgn(v) (abs((v))<eps?0:((v)<0?-1:1))
#define sqr(v) ((v)*(v))
#define mb make_pair
#define debug 0
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const double eps=1e-9;
const double pi=acos(-1);
char mp[51][51];
char sp[10][51][51];
int dp[1<<10][51][51][2];
const int inf=1e9+100;
int w,h,k;
struct State
{
	int sta,loc,flr;
	State(){}
	State(int s,int l,int f)
	{
		sta=s;loc=l;flr=f;
	}
};
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
bool vis[(1<<10)*5002+5000+2];
queue<State> q;
inline int tod(int sta,int x,int y,int flr)
{
	return sta*5002+(x*h+y)*2+flr;
}
void dfs(int sx,int sy)
{
	int x,y,cur,nsta,sta,flr,sgn;
	int i,j;
	State now;
	dp[0][sx][sy][0]=0;
	//cout <<sx<<" "<<sy<<" "<<h<<endl;
	q.push(State(0,sx*h+sy,0));
	vis[(sx*h+sy)*2]=true;
	while(!q.empty())
	{
		now=q.front();	
		q.pop();
		x=now.loc/h;
		y=now.loc%h;
		sta=now.sta;
		flr=now.flr;
		//cout <<sta<<" x&y:"<<x<<" "<<y<<" "<<flr<<" "<<vis[tod(sta,x,y,flr)]<<" "<<dp[sta][x][y][flr]<<endl;
		vis[tod(sta,x,y,flr)]=false;
		if(mp[x][y]=='|')
		{
			if(dp[sta][x][y][flr^1]>dp[sta][x][y][flr]+1)
			{
				dp[sta][x][y][flr^1]=dp[sta][x][y][flr]+1;
				if(!vis[tod(sta,x,y,flr^1)])
				{
					vis[tod(sta,x,y,flr^1)]=true;
					q.push(State(sta,x*h+y,flr^1));
				}
			}
		}
		for(cur=0,j=0;j<k;++j)
			if((sta&(1<<j))&&sp[j][x][y]=='*')cur^=1;
		if(isupper(mp[x][y])&&(cur^flr)==1)
		{
			if(sta&(1<<(mp[x][y]-'A')))
				nsta=sta&(~(1<<(mp[x][y]-'A')));
			else
				nsta=sta|(1<<(mp[x][y]-'A'));
			sgn=(sp[mp[x][y]-'A'][x][y]=='*');
			if(dp[nsta][x][y][flr^sgn]>dp[sta][x][y][flr]+1)
			{
				dp[nsta][x][y][flr^sgn]=dp[sta][x][y][flr]+1;
				if(!vis[tod(nsta,x,y,flr^sgn)])
				{
					vis[tod(nsta,x,y,flr^sgn)]=true;
					q.push(State(nsta,x*h+y,flr^sgn));
				}
			}
		}
		if(islower(mp[x][y])&&(cur^flr)==0)
		{
			if(sta&(1<<(mp[x][y]-'a')))
				nsta=sta&(~(1<<(mp[x][y]-'a')));
			else 
				nsta=sta|(1<<(mp[x][y]-'a'));
			sgn=(sp[mp[x][y]-'a'][x][y]=='*');
			if(dp[nsta][x][y][flr^sgn]>dp[sta][x][y][flr]+1)
			{
				dp[nsta][x][y][flr^sgn]=dp[sta][x][y][flr]+1;
				if(!vis[tod(nsta,x,y,flr^sgn)])
				{
					vis[tod(nsta,x,y,flr^sgn)]=true;
					q.push(State(nsta,x*h+y,flr^sgn));
				}
			}
		}
		for(i=0;i<4;++i)
		{
			sx=x+dx[i];
			sy=y+dy[i];
			if(sx<0||sx>=w||sy<0||sy>=h)continue;
			for(cur=0,j=0;j<k;++j)
				if((sta&(1<<j))&&sp[j][sx][sy]=='*')cur^=1;
			if((isupper(mp[sx][sy])||mp[sx][sy]=='^')&&(cur^flr)==1)
			{
				if(dp[sta][sx][sy][flr]>dp[sta][x][y][flr]+1)
				{
					dp[sta][sx][sy][flr]=dp[sta][x][y][flr]+1;
					if(!vis[tod(sta,sx,sy,flr)])
					{
						vis[tod(sta,sx,sy,flr)]=true;
						q.push(State(sta,sx*h+sy,flr));
					}
				}
			}
			else if((islower(mp[sx][sy])||mp[sx][sy]=='_'||mp[sx][sy]=='&'||mp[sx][sy]=='%')&&(cur^flr)==0)
			{
				if(dp[sta][sx][sy][flr]>dp[sta][x][y][flr]+1)
				{
					dp[sta][sx][sy][flr]=dp[sta][x][y][flr]+1;
					if(!vis[tod(sta,sx,sy,flr)])
					{
						vis[tod(sta,sx,sy,flr)]=true;
						q.push(State(sta,sx*h+sy,flr));
					}
				}
			}
			else if(mp[sx][sy]=='|')
			{
				if(dp[sta][sx][sy][flr]>dp[sta][x][y][flr]+1)
				{
					dp[sta][sx][sy][flr]=dp[sta][x][y][flr]+1;
					if(!vis[tod(sta,sx,sy,flr)])
					{
						vis[tod(sta,sx,sy,flr)]=true;
						q.push(State(sta,sx*h+sy,flr));
					}
				}
			}
		}
	}
}
int main()
{
	int i,j,p;
	int sx,sy,tx,ty;
	scanf("%d%d",&h,&w);
	for(i=0;i<w;++i)
		scanf("%s",mp[i]);
	scanf("%d",&k);
	for(i=0;i<k;++i)
		for(j=0;j<w;++j)
			scanf("%s",sp[i][j]);	
	int full=1<<k;
	for(i=0;i<full;++i)
		for(j=0;j<w;++j)
			for(p=0;p<h;++p)
				dp[i][j][p][0]=dp[i][j][p][1]=inf;
	for(i=0;i<w;++i)
		for(j=0;j<h;++j)
			if(mp[i][j]=='%')sx=i,sy=j;
			else if(mp[i][j]=='&')tx=i,ty=j;
	//cout <<"pre finished"<<" "<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<" "<<full<<endl;
	dfs(sx,sy);
	int ans=inf;
	for(i=0;i<full;++i)
	{
		ans=min(ans,dp[i][tx][ty][0]);
		ans=min(ans,dp[i][tx][ty][1]);
	}
	if(ans!=inf)printf("%d\n",ans);
	else printf("-1\n");
	return 0;
}

Measured memory_bytes: 27532