KON PA 2013

#include "iostream"
#include "vector"
#include "algorithm"
#include "utility"
#include "cstdio"
#include "functional"
#include "set"
#include "algorithm"
#include <cassert>
#include <ctime>

using namespace std;

vector<int> konduktorzy;


typedef long long int lli;

lli sprawdzono_przedzialow (long long int t)
{//ile przedzialow sprawdzono lub zaczęto sprawdzać w chwili t

    if (t<0) return 0;
    lli licznik=0;

    for (vector<int>::iterator konduktor =konduktorzy.begin();konduktor!=konduktorzy.end();++konduktor )
    {
        licznik += (t+(*konduktor))/(*konduktor); //
    }
    return licznik;

};


lli przybliz_czas_double(lli przedzialow, int sup)
{
    double predkosc=0;
    przedzialow-=konduktorzy.size()*(1-sup);//
    for (vector<int>::iterator konduktor = konduktorzy.begin(); konduktor != konduktorzy.end(); ++konduktor )
    {
        predkosc+=1.0/(*konduktor);
    }
    return (lli)((przedzialow)/predkosc)-1+sup;
}


lli binarne(lli przedzialow)
{

    //lli bb= przybliz_czas(przedzialow,1);
    //lli aa= przybliz_czas(przedzialow,0);

    lli b= przybliz_czas_double(przedzialow,1);
    lli a= przybliz_czas_double(przedzialow,0);

    while (sprawdzono_przedzialow(b) < przedzialow )
    {
            b=b+(b-a);
            a=b-1;
            //printf("a jednak!");

    }
    while ( sprawdzono_przedzialow(a) >= przedzialow )
    {
            a=a-(b-a);
            if (a<0)a=-1;

            //printf("koniec swiata!");
    }

    while (a<b-1)
    {// F(a)<przedzialow<=F(b)
        lli c=(a+b+1)/2;
        lli dzial = sprawdzono_przedzialow(c);
        if (dzial<przedzialow) a=c; else    b=c;
    }
    return b;

}

int main()
{
    lli przedzialow;
    int k;

    scanf("%lld %d",&przedzialow,&k);
    konduktorzy.resize(k);  //czasy konduktorow

    for (int i=0;i<k;i++)
        scanf("%d",&konduktorzy[i]);


    lli t_koniec = binarne(przedzialow);

    lli sprawdzono = sprawdzono_przedzialow(t_koniec);

    int zakres_czasu = (*max_element(konduktorzy.begin(),konduktorzy.end()))+1;

    vector <pair<int,int> > sprawdzenia; //sprawdzenie w czasie t konduktora k.
    sprawdzenia.reserve(k);

    for (int kon=0;kon<k;kon++)
    {
        //n log n dzieki magii liczb harmonicznych;)
        for (int hopek= (int)(konduktorzy[kon]*((t_koniec)/konduktorzy[kon]) -t_koniec ); hopek >= -zakres_czasu; hopek-= konduktorzy[kon])
        {
            sprawdzenia.push_back(make_pair(hopek,kon) );
        }
    }


    sort(sprawdzenia.begin(),sprawdzenia.end(),greater<pair<int,int> >());


    vector<lli> wyniki(k,-1);

    int ind=0;
    while (sprawdzono>przedzialow )
    {
        sprawdzono--;
        ind++;
    }
    for(;ind<sprawdzenia.size();ind++)
    {
        int kond=sprawdzenia[ind].second;
        if (wyniki[kond]<0) wyniki[kond]=sprawdzono;
        sprawdzono--;
    }

    for(int i=0;i<k;i++)
    {
        printf("%lld ", wyniki[i]);
    }


    return 0;
}