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ş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ţa

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 prima linie 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 și precizări

• 2 ≤ n ≤ 360
• 1 ≤ p ≤ 100 000
• 1 ≤ ci ≤ 100 000

Exemplu

roata.in

476 4 1 5 2 8 3

roata.out

293 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, … , 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.

#include <bits/stdc++.h>
using namespace std;

ifstream fin("roata.in");
ofstream fout("roata.out");

int x[100001], o[100001], n, p;

long long int s = 0;

int main()
{
    fin >> n >> p;
    for (int i = 1; i<=p; i++)
    {
        fin >> x[i];
        s = s + x[i];
        o[i] = i;
    }
    fout << s << '\n';
    int pozmin;
    if (p > n)
    {
        for (int i = n + 1; i<=p; i++)
        {
            pozmin = 1;
            for (int j = 2; j <=n; j++)
                if (x[j] < x[pozmin])
                    pozmin = j;

            fout << o[pozmin] << ' ';
            o[pozmin] = o[i];
            x[pozmin]+=x[i];
            if (x[pozmin] >1000000)

                for (int j = 1; j <=n; j++)
                {
                    x[j] = x[j] - 1000000;
                }


        }
        p = n;
    }
    int pozmax = 1;
    for (int i = 2; i<=p; i++)
    {
        if (x[pozmax] <= x[i])pozmax = i;
    }
    for (int i = 1; i<=p; i++)
    {
        pozmin = 1;
        for (int j = 2; j<=p; j++)
            if (x[j] < x[pozmin])
                pozmin = j;

        fout << o[pozmin] << ' ';
        x[pozmin] += 1000000;
    }
    fout << '\n';
    fout << pozmax << '\n';
    
    fin.close();
    fout.close();
    
    return 0;
}