Un iepuras se gaseste intr-o gradina plina de surprize. Harta gradinii poate fi reprezentata sub forma unei table dreptunghiulare cu $m$ linii, numerotate de la 1 la $m$ de sus in jos, si $n$ coloane, numerotate de la 1 la $n$ de la stanga la dreapta. In fiecare celula a acestei gradini se poate gasi cel mult una dintre urmatoarele surprize: sageata, pom, zid, trapa, morcov, bomba.
O sageata indica una din directiile nord, sud, est, vest. Odata ajuns intr-o celula continand o astfel de sageata iepurasul isi va continua deplasarea in sensul indicat de sageata, iar aceasta dispare.
Intr-o celula in care se gaseste un pom sau un zid iepurasul nu poate sa patrunda, insa daca se “loveste†de un pom, el isi pastreaza directia, insa schimba sensul (daca se deplasa spre nord, isi va schimba sensul spre sud, daca se deplasa spre est, se va deplasa dupa aceea spre vest etc).
Daca iepurasul intra intr-o celula continand o trapa, toate zidurile aflate pe teren dispar si vor aparea alte ziduri, în pozitii precizate. Daca iepurasul va trece din nou printr-o celula continand o trapa, zidurile nou construite dispar si vor reaparea zidurile initiale. Mai exact exista doua grupe de ziduri care comuta la fiecare trecere printr-o celula care contine o trapa.
Intr-o celula in care se gaseste un pom sau un zid iepurasul nu poate sa patrunda, insa daca se "loveste" de un pom, el isi pastreaza directia, insa schimba sensul (daca se deplasa spre nord, isi va schimba sensul spre sud, daca se deplasa spre est, se va deplasa dupa aceea spre vest etc).
Daca iepurasul intra intr-o celula continand o trapa, toate zidurile aflate pe teren dispar si vor aparea alte ziduri, In pozitii precizate. Daca iepurasul va trece din nou printr-o celula continand o trapa, zidurile nou construite dispar si vor reaparea zidurile initiale. Mai exact exista doua grupe de ziduri care comuta la fiecare trecere printr-o celula care contine o trapa.
Daca iepurasul va trece de doua ori prin vecinatatea unei celule continand o bomba (adica prin celulele
invecinate la sud, nord, est sau vest cu celula continand bomba), bomba va exploda iar iepurasul se
transforma instantaneu in ingeras. De asemenea, daca iepurasul intra intr-o celula continand o bomba se
transforma instantaneu în ingeras. Iepurasul va rontai toti morcovii care ii ies în cale. Evident ca daca trece a doua oara prin aceeasi celula, la a doua trecere nu va mai gasi morcov.
transforma instantaneu in ingeras. Iepurasul va rontai toti morcovii care ii ies in cale. Evident ca daca trece a doua oara prin aceeasi celula, la a doua trecere nu va mai gasi morcov.
Surprizele din gradina sunt codificate astfel: 1 pentru sageata spre nord, 2 pentru sageata spre vest, 3 pentru sageata spre sud, 4 pentru sageata spre est, 5 pentru pom, 6 pentru bomba, 7 pentru morcov, 8 pentru zid, 9 pentru trapa. Casutele libere de pe harta gradinii se codifica cu 0.
Initial, se cunosc pozitia si sensul de deplasare ale iepurasului. Expeditia acestuia se termina in urmatoarele situatii:
* la explozia unei bombe, caz in care se transforma in ingeras;
* la parasirea gradinii (adica la iesirea în afara zonei dreptunghiulare date), caz in care se rataceste;
* la parasirea gradinii (adica la iesirea in afara zonei dreptunghiulare date), caz in care se rataceste;
* in momentul in care reuseste sa rontaie toti morcovii, caz in care este fericit.
h2. Cerinta
h2. Date de intrare
Fisierul de intrare $iepuras.in$ ...
Pe prima linie a fisierului de intrare $iepuras.in$ se gasesc doua numere intregi $m$ si $n$, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale hartii.
Linia a doua a fisierului contine trei numere naturale, separate prin cate un spatiu, reprezentand linia si coloana pozitiei initiale a iepurasului pe harta precum si directia spre care acesta este orientat. Directia este codificata astfel: $1$ pentru nord, $2$ pentru vest, $3$ pentru sud, $4$ pentru est.
Urmatoarele $m$ linii contin cate $n$ numere intregi separate prin cate un spatiu, reprezentand codificarea hartii gradinii, conform celor precizate mai sus.
Urmatoarea linie contine un singur numar natural $t$ reprezentand numarul de celule ce vor contine ziduri dupa prima trecere printr-o celula continand o trapa. Urmatoarele $t$ linii contin cate doua numere naturale $i$ si $j$, separate printr-un spatiu, reprezentand coordonatele cate unei celule ce va contine zid dupa o prima trecere printr-o celula continand o trapa.
h2. Date de iesire
In fisierul de iesire $iepuras.out$ ...
Fisierul de iesire $iepuras.out$ va contine pe prima sa linie unul dintre cuvintele INGERAS, RATACIT
respectiv FERICIT, corespunzator starii finale a iepurasului. A doua linie a fisierului va contine doua
numere intregi separate printr-un spatiu, reprezentand linia si coloana ultimei pozitii de pe teren a iepurasului, adica pozitia in care a murit, sau in care a devenit fericit, respectiv ultima pozitie a sa de pe teren, inainte de a se rataci.
A treia linie a fisierului va contine doua numere intregi separate printr-un spatiu, reprezentând numarul de morcovi culesi pana in momentul terminarii expeditiei, respectiv numarul de pasi pe care ii face iepurasul pana ajunge in starea finala.
h2. Restrictii
