grup

Administratorul rețelei cu $N$ calculatoare de la SRI împarte, din motive strategice, aceste calculatoare în mai multe grupuri. De fapt, important este doar numărul de grupuri și numărul de calculatoare din fiecare grup, așa că împarțirea este descrisă prin șirul numerelor de calculatoare din fiecare grup, ordonat crescător.

Periodic, el procedează la o nouă împarțire pe grupe a calculatoarelor. Dintre toate împarțirile posibile ale calculatoarelor în grupuri putem alege ca urmatoare împarțire doar aceea a cărei descriere precede sau succede lexicografic imediat împarțirii curente.

Nota: Spunem că șirul $x_1 x_2 \ldots x_p$ precede lexicografic șirul $y_1 y_2 \ldots y_k$ dacă:

• există un indice $j$, astfel încât $x_i=y_i$ pentru toți indicii $i<j$ și $x_j<y_j$

SAU

• $p<k$ și $x_i=y_i$ pentru toți indicii $i \leq p$

Exemple:

• $3 \ 7 \ \textbf{2} \ 5$ precede lexicografic $3 \ 7 \ \textbf{4} \ 1 \ 6 \ 2$
• $\textbf{1} \ 2 \ 3$ precede lexicografic $\textbf{2}$

Cerință

Dându-se o împarțire în grupe a celor $N$ calculatoare, determinați cele două variante candidate pentru împartirea următoare.

Date de intrare

Fișier de intrare: grup.in

Linia $1$: $N$, $k$, numere naturale nenule, reprezentând numărul total ($N$) al calculatoarelor din rețea și numărul ($k$) de grupe.

Linia $2$: $g_1$, $g_2$, $\dots$, $g_k$, numărul calculatoarelor din fiecare grupă.

Date de ieșire

Fișier de ieșire: grup.out

Linia $1$: $p$, numărul de grupe din împarțirea care precede lexicografic imediat împartirea dată;

Linia $2$: $h_1$, $h_2$, $\dots$, $h_p$, numărul de calculatoare din cele $p$ grupe ale împarțirii precedente;

Linia $3$: $u$, numărul de grupe din împarțirea care succede lexicografic imediat împarțirea dată;

Linia $4$: $t_1$, $t_2$, $\dots$, $t_u$, numărul de calculatoare din cele $u$ grupe ale împarțirii următoare.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$
• $g_1 + g_2+ \ldots + g_k = h_1 + h_2 + \ldots + h_p = t_1 + t_2 + \ldots + t_u = N$
• $1 \leq g_1 \leq g_2 \leq \ldots \leq g_k \text{;} 1 \leq h_1 \leq h_2 \leq \ldots \leq h_p \text{;} 1 \leq t_1 \leq t_2 \leq \ldots \leq t_u$;
• $1 < k < N$
• $1 \leq p, u \leq N$

Exemplu

grup.in

14 3
2 6 6

grup.out

3
2 5 7
2
2 12