Din nefericire doi elfi s-au pierdut din nou în labirintul minotaurilor.
Din fericire au și ei la dispoziție câte o hartă a acestuia.
Labirintul este descris printr-o matrice cu m linii și n coloane, având elemente din mulțimea {0, 1}.
Un element cu valoarea 1 reprezintă un zid, în timp ce un element cu valoarea 0 reprezintă un spațiu liber. Primul elf se află inițial în colțul din stânga-sus al labirintului (1, 1), iar al doilea în colțul din dreapta-jos (m, n).
În pozițiile inițiale ale celor doi nu pot exista ziduri, iar ei se pot deplasa doar în spațiile libere, fără a părăsi matricea.
    Pentru a evada din labirint, primul elf trebuie să ajungă în poziția (i1, j1), iar al doilea în poziția (i2, j2).
    Înțelepții le comunică telepatic un șir de mișcări pe care cei doi le pot efectua. Șirul este format din k mutări, codificate prin literele N, E, S și V, reprezentând deplasări de un pătrățel înspre Nord, Est, Sud, respectiv Vest.
    Cei doi elfi trebuie să efectueze toate mișcările din acest șir, în ordinea dată. Totuși, cei doi pot decide care dintre ei va efectua o mișcare. Evident, vor trebui să decidă în așa fel încât amândoi să ajungă la destinații.

Fișierul de intrare INPUT.TXT conține pe prima linie dimensiunile m și n ale labirintului, separate printr-un spațiu.
    Pe următoarele m linii se află descrierea labirintului; fiecare linie conține n valori, separate prin câte un spațiu.
    Următoarea linie va conține două numere separate printr-un spațiu care reprezintă coordonatele la care trebuie să ajungă primul elf.
    Urmează o altă linie care va conține două numere separate printr-un spațiu și care reprezintă coordonatele la care trebuie să ajungă al doilea elf.
    Următoarea linie va conține numărul k al mișcărilor comunicate telepatic.
    Ultima linie va conține k caractere, neseparate prin spațiu, care descriu cele k mișcări.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină câte o linie pentru fiecare mișcare efectuată.
    O linie va conține valoarea 1 dacă mutarea corespunzătoare a fost efectuată de primul elf și valoarea 2 în caz contrar.

  • numărul liniilor matricei care reprezintă labirintul este cuprins între 3 și 60;
  • numărul coloanelor matricei care reprezintă labirintul este cuprins între 3 și 20;
  • numărul mișcărilor care trebuie efectuate este cuprins între 2 și 200;
  • există întotdeauna cel puțin o soluție;
  • în cazul în care există mai multe soluții, poate fi aleasă oricare dintre ele;
  • prin deplasare la Nord se înțelege deplasarea pe linia precedentă;
  • prin deplasare la Sud se înțelege deplasarea pe linia următoare;
  • prin deplasare la Vest se înțelege deplasarea pe coloana precedentă;
  • prin deplasare la Est se înțelege deplasarea pe coloana următoare.


  • INPUT.TXT
    5 5
    0 0 1 0 0
    0 0 0 1 1
    0 0 0 0 0
    1 0 0 0 0
    0 1 0 0 0
    2 2
    4 4
    6
    SNEEVV

    OUTPUT.TXT
    1
    2
    1
    1
    2
    1