Problem
Pemburu harta karun Vasya terjumpa peta penjara bawah tanah purba. Penjara adalah labirin bersaiz NM (1NM100 , NM100). Setiap sel labirin sama ada kosong dan boleh dilalui, atau mengandungi dinding. Anda hanya boleh bergerak dari sel ke sel bersebelahan dengan dinding (contohnya, setiap sel boleh mempunyai tidak lebih daripada 4 sel bersebelahan).
Dalam salah satu sel ada harta karun yang Vasya mahu dapatkan. Labirin mempunyai K pintu masuk dari mana Vasya boleh memulakan perjalanannya.
Diperlukan untuk menentukan dari pintu masuk mana Vasya perlu memulakan perjalanannya supaya jarak yang ditempuh ke harta karun adalah paling sedikit. Jika terdapat beberapa input sedemikian, cetak input dengan nombor terkecil.
Input
Baris pertama mengandungi 2 nombor N dan M, yang mentakrifkan dimensi labirin. Perihalan labirin berikut: N baris dengan M aksara setiap satu. 0 bermakna sel itu bebas; 1 bahawa terdapat dinding di dalam sangkar. Simbol * menandakan sel dengan harta karun (ada betul-betul satu sel sedemikian dalam labirin).
Baris ke (N+2) mengandungi nombor K (1<=K<= NxM) -- bilangan pintu masuk ke labirin. Seterusnya, garisan K mengandungi koordinat input. Oleh itu, baris ke-i mengandungi nombor xi dan yi, bermakna input ke-i terletak pada baris ke-xi dan dalam lajur ke-yi (1xiN1yiM). Ia dijamin bahawa koordinat input adalah berbeza secara berpasangan, dan semua input terletak dalam sel kosong. Tiada satu pun pintu masuk berada dalam sangkar harta karun.
Output
Perlu untuk memaparkan satu nombor - nombor input yang diingini (penomboran bermula dari 1). Jika harta itu tidak dapat dicapai, cetak -1.
Contoh
| # |
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 |