catmin

///O(n*(log(n)+sigma))
#include <fstream>
using namespace std;
ifstream  fin("catmin.in");
ofstream fout("catmin.out");
int n,i,m,j,c,nh;
char b[1000002];
int r,x,heapMin[100002];
char a[12];
void urc(int f){
    while(f>1 && heapMin[f/2]>heapMin[f]){
        int aux=heapMin[f/2];
        heapMin[f/2]=heapMin[f];
        heapMin[f]=aux;
        f=f/2;
    }
}
void cobor(int p, int nh){
    while(p*2<=nh){
        int r=p*2;
        if(r+1<=nh && heapMin[r+1]<heapMin[r]){ r=r+1; }
        if(heapMin[p]>heapMin[r]){
            int aux=heapMin[r];
            heapMin[r]=heapMin[p];
            heapMin[p]=aux;
            p=r;
        }
        else{
            break;
        }
    }
}
int main(){
    fin>>n; nh=0;
    for(i=1;i<=n;i++){///O(n)
        fin>>a;///citesc numarul ca sir de cifre
        x=0;///construiesc numarul
        ///O(sigma)
        for(r=0;a[r]!=0;r++){ x=x*10+(a[r]-'0'); }
        m=m+r;///numarul total de cifre
        ///completez cu cifre de 9
        while(r<9){x=x*10+9; r++;}
        ///adaug in heap-min
        nh++; heapMin[nh]=x;
        ///O(log(n))
        urc(nh);
    }

    r=100000000;
    for(i=0;i<=m-1;i++){///O(n*sigma)
        ///extrag din heap prima cifra de la cel mai mic numar
        b[i]='0'+heapMin[1]/r;
        ///tai prima cifra si completez cu 9
        heapMin[1]=(heapMin[1]%r)*10+9;
        ///actualizez pozitia in heap
        ///O(log(n))
        cobor(1,nh);
    }
    b[m]=0;
    fout<<b;
    return 0;
}