Regele Arthur, singurul supravietuitor al unei sangeroase batalii, a ramas ranit pe campul de lupta. Singura lui salvare ar fi sa ajunga la castel, unde va fi in siguranta. Arthur nu are la dispozitie nici un cal pentru a se deplasa mai usor, insa pe drumul spre castel poate trece pe la mai multe hanuri, de unde poate imprumuta cate un cal. Asadar pleaca pe jos spre castel. Ajuns la un han, Arthur isi potoleste setea, dar nu mai pierde vremea si pleaca mai departe. El poate decide daca va pleca calare sau pe jos. Arthur stie insa ca un cal nu poate parcurge mai mult de K pasi. Daca distanta de la hanul curent pana la castel sau pana la urmatorul han este mai mare de K pasi, atunci este obligat sa plece pe jos, deoarece nu poate sa abandoneze calul pe drum. Chiar daca pana la urmatorul han Arthur poate ajunge calare (mai putin de K pasi de cal), el poate decide sa plece pe jos. In acest caz va parcurge toata distanta pana la hanul urmator sau pana la castel pe jos.

Harta regatului lui Arthur poate fi reprezentata sub forma unei table dreptunghiulare cu m linii numerotate de la 1 la m de sus in jos, si n coloane numerotate de la 1 la n de la stanga la dreapta. La un pas, Arthur se poate deplasa pe jos, din pozitia marcata cu , in oricare din cele 8 pozitii marcate cu , conform figurii 1 de mai jos, astfel incat sa ramana pe tabla. Calare insa, Arthur se poate deplasa, din pozitia marcata cu , in oricare din cele 8 pozitii marcate cu , conform figurii 2 de mai jos, astfel incat sa ramana pe tabla.

Fiind data o "harta" a regatului se cere sa se determine numarul minim de pasi pe care ii face Arthur (pe jos sau calare) pentru a ajunge la castel, precum si un traseu parcurs de Arthur pentru a obtine acest numar minim de mutari.

Date de intrare

Pe prima linie a fisierului de intrare arthur.in se gasesc numerele intregi m, n, k si p, separate prin cate un spatiu, cu urmatoarea semnificatie: m numarul de linii ale hartii, n numarul de coloane ale hartii, k numarul maxim de pasi pe care ii poate face un cal, iar p numarul de hanuri de pe harta. Linia a doua a fisierului contine doua numere naturale, separate printr-un spatiu, reprezentand linia si coloana pozitiei initiale a lui Arthur pe harta. Linia a treia a fisierului de intrare contine doua numere naturale, separate printr-un spatiu, reprezentand coordonatele (linia si coloana) castelului pe harta. Urmatoarele p linii contin cate doua numere naturale, separate printr-un spatiu, reprezentand coordonatele (linia si coloana) cate unui han pe harta.

Fisierul arthur.out va contine pe prima linie numarul natural min reprezentand numarul minim de pasi prin care Arthur ajunge la castel. Pe urmatoarele min+1 linii sunt afisate in ordine pozitiile prin care trece Arthur pe drumul optim. Pentru fiecare pozitie se afiseaza pe o linie separata, indicele de linie si indicele de coloana, separate printr-un spatiu.

• 1 < m, n <= 200
• 0 <= k <= 1000
• 0 <= p <= 100
• Daca pentru datele de intrare exista mai multe trasee optime, poate fi afisat oricare dintre acestea.