Беззработный Дэйв от скуки соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит
K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры
NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.
Входные данные
Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.
Выходные данные
Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 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
|