pitagora

Să considerăm un dreptunghi în plan cu laturile $a$ şi $b$. Conform teoremei lui Pitagora lungimea diagonalei $d$ respectă relaţia $d^2 = a^2 + b^2$. Lungimile laturilor $a$ şi $b$ pot fi alese din mulţimea numerelor naturale astfel încât lungimea diagonolei să fie tot un număr natural. De exemplu pentru un dreptunghi cu laturile $5$ şi $12$ vom avea a diagonală de lungime $13$.

Această proprietate se poate generaliza şi pentru spaţiu. Dacă avem un paralelipiped dreptunghic cu cele trei muchii $a$, $b$ şi $c$, atunci lungimea diagonalei şi lungimile muchiilor respectă relaţia: $d^2 = a^2 + b^2 + c^2$. De asemenea putem găsi lungimi din mulţimea numerelor naturale pentru muchii astfel ca şi diagonala să fie un număr natural. De exemplu dacă muchiile paralelipipedului dreptunghic sunt $4$, $4$ respectiv $2$, atunci diagonala va avea lungimea $6$.

În general, dacă avem un paralelipiped dreptunghic dintr-un spaţiu $k$-dimensional, ale cărui muchii au lungimile $a_1, a_2, \dots, a_k$ lungimea diagonalei şi lungimile muchiilor vor respecta relaţia $d^2 = a_1^2 + a_2^2 + \dots + a_k^2$

Cerință

Cunoscând dimensiunea $k$ a spaţiului, se cere să se găsească un paralelipiped $k$-dimensional în care atât diagonala $d$ cât şi lungimile laturilor $a_1, a_2, \dots, a_k$ sunt numere naturale. 

Date de intrare

Fişierul pitagora.in va conţine pe prima linie valoarea lui $k$ cu semnificaţia de mai sus.

Date de ieșire

Fişierul pitagora.out va conţine mai multe linii. Pe prima linie se va scrie valoarea lui $d$, pe linia a doua se va scrie valoarea $p$ (numărul de numere distincte din şirul $a_1, a_2, \dots , a_k)$, iar pe următoarele p linii câte două numere naturale separate printr-un spaţiu: pe linia $i + 2$ se vor afla numerele $f_i$ şi $c_i$, cu semnificaţia că, un număr de fi muchii ale paralelipipedului $k$-dimensional sunt egale cu valoarea $c_i$.

Restricții și precizări

• $2 \leq k \leq 100 \ 000 \ 000$
• $0 < d_2 \leq 2 \ 000 \ 000 \ 000$
• $0 < c_1, c_2, \dots, c_p, f_1, f_2, \cdot, f_p$
• $d_2 = f_1 \cdot c_1^2 + f_2 \cdot c_2^2 + \dots + f_p \cdot c_p^2$
• $k = f_1 + f_2 + \dots + f_p$
• Soluţia problemei nu este unică. Se acceptă orice soluţie corectă

Exemplul 1

pitagora.in

4

pitagora.out

2
1
4 1

Explicație

În spaţiul $4$-dimensional $(k=4)$, diagonala de lungime $2$, se obţine cu $4$ laturi de lungime $1$, pentru că $2^2 = 1^2 + 1^2 + 1^2 + 1^2$.

Exemplul 2

pitagora.in

3

pitagora.out

6
2
1 2
2 4

Explicație

În spaţiul tridimensional $(k=3)$, diagonala de lungime $6$ se obţine cu ajutorul unei muchii de lungime $2$ şi a altor două muchii de lungime $4$. $(6^2 = 2^2 + 4^2 + 4^2)$