Problem
The treasure hunter Vasya came across a map of an ancient dungeon. The dungeon is an NM size maze (1NM100 , NM100). Each cell of the labyrinth is either empty and traversable, or contains a wall. You can only move from a cell to a cell adjacent to the wall (for example, each cell can have no more than 4 adjacent cells).
In one of the cells there is a treasure that Vasya wants to get. The labyrinth has K entrances from which Vasya can start his journey.
It is required to determine from which entrance Vasya needs to start his journey so that the distance traveled to the treasure is the least. If there are several such inputs, print the input with the smallest number.
Input
The first line contains 2 numbers N and M, which define the dimensions of the maze. The description of the labyrinth follows: N lines with M characters each. 0 means that the cell is free; 1 that there is a wall in the cage. The symbol * denotes a cell with a treasure (there is exactly one such cell in the labyrinth).
The (N+2)th line contains the number K (1<=K<= NxM) -- the number of entrances to the labyrinth. Next, K lines contain the coordinates of the inputs. Thus, the i-th line contains numbers xi and yi, meaning that the i-th input is located in the xi-th line and in the yi-th column (1xiN1yiM). It is guaranteed that the coordinates of the inputs are pairwise different, and that all the inputs are located in empty cells. None of the entrances are in the treasure cage.
Output
It is necessary to display one number - the desired input number (numbering starts from 1). If the treasure cannot be reached, print -1.
Examples
| # |
Input |
Output |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |