roata

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 $c_i$, apoi se aşează 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, $c_i$, 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 $c_i$, 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 și precizări

• $2 \leq n \leq 360$;
• $1 \leq p \leq 100 \ 000$;
• $1 \leq c_i \leq 100 \ 000$;
• pentru rezolvarea primei cerinţe se acordă $20\%$ din punctaj, iar pentru celelalte două cerinţe se acordă câte $40\%$ din punctaj fiecare.

Exemplu

roata.in

4
7
6 4 1 5 2 8 3

roata.out

29
3 5 2 4 1 7 6
3

Explicație

Roata are $n = 4$ cabine şi numărul de clienţi este $p = 7$. Primul client cumpără $6$ rotiri, al doilea $4$ rotiri , $\dots$ , 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$.