bomboane

Zeno are $n$ cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Împărțirea frățească se realizează astfel:

• Numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane $k$ colegi și din cutia $2$ vor primi tot $k$ colegi, și din cutia $3$ tot $k$ colegi etc);
• Bomboanele din fiecare cutie se împart în mod egal între cei $k$ colegi, aceștia primind un număr nenul de bomboane;
• În final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă $n = 3$, iar în cutii se găsesc $14, 23$ respectiv $17$ bomboane, din prima cutie oferă câte $4$ bomboane pentru $3$ colegi, din a doua cutie câte $7$ bomboane pentru $3$ colegi, iar din ultima cutie câte $5$ bomboane pentru $3$ colegi, iar în fiecare cutie rămân $2$ bomboane.

Împărțirea diferențiată se realizează în felul următor:

• dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
• din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
• diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă $n = 3$, iar în cutii se găsesc $14, 23$ respectiv $17$ bomboane, bomboanele din prima cutie se pot împărți astfel $(3, 4, 6, 1)$, bomboanele din a doua cutie $(6, 2, 7, 1, 3, 4)$, iar bomboanele din a treia cutie se pot împărți astfel $(2, 1, 3, 7, 4)$.

Cerința

Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:

$a)$ Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.

$b)$ O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată.

Date de intrare

Fișierul de intrare bomboane.in conține pe prima linie două numere naturale p (numărul cerinței de rezolvat), și n (numărul de cutii), despărțite printr-un spațiu. Pe următoarea linie se găsesc n valori naturale, separate prin câte un spațiu, reprezentând numărul de bomboane din fiecare cutie.

Date de ieșire

Dacă $p = 1$ se va rezolva numai punctul a) din cerință. În acest caz fișierul de ieșire bomboane.out va conține o valoare naturală reprezentând numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.

Dacă $p = 2$ se rezolvă numai punctul b). Fișierul de ieșire bomboane.out va conține $n$ linii. Pe fiecare linie $i$, prima valoare nri reprezintă numărul maxim de colegi care pot primi bomboane din cutia $i$, urmată de nri valori separate prin câte un spațiu reprezentând o modalitate de împărțire a bomboanelor din cutia $i$, dacă Zeno alege împărțirea diferențiată.

Restricții și precizări

• $1 \leq p \leq 2$
• Dacă $p = 1$ atunci $1 \leq n \leq 10 \ 000$ și $1 \leq$ numărul de bomboane din cutii $\leq 10^6$
• Dacă $p = 2$ atunci $1 \leq n \leq 200$ și $1 \leq$ numărul de bomboane din cutii $\leq 10^5$
• Dacă există mai multe soluții se poate afișa oricare.
• Pentru rezolvarea fiecărei cerințe se acordă $50$% din punctaj.

Exemplul 1

bomboane.in

1 3
14 23 17

bomboane.out

3

Explicație

Se rezolvă numai punctul $a)$. Numărul maxim de colegi care pot primi bomboane dacă Zeno alege împărțirea frățească e $3$.

Exemplul 2

bomboane.in

2 3
14 23 17

bomboane.out

4 3 4 6 1
6 6 2 7 1 3 4
5 2 1 3 7 4

Explicație

Se rezolvă numai punctul $b)$. Din prima cutie pot primi bomboane maxim $4$ colegi. O modalitate de împărțire astfel încât fiecare coleg să primească un număr diferit de bomboane, iar diferențele dintre bomboanele primite de doi colegi consecutivi să fie distincte două câte două este $(3,4,6,1)$. Este corectă și soluția $(1, 2, 7, 4)$.