def encode(floors, x, y, z)
    (floors[0] << 2513) + (floors[1] << 13) + (x << 7) + (y << 1) + z
end

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

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

floor0 = floor1 = 0

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

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

move = {}
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 == ?*
                m |= 1 << i * w + j
            end
        end
    end
    move[s] = m
end

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

catch(:break) do
    until queue.empty?
        state = queue.shift
        floors, x, y, z = decode(state)
        next_states = []
        if floors[z ^ 1][y * w + x] == 1
            next_states << encode(floors, x, y, z ^ 1)
        end
        [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dx, dy|
            u, v = x + dx, y + dy
            next if u < 0 || u >= w || v < 0 || v >= h
            next if floors[z][v * w + u] != 1
            next_states << encode(floors, u, v, z)
        end
        if c = switch[[x, y]]
            z1 = z
            z1 ^= 1 if move[c][y * w + x] == 1
            next_states << encode([floors[0] ^ move[c], floors[1] ^ move[c]], x, y, z1)
        end
        next_states.each do |s|
            next if dist[s]
            dist[s] = dist[state] + 1
            floors, x, y, z = decode(s)
            if x == gx && y == gy
                puts dist[s]
                throw(:break)
            end
            queue << s
        end
    end
    puts -1
end