O echipă de cercetători a construit un robot pentru realizarea de operaţiuni industriale în medii greu accesibile. Robotul este acţionat de un motor electric alimentat de un acumulator cu proprietatea de a se autoîncărca folosind energia mediului ambiant.
Pentru testele preliminare s-a construit o suprafaţă de testare de formă pătrată, compusă din N x N pătrate de dimensiune unitate, pentru fiecare pătrat cunoscându-se cantitatea de energie, posibil egală cu zero, pe care o poate acumula robotul dacă ajunge în poziţia respectivă. Robotul se va deplasa conform unui şir de comenzi codificat prin caracterele N, E, S, V (N - deplasare cu o poziţie către nord, E - deplasare cu o poziţie către est, S - deplasare cu o poziţie către sud, V - deplasare cu o poziţie către vest). Şirul de comenzi este corect, adică robotul nu va trece de mai multe ori prin aceeaşi poziţie şi nu va depăşi marginile suprafeţei de testare.
Iniţial, acumulatorul robotului este descărcat complet, dar acesta se găseşte cu siguranţă într-o poziţie de unde poate acumula energie. Deplasarea robotului dintr-o poziţie în alta consumă o unitate de energie. Cantitatea de energie ce poate fi stocată în acumulator este nelimitată.
Robotul se opreşte când a efectuat toate comenzile din şirul dat sau când ajungând într-o poziţie energia acumulatorului devine zero, iar în respectiva poziţie nu poate acumula energie.
Cerinţă
Cunoscând dimensiunea suprafeţei de testare, cantitatea de energie din fiecare poziţie, poziţia iniţială şi succesiunea de comenzi determinaţi poziţia unde se opreşte robotul.
Date de intrare
Fişierul robot4.in are următoarea structură:
- Pe prima linie se află numerele naturale N M L C separate prin câte un spaţiu, cu semnificaţia: N -dimensiunea suprafeţei de testare, M – numărul comenzilor, L şi C – coordonatele poziţiei iniţiale (linia, respectiv coloana);
- Pe a doua linie se găsesc M caractere din mulţimea {‘N’, ‘E’, ‘S’, ‘V’}, separate prin câte un spaţiu reprezentând şirul de comenzi;
- Pe următoarele N linii se află câte N valori naturale, separate prin câte un spaţiu, reprezentând numărul unităţilor de energie disponibile în fiecare poziţie a suprafeţei de testare.
Date de ieşire
Fişierul robot4.out va conţine două numere naturale X şi Y, scrise pe prima linie din fişier, separate printr-un spaţiu, reprezentând numărul liniei şi respectiv numărul coloanei unde robotul se opreşte.
Restricţii
• 2 ≤ N ≤ 1000
• 2 ≤ M ≤ 5000
• Cantitatea de energie dintr-o poziţie este un număr natural mai mic sau egal cu 1000000.
• Liniile şi coloanele suprafeţei de testare se consideră numerotate de sus în jos, respectiv de la stânga la dreapta, începând cu valoarea 1.
Exemple
robot4.in
robot4.out
5 4 1 1
S S S E
2 2 3 4 5
0 0 3 0 1
1 4 4 4 4
0 0 5 5 5
0 1 1 0 0