KNIGHTSG - KNIGHTS level testing

The image above is an example of a level in Arzola's videogame 'KNIGHTS'. The rules are very simple. The player is given a chess board, where each square is either empty, contains a wall, or contains a knight of one of three colours. Some squares are also marked with a colour - the player beats the level if all marked squares contain a knight of their respective colour at the same time. To accomplish this, the player can select any knight and place him on an empty square using the classic chess knight move (2 squares in one direction, 1 square in a direction perpendicular to the first).

You will help test a few new level designs for this game. Given a starting configuration and several goal configurations (depicting which squares contain which knight), find the minimum number of moves required to get to those goal configurations.

Input

The first line contains two integers 1 ≤ r,c < 24.

The following r lines contain c characters each, describing the starting configuration of the level. The characters in the grid will be '#' for wall, '.' for an empty square, and 'R', 'B' and 'Y' for a red, blue and yellow knight, respectively. The number of squares that are not walls will be at most 12.

A blank line follows, followed by a line with an integer 1 ≤ q ≤ 75,000 - the number of suggested goal configurations for this level. You may assume that q*r*c ≤ 106.

q descriptions of goal configurations follow, separated by blank lines. Each description will be r rows consisting of c characters, from the same set as the starting configuration. You may assume that the walls are at the same places as in the starting configuration, and that the number of knights of each colour is the same as the number of knights of that colour in the starting configuration.

Output

For each suggested goal configuration, if it is not reachable from the starting configuration in any number of moves, output -1.

Otherwise, output the minimum number of moves required to reach that goal configuration from the starting configuration.

Example

Input:
3 4
#BYY
..R#
.BYR

4
#BYY
..R#
.BYR

#.YY
..R#
BBYR

#Y.Y
B.R#
.YRB

#..R
YYB#
YBR.

Output:
0
1
19
-1


Added by:Hodobox
Date:2017-08-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:inspired by indie game KNIGHTS

hide comments
2017-12-23 06:58:16 Min_25
@Hodobox
The image is not visible.

RE: fixed, hopefully. no idea why it didn't work, I just reuploaded it.

@Hodobox
Thank you ! Now, it is visible.

Last edit: 2017-12-24 05:33:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.