program project1;
var i,n:dword;
    digits:array [0..255] of dword;
    numb:array of dword;
    timed:array of dword;

procedure MSD(left,right,offset:dword);
var i,index,t,p:dword;
    pocket:array [0..255] of dword;
begin
    if (offset > 3) then exit;
    if (right - left > 1) then
    begin
        for i := 0 to 255 do
        begin
            digits[i] := 0;
            pocket[i] := 0;
        end;

        index := 0;
        for i := left to right do
        begin
            index := (numb[i] shr ((3-offset) * 8)) and 255;
            digits[index] += 1;
        end;

        t := left;
        for i := 0 to 255 do
        begin
            p := digits[i] + t;
            digits[i] := t;
            pocket[i] := digits[i];
            t := p;
        end;

        for i := left to right do
        begin
            index := ((numb[i] shr ((3-offset) * 8)) and 255);
            p := digits[index];
            timed[p] := numb[i];
            digits[index] := p+1;
        end;

        for i := left to right do
            numb[i] := timed[i];

            for i := 0 to 254 do
            begin
                if ((pocket[i] < pocket[i+1]) and (pocket[i] >= left)) then
                MSD(pocket[i],(pocket[i+1] - 1),offset+1);
            end;
    end;
end;

begin
    read(n);
    setlength(numb,n);
    setlength(timed,n);
    for i:=0 to n do
        numb[i] := random(10);
    MSD(0,n-1,0);
    writeln;
    for i := 0 to n-1 do
        writeln(numb[i]);
    readln;
    readln;

end.