Ionică, tânăr inginer constructor vrea să-şi schimbe locul de muncă cu unul mai bine plătit. Pentru a ocupa acest nou post trebuie să prezinte un CV şi să susţină o probă teoretică. Dacă la CV stă foarte bine, datorită seriozităţii de care a dat dovadă la vechiul loc de muncă, hopul cel mai mare este proba teoretică. La acestă probă el primeşte ca sarcină pavarea pieţei din centrul oraşului, de formă pătratică, având latura de 2n metri. Acesteia îi asociem un tablou bidimensional cu 2n linii şi 2n coloane, atât liniile cât şi coloanele fiind numerotate cu numere de la 1 la 2n. Dalele care vor fi folosite la pavare sunt formate din 3 pătrate, fiecare de latură 1 m, ca în figura:
Piaţa conţine un pom vechi de câteva sute de ani, care trebuie să rămână şi după pavare. Acest pom ocupă un singur pătrat de latură 1 m din piaţă (cât un element din tabloul bidimensional asociat pieţei).
Prin pavarea pieţei se înţelege acoperirea fiecărui pătrat de latură 1 m al pieţei cu exact o singură dală, exceptând pătratul unde se găseşte pomul. Pentru a vizualiza modalitatea de pavare a pieţei, Ionică va numerota dalele cu numere naturale consecutive începând de la 1. Numărul asociat unei dale va fi scris în fiecare pătrat din piaţă acoperit de dala respectivă.
Cerinţă
Scrieţi un program care să determine o modalitate de pavare a pieţei, care să respecte condiţiile de mai sus.
Date de intrare
Fişierul de intrare pav.in va conţine pe prima linie numărul n, iar pe linia a doua poziţia pomului descrisă prin indicii liniei şi coloanei corespunzătoare, separate printr-un spaţiu.
Date de ieşire
Fişierul de ieşire pav.out va conţine 2n linii, pe fiecare linie fiind scrise 2n numere naturale separate prin câte un spaţiu. Valorile scrise în fişierul de ieşire sunt numere consecutive începând cu 1 asociate dalelor care acoperă piaţa. Pentru elementul din tablou unde se găseşte pomul se va folosi cifra 0.
Restricţii
1 ≤ n ≤ 9
soluţia nu este unică, se poate afişa orice soluţie.
o dală poate fi rotită cu 90°, 180°, respectiv 270°.
Exemple
pav.in
pav.out
Explicaţii
2
1 4
2 2 5 0
2 1 5 5
3 1 1 4
3 3 4 4
Am pavat o piaţă cu 4 linii şi 4 coloane, având pomul pe linia 1 şi coloana 4. Pentru pavare s-au utilizat 5 dale (numerotate cu 1, 2, 3, 4, 5). Fişierul de ieşire corespunde pavării:
