def encode(switch_state, x, y, z)
    (switch_state << 13) + (x << 7) + (y << 1) + z
end

def decode(state)
    [state >> 13, (state >> 7) & 0b111111, (state >> 1) & 0b111111, state & 0b1]
end

w, h = gets.split.map(&:to_i)

init_floor = wall = stair = 0

switch = {}
gx = gy = nil
sx = sy = nil

(0..h-1).each do |i|
    gets.chomp.each_char.with_index do |c, j|
        bit = 1 << i * w + j
        case c
        when ?#
            wall   |= bit
        when ?_
        when ?^
            init_floor |= bit
        when /[a-z]/
            switch[[j, i]] = c.ord - ?a.ord
        when /[A-Z]/
            init_floor |= bit
            switch[[j, i]] = c.ord - ?A.ord
        when ?|
            stair |= bit
        when ?&
            gx = j
            gy = i
        when ?%
            sx = j
            sy = i
        end
    end
end

mover = (0..h-1).map { [0] * w }
gets.to_i.times do |k|
    s = (?a.ord + k).chr
    m = 0
    (0..h-1).each do |i|
        gets.chomp.each_char.with_index do |c, j|
            if c == ?*
                mover[i][j] |= (1 << k)
            end
        end
    end
end

init_state = encode(0, sx, sy, 0)
dist = {init_state => 0}
queue = [init_state]

def one_num_parity(x)
    k = 0
    until x == 0
        x &= (x - 1)
        k ^= 1
    end
    k
end

dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
catch(:break) do
    until queue.empty?
        state = queue.shift
        switch_state, x, y, z = decode(state)
        next_states = []

        if stair[y * w + x] == 1
            next_states << encode(switch_state, x, y, z ^ 1)
        end

        if i = switch[[x, y]]
            next_states << encode(switch_state ^ (1 << i), x, y, z ^ mover[y][x][i])
        end

        dirs.each do |dx, dy|
            u, v = x + dx, y + dy
            pos = v * w + u
            next if wall[pos] == 1
            if stair[pos] == 1
                next_states << encode(switch_state, u, v, z)
            elsif init_floor[pos] ^ one_num_parity(mover[v][u] & switch_state) == z
                next_states << encode(switch_state, u, v, z)
            end
        end

        next_states.each do |s|
            next if dist[s]
            dist[s] = dist[state] + 1
            _, x, y, _ = decode(s)
            if x == gx && y == gy
                puts dist[s]
                throw(:break)
            end
            queue << s
        end
    end
    puts -1
end