Problem
Der Schatzsucher von Vashe hat eine Karte des alten Dungeons gefunden. Der Dungeon ist ein Labyrinth der Größe NM (1NM100 , NM100). Jede Zelle des Labyrinths ist entweder leer und kann durch sie geleitet werden oder enthält eine Wand. Aus der Zelle kann man nur in eine an der Wand angrenzende Zelle übergehen (jede Zelle kann also nicht mehr als 4 benachbarte Zellen haben).
In einer der Zellen befindet sich ein Schatz, den Vasya bekommen möchte. Es gibt K-Eingänge im Labyrinth, aus denen Vasya ihre Reise beginnen kann.
Sie müssen bestimmen, von welchem Eingang Sie Ihre Reise beginnen müssen, damit die zurückgelegte Entfernung zum Schatz am wenigsten beträgt. Wenn es mehrere Eingänge gibt, müssen Sie den Eingang mit der kleinsten Nummer anzeigen.
Eingabe
Die erste Zeile enthält 2 Zahlen N und M, die die Größe des Labyrinths angeben. Es folgt eine Beschreibung des Labyrinths: N Zeilen mit jeweils M Zeichen. 0 bedeutet, dass die Zelle frei ist; 1, dass sich eine Wand im Käfig befindet. Das Symbol * bezeichnet einen Käfig mit einem Schatz (dieser Käfig ist genau einer im Labyrinth).
In der (N+2)-ten Zeile ist die Zahl K (1<=K<= NxM) -- die Anzahl der Eingänge in das Labyrinth. Als nächstes enthalten die K-Zeilen die Koordinaten der Eingaben. So enthält die i-ten Zeile die Zahlen xi und yi, was bedeutet, dass sich die i-ten Eingabe in der xi-ten Zeile und in der yi-ten Spalte (1xiN1yiM) befindet. Es ist garantiert, dass die Koordinaten der Eingänge paarweise unterschiedlich sind und dass sich alle Eingänge in leeren Zellen befinden. Keiner der Eingänge befindet sich in einem Schatzkäfig.
Ausgabe
Sie müssen eine Zahl ausgeben - die gewünschte Eingangsnummer (die Nummerierung beginnt mit 1). Wenn es unmöglich ist, den Schatz zu erreichen, bringen Sie -1 heraus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |