program Project4;

{$APPTYPE CONSOLE}
{$R *.res}

uses
    System.SysUtils;

type
    Matrix = array of array of Integer;

procedure PrintMatrix(ToPringt: Matrix);
var
    I, J: Integer;
begin
    for I := 0 to High(ToPringt) do
    begin
        for J := 0 to High(ToPringt[0]) do
            Write(ToPringt[I, J]:5);
        Writeln;
    end;
end;

function Getmatrix(): Matrix;
var
    Cols, Rows, I, J: Integer;
    NewMatrix: Matrix;
begin
    Writeln('Введтие кол-во строк матрицы');
    Readln(Rows);
    Writeln('Введтие кол-во столбцов матрицы');
    Readln(Cols);
    SetLength(NewMatrix, Cols, Rows);
    Writeln('Введите элементы матрицы');
    for I := 0 to High(NewMatrix) do
        for J := 0 to High(NewMatrix[0]) do
        begin
            Write('a[', I, ',', J, '] = ');
            Readln(NewMatrix[I, J]);
        end;
    Getmatrix := NewMatrix;
end;

procedure Swap(var A, B: Integer; Min, Max: Integer; var IsntSwapped: Boolean);
begin
    if (Min < Max) and (A > B) then
    begin
        IsntSwapped := false;
        A := A xor B;
        B := A xor B;
        A := A xor B;
    end;
end;

function Sort(ToSort: Matrix): Matrix;
var
    I, N, J, IStart, JStart, Cols, Rows: Integer;
    IsSorted: Boolean;
begin
    N := 0;
    repeat
        Inc(N);
        Cols := High(ToSort[0]);
        Rows := High(ToSort);
        IStart := 0;
        JStart := 0;
        IsSorted := true;
        if N = 10000000 then
        begin
            Writeln;
            Writeln('PreSorted');
            PrintMatrix(ToSort);
            N := 0;
        end;
        while (IStart < Rows) and (JStart < Cols) do
        begin

            for J := JStart to Cols do // верх
                Swap(ToSort[IStart, J], ToSort[IStart, J + 1], J, Cols,
                  IsSorted);
            if Cols < high(ToSort[0]) then
                Inc(JStart);
            for I := IStart to Rows do // право
                Swap(ToSort[I, Cols], ToSort[I + 1, Cols], I, Rows, IsSorted);
            Inc(IStart);
            for J := Cols downto JStart do // низ
                Swap(ToSort[Rows, J], ToSort[Rows, J - 1], JStart, J, IsSorted);
            Dec(Cols);
            for I := Rows downto IStart do // лево
                Swap(ToSort[I, JStart], ToSort[I - 1, JStart], IStart, I,
                  IsSorted);

            Dec(Rows);
            JStart := IStart - 1;
        end;
    until IsSorted;
end;

var
    Test: Matrix;

begin

    { Test := [[6,6,3,0,7,8,0,1,8,6,9],
      [9,4,2,3,7,7,2,2,2,9,8],
      [2,4,8,6,5,1,4,7,0,8,7],
      [4,8,7,1,5,0,4,4,7,2,4],
      [3,8,8,3,6,3,1,0,2,5,8],
      [8,3,9,1,1,3,9,6,0,6,1],
      [1,0,4,6,6,1,2,7,8,1,5],
      [8,0,9,7,1,4,0,6,9,5,2],
      [6,0,3,1,3,9,1,5,0,1,8],
      [2,6,8,9,0,7,9,8,5,6,6],
      [2,5,9,1,3,1,4,5,4,6,6]]; }

 {   Test := [[116, 489, 124, 392, 52, 167, 191, 230, 258, 240, 308, 410, 396,
      221, 50, 452, 60, 472, 402, 276, 65, 260, 481, 474],
      [78, 317, 196, 96, 396, 152, 312, 167, 399, 128, 431, 367, 55, 163, 287,
      332, 401, 457, 313, 306, 481, 496, 86, 137], [414, 262, 110, 315, 189,
      209, 181, 355, 8, 149, 313, 234, 471, 94, 334, 105, 428, 140, 10, 267,
      289, 183, 396, 397], [184, 69, 375, 108, 447, 175, 492, 81, 231, 58, 181,
      133, 42, 496, 478, 190, 447, 76, 358, 406, 349, 52, 361, 306],
      [122, 207, 377, 341, 486, 318, 348, 231, 365, 213, 130, 120, 333, 73, 407,
      333, 157, 231, 3, 412, 412, 201, 63, 432], [162, 320, 320, 213, 324, 490,
      47, 132, 207, 69, 485, 240, 297, 151, 95, 412, 210, 450, 267, 329, 366,
      357, 356, 373], [168, 25, 248, 117, 48, 448, 393, 421, 143, 445, 178, 166,
      498, 134, 407, 375, 165, 498, 412, 264, 88, 167, 36, 6],
      [136, 91, 202, 462, 433, 233, 65, 304, 463, 447, 45, 298, 241, 429, 83,
      258, 175, 63, 96, 351, 472, 429, 414, 75], [43, 392, 163, 367, 444, 92,
      284, 0, 489, 242, 481, 457, 246, 431, 488, 409, 379, 374, 202, 51, 88,
      108, 133, 236], [414, 154, 89, 24, 71, 184, 33, 206, 177, 126, 418, 40,
      70, 198, 359, 371, 162, 44, 309, 499, 448, 126, 12, 244],
      [75, 186, 472, 98, 226, 363, 486, 434, 259, 427, 453, 290, 2, 260, 429,
      305, 209, 274, 279, 119, 12, 448, 339, 181], [14, 331, 388, 44, 299, 134,
      288, 287, 142, 344, 449, 384, 211, 435, 480, 314, 139, 483, 281, 143, 244,
      69, 368, 401], [115, 3, 290, 173, 346, 392, 231, 127, 346, 291, 83, 395,
      474, 442, 135, 124, 138, 166, 147, 158, 311, 45, 93, 273],
      [294, 465, 479, 29, 166, 196, 437, 445, 462, 486, 428, 295, 344, 114, 440,
      250, 113, 321, 37, 420, 351, 84, 339, 196], [347, 156, 4, 78, 421, 210,
      90, 69, 410, 16, 378, 381, 412, 202, 460, 150, 353, 138, 432, 487, 14,
      340, 280, 24], [225, 397, 44, 489, 7, 173, 422, 209, 126, 283, 181, 10,
      192, 358, 24, 252, 395, 358, 385, 328, 235, 59, 337, 411],
      [361, 387, 66, 213, 151, 351, 182, 7, 376, 480, 352, 23, 165, 101, 62,
      236, 94, 169, 254, 129, 20, 450, 457, 494], [114, 180, 91, 155, 455, 452,
      288, 166, 59, 133, 127, 120, 106, 208, 58, 274, 100, 174, 133, 212, 6, 0,
      86, 294], [296, 148, 233, 66, 304, 208, 390, 410, 429, 71, 99, 471, 260,
      27, 51, 424, 192, 185, 463, 32, 473, 442, 129, 385],
      [111, 480, 28, 346, 316, 245, 488, 113, 93, 297, 358, 307, 218, 221, 362,
      351, 243, 217, 190, 35, 109, 86, 14, 73], [123, 209, 20, 320, 36, 54, 320,
      354, 18, 348, 455, 323, 179, 43, 94, 183, 83, 485, 377, 462, 168, 244,
      205, 470], [323, 112, 288, 256, 251, 94, 276, 24, 465, 455, 223, 106, 225,
      167, 76, 38, 476, 4, 288, 370, 265, 38, 171, 199],
      [122, 7, 452, 123, 208, 51, 404, 378, 3, 49, 496, 424, 266, 63, 102, 424,
      71, 431, 357, 224, 319, 487, 457, 415], [408, 339, 485, 163, 455, 335,
      204, 285, 440, 88, 134, 244, 141, 153, 315, 413, 50, 344, 102, 176, 171,
      152, 272, 413], [402, 363, 298, 334, 180, 446, 380, 135, 49, 37, 214, 369,
      66, 240, 423, 168, 344, 210, 483, 177, 429, 358, 282, 418],
      [115, 443, 173, 475, 384, 281, 244, 256, 66, 72, 261, 91, 36, 370, 105,
      494, 208, 498, 194, 104, 438, 446, 347, 309],
      [421, 434, 331, 460, 168, 94, 483, 43, 80, 380, 218, 236, 273, 404, 250,
      268, 293, 457, 302, 493, 479, 331, 131, 474],
      [105, 489, 469, 430, 163, 178, 480, 169, 96, 364, 53, 450, 449, 283, 88,
      471, 89, 218, 11, 156, 151, 369, 220, 303], [248, 426, 311, 480, 143, 354,
      330, 90, 303, 357, 355, 178, 125, 52, 379, 402, 400, 49, 139, 408, 350,
      300, 318, 9], [369, 330, 404, 260, 320, 474, 322, 235, 268, 165, 182, 237,
      366, 499, 25, 242, 33, 463, 147, 92, 428, 409, 345, 37],
      [338, 108, 256, 101, 229, 312, 452, 447, 108, 302, 110, 312, 449, 69, 269,
      328, 34, 119, 410, 460, 369, 142, 35, 400], [23, 397, 375, 387, 153, 225,
      80, 460, 484, 366, 421, 211, 218, 220, 6, 456, 212, 234, 129, 64, 389,
      213, 292, 463], [193, 319, 57, 309, 498, 385, 167, 196, 72, 355, 78, 332,
      436, 65, 294, 382, 221, 149, 327, 82, 147, 57, 109, 313],
      [113, 453, 248, 134, 12, 471, 11, 310, 105, 411, 193, 334, 167, 271, 462,
      99, 199, 225, 139, 363, 142, 174, 20, 146], [440, 246, 343, 239, 385, 209,
      315, 136, 209, 243, 196, 45, 137, 33, 183, 101, 343, 267, 226, 24, 372,
      460, 214, 450], [187, 228, 383, 422, 418, 246, 171, 438, 433, 101, 194,
      266, 128, 272, 425, 395, 96, 57, 124, 424, 74, 416, 462, 166],
      [41, 38, 19, 375, 447, 495, 274, 480, 32, 393, 51, 157, 325, 393, 217,
      463, 72, 257, 111, 35, 338, 417, 473, 71], [342, 331, 428, 315, 335, 290,
      375, 270, 265, 217, 381, 380, 226, 296, 491, 438, 326, 213, 233, 235, 220,
      267, 69, 202], [339, 161, 351, 317, 305, 426, 327, 123, 64, 447, 32, 115,
      66, 459, 145, 241, 17, 281, 391, 108, 11, 337, 236, 276],
      [265, 173, 209, 125, 183, 238, 351, 74, 261, 225, 475, 173, 439, 58, 465,
      339, 390, 257, 315, 279, 263, 376, 371, 367],
      [68, 492, 217, 439, 376, 461, 191, 2, 425, 75, 51, 132, 217, 201, 439,
      326, 96, 458, 354, 340, 484, 471, 302, 459], [316, 52, 217, 253, 21, 457,
      13, 389, 301, 342, 56, 191, 20, 411, 197, 300, 34, 472, 248, 364, 6, 332,
      122, 188], [318, 488, 182, 304, 21, 30, 382, 96, 189, 258, 123, 324, 243,
      437, 481, 467, 61, 162, 330, 375, 144, 247, 306, 184],
      [260, 53, 306, 11, 222, 438, 453, 483, 430, 29, 435, 32, 274, 208, 367,
      271, 459, 459, 1, 262, 288, 373, 56, 97], [491, 280, 302, 344, 2, 247, 43,
      70, 182, 497, 44, 468, 224, 371, 374, 251, 304, 139, 394, 214, 2, 448,
      193, 353], [294, 59, 415, 185, 246, 43, 395, 386, 496, 208, 20, 441, 136,
      108, 480, 182, 485, 364, 350, 276, 164, 399, 46, 88],
      [85, 250, 457, 149, 479, 342, 95, 43, 87, 448, 49, 443, 331, 358, 324,
      139, 102, 157, 471, 15, 351, 432, 114, 196], [159, 211, 229, 137, 97, 416,
      189, 395, 12, 327, 99, 495, 85, 246, 407, 154, 113, 476, 353, 188, 59, 37,
      351, 126]]; }

     Test := [[438,448,375,422,33,420,325,24,306,186,469,415,357,399,128,58,163,309,233,194,17,129,477,2,416,450,238,444,268,226,98,211,254,228,122,321,290,91,171],
      [330,461,51,269,104,80,323,345,140,3,204,471,281,50,207,374,308,470,373,5,83,181,381,256,79,87,258,161,129,276,307,268,71,137,402,232,466,359,372],
      [421,93,105,98,440,63,254,317,160,46,354,313,350,417,85,87,148,79,294,189,17,322,162,216,363,195,435,399,143,147,474,408,448,98,451,412,478,83,440],
      [193,325,270,97,114,274,462,457,351,486,50,253,153,171,170,355,99,431,389,235,244,127,354,173,12,71,446,365,252,465,173,108,65,139,101,364,247,224,47],
      [441,400,238,84,413,92,394,321,236,278,243,351,481,89,347,196,65,470,96,85,42,327,97,205,385,312,442,187,13,69,306,107,375,383,447,334,6,43,440],
      [80,118,250,209,87,8,114,192,18,217,443,36,393,151,138,5,114,302,33,198,100,150,206,307,167,471,135,475,97,142,13,189,22,30,15,467,292,117,10],
      [196,271,120,423,469,70,33,413,456,236,378,332,31,473,344,340,430,411,442,42,115,373,138,94,376,204,253,14,362,135,171,212,496,292,336,427,480,227,236],
      [236,134,58,178,239,218,309,481,216,177,190,85,55,349,75,395,322,132,25,46,265,317,18,50,321,64,165,336,239,136,416,359,202,175,205,407,56,195,399],
      [376,66,223,36,336,172,50,116,363,420,397,14,294,454,180,471,419,115,8,357,174,52,473,241,80,260,330,382,379,144,167,338,126,233,149,480,41,281,182],
      [377,270,448,302,415,342,122,122,404,21,204,286,292,48,338,224,323,93,481,455,75,342,167,236,218,252,58,387,60,305,200,429,138,433,130,86,226,249,57],
      [399,458,138,425,361,175,357,375,289,288,9,325,386,59,325,107,34,103,211,83,163,283,234,61,98,321,274,148,359,418,252,498,73,36,82,497,436,417,306],
      [61,360,377,269,98,51,480,313,370,312,325,95,482,14,165,394,115,223,77,326,39,400,209,16,371,35,10,251,349,477,327,170,117,297,149,222,285,14,135],
      [9,118,7,404,335,33,322,269,483,407,142,466,274,359,90,266,160,151,360,397,63,41,229,463,392,485,155,477,185,364,443,108,101,87,67,208,32,496,374],
      [483,48,266,26,343,207,10,53,310,27,30,489,71,425,116,72,468,389,43,11,350,377,344,84,118,464,34,364,186,292,382,233,164,276,377,348,296,14,385],
      [256,382,431,345,450,154,375,371,183,485,14,98,318,489,484,24,105,204,182,408,378,173,145,367,17,144,297,325,295,47,267,276,454,3,286,129,418,31,394],
      [429,243,93,350,379,172,193,63,244,179,251,271,144,114,105,6,83,236,64,327,305,357,50,75,135,217,238,144,314,202,355,105,73,310,252,165,285,322,266],
      [195,324,81,53,145,44,275,123,161,348,497,203,392,354,204,88,71,192,18,215,162,433,49,248,41,323,145,198,334,362,440,221,260,470,369,3,224,304,404],
      [31,360,94,77,295,317,498,462,251,369,221,180,472,267,107,103,261,274,332,11,322,398,77,288,298,407,275,443,422,485,200,363,267,288,486,355,68,356,253],
      [431,42,361,394,328,112,181,468,454,153,366,107,228,392,292,82,132,282,305,278,387,42,55,40,266,168,358,413,184,280,252,35,405,20,400,469,460,4,248],
      [176,117,439,320,289,55,377,472,471,475,205,353,72,262,77,366,388,486,321,127,160,253,268,283,174,401,331,202,208,491,322,121,128,33,128,160,448,221,265],
      [484,389,196,387,437,478,426,179,272,327,154,12,482,139,376,88,422,349,155,146,388,224,175,263,479,152,83,225,39,133,416,418,166,220,336,238,463,366,330],
      [305,247,222,58,374,53,479,340,481,251,444,206,311,292,75,377,259,213,432,408,285,394,201,140,138,411,236,345,261,303,138,125,56,18,350,398,166,166,300],
      [210,499,311,101,473,94,427,104,125,91,343,76,24,30,458,45,410,45,81,419,463,317,134,79,178,113,319,150,293,441,176,211,93,413,222,408,473,292,228],
      [45,211,306,110,253,418,226,113,94,97,473,440,352,84,246,337,392,365,232,423,359,275,277,311,183,414,131,483,111,308,50,72,117,317,36,208,156,207,380],
      [161,452,0,224,52,319,1,323,126,347,75,329,42,240,369,368,270,433,494,426,339,286,243,2,286,47,400,322,35,48,38,180,185,485,71,470,359,51,225],
      [491,182,90,5,135,35,478,7,331,247,449,265,274,162,280,40,374,209,497,438,4,419,179,288,78,308,394,144,57,168,399,8,219,208,2,244,248,280,107],
      [466,307,40,68,75,85,282,263,18,404,444,196,261,361,112,220,72,2,301,426,327,140,334,449,163,348,440,46,66,160,36,292,94,101,31,130,464,350,103],
      [203,295,44,376,239,113,471,137,146,106,487,429,241,447,354,280,325,472,90,405,226,144,235,197,358,368,152,102,159,330,481,256,222,398,98,130,282,263,95],
      [336,191,210,293,440,78,230,295,344,239,321,205,158,373,444,377,58,59,347,18,370,461,368,477,316,124,231,206,342,348,223,497,61,377,254,213,15,351,295],
      [118,127,73,307,363,338,124,323,382,278,21,40,70,434,245,224,374,323,233,477,315,346,23,452,496,15,324,143,280,119,231,361,207,264,228,391,297,154,5],
      [139,191,301,349,428,320,308,152,62,316,152,380,390,282,373,480,271,103,120,310,347,13,480,43,262,46,160,333,306,206,354,427,220,317,93,286,14,497,95],
      [132,187,363,261,327,127,239,340,78,333,283,456,287,176,343,158,125,210,257,86,381,160,475,346,356,462,225,160,72,189,87,466,274,8,488,123,484,252,153],
      [415,23,206,81,499,23,249,66,251,376,159,467,75,256,410,213,471,212,16,404,364,402,79,267,388,246,317,182,279,187,220,174,373,56,342,63,175,78,476],
      [322,106,395,474,283,413,222,11,209,363,294,17,410,467,347,288,12,444,438,192,252,206,67,287,63,156,484,94,19,413,346,37,393,236,194,298,469,428,295],
      [354,166,235,107,318,484,170,309,207,25,267,330,119,237,385,223,116,39,108,410,127,428,128,492,296,16,256,124,174,273,49,319,84,148,83,26,16,98,248],
      [302,393,346,277,68,251,83,227,300,7,12,77,258,361,18,168,425,38,243,311,301,227,46,134,434,475,448,245,471,153,359,207,17,291,305,17,280,151,59],
      [241,212,289,456,116,162,195,291,458,65,479,158,487,273,287,447,75,347,212,343,92,302,337,256,146,147,305,59,466,55,1,388,274,478,2,98,12,271,429],
      [472,238,184,489,179,491,495,371,434,229,344,230,170,67,307,466,438,374,33,310,468,357,135,324,402,64,90,383,9,270,189,434,303,417,239,104,408,312,157],
      [264,150,276,370,329,122,325,330,320,466,12,64,223,478,461,460,115,102,359,87,115,401,111,362,163,40,409,426,252,327,202,58,125,216,268,159,192,486,305],
      [201,77,233,269,417,496,206,465,456,342,457,124,2,48,225,42,363,39,414,207,289,213,399,78,493,263,454,439,7,210,302,267,128,296,157,9,381,131,194]];

    PrintMatrix(Test);
    Sort(Test);
    Writeln;
    PrintMatrix(Test);
    Readln;

end.