iepuras

Un iepuraş se găseşte într-o grădină plină de surprize.

Harta grădinii poate fi reprezentată sub forma unei table dreptunghiulare cu $m$ linii, numerotate de la $1$ la $m$ de sus în jos, şi $n$ coloane, numerotate de la $1$ la $n$ de la stânga la dreapta.

În fiecare celulă a acestei grădini se poate găsi cel mult una dintre următoarele surprize: săgeată, pom, zid, trapă, morcov, bombă.

O săgeată indică una din direcţiile nord, sud, est, vest. Odată ajuns într-o celulă conţinând o astfel de săgeată iepuraşul îşi va continua deplasarea în sensul indicat de săgeată, iar aceasta dispare.

Într-o celulă în care se găseşte un pom sau un zid iepuraşul nu poate să pătrundă, însă dacă se “loveşte” de un pom, el îşi păstrează direcţia, însă schimbă sensul (dacă se deplasa spre nord, îşi va schimba sensul spre sud, dacă se deplasa spre est, se va deplasa după aceea spre vest etc).

Dacă iepuraşul intră într-o celulă conţinând o trapă, toate zidurile aflate pe teren dispar şi vor apărea alte ziduri, în poziţii precizate. Dacă iepuraşul va trece din nou printr-o celulă conţinând o trapă, zidurile nou construite dispar şi vor reapărea zidurile iniţiale. Mai exact există două grupe de ziduri care comută la fiecare trecere printr-o celulă care conţine o trapă.

Dacă iepuraşul va trece de două ori prin vecinătatea unei celule conţinând o bombă (adică prin celulele învecinate la sud, nord, est sau vest cu celula conţinând bombă), bomba va exploda iar iepuraşul se transformă instantaneu în îngeraş. De asemenea, dacă iepuraşul întră într-o celulă conţinând o bombă se transformă instantaneu în ingeras.

Iepuraşul va ronţăi toţi morcovii care îi ies în cale. Evident că dacă trece a doua oară prin aceeaşi celulă, la a doua trecere nu va mai găsi morcov.

Surprizele din grădină sunt codificate astfel: $1$ pentru săgeată spre nord, $2$ pentru săgeată spre vest, $3$ pentru săgeată spre sud, $4$ pentru săgeată spre est, $5$ pentru pom, $6$ pentru bombă, $7$ pentru morcov, $8$ pentru zid, $9$ pentru trapă. Căsuţele libere de pe harta grădinii se codifică cu $0$.

Iniţial, se cunosc poziţia şi sensul de deplasare ale iepuraşului. Expediţia acestuia se termină în următoarele situaţii:

• la explozia unei bombe, caz în care se transformă în îngeraş
• la părăsirea grădinii (adică la ieşirea în afara zonei dreptunghiulare date), caz în care se rătăceşte
• în momentul în care reuşeşte să ronţăie toţi morcovii, caz în care este fericit

Cerință

Fiind data harta grădinii se cere să se determine starea finală a iepuraşului (îngeraş, rătăcit respectiv fericit), numărul de morcovi ronţăiţi până în momentul terminării expediţiei, precum şi numărul de paşi pe care îi face iepuraşul până la acest moment.

Date de intrare

Pe prima linie a fişierului de intrare iepuras.in se găsesc două numere întregi $m$ şi $n$, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale hărţii.

Linia a doua a fişierului conţine trei numere naturale, separate prin câte un spaţiu, reprezentând linia si coloana poziţiei iniţiale a iepuraşului pe hartă precum şi direcţia spre care acesta este orientat. Direcţia este codificată astfel: $1$ pentru nord, $2$ pentru vest, $3$ pentru sud, $4$ pentru est.

Următoarele $m$ linii conţin câte $n$ numere întregi separate prin câte un spaţiu, reprezentând codificarea hărţii grădinii, conform celor precizate mai sus.

Următoarea linie conţine un singur număr natural $t$ reprezentând numărul de celule ce vor conţine ziduri după prima trecere printr-o celulă conţinând o trapă. Următoarele $t$ linii conţin câte două numere naturale $i$ şi $j$, separate printr-un spaţiu, reprezentând coordonatele câte unei celule ce va conţine zid după o primă trecere printr-o celulă conţinând o trapă.

Date de ieșire

Fişierul de ieşire iepuras.out va conţine pe prima sa linie unul dintre cuvintele INGERAS, RATACIT respectiv FERICIT, corespunzător stării finale a iepuraşului. A doua linie a fişierului va conţine două numere întregi separate printr-un spaţiu, reprezentând linia şi coloana ultimei poziţii de pe teren a iepuraşului, adică poziţia în care a murit, sau în care a devenit fericit, respectiv ultima poziţie a sa de pe teren, înainte de a se rătăci.

A treia linie a fişierului va conţine două numere întregi separate printr-un spaţiu, reprezentând numărul de morcovi culeşi până în momentul terminării expediţiei, respectiv numărul de paşi pe care îi face iepuraşul până ajunge în starea finală.

Restricții și precizări

• poziţia iniţială a iepuraşului este una validă, adică este o celulă liberă din interiorul terenului
• pentru datele de test, se asigură că iepuraşul va face un număr finit de paşi până la terminarea expediţiei sale
• $1 \leq m, n \leq 200$
• $0 \leq t \leq 20$
• numărul maxim de ziduri aflate la un moment dat pe teren este de cel mult $50$, şi este posibil ca la un moment dat să nu existe niciun zid pe teren
• se garantează că pentru datele de intrare iepuraşul nu poate ajunge simultan în două din cele trei stări
• pomii şi trapele sunt obiecte care rămân permanent în teren, în poziţiile lor iniţiale
• într-o celulă a grădinii se poate găsi la un moment dat o singură surpriză (pom, zid, trapă, morcov, săgeată, bombă)

Exemplul 1

iepuras.in

10 15
7 1 4
0 0 6 0 5 5 0 7 0 0 0 0 0 0 0
0 0 0 0 5 5 0 0 4 0 0 0 0 0 3
0 5 5 0 5 5 0 0 0 0 0 0 0 0 0
0 5 5 0 5 5 0 1 7 0 0 7 0 0 2
0 0 0 0 5 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 0 0
0 3 0 0 0 5 6 0 0 5 5 5 0 0 0
0 7 0 0 0 0 0 0 0 0 0 0 0 5 0
0 4 0 0 0 7 0 0 3 5 0 0 0 5 0
0 6 0 0 0 0 0 0 1 5 0 0 0 5 0
0

iepuras.out

FERICIT
1 8
5 37

Explicație

$0 \ 0 \ 6 \ 0 \ 5 \ 5 \ 0 \ \textcolor{#228B22}{7} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \\ 0 \ 0 \ 0 \ 0 \ 5 \ 5 \ 0 \ \textcolor{#228B22}{0} \ \textcolor{#228B22}{4 \ 0 \ 0 \ 0 \ 0 \ 0 \ 3} \\ 0 \ 5 \ 5 \ 0 \ 5 \ 5 \ 0 \ \textcolor{#228B22}{0} \ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \ 0 \ 0 \ \textcolor{#228B22}{0} \\ 0 \ 5 \ 5 \ 0 \ 5 \ 5 \ 0 \ \textcolor{#228B22}{1} \ \textcolor{#228B22}{7 \ 0 \ 0 \ 7 \ 0 \ 0 \ 2} \\ 0 \ 0 \ 0 \ 0 \ 5 \ 5 \ 0 \ 0 \ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \\ 0 \ 0 \ 0 \ 0 \ 0 \ 5 \ 0 \ 0 \ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \\ \textcolor{#8a42f5}{0} \ \textcolor{#8a42f5}{3} \ 0 \ 0 \ 0 \ 5 \ 6 \ 0 \ \textcolor{#228B22}{0} \ 5 \ 5 \ 5 \ 0 \ 0 \ 0 \\ 0 \ \textcolor{#8a42f5}{7} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \ 0 \ 5 \ 0 \\ 0 \ \textcolor{#8a42f5}{4 \ 0 \ 0 \ 0 \ 7 \ 0 \ 0 \ 3} \ 5 \ 0 \ 0 \ 0 \ 5 \ 0 \\ 0 \ 6 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \textcolor{#228B22}{1} \ 5 \ 0 \ 0 \ 0 \ 5 \ 0 \\$

Exemplul 2

iepuras.in

6 5
2 1 3
0 0 0 7 0
0 0 0 0 0
9 6 7 2 0
8 0 0 0 0
7 8 0 0 0
4 8 9 1 0
4
4 4
5 4
1 5
2 5

iepuras.out

INGERAS
3 3
2 11

Explicație

$0 \ 0 \ 0 \ 7 \ 0 \\ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \ 0 \\ \textcolor{#228B22}{9} \ 6 \ \textcolor{#228B22}{7 \ 2} \ 0 \\ \textcolor{#228B22}{8} \ 0 \ 0 \ \textcolor{#228B22}{0} \ 0 \\ \textcolor{#228B22}{7} \ 8 \ 0 \ \textcolor{#228B22}{0} \ 0 \\ \textcolor{#228B22}{4 \ 8 \ 9 \ 1} \ 0 \\$

Exemplul 3

iepuras.in

4 3
2 1 3
0 0 0
0 0 0
9 6 7
8 0 0
4
4 3
1 2
1 3
2 3

iepuras.out

RATACIT
4 1
0 3

Explicație

$2 \ 1 \ 3 \\ 0 \ 0 \ 0 \\ \textcolor{#228B22}{0} \ 0 \ 0 \\ \textcolor{#228B22}{9} \ 6 \ 7 \\ \textcolor{#228B22}{8} \ 0 \ 0 \\$

Exemplul 4

iepuras.in

5 4
2 1 3
4 0 7 0
0 0 0 0
0 0 0 0
5 0 0 0
0 0 0 0
0

iepuras.out

FERICIT
1 3
1 5

Explicație

$\textcolor{#228B22}{4 \ 0 \ 7} \ 0 \\ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \\ \textcolor{#228B22}{0} \ 0 \ 0 \ 0 \\ 5 \ 0 \ 0 \ 0 \\ 0 \ 0 \ 0 \ 0 \\$