cai

Avem o tablă de șah de dimensiune $N \times N$ și o piesă cal, dar mai specială decât cea cunoscută la popularul sport al minții. Calul din problema noastră face de asemenea mutări în formă de $L$, fără a părăsi tabla de șah. Una dintre laturile $L$-ului are lungimea de două pătrățele iar cealaltă latură poate avea orice lungime $x \ (1 \leq x \leq N)$. Numim mutare de tip $x$ o mutare în care o latură are lungimea $2$ iar cealaltă are lungimea $x$.

O secvență de mutări o vom codifica sub forma unui șir descrescător de numere naturale reprezentând tipurile mutărilor din care este formată, indiferent de ordinea în care acestea au fost efectuate. De exemplu șirul $4\ 4\ 4\ 2$ codifică trei mutări de tip 4 și una de tip 2. Spunem că șirul de mutări $a_1, a_2,\ldots,a_k$ este mai mare lexicografic decât $b_1, b_2,\ldots,b_k$ dacă există $i$ unde $1 \leq i \leq k$, astfel încât: $a_i > b_i$ și $a_j = b_j$, pentru fiecare $j < i$.

Cerință

Determinați o poziție inițială a calului și o secvență de mutări astfel încât să vizităm exact o dată fiecare poziție de pe tablă (poziția inițială se consideră vizitată prin simplul fapt că se pornește de acolo). Dacă există mai multe soluții se cere cea pentru care șirul obținut în urma codificării mutărilor este maxim lexicografic.

Date de intrare

Fișierul de intrare cai.in conține pe prima linie numărul $N$ care reprezintă numărul de linii și de coloane ale tablei de joc.

Date de ieșire

Fișierul de ieșire cai.out conține $N^2$ linii, pe fiecare dintre acestea aflându-se două numere naturale $lin$ și $col$, separate prin spațiu, reprezentând coordonatele linie, coloană pentru câte o poziție pe care calul o vizitează, în ordinea efectuării mutărilor.

Restricții și precizări

• $2 \leq N \leq 400$.
• Liniile și coloanele sunt numerotate începând cu $1$.
• Se va acorda punctaj parțial pentru o soluție corectă, dar pentru care șirul obținut în urma codificării nu este maxim lexicografic.

Exemplul 1

cai.in

2

cai.out

1 1
2 2
1 2
2 1

Explicație

Soluția se codifică prin șirul $2 \ 2 \ 1$, fiind formată din două mutări de tip $2$ și o mutare de tip $1$. O posibilă ordine în efectuarea mutărilor este următoarea: Calul pornește din poziția $(1,1)$, face mai întâi o mutare de tip $2$ - ajungând în poziția $(2,2)$, apoi face o mutare de tip $1$, ajungând în poziția $(1,2)$ și în final face o altă mutare de tip $2$, ajungând în poziția finală $(2,1)$. În tabelul de mai jos este notată ordinea în care este vizitată fiecare poziție.

O altă variantă ar fi secvența de mutări codificată prin șirul $2 \ 1 \ 1$, dar care nu este maxim lexicografic.
Calul pornește din poziția $(1,1)$, face mai întâi o mutare de tip $1$ -- ajungând în poziția $(1,2)$, apoi face o mutare de tip $2$, ajungând în poziția $(2,1)$ și în final face o altă mutare de tip $1$, ajungând în poziția finală $(2,2)$.