Făt-Frumos a plecat din nou să salveze o frumoasă fată de împărat. În ţara pe care o traversează se află ape şi munţi şi păduri şi câmpii. Harta ţării poate fi reprezentată ca o matrice cu N linii şi M coloane, elementele matricei fiind:
c - dacă elementul reprezintă o porţiune de câmpie
a - dacă elementul reprezintă o zonă acoperită cu apă
m - dacă elementul reprezintă o zonă muntoasă
p - dacă elementul reprezintă o zonă împădurită.
Iată un exemplu de hartă:

Făt-Frumos se află în colţul stânga-sus al hărţii (elementul de pe linia 1 şi coloana 1) şi trebuie să ajungă în colţul din dreapta-jos (elementul de pe linia N şi coloana M), unde se află fata de împărat. În colţul stânga-sus şi colţul dreapta jos se află zone de câmpie.
La un pas, Făt-Frumos se poate deplasa din elementul curent în unul dintre cele 4 elemente învecinate sus, jos, stânga, dreapta.
Făt-Frumos nu ştie să înoate (deci nu poate trece prin apă), îi este frică de vietăţile pădurii (deci nu va trece prin păduri), iar condiţia fizică nu îi permite să treacă prin munţi.
Pentru a-l ajuta pe Făt-Frumos tu poţi construi cel mult K poduri şi poţi incendia cel mult L păduri.
Podurile pot fi doar orizontale sau verticale, pot trece doar peste ape, pot avea orice lungime şi trebuie să fie complete (adică extremităţile podului nu pot fi în apă, podul trebuie să traverseze întreaga secvenţă de elemente consecutive pe linie/coloană acoperită de apă).
Făt-Frumos se poate urca pe un pod doar pe la unul dintre capetele podului, iar odată urcat pe pod trebuie să îl parcurgă în întregime. Pentru a urca pe un pod orizontal Făt Frumos trebuie să se afle pe linia pe care este construit podul, la unul dintre capete (la capătul din stânga se poate urca deplasându-se doar spre Est, adică din celula de pe aceeaşi linie, coloana precedentă; la capătul din dreapta al podului orizontal el se poate urca doar deplasându-se spre vest, adică din elementul situat pe aceeaşi linie, coloana următoare). Pentru a urca pe un pod vertical Făt Frumos trebuie să se afle pe coloana pe care este construit podul, la unul dintre capete (pentru capătul de sus el se deplasează spre Sud, pentru capătul de jos, el se deplasează spre Nord). Coborârea de pe pod se face pe linia (pentru pod orizontal), respectiv coloana (pentru pod vertical) pe care se află podul, pe poziţia la care se termină podul.
Podurile nu se pot intersecta, dar dacă este necesar podurile pot fi construite unul deasupra celuilalt (astfel încât nu se poate trece de pe un pod pe altul).

O pădure este o zonă maximală formată numai din elemente împădurite (cu valoarea p) astfel încât între oricare două elemente din aceeaşi pădure se poate ajunge prin mişcări de tipul celor descrise mai sus, trecând doar prin elemente împădurite. Incendierea unei păduri va determina eliminarea sa de pe hartă (integral).

Cerinţă

Date de intrare

Date de ieşire

Restricţii

• 1 ≤ M, N ≤ 50
• 1 ≤ K, L ≤ 10
• Pentru datele de test va exista întotdeauna soluţie, nu neapărat unică.

Exemple