Problem
O caçador de tesouros Vasya encontrou um mapa de uma antiga masmorra. A masmorra é um labirinto de tamanho NM (1NM100, NM100). Cada célula do labirinto é vazia e atravessável ou contém uma parede. Você só pode mover de uma célula para uma célula adjacente à parede (por exemplo, cada célula não pode ter mais de 4 células adjacentes).
Em uma das celas há um tesouro que Vasya quer pegar. O labirinto tem K entradas a partir das quais Vasya pode iniciar sua jornada.
É necessário determinar de qual entrada Vasya precisa iniciar sua jornada para que a distância percorrida até o tesouro seja a menor. Se houver várias dessas entradas, imprima a entrada com o menor número.
Entrada
A primeira linha contém 2 números N e M, que definem as dimensões do labirinto. A descrição do labirinto segue: N linhas com M caracteres cada. 0 significa que a célula está livre; 1 que há uma parede na gaiola. O símbolo * denota uma cela com um tesouro (existe exatamente uma dessas celas no labirinto).
A (N+2)ª linha contém o número K (1<=K<= NxM) -- o número de entradas para o labirinto. Em seguida, K linhas contêm as coordenadas das entradas. Assim, a i-ésima linha contém os números xi e yi, significando que a i-ésima entrada está localizada na xi-ésima linha e na yi-ésima coluna (1xiN1yiM). É garantido que as coordenadas das entradas sejam diferentes em pares e que todas as entradas estejam localizadas em células vazias. Nenhuma das entradas está na jaula do tesouro.
Saída
É necessário exibir um número - o número de entrada desejado (a numeração começa em 1). Se o tesouro não puder ser alcançado, imprima -1.
Exemplos
| # |
Entrada |
Saída |
| 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 |