“Arrows” este un joc care se joacă pe o tablă dreptunghiulară a cărei suprafaţă este împărţită în NxM 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:

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.

Cerința

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 ≤ N, M ≤ 500
• Liniile sunt numerotate de la 1 la N, iar coloanele de la 1 la M.
• Punctaj. 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.