Pe o masă se află N stive (numerotate de la 1 la N). Stiva i conţine i jetoane (1≤i≤N). La o mutare se poate alege o mulţime de stive şi se pot extrage din fiecare stivă care face parte din mulţimea aleasă acelaşi număr de jetoane.
Cerinţă
Să se determine o secvenţă cu număr minim de mutări care să golească toate cele N stive.
Date de intrare
Fişierul de intrare stive.in conţine pe prima linie numărul natural N.
Date de ieşire
Fişierul de ieşire stive.out va conţine pe prima linie un număr natural MIN reprezentând minim de mutări efectuate. Pe următoarele MIN linii sunt descrise mutările, câte o mutare pe o linie. Linia ce descrie o mutare are forma: nr s1 s2 ... snr x
unde nr reprezintă numărul de stive din mulţimea selectată la mutarea respectivă; s1, s2, ..., snr sunt stivele selectate, iar x reprezintă numărul de jetoane extrase din fiecare stivă s1, s2, ..., snr. Valorile de pe aceeaşi linie sunt separate prin spaţii.
Restricţii
1 ≤ N ≤ 30000
Exemple
stive.in
stive.out
Explicaţii
3
2
2 2 3 2
2 1 3 1
Configuraţia iniţială a stivelor este 1 2 3
La prima mutare sunt selectate 2 stive (2 şi 3) şi se extrag câte 2 jetoane din fiecare. Se obţine configuraţia: 1 0 1
La ultima mutare se aleg stivele 1 şi 3, se extrage câte un singur jeton din fiecare şi astfel au fost golite toate stivele.