Problem: It was the last day of the summer camp you strayed into the labyrinth on the way to Komaba Campus, the University of Tokyo. The contest has just begun. Your teammates must impatiently wait for you. So you have to escape from this labyrinth as soon as possible.
The labyrinth is represented by a grid map. Initially, each grid except for walls and stairs is either on the first floor or on the second floor. Some grids have a switch which can move up or down some of the grids (the grids on the first floor move to the second floor, and the grids on the second floor to the first floor).
In each step, you can take one of the following actions:


* Move to an adjacent grid (includes stairs) on the same floor you are now in.

* Move to another floor (if you are in the stairs grid).

* Operate the switch (if you are in a grid with a switch).




Luckily, you have just found a map of the labyrinth for some unknown reason. Let's calculate the minimum step to escape from the labyrinth, and go to the place your teammates are waiting!



Input

The format of the input is as follows.


> W H
> M11M12M13...M1W
> M21M22M23...M2W
> ........
> MH1MH2MH3...MHW
> S
> MS111MS112MS113...MS11W
> MS121MS122MS123...MS12W
> ........
> MS1H1MS1H2MS1H3...MS1HW
> MS211MS212MS213...MS21W
> MS221MS222MS223...MS22W
> ........
> MS2H1MS2H2MS2H3...MS2HW
> MSS11MSS12MSS13...MSS1W
> MSS21MSS22MSS23...MSS2W
> ........
> MSSH1MSSH2MSSH3...MSSHW
>

The first line contains two integers W (3 ≤ W ≤ 50) and H (3 ≤ H ≤ 50). They represent the width and height of the labyrinth, respectively.
The following H lines represent the initial state of the labyrinth. Each of Mij is one of the following symbols:


* '#' representing a wall,
* '|' representing stairs,
* '_' representing a grid which is initially on the first floor,
* '^' representing a grid which is initially on the second floor,
* a lowercase letter from 'a' to 'j' representing a switch the grid has, and the grid is initially on the first floor,
* an uppercase letter from 'A' to 'J' representing a switch the grid has, and the grid is initially on the second floor,
* '%' representing the grid you are initially in (which is initially on the first floor) or
* '&' representing the exit of the labyrinth (which is initially on the first floor).



The next line contains one integer S (0 ≤ S ≤ 10), and then the following SH lines represent the information of the switches. Each of MSkij is one of:


* '#' if Mij is a '#',
* '|' if Mij is a '|',
* '*' if the grid is moved by the switch represented by the k-th alphabet letter, or
* '.' otherwise.



Note that the grid which contains a switch may be moved by operating the switch. In this case, you will move together with the grid.
You may assume each of the '%' (start) and '&' (goal) appears exacyly once, that the map is surround by walls, and that each alphabet in the map is any of the letters from 'A' (or 'a') to S-th alphabet letter.

Output

Print the minimum step to reach the goal in one line. If there is no solution, print "-1".

Examples

Input

6 6
######
#_|A%#
#B#_|#
#^BBa#
#B&A##
######
2
######
#*|*.#
#.#.|#
#*.**#
#...##
######
######
#*|*.#
#*#.|#
#..**#
#..*##
######


Output

21


Input

6 6

_|A%#
B#_|#
^BBa#
B&A##

2

*|*.#
.#.|#
*.**#
...##


*|*.#
*#.|#
..**#
..*##


Output

21


Input

8 3

%||Aa&#

2

*||*..#


.||*.*#


Output

7


Input

3 4

%#
&#

0


Output

1


Input

3 5

%#
^#
&#

0


Output

-1

Solution (in CPP):

Solution:
/*
 Author : Speedcell
 Update : 2013-05-30
Version : soppYcell 2.2(a)
*/

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <memory>
#include <complex>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

#pragma pack(4)

#ifndef __CONSTANT__
#define __CONSTANT__

typedef long long LONG;

const double pi = acos(-1.0);
const int   inf = 0x7f7f7f7f;
const LONG  INF = 0x7f7f7f7f7f7f7f7fll;

const int go[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

#endif // __CONSTANT__

#ifndef __IO__
#define __IO__

inline bool RD(int    & a) {return scanf("%d",&a)!=EOF;}
inline bool RD(char   & a) {return scanf("%c",&a)!=EOF;}
inline bool RD(char   * a) {return scanf("%s", a)!=EOF;}
inline bool RD(double & a) {return scanf("%lf",&a)!=EOF;}
inline bool RD(LONG   & a) {return scanf("%I64d",&a)!=EOF;}

template<class T1> inline bool
    IN(T1 & a) {return RD(a);}
template<class T1,class T2> inline bool
    IN(T1 & a,T2 & b) {return RD(a)&&RD(b);}
template<class T1,class T2,class T3> inline bool
    IN(T1 & a,T2 & b,T3 & c) {return RD(a)&&RD(b)&&RD(c);}
template<class T1,class T2,class T3,class T4> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d) {return RD(a)&&RD(b)&&RD(c)&&RD(d);}
template<class T1,class T2,class T3,class T4,class T5> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e);}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e,T6 & f) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e)&&RD(f);}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline bool
    IN(T1 & a,T2 & b,T3 & c,T4 & d,T5 & e,T6 & f,T7 & g) {return RD(a)&&RD(b)&&RD(c)&&RD(d)&&RD(e)&&RD(f)&&RD(g);}

inline void PT(int    a) {printf("%d",a);}
inline void PT(char   a) {printf("%c",a);}
inline void PT(char * a) {printf("%s",a);}
inline void PT(double a) {printf("%f",a);}
inline void PT(LONG   a) {printf("%I64d",a);}
inline void PT(const char a[]) {printf("%s",a);}

template<class T1> inline void
    OT(T1 a) {PT(a);}
template<class T1,class T2> inline void
    OT(T1 a,T2 b) {PT(a),PT(' '),PT(b);}
template<class T1,class T2,class T3> inline void
    OT(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PT(c);}
template<class T1,class T2,class T3,class T4> inline void
    OT(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d);}
template<class T1,class T2,class T3,class T4,class T5> inline void
    OT(T1 a,T2 b,T3 c,T4 d,T5 e) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e);}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
    OT(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f);}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
    OT(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f,T7 g) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f),PT(' '),PT(g);}

template<class T1> inline void
    OL(T1 a) {PT(a),PT('\n');}
template<class T1,class T2> inline void
    OL(T1 a,T2 b) {PT(a),PT(' '),PT(b),PT('\n');}
template<class T1,class T2,class T3> inline void
    OL(T1 a,T2 b,T3 c) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT('\n');}
template<class T1,class T2,class T3,class T4> inline void
    OL(T1 a,T2 b,T3 c,T4 d) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT('\n');}
template<class T1,class T2,class T3,class T4,class T5> inline void
    OL(T1 a,T2 b,T3 c,T4 d,T5 e) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT('\n');}
template<class T1,class T2,class T3,class T4,class T5,class T6> inline void
    OL(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f),PT('\n');}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> inline void
    OL(T1 a,T2 b,T3 c,T4 d,T5 e,T6 f,T7 g) {PT(a),PT(' '),PT(b),PT(' '),PT(c),PT(' '),PT(d),PT(' '),PT(e),PT(' '),PT(f),PT(' '),PT(g),PT('\n');}

#endif // __IO__

#ifndef __MACRO__
#define __MACRO__

#define ML(times) int tcase; IN(tcase); FOR(times,1,tcase)

#define FOR(i,a,b) for(int i=int(a),_##i=int(b);i<=_##i;i++)
#define DWN(i,b,a) for(int i=int(b),_##i=int(a);_##i<=i;i--)
#define ECH(i,u,pre,next) for(int i=int(pre[u]);i!=-1;i=int(next[i]))

#define MEM(a,v) memset(a,v,sizeof(a))
#define CLR(a,v) FOR(_i##a,0,sizeof(a)/sizeof(a[0])-1) a[_i##a]=v

#define LOOP(a,n)                                               \
    FOR(_i##a,0,(n)-1)                                          \
        OT(a[_i##a]),OT(_i##a!=__i##a?' ':'\n')
#define LOOP2(a,n,m)                                            \
    FOR(_i##a,0,(n)-1) FOR(_j##a,0,(m)-1)                       \
        OT(a[_i##a][_j##a]),OT(_j##a!=__j##a?' ':'\n')
#define LOOPG(G,n,pre,next)                                     \
    FOR(_i##a,0,(n)-1) ECH(_j##a,_i##a,pre,next)                \
        OL(_i##a,G[_j##a].v,G[_j##a].w)

#endif // __MACRO__

#ifndef __BIT__
#define __BIT__

template<class T> inline T lb(T i) {return i&-i;}
template<class T> inline T lc(T i) {return i<<1;}
template<class T> inline T rc(T i) {return i<<1|1;}
template<class T> inline T at(T a,int i) {return a& (T(1)<<i);}
template<class T> inline T nt(T a,int i) {return a^ (T(1)<<i);}
template<class T> inline T s1(T a,int i) {return a| (T(1)<<i);}
template<class T> inline T s0(T a,int i) {return a&~(T(1)<<i);}

#endif // __BIT__

#ifndef __DOUBLE__
#define __DOUBLE__

const double eps = 1e-8;

inline int cmp(double a,double b=0) {return fabs(b-a)<eps?0:((b-a)<eps?+1:-1);}

inline double smax(double a,double b) {return cmp(b,a)<0?a:b;}
inline double smin(double a,double b) {return cmp(a,b)<0?a:b;}
template<typename type> inline type smax(type a,type b) {return b<a?a:b;}
template<typename type> inline type smin(type a,type b) {return a<b?a:b;}

#endif // __DOUBLE__

const int MAXV = 51;
const int MAXE = 1<<10;

int n,m,s;
char a[MAXV][MAXV],b[MAXV][MAXV];
map<int,map<int,map<int,bool> > > switcher;//TODO

deque<int> X,Y,F,B;
int dis[MAXV][MAXV][2][MAXE];
bool inq[MAXV][MAXV][2][MAXE];

int floor(int x,int y,int b)
{
	int ans=(a[x][y]=='^'||('A'<=a[x][y]&&a[x][y]<='Z'));
	FOR(i,0,s-1) if(at(b,i))
	{
		if(switcher[i][x][y]) ans^=1;
	}
	return ans;
}
bool sameFloor(int x,int y,int f,int b)
{
	if(a[x][y]=='#') return false;
	else if(a[x][y]=='|') return true;
	else return floor(x,y,b)==f;
}
bool within(int x,int y,int f,int b)
{
	if((0<=x&&x<n)&&(0<=y&&y<m)) return sameFloor(x,y,f,b);
	else return false;
}

void update(int xx,int yy,int ff,int bb,int x,int y,int f,int b)
{
	if(dis[xx][yy][ff][bb]>dis[x][y][f][b]+1)
	{
		dis[xx][yy][ff][bb]=dis[x][y][f][b]+1;
		if(!inq[xx][yy][ff][bb])
		{
			inq[xx][yy][ff][bb]=true;
			X.push_back(xx);
			Y.push_back(yy);
			F.push_back(ff);
			B.push_back(bb);
		}
	}
}

int SPFA(int x,int y,int f,int b,int tx,int ty)
{
	MEM(dis,inf); dis[x][y][f][b]=0;
	MEM(inq,false); inq[x][y][f][b]=true;

	while(!X.empty()) X.pop_front();
	while(!Y.empty()) Y.pop_front();
	while(!F.empty()) F.pop_front();
	while(!B.empty()) B.pop_front();
	X.push_back(x);
	Y.push_back(y);
	F.push_back(f);
	B.push_back(b);

	while(!X.empty())
	{
		x=X.front(); X.pop_front();
		y=Y.front(); Y.pop_front();
		f=F.front(); F.pop_front();
		b=B.front(); B.pop_front();
		inq[x][y][f][b]=false;
		if(x==tx&&y==ty&&sameFloor(tx,ty,f,b)) return dis[x][y][f][b];
		FOR(i,0,3)
		{
			int xx=x+go[i][0];
			int yy=y+go[i][1];
			if(within(xx,yy,f,b)) update(xx,yy,f,b,x,y,f,b);
		}
		if(a[x][y]=='|')
			update(x,y,!f,b,x,y,f,b);
		if(sameFloor(x,y,f,b)&&'a'<=a[x][y]&&a[x][y]<='z')
			update(x,y,f^switcher[a[x][y]-'a'][x][y],nt(b,a[x][y]-'a'),x,y,f,b);
		if(sameFloor(x,y,f,b)&&'A'<=a[x][y]&&a[x][y]<='Z')
			update(x,y,f^switcher[a[x][y]-'A'][x][y],nt(b,a[x][y]-'A'),x,y,f,b);
	}

	int ans=inf;
	FOR(i,0,((1<<s)-1))
	{
		ans=smin(ans,dis[tx][ty][floor(tx,ty,i)][i]);
	}
	return ans==inf?-1:ans;
}

int main()
{
    while(IN(m,n))
	{
		FOR(i,0,n-1)
		{
			getchar();
			IN(a[i]);
		}
		IN(s);
		switcher.clear();
		FOR(k,0,s-1)
		{
			FOR(i,0,n-1)
			{
				getchar();
				IN(b[i]);
			}
			FOR(i,0,n-1) FOR(j,0,m-1)
			{
				if(b[i][j]=='*')
				{
					switcher[k][i][j]=true;
				}
			}
		}
		int x,y,tx,ty;
		FOR(i,0,n-1) FOR(j,0,m-1)
		{
			if(a[i][j]=='%')
			{
				x=i;
				y=j;
			}
			else if(a[i][j]=='&')
			{
				tx=i;
				ty=j;
			}
		}
		OL(SPFA(x,y,0,0,tx,ty));
	}

    return 0;
}