Unemployed Dave out of boredom built a labyrinth out of cardboard boxes in his own living room. Maze contains
K inputs. When his girlfriend Annie returned, the labyrinth grew incredibly from the inside, and the unfortunate inventor himself got lost there and can't get out.
The only thing Annie found in the room was a map of the labyrinth, which has dimensions of
NxM cells. The map showed the place where Dave is located (no one knows how it happened). The cells of the labyrinth are either empty, which you can walk through, or there is a wall in them and you cannot walk through them. A cell can have up to 4 adjacent cells, which can be accessed from the current one.
Annie has invited you to help her figure out where to start on her way to get to Dave as quickly as possible. If there are multiple such entrances, Annie will go from the entrance with the smallest number.
Input
The program takes several lines as input. The first line contains 2 numbers N and M (1<= N, M <= 100, NxM <= 100), dimensions labyrinth. This is followed by N lines of M characters each - a description of the labyrinth. 0 means that the cell is free; 1 that there is a wall in the cage. The symbol * denotes a cage with Dave.
The (N+2)th line contains the number K (1<=K<=NxM) -- the number of entrances to the labyrinth. The K lines then contain the coordinates of the inputs. The ith line contains the numbers xi and yi meaning that i- The th entry is located in the xith row and in the yith column (1<=xi<=N,1<=yi<=M).
The coordinates of the entrances are pairwise different, all the entrances are located in empty cells. None of the entrances are in the cage with Dave.
Output
Print one number - the input number (numbering starts from 1). If Dave can't be reached, print -1.
Examples
| # |
Input |
Output |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
eleven
15
4 1
5 5
|
1
|
| 2 |
3 3
010
1*1
010
4
eleven
13
3 1
3 3
|
-1
|