Problem
Le chasseur de trésors Vasya est tombé sur une carte d'un ancien donjon. Le donjon est un labyrinthe de taille NM (1NM100 , NM100). Chaque cellule du labyrinthe est soit vide et traversable, soit contient un mur. Vous ne pouvez vous déplacer que d'une cellule à une cellule adjacente au mur (par exemple, chaque cellule ne peut pas avoir plus de 4 cellules adjacentes).
Dans l'une des cellules, il y a un trésor que Vasya veut obtenir. Le labyrinthe a K entrées à partir desquelles Vasya peut commencer son voyage.
Il est nécessaire de déterminer à partir de quelle entrée Vasya doit commencer son voyage afin que la distance parcourue jusqu'au trésor soit la plus faible. S'il y a plusieurs entrées de ce type, imprimez l'entrée avec le plus petit numéro.
Entrée
La première ligne contient 2 nombres N et M, qui définissent les dimensions du labyrinthe. La description du labyrinthe suit : N lignes de M caractères chacune. 0 signifie que la cellule est libre ; 1 qu'il y a un mur dans la cage. Le symbole * désigne une cellule avec un trésor (il y a exactement une telle cellule dans le labyrinthe).
La (N+2)ème ligne contient le nombre K (1<=K<= NxM) -- le nombre d'entrées au labyrinthe. Ensuite, K lignes contiennent les coordonnées des entrées. Ainsi, la ième ligne contient les nombres xi et yi, ce qui signifie que la ième entrée est située dans la xi-ième ligne et dans la yi-ième colonne (1xiN1yiM). Il est garanti que les coordonnées des entrées sont deux à deux différentes et que toutes les entrées sont situées dans des cellules vides. Aucune des entrées ne se trouve dans la cage au trésor.
Sortie
Il est nécessaire d'afficher un numéro - le numéro d'entrée souhaité (la numérotation commence à partir de 1). Si le trésor ne peut pas être atteint, écrivez -1.
Exemples
| # |
Entrée |
Sortie |
| 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 |