misholovac

Dat je lavirint dimenzija m x n. Tacno jedno polje lavirinta sadrži sir, dok su ostala polja prolaz ili zid. U njemu se nalaze macka i miš na odredenim pocetnim pozicijama. Oni se krecu naizmenicno, po potezima, pri cemu je miš prvi. U svom potezu macka ili miš mogu da se pomere na susedno polje (pri tome su dijagonalna polja takode susedna), ili da ostanu na istom polju. Pri pomeranju macke na polje na kome je miš ona ga jede, dok pri pomeranju miša na polje na kome je sir on jede sir. Macka ne sme da se pomeri na polje na kome je sir. U svakom trenutku macka zna tacnu poziciju miša i obrnuto. Cilj miša je da pojede sir, a macke da ga spreci, bez obzira da li ce ga pojesti ili ne. Ispitati šta ce se od ova dva desiti pri njihovom optimalnom kretanju. <br><br>
Sa prvog standardnog ulaza ucitavaju se dimenzije lavirinta m i n, pri cemu je m broj vrsta, a n broj kolona (1 <= m, n <= 50). U svakom od sledecih m redova nalazi se po n znakova koji opisuju lavirint. Znak "*" predstavlja polje na kome je sir, "X" polje koje sadrži zid, dok "." predstavlja prazno polje. Ostali znakovi se nece pojavljivati. U sledecem redu nalazi se broj p (1 <= p <= 8), i to je broj parova pocetnih pozicija macke i miša koje se ispituju. U svakom od sledecih p redova nalaze se po cetri broja. Prvi par brojeva predstavlja koordinate miša (prvo broj vrste, zatim broj kolone), a drugi macke. Gornje-levo polje lavirinta ima koordinate (1, 1), a donje-desno (m, n). <br><br>
Na standardni izlaz treba ispisati p redova. Za i-ti par pozicija macke i miša iz ulaznog fajla u i-ti red izlaznog fajla treba upisati 1 ukoliko miš uspeva da pojede sir, a 0 ukoliko macka može da ga spreci. <br><br>

Primer: <br><br>
Ulaz: <br>
4 3<br>
.*. <br>
... <br>
.X. <br>
... <br>
2<br>
3 1 3 3<br>
4 2 2 2<br>
<br>Izlaz: <br>
1<br>0