human
CPP solution for "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...":


 ... Write me a Python program to calculate the minimum step to escape from the labyrinth, and go to the place your teammates are waiting!?
assistant
#Here is Python program to calculate the minimum step to escape from the labyrinth, and go to the place your teammates are waiting!
.
 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

struct state{
	int lev, r, c, swit, dist;

	void pp(int k){
		string s;
		int x = swit;
		rep(i, k) s += '0' + !!(x&(1<<i));
		printf("lev = %d, pos = (%d, %d), swit = %s, dist = %d\n", lev, r, c, s.c_str(), dist);
	}
};

int pos[50][50][1 << 10];
int vis[2][50][50][1 << 10];

int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

int grid(char c){
	return c == '^' || !!isupper(c);
}

void go(state &s, queue<state> &q){
	if (vis[s.lev][s.r][s.c][s.swit]) return;
	vis[s.lev][s.r][s.c][s.swit] = 1;
	q.push(s);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int w, h;
	cin >> w >> h;
	vector<string> v(h);
	rep(i, h) cin >> v[i];

	int n;
	cin >> n;
	vector<vector<string>> sw(n);
	rep(i, n){
		sw[i].resize(h);
		rep(j, h) cin >> sw[i][j];
	}

	int sr = -1, sc = -1;
	int gr = -1, gc = -1;
	rep(i, h) rep(j, w){
		char &c = v[i][j];
		if (c == '%') sr = i, sc = j;
		if (c == '&') gr = i, gc = j;
		if (c == '#') continue;
		if (c == '|') continue;
		int def = grid(c);
		if (isupper(c)) c += 'a' - 'A';
		rep(k, 1 << n){
			int &x = pos[i][j][k];
			x = def;
			rep(l, n) if ((k>>l&1) && sw[l][i][j] == '*') x ^= 1;
		}
	}

	queue<state> q;
	state init{ 0, sr, sc, 0, 0 };
	go(init, q);

	while (!q.empty()){
		auto s = q.front();
		q.pop();

		//s.pp(n);

		if (s.r == gr && s.c == gc){
			cout <<...