Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.
Roata are n cabine, numerotate de la 1 la n în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina 1 aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire 1 EUR şi poate cumpăra un număr oarecare de rotiri.
Cei p clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine i îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri ci, 1≤ i ≤ p, apoi se aşază la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.
Cerinţă
Să se scrie un program care, cunoscând numărul n de cabine al roţii, numărul p de clienţi, precum şi numărul de rotiri cumpărate de fiecare client, ci, 1≤ i ≤ p, să calculeze:
• suma totală încasată de administratorul roţii de la clienţi;
• ordinea în care coboară clienţii din roată;
• numărul cabinei din care coboară ultimul client.
Date de intrare
Fişierul de intrare roata.in conţine pe primul rând numărul natural n, pe al doilea rând numărul natural p, iar pe al treilea rând numerele naturale ci, 1≤ i ≤ p, separate printr-un spaţiu, cu semnificaţiile de mai sus.
Date de ieşire
Fişierul de ieşire roata.out va conţine pe prima linie suma totală încasată, pe a doua linie numerele de ordine ale clienţilor, în ordinea coborârii, separate printr-un spaţiu, iar pe a treia linie numărul cabinei din care va coborî ultimul client.
Restricţii
• 2 ≤ n ≤ 360
• 1 ≤ p ≤ 100 000
• 1 ≤ ci ≤ 100 000, pentru 1≤i≤p
Exemple
roata.in
roata.out
Explicaţii
4
7
6 4 1 5 2 8 3
29
3 5 2 4 1 7 6
3
Roata are n=4 cabine şi numărul de clienţi este p=7.
Primul client cumpără 6 rotiri, al doilea 4 rotiri , ... , iar al şaptelea client cumpără 3 rotiri. Suma totală încasată este de 29 EUR.
După ce primii 4 clienţi se urcă în roată şi se efectuează o rotire completă, primul care coboară este clientul al 3-lea şi imediat se urcă clientul al 5-lea. După încă 2 rotiri, clientul al 5-lea coboară şi se urcă clientul al 6-lea. După încă o rotire coboară clientul al 2-lea şi se urcă al 7-lea client. Ultimii 4 clienţi coboară în ordinea 4,1,7,6.
Cabina din care coboară ultimul client este cabina cu numărul 3.