struguri

Istorie: “În 29 septembrie 1474 Ștefan cel Mare a cerut ajutor papei Sixtus al IV-lea în vederea apropiatului război care bătea la ușă”. Apropiindu-se toamna și fiind în criză de timp din cauza războiului iminent, Ștefan a hotărât să supravegheze personal recoltarea strugurilor de la viile Huși, din apropiere de Vaslui, vie la care Ștefan ținea foarte mult. Strugurii recoltați au fost depozitați în grămezi la marginea fiecărui rând de vie. Se cunoaște, pentru fiecare dintre cele $N$ rânduri, cantitatea (în ocale) recoltată de pe rândul respectiv. Ștefan a hotărât ca transportul strugurilor la cramă să se facă cu ajutorul unor căruțe, o căruță putând transporta orice cantitate de struguri. Recolta fiind foarte bogată, transportul se va face în una sau mai multe ture. Ștefan, care supraveghea atent activitatea, a constatat că la fiecare tură dispune de exact atâtea căruțe câte grămezi au mai rămas de transportat. Ștefan era un conducător corect astfel încât a hotărât ca toate căruțele disponibile la un moment dat să transporte aceeași cantitate de struguri.

Cerințe

1. Determinați cea mai lungă secvență de grămezi pe care le pot transporta cele $N$ căruțe în prima tură.
2. Determinați o modalitate de transport a tuturor strugurilor la cramă, conform cerințelor lui Ștefan.

Date de intrare

Fișierul de intrare struguri.in conține pe prima linie două numere naturale $C$ și $N$, separate printr-un spațiu, reprezentând cerința ($1$ sau $2$) și numărul de grămezi de struguri care trebuie transportate. Linia a doua conține $N$ numere naturale nenule, separate prin câte un spațiu, reprezentând cele $N$ cantități de struguri.

Date de ieșire

Dacă cerința este $1$, în fișierul de ieșire struguri.out se vor afișa pe prima linie trei numere naturale, separate prin câte un spațiu, reprezentând lungimea secvenței de grămezi, numărul de ordine al primei grămezi din secvență, respectiv numărul de ordine al ultimei grămezi din secvență.
Dacă cerința este $2$, în fișierul de ieșire se vor afișa: pe prima linie numărul $T$ de ture; fiecare dintre următoarele $T$ linii are aceeași structură:

• primele trei valori reprezintă:
  • numărul de căruțe care transportă struguri în tura respectivă
  • cantitatea de struguri pe care o transportă fiecare căruță
  • numărul de grămezi transportate;
• următoarele valori de pe linia respectivă reprezintă numerele de ordine ale grămezilor transportate în tura respectivă; valorile vor fi afișate ordonate crescător și separate prin câte un spațiu.

Restricții și precizări

• $1\leq N \leq 20 \ 000$;
• Cantitățile sunt mai mici ca $100 \ 000$;
• Pentru ambele cerințe orice soluție corectă este acceptată;
• Pentru cerința $1$ se acordă $46$ puncte, iar pentru cerința $2$ se acordă $54$ puncte.

Exemplul 1

struguri.in

1 10
2 1 3 4 5 10 6 8 9 7

struguri.out

5 6 10

Explicație

De la grămada a șasea până la a zecea sunt în total $40$ ocale; fiecare dintre cele $10$ căruțe va transporta câte $4$ ocale.

Exemplul 2

struguri.in

2 5
7 8 11 2 5

struguri.out

3
5 4 3 1 2 5
2 1 1 4
1 11 1 3

Explicație

O soluție posibilă poate fi următoarea:
Tura 1: există $5$ grămezi, deci sunt $5$ căruțe (fiecare căruță transportă câte $4$ oca din $3$ grămezi ($1 \ 2 \ 5$))
Tura 2: au mai rămas $2$ grămezi deci sunt $2$ căruțe, fiecare transportă câte $1$ oca din grămada $4$
Tura 3: a mai rămas o grămadă deci dispunem de $1$ căruță, ce va transporta $11$ ocale din grămada $3$
O altă soluție corectă poate fi descrisă în fișierul de ieșire astfel:

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

În această situație sunt 2 ture, în prima se transportă cu fiecare din cele $5$ căruțe, câte $3$ ocale, din grămezile $1$ și $2$. La a două tură se vor folosi $3$ căruțe care transportă fiecare câte $6$ ocale din grămezile $3$, $4$ și $5$