#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


bool is_change[10][50][50];

struct State{
	State(int arg_floor,int arg_row,int arg_col,int arg_button_state,int arg_step){
		floor = arg_floor;
		row = arg_row;
		col = arg_col;
		button_state = arg_button_state;
		step = arg_step;
	}

	bool operator<(const struct State &arg) const{
		return step > arg.step;
	};
	int floor,row,col,button_state,step;
};

int W,H,POW[11],diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
char first_map[50][51];

int dp[2][51][51][1024];


int main(){

	for(int i = 0; i < 11; i++)POW[i] = pow(2,i);

	scanf("%d %d",&W,&H);

	int start_row,start_col;

	for(int row = 0; row < H; row++){
		scanf("%s",first_map[row]);
		for(int col = 0; col < W; col++){
			if(first_map[row][col] == '%'){
				start_row = row;
				start_col = col;
				first_map[row][col] = '_';
			}
		}
	}

	int S;
	scanf("%d",&S);

	for(int i = 0; i < S; i++){
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				is_change[i][row][col] = false;
			}
		}
	}


	char tmp_map[H][W+1];

	for(int i = 0; i < S; i++){

		for(int row = 0; row < H; row++){
			scanf("%s",tmp_map[row]);
			for(int col = 0; col < W; col++){
				if(tmp_map[row][col] == '*'){
					is_change[i][row][col] = true;
				}
			}
		}
	}

	for(int i = 0; i < 2; i++){
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				for(int state = 0; state < POW[S]; state++)dp[i][row][col][state] = BIG_NUM;
			}
		}
	}


	priority_queue<State> Q;
	dp[0][start_row][start_col][0] = 0;
	Q.push(State(0,start_row,start_col,0,0));

	int calc_map[2][H][W];

	while(!Q.empty()){

		if(Q.top().step > dp[Q.top().floor][Q.top().row][Q.top().col][Q.top().button_state]){
			Q.pop();
			continue;
		}

		int calc_table[H][W];
		for(int row = max(0,Q.top().row-1); row <= min(Q.top().row+1,H-1); row++){
			for(int col = max(0,Q.top().col-1); col <= min(Q.top().col+1,W-1); col++)calc_table[row][col] = 0;
		}

		for(int loop = 0; loop < S; loop++){
			if(Q.top().button_state & (1 << loop)){
				for(int row = max(0,Q.top().row-1); row <= min(Q.top().row+1,H-1); row++){
					for(int col = max(0,Q.top().col-1); col <= min(Q.top().col+1,W-1); col++){
						if(is_change[loop][row][col])calc_table[row][col]++;
					}
				}
			}
		}

		for(int row = max(0,Q.top().row-1); row <= min(Q.top().row+1,H-1); row++){
			for(int col = max(0,Q.top().col-1); col <= min(Q.top().col+1,W-1); col++){
				switch(first_map[row][col]){
				case '#':
					calc_map[0][row][col] = '#';
					calc_map[1][row][col] = '#';
					break;
				case '|':
					calc_map[0][row][col] = '|';
					calc_map[1][row][col] = '|';
					break;
				case '^':
					if(calc_table[row][col]%2 == 0){
						calc_map[0][row][col] = '^';
						calc_map[1][row][col] = '^';
					}else{
						calc_map[0][row][col] = '_';
						calc_map[1][row][col] = '_';
					}
					break;
				case '_':
					if(calc_table[row][col]%2 == 0){
						calc_map[0][row][col] = '_';
						calc_map[1][row][col] = '_';
					}else{
						calc_map[0][row][col] = '^';
						calc_map[1][row][col] = '^';
					}
					break;
				case '&':
					if(calc_table[row][col]%2 == 0){
						calc_map[0][row][col] = '&';
						calc_map[1][row][col] = '_';
					}else{
						calc_map[0][row][col] = '^';
						calc_map[1][row][col] = '&';
					}
					break;
				default:
					if(first_map[row][col] >= 'a' && first_map[row][col] <= 'j'){
						if(calc_table[row][col]%2 == 0){
							calc_map[0][row][col] = first_map[row][col];
							calc_map[1][row][col] = '_';
						}else{
							calc_map[0][row][col] = '^';
							calc_map[1][row][col] = first_map[row][col]-32;
						}
					}else{
						if(calc_table[row][col]%2 == 0){
							calc_map[0][row][col] = '^';
							calc_map[1][row][col] = first_map[row][col];
						}else{
							calc_map[0][row][col] = first_map[row][col]+32;
							calc_map[1][row][col] = '_';
						}
					}
					break;
				}
			}
		}

		for(int i = 0; i < 4; i++){
			int adj_row = Q.top().row + diff_row[i];
			int adj_col = Q.top().col + diff_col[i];

			if(Q.top().floor == 0){

				if(calc_map[0][adj_row][adj_col] == '_'){
					if(dp[0][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[0][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(0,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}
				}else if(calc_map[0][adj_row][adj_col] == '|'){

					if(dp[1][adj_row][adj_col][Q.top().button_state] > Q.top().step+2){
						dp[1][adj_row][adj_col][Q.top().button_state] = Q.top().step+2;
						Q.push(State(1,adj_row,adj_col,Q.top().button_state,Q.top().step+2));
					}

					if(dp[0][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[0][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(0,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}

				}else if(calc_map[0][adj_row][adj_col] == '&'){
					printf("%d\n",Q.top().step+1);
					return 0;
				}else if(calc_map[0][adj_row][adj_col] >= 'a' && calc_map[0][adj_row][adj_col] <= 'j'){

					if(dp[0][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[0][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(0,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}

					int num = calc_map[Q.top().floor][adj_row][adj_col] - 'a';

					int next_floor = Q.top().floor;
					if(is_change[num][adj_row][adj_col]){
						next_floor = 1;
					}

					int next_state;
					if(Q.top().button_state & (1 << num)){
						next_state = Q.top().button_state - POW[num];
					}else{
						next_state = Q.top().button_state + POW[num];
					}

					if(dp[next_floor][adj_row][adj_col][next_state] > Q.top().step+2){
						dp[next_floor][adj_row][adj_col][next_state] = Q.top().step+2;
						Q.push(State(next_floor,adj_row,adj_col,next_state,Q.top().step+2));
					}
				}
			}else{
				if(calc_map[1][adj_row][adj_col] == '^'){
					if(dp[1][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[1][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(1,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}
				}else if(calc_map[1][adj_row][adj_col] == '|'){

					if(dp[0][adj_row][adj_col][Q.top().button_state] > Q.top().step+2){
						dp[0][adj_row][adj_col][Q.top().button_state] = Q.top().step+2;
						Q.push(State(0,adj_row,adj_col,Q.top().button_state,Q.top().step+2));
					}

					if(dp[1][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[1][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(1,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}

				}else if(calc_map[1][adj_row][adj_col] == '&'){
					printf("%d\n",Q.top().step+1);
					return 0;
				}else if(calc_map[1][adj_row][adj_col] >= 'A' && calc_map[1][adj_row][adj_col] <= 'J'){

					if(dp[1][adj_row][adj_col][Q.top().button_state] > Q.top().step+1){
						dp[1][adj_row][adj_col][Q.top().button_state] = Q.top().step+1;
						Q.push(State(1,adj_row,adj_col,Q.top().button_state,Q.top().step+1));
					}

					int num = calc_map[Q.top().floor][adj_row][adj_col] - 'A';

					int next_floor = Q.top().floor;
					if(is_change[num][adj_row][adj_col]){
						next_floor = 0;
					}

					int next_state;
					if(Q.top().button_state & (1 << num)){
						next_state = Q.top().button_state - POW[num];
					}else{
						next_state = Q.top().button_state + POW[num];
					}

					if(dp[next_floor][adj_row][adj_col][next_state] > Q.top().step+2){
						dp[next_floor][adj_row][adj_col][next_state] = Q.top().step+2;
						Q.push(State(next_floor,adj_row,adj_col,next_state,Q.top().step+2));
					}
				}
			}
		}
		Q.pop();
	}

	printf("-1\n");

	return 0;
}

Measured memory_bytes: 24784