Fișierul intrare/ieșire	immortal.in, immortal.out	Sursă	OJI 2010, clasele 11-12
Autor	Marinel Șerban	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Immortal (clasele 9-10)

Notă: aceasta este o variantă modificată a problemei Immortal de la OJI 2010 (Infoarena, Campion) cu teste ceva mai grele.

Cei care au văzut filmul Nemuritorul știu că fraza cu care nemuritorii încep lupta este „Nu poate să rămână decât unul singur”. Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din N linii (numerotate de la 1 la N) și M coloane (numerotate de la 1 la M) se află maxim N x M – 1 nemuritori. Doi nemuritori vecini se „luptă” între ei și cel care pierde lupta este eliminat. „Lupta” constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală și nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziția (i,j) înțelegem un nemuritor din una dintre pozițiile , (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j) se va găsi în una dintre pozițiile: , (i+2,j), (i,j-2) sau (i,j+2), dacă această poziție este liberă și este în interiorul zonei.

Cerință

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

Date de intrare

Fișierul de intrare immortal.in conține pe prima linie trei valori naturale N, M, I, separate prin câte un spațiu, reprezentând numărul de linii, numărul de coloane ale zonei descrise și respectiv numărul de nemuritori existenți inițial. Următoarele I linii conțin fiecare câte două numere naturale x și y, separate printr-un spațiu, reprezentând pozițiile unde se găsesc inițial cei I nemuritori (linia și coloana).

Date de ieșire

Fișierul de ieșire immortal.out va conține I – 1 linii, fiecare linie descriind o „luptă”. Luptele vor fi scrise în ordinea în care au avut loc. O linie va conține 4 numere naturale care indică: primele două poziția de pe care pleacă un nemuritor la „luptă”, ultimele două poziția pe care acesta ajunge după „luptă”. Pentru ca „lupta” să fie corectă, în poziția peste care nemuritorul „sare” trebuie să existe un nemuritor care va „muri”. O poziție va fi specificată prin indicele de linie urmat de indicele de coloană. Valorile scrise pe aceeași linie vor fi separate prin spații.

Restricții

• 2 ≤ N, M ≤ 20
• 2 ≤ I ≤ min(15, N * M – 1)
• Pentru datele de test există întotdeauna soluție.

Exemplu

immortal.in	immortal.out	Explicație
3 4 4 1 2 2 1 3 2 3 3	3 3 3 1 3 1 1 1 1 1 1 3