arrows

“Arrows” este un joc care se joacă pe o tablă dreptunghiulară a cărei suprafață este împărțită în $N \cdot M$ celule, aranjate pe $N$ linii și $M$ coloane. În fiecare celulă se află o săgeată (sus, jos, stânga sau dreapta), ca în figura de mai jos:

Figura 1 din enunțul original al problemei arrows.Mărește schema ↗

Când este la mutare, un jucător poate alege o poziție de start pe care plasează un jeton, apoi deplasează jetonul la celula învecinată în sensul indicat de săgeată. Deplasarea continuă până când jetonul părăsește tabla de joc, caz în care jucătorul obține un punctaj egal cu numărul de celule parcurse de jetonul său.
Există însă poziții de start denumite favorabile, pentru care jetonul nu va părăsi niciodată tabla de joc. De exemplu, toate pozițiile din figură cu fundal gri sunt favorabile. Jucătorul care alege o poziție de start favorabilă obține un punctaj egal cu numărul de celule distincte vizitate înmulțit cu $1000$.

Scrieți un program care, cunoscând configurația tablei de joc, rezolvă una dintre următoarele cerințe:

1. determină punctajul pe care îl obține un jucător care plasează jetonul său pe o poziție de start specificată;
2. determină numărul de celule favorabile de pe tabla de joc;
3. determină punctajul maxim pe care jucătorul îl poate obține la o mutare, alegând convenabil poziția de start.

Date de intrare

Fișierul de intrare arrows.in conține pe prima linie cerința care trebuie să fie rezolvată ($1, 2$ sau $3$). Pe a doua linie se află numerele naturale $N \ M$, care reprezintă numărul de linii și respectiv de coloane de pe tabla de joc. Pe următoarele $N$ linii se află câte $M$ numere din mulțimea {$1,2,3,4$} reprezentând săgețile aflate în celulele de pe tabla de joc ($1$ semnificând săgeata la dreapta, $2$ săgeata în sus, $3$ săgeata la stânga și $4$ săgeata în jos). Pe ultima linie sunt scrise numerele naturale $lin \ col$, reprezentând linia și coloana pe care se află poziția de start specificată. Valorile scrise pe aceeași linie în fișierul de intrare sunt separate prin spații.

Date de ieșire

Fișierul de ieșire arrows.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul pentru cerința specificată pe prima linie a fișierului de intrare.

Restricții și precizări

• $1 \leq N, M \leq 500$;
• Liniile sunt numerotate de la $1$ la $N$, iar coloanele de la $1$ la $M$.
• Pentru teste valorând $20$ de puncte cerința este $1$. Pentru teste valorând $40$ de puncte cerința este $2$. Pentru celelalte teste, valorând de asemenea $40$ de puncte, cerința este $3$.

Exemplul 1

arrows.in

1
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5

arrows.out

2000

Explicație

Exemplul corespunde tablei de joc din figură. Punctajele pentru fiecare poziție sunt:

1 14000 14000 14000 1
15000 14000 14000 14000 1
16000 14000 14000 14000 14000
15000 14000 14000 14000 14000
1 4000 4000 2 2000
2 4000 4000 1 2000

Cerința este $1$: punctajul care se obține plecând din poziția de start aflată pe linia $5$ și coloana $5$ este $2000$.

Exemplul 2

arrows.in

2
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5

arrows.out

23

Explicație

Cerința este $2$: există $23$ de poziții favorabile.

Exemplul 3

arrows.in

3
6 5
3 1 1 4 2
1 2 4 3 1
4 2 1 1 4
1 2 3 3 3
3 1 4 4 4
2 2 3 4 2
5 5

arrows.out

16000

Explicație

Cerința este $3$: punctajul maxim se poate obține plasând jetonul în punctul de start de pe linia $3$ și coloana $1$.