Sa consideram un labirint de forma dreptunghiulara, format din n*m camere dispuse sub forma unei matrice cu n linii si m coloane. Vom considera ca liniile sunt numerotate de la 1 la n, iar coloanele sunt numerotate de la 1 la m. Camerele labirintului au usi care se deschid intr-o singura directie, permitand deplasarea in una dintre cele 8 camere invecinate. Pentru a codifica iesirile din camere, in fiecare element al matricei ce codifica labirintul va fi memorat un numar natural din intervalul [0, 255]. Fiecare bit 1 din reprezentarea binara a unui element din matrice corespunde unei usi in una dintre directiile posibile de miscare, în urmatoarea ordine: N, NE, E, SE, S, SV, V, NV. Mai exact daca bitul are valoarea 1 exista usa in directia corespunzatoare bitului, iar daca bitul are valoarea 0 usa corespunzatoare nu exista. Bitii sunt numerotati începând cu cel mai putin semnificativ.
In labirint se afla un soarece in camera de pe linia L0 si coloana C0. Soarecele ar vrea sa iasa din labirint, dar numai dupa ce a trecut printr-un anumit numar de camere (nmin). Imediat ce a trecut prin cele nmin camere soarecele poate parasi labirintul. Soarecele este istet si nu va trece de doua ori prin aceeasi camera. Soarecele poate iesi din labirint doar daca el se afla într-o camera care are usa într-o directie care îl conduce în afara labirintului.

Cerinta

Scrieti un program care sa determine un traseu al soarecelui care sa aiba cel putin lungimea nmin si care sa nu treaca de doua ori prin aceeasi camera. Traseul va incepe din camera initiala a soarecelui si se va termina intr-o camera care are usa spre iesirea din labirint.

Date de intrare

Fisierul de intrare labirint.in contine pe prima linie doua numere naturale separate printr-un spatiu n si m cu semnificatia din enunt. Pe fiecare dintre urmatoarele n linii se afla cate m numere naturale separate prin spatii, reprezentand codificarea labirintului. Pe urmatoarea linie a fisierului de intrare se afla doua numere naturale separate printr-un spatiu L0 si C0, reprezentand linia si coloana corespunzatoare camerei in care se afla initial soarecele. Ultima linie a fisierului de intrare contine numarul minim de camere prin care trebuie sa treaca soarecele soarecele înainte de a parasi labirintul.

Date de iesire

Fisierul de iesire labirint.out va contine pe prima linie un numar natural Lg, reprezentand numarul de camere pe care le poate vizita soarecele pana la iesire, fara a trece de mai multe ori prin aceeasi camera si trecand prin cel putin nmin camere. Pe urmatoarele Lg linii se afla cate doua numere naturale separate printr-un spatiu L C, reprezentand coordonatele camerelor (linie, coloana) prin care trece soarecele pe traseul determinat.

Restrictii

• 0 < n, m <= 50
• Pentru datele de test problema are intotdeauna solutie.

Exemple

prof. Marinel Serban
Liceul de Informatica "Grigore Moisil" Iasi
Contact:marinel_serban@yahoo.com