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

procedure MSD(left,right,offset:dword);
var i,number,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;

        number := 0;
        for i := left to right do
        begin
            number := (numbers[i] shr ((3-offset) * 8)) and $FF;
            digits[number] += 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
            number := ((numbers[i] shr ((3-offset) * 8)) and $FF);
            p := digits[number];
            timed[p] := numbers[i];
            digits[number] := p+1;
        end;

        for i := left to right do
            numbers[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(numbers,n);
    //setLength(timed,n);
    //for i := 0 to n-1 do
    //    read(numbers[i]);
    randomize;
    setlength(numbers,1000000);
    setlength(timed,1000000);
    for i:=0 to 1000000 do
        numbers[i] := random(1000001);
    MSD(0,999999,0);
    writeln;
    for i := 0 to 999999 do
        writeln(numbers[i]);

end.