Agentul 070 are o nouă misiune. El trebuie să se infiltreze în baza militară a inamicilor lui, unde se află echipamente de ultima generaţie şi invenţii neobişnuite. Ca să îşi îndeplinească misiunea cu succes el trebuie să intre în bază, să extragă toată informţia necesară şi să iasă înainte de a fi capturat. Baza inamicilor săi poate fi reprezentată ca o matrice de nxm elemente. Aliaţii săi au reuşit să îi asigure o cale de intrare în bază în punctele de coordonate xi,yi, informaţiile necesare lui fiind situate în punctul de coordonate xf,yf. Una din invenţiile neobişnuite din acea bază este un dispoziv de teleportare. Odată păşit în unul din aceste aparate agentul nostru ar avea posibilitatea să călătorească oriunde în bază. Dar neavând cunoştinţele necesare ca să programeze coordonatele dorite de el nu le poate folosi pentru teleportare exact lângă punctul de extragere al informaţiei dorite. Din fericire pentru el, aceste dispozitive au memorate în ele coordonate folosite la testarea acestora. El poate să călătorească instant la aceste coordonate. Acestea fiind spuse, agentul nostru vă roagă să îl ajutaţi în misiunea sa.
Cerinţă

     1. Aflaţi distanta minimă dintre punctul de infiltrare şi primul dispozitiv de teleportare. În caz că gaseşte un astfel de dispozitiv precizaţii distanţa minimă parcursă până la el şi numărul său de ordine, altfel afişaţi -1.

     1. Aflaţi distanta minimă dintre punctul de infiltrare şi primul dispozitiv de teleportare. În caz că gaseşte un astfel de dispozitiv precizaţii distanţa minimă parcursă până la el, altfel afişaţi -1.

     2. Aflaţi distanţa minimă pe care trebuie să o parcurgă agentul ca să ajungă în punctul de extragere al informaţiei.
h2. Date de intrare

* 1<=k<=n*m;
* 0<=p<=50;
* Există întotdeauna soluţie;

* Prima cerinţă reprezintă 30% din punctaj, în timp ce a doua cerinţă reprezintă restul de 70% din punctaj.

* Prima cerinţă reprezintă 30% din punctaj, în timp ce a doua cerinţă reprezintă restul de 70% din punctaj. Dacă alegeţi să rezolvaţi doar a doua cerinţa, este necesar să afişaţi şi o valoare pentru prima cerinţă, chiar dacă aceasta este greşită.
 

* Agentul poate să se deplaseze numai în diecţiile N, S, E, V;

2
4 1
3 8

| 2 1

| 2

5
|