Pariul Broscuțelor

Câteva broscuţe din oraşul C..., mergând la plimbare prin parcul din centrul oraşului şi descoperind un mozaic asemănător unei table de şah de dimensiune $n \times n$, au inventat un joc cu următoarele reguli:

• fiecare broscuţă porneşte din centrul pătrăţelului aflat în colţul din stânga-sus al tablei, trece prin fiecare pătrăţel al mozaicului, şi se întoarce în pătrăţelul de unde a pornit;
• poate sări din centrul unui pătrăţel oarecare în centrul oricăruia din pătrăţelele vecine aflate în direcţiile: N, S, E, V, NE, NV, SE, SV;
• dacă se unesc centrele pătrăţelelor în ordinea în care au fost parcurse, se obţine o linie închisă care nu trebuie să se autointersecteze.

Una din broscuţe – mai nechibzuită – face pariu pe greutatea ei în musculiţe, că poate găsi o ordine în care să acopere cu sărituri mozaicul astfel încât, lungimea drumului parcurs să nu poată fi depăşită. Lungimea este în sens geometric: drumul dintre centrele a două pătrate cu o latură comună este $1$, iar între centrele a două pătrate ce au doar un vârf comun, distanţa este $\sqrt2$.

Cerință

Din păcate, broscuţa nu prea ştie cum să procedeze, aşa că vă roagă să îi indicaţi ordinea în care trebuie să parcurgă pătrăţelele tablei astfel încât să nu piardă pariul.

Date de intrare

Fişierul de intrare frog.in, conţine pe prima linie valoarea lui $n$.

Date de ieșire

În fişierul frog.out se vor scrie, pe linia $i$ ($i = 1 \dots n^2+1$), două perechi de valori separate printr-un spaţiu, reprezentând coordonatele pătrăţelului unde trebuie să sară broscuţa la pasul $i$ (se consideră că în colţul din stânga sus avem coordonatele $(1,1)$ iar localizarea unui pătrăţel se face ca în matrice).

Restricții și precizări

• $2 \le n \le 250$

Exemplu

frog.in

4

frog.out

1 1
2 2
2 1
3 1
3 2
4 1
4 2
3 3
4 3
4 4
3 4
2 3
2 4
1 4
1 3
1 2
1 1