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:
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-5L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define seg_size 262144LL
#define MOD 998244353LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

// geometry library

typedef complex<long double> Point;
typedef pair<complex<long double>, complex<long double>> Line;

typedef struct Circle {
    complex<long double> center;
    long double r;
}Circle;

//内積、 dot(a,b) = |a||b|cos()
long double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}
//外積、cross(a,b) = |a||b|sin()
long double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

//線分と点の距離
long double Dist_Line_Point(Line a, Point b) {
    if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);
    if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);
    return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);
}

//線分の交差判定
int is_intersected_ls(Line a, Line b) {
    return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < 0) &&
        (cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < 0);
}

//線分の交点
Point intersection_l(Line a, Line b) {
    Point da = a.second - a.first;
    Point db = b.second - b.first;
    return a.first + da * cross(db, b.first - a.first) / cross(db, da);
}

//線分と線分の距離
long double Dist_Line_Line(Line a, Line b) {
    if (is_intersected_ls(a, b) == 1) {
        return 0;
    }
    return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });
}

//円と円の交点
pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {
    long double dist = abs(a.center - b.center);
    assert(dist <= eps + a.r + b.r);
    assert(dist+eps >= abs(a.r - b.r));
    Point target = b.center - a.center;
    long double pointer = target.real() * target.real() + target.imag() * target.imag();
    long double aa = pointer + a.r * a.r - b.r * b.r;
    aa /= 2.0L;
    Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa))/pointer,
            (aa* target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer};
    Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,
        (aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };
    r = r + a.center;
    l = l + a.center;
    return mp(l, r);
}

//end of geometry

template<typename A>
A pows(A val, ll b) {
    assert(b >= 1);
    A ans = val;
    b--;
    while (b) {
        if (b % 2) {
            ans *= val;
        }
        val *= val;
        b /= 2LL;
    }
    return ans;
}

template<typename A>
class Compressor {
public:
    bool is_zipped = false;
    map<A, ll> zipper;
    map<ll, A> unzipper;
    queue<A> fetcher;
    Compressor(){
        is_zipped = false;
        zipper.clear();
        unzipper.clear();
    }
    void add(A now) {
        assert(is_zipped == false);
        zipper[now] = 1;
        fetcher.push(now);
    }
    void exec() {
        assert(is_zipped == false);
        int cnt = 0;
        for (auto i = zipper.begin(); i != zipper.end(); ++i) {
            i->second = cnt;
            unzipper[cnt] = i->first;
            cnt++;
        }
        is_zipped = true;
    }
    ll fetch() {
        assert(is_zipped == true);
        A hoge = fetcher.front();
        fetcher.pop();
        return zipper[hoge];
    }
    ll zip(A now) {
        assert(is_zipped == true);
        assert(zipper.find(now) != zipper.end());
        return zipper[now];
    }
    A unzip(ll a) {
        assert(is_zipped == true);
        assert(a < unzipper.size());
        return unzipper[a];
    }
    ll next(A now) {
        auto x = zipper.upper_bound(now);
        if (x == zipper.end()) return zipper.size();
        return (ll)((*x).second);
    }
    ll back(A now) {
        auto x = zipper.lower_bound(now);
        if (x == zipper.begin()) return -1;
        x--;
        return (ll)((*x).second);
    }
};

template<typename A>
class Matrix {
public:
    vector<vector<A>> data;
    Matrix(vector<vector<A>> a) :data(a){

    }
    Matrix operator + (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = obj.data[i][q] + (this -> data[i][q]);
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator - (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = this->data[i][q] - obj.data[i][q];
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator * (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data[0].size());
        REP(i, this -> data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[0].size()) {
                A hoge = (this -> data[i][0]) * (obj.data[0][q]);
                for(int t = 1;t < obj.data[i].size();++t){
                    hoge += this -> data[i][t] * obj.data[t][q];
                }
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix &operator *= (const Matrix obj) {
        *this = (*this * obj);
        return *this;
    }
    Matrix& operator += (const Matrix obj) {
        *this = (*this + obj);
        return *this;
    }
    Matrix& operator -= (const Matrix obj) {
        *this = (*this - obj);
        return *this;
    }
};

class modint {
public:
    using u64 = std::uint_fast64_t;
    u64 value = 0;
    u64 mod;
    modint(ll a, ll b): value(((a%b) + 2 * b) % b),mod(b) {

    }
    modint operator+(const modint rhs) const{
        return modint(*this) += rhs;
    }
    modint operator-(const modint rhs) const{
        return modint(*this) -= rhs;
    }
    modint operator*(const modint rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator/(const modint rhs) const{
        return modint(*this) /= rhs;
    }
    modint& operator+=(const modint rhs) {
        assert(rhs.mod == mod);
        value += rhs.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
    modint& operator-=(const modint rhs) {
        assert(rhs.mod == mod);
        if (value < rhs.value) {
            value += mod;
        }
        value -= rhs.value;
        return *this;
    }
    modint& operator*=(const modint rhs) {
        assert(rhs.mod == mod);
        value = (value *  rhs.value) % mod;
        return *this;
    }
    modint& operator/=(modint rhs) {
        assert(rhs.mod == mod);
        ll rem = mod - 2;
        while (rem) {
            if (rem % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            rem /= 2LL;
        }
        return *this;
    }
    friend ostream& operator<<(ostream& os, modint& p) {
        os << p.value;
        return (os);
    }
};

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define int ll
int grid[2][50][50];
int dp[2][50][50][(1 << 10)];
int cnt[50][50];
int cnter(int a) {
    int ans = 0;
    REP(t, 20) {
        if ((1 << t) & a) {
            ans++;
        }
    }
    return ans;
}
void solve(){
    int w, h;
    cin >> w >> h;
    REP(i, 2) {
        REP(q, 50) {
            REP(j, 50) {
                REP(t, (1 << 10)) {
                    dp[i][q][j][t] = 1e9;
                }
            }
        }
    }
    queue<tuple<int, int, int, int>> next;
    tuple<int, int, int> goal;
    REP(i, h) {
        string s;
        cin >> s;
        REP(q, w) {
            if (s[q] == '|') {
                grid[0][i][q] = 1;
                grid[1][i][q] = 1;
            }
            if (s[q] == '_') {
                grid[0][i][q] = 2;
            }
            if (s[q] == '^') {
                grid[1][i][q] = 2;
            }
            if (s[q] == '%') {
                grid[0][i][q] = 2;
                dp[0][i][q][0] = 0;
                next.push(make_tuple(0, i, q, 0));
            }
            if (s[q] == '&') {
                grid[0][i][q] = 2;
                goal = make_tuple(0, i, q);
            }
            if (s[q] >= 'a' && s[q] <= 'z') {
                grid[0][i][q] = 3 + s[q] - 'a';
            }
            if (s[q] >= 'A' && s[q] <= 'Z') {
                grid[1][i][q] = 3 + s[q] - 'A';
            }
        }
    }
    int s;
    cin >> s;
    REP(tea, s) {
        REP(i, h) {
            string b;
            cin >> b;
            REP(q, w) {
                if (b[q] != '.') {
                    cnt[i][q] |= (1 << tea);
                }
            }
        }
    }
    while (next.empty() == false) {
        tuple<int, int, int, int> now = next.front();
        next.pop();
        int cost = dp[get<0>(now)][get<1>(now)][get<2>(now)][get<3>(now)] + 1;
        if (grid[0][get<1>(now)][get<2>(now)] == 1) {
            if (dp[(get<0>(now) + 1) % 2][get<1>(now)][get<2>(now)][get<3>(now)] == 1e9) {
                dp[(get<0>(now) + 1) % 2][get<1>(now)][get<2>(now)][get<3>(now)] = cost;
                next.push(make_tuple((get<0>(now) + 1) % 2, get<1>(now), get<2>(now), get<3>(now)));
            }
        }
        if (grid[(get<0>(now) + cnter(cnt[get<1>(now)][get<2>(now)] & get<3>(now))) % 2][get<1>(now)][get<2>(now)] >= 3) {
            int target = grid[(get<0>(now) + cnter(cnt[get<1>(now)][get<2>(now)] & get<3>(now))) % 2][get<1>(now)][get<2>(now)];
            target -= 3;
            int nexts = get<0>(now);
            if ((1 << target) & cnt[get<1>(now)][get<2>(now)]) {
                nexts++;
                nexts %= 2;
            }
            if (dp[nexts][get<1>(now)][get<2>(now)][get<3>(now) ^ (1 << target)] == 1e9) {
                dp[nexts][get<1>(now)][get<2>(now)][get<3>(now) ^ (1 << target)] = cost;
                next.push(make_tuple(nexts, get<1>(now), get<2>(now), get<3>(now) ^ (1 << target)));
            }
        }
        const int dx[4] = { 1,0,-1,0 };
        const int dy[4] = { 0,1,0,-1 };
        REP(t, 4) {
            int x = dx[t] + get<1>(now);
            int y = dy[t] + get<2>(now);
            if (x >= 0 && x < h && y >= 0 && y < w) {
                if (dp[get<0>(now)][x][y][get<3>(now)] != 1e9) continue;
                if (grid[(get<0>(now) + cnter(cnt[x][y] & get<3>(now))) % 2][x][y] >= 1) {
                    dp[get<0>(now)][x][y][get<3>(now)] = cost;
                    next.push(make_tuple(get<0>(now), x, y, get<3>(now)));
                }
            }
        }
    }
    int ans = 1e9;
    REP(i, (1 << s)) {
        ans = min(ans, dp[0][get<1>(goal)][get<2>(goal)][i]);
        ans = min(ans, dp[1][get<1>(goal)][get<2>(goal)][i]);
    }
    if (ans == 1e9) ans = -1;
    cout << ans << endl;
}

#undef int
int main() {
    init();
    solve();
}