pavele

Avem o suprafață dreptunghiulară pătratică de dimensiune $n \cdot n$ ($n$ - impar). Colțul de dimensiune $1 \cdot 1$ din stânga-sus lipsește. Se dorește pavarea a cât mai mult din suprafața sa cu dale de dimensiune $1 \cdot 2$ (sau $2 \cdot 1$). Trebuie folosite cât mai multe dale și în plus, numărul de dale orizontale folosite trebuie să fie egal cu numărul de dale verticale folosite pentru pavare.

Date de intrare

Fișierul pavele.in conține pe prima linie numărul $n$.

Date de ieșire

Fișierul pavele.out conține pe prima linie un număr $r$, ce reprezintă numărul de dale verticale (orizontale) folosite. Următoarele $n$ linii conțin câte $n$ numere întregi, separate printr-un spațiu, reprezentând codificarea modului de pavare.

Numerele trebuie să fie cuprinse între $-r$ și $r$. Valoarea $0$ semnifică faptul că acea poziție a zonei dreptunghiulare nu se pavează (sau lipsește, întrucât se afișează $0$ și în contul colțului stânga sus).

Pentru codificarea dalelor orizontale se folosesc câte două numere egale, cuprinse între $1$ și $r$, așezate unul lângă altul pe aceeași linie iar pentru codificarea dalelor verticale se folosesc câte două numere egale cuprinse, cuprinse între $-r$ și $-1$, așezate unul sub altul.

Restricții și precizări

• $5 \leq n \leq 299$;
• $n$ – impar;
• dalele orizontale se codifică folosind valori pozitive iar cele verticale folosind valori negative;
• evident, dalele nu se pot suprapune și trebuie să fie complet incluse în zona dreptunghiulară;

Exemplu

pavele.in

5

pavele.out

6
 0   1   1  -1  -2
-3  -4  -5  -1  -2
-3  -4  -5   4   4
 2   2  -6   5   5
 3   3  -6   6   6

Explicație

Aici datele sunt indentate doar pentru o mai ușoară înțelegere a exemplului.

Colțul din stânga sus se codifică prin $0$ întrucât lipsește. Nu mai avem alte valori $0$ întrucât se poate pava tot restul zonei folosind $6$ dale orizontale (codificate prin numere cuprinse între $1$ și $6$) și $6$ dale verticale cu numere cuprinse între $-6$ și $-1$.