5
\$\begingroup\$

This solves Project Euler #11: In the 20×20 grid below, four numbers along a diagonal line have been marked as bold.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

This program intends to find the greatest product of n adjacent numbers in the same direction (up, down, left, right, or diagonally) in the mxm grid.

Assumptions:

  • The directions up-down and left-right are taken as same directions as vertical and horizontal respectively. (Commutative property of multiplication)
  • When calculating diagonal products, both the diagonal directions are considered viz., top-left to bottom-right and top-right to bottom-left.

Solution:

grid = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

grid = grid.split("\n")
grid = [x.split(" ") for x in grid]
grid = [[int(y) for y in x] for x in grid]

n = 4 # range of numbers to be considered for product

# Function for largest product in vertical or horizontal direction, i.e, rows or columns
def product_orthogonal(grid):
    productOrtho = 1
    for row in grid:
        for x in range(0, len(row)-(n-1)):
            product = 1
            for i in range (0, n):
                product = product * row[x+i]
            if productOrtho < product:
                productOrtho = product

    grid_transpose = [list(i) for i in zip(*grid)]  # Get transpose of grid to get products in vertical direction
    for row in grid_transpose:
        for x in range(0, len(row)-(n-1)):
            product = 1
            for i in range (0, n):
                product = product * row[x+i]
            if productOrtho < product:
                productOrtho = product

    return productOrtho

# Function for largest product in diagonal direction
def product_diagonal(grid):
    productD = 1
    for r in range(0, len(grid)-(n-1)):
        for c in range(0, len(grid[r])-(n-1)):
            product = 1
            for i in range (0, n):
                product = product * grid[r+i][c+i]
            if productD < product:
                productD = product

    grid_reversed = grid[:]  # Get grid with reversed rows
    for row in grid_reversed:
        row.reverse()
    for r in range(0, len(grid_reversed)-(n-1)):
        for c in range(0, len(grid_reversed[r])-(n-1)):
            product = 1
            for i in range (0, n):
                product = product * grid_reversed[r+i][c+i]
            if productD < product:
                productD = product

    return productD


largestProductInGrid  = max(product_orthogonal(grid), product_diagonal(grid))
print("Largest product in the grid is : "+ str(largestProductInGrid))

Time required for execution:

Grid size = 20x20, Numbers in product = 2, Largest Product = 9603, Time required = 1ms Grid size = 20x20, Numbers in product = 3, Largest Product = 811502, Time required = 1ms
Grid size = 20x20, Numbers in product = 4, Largest Product = 70600674, Time required = 2ms
Grid size = 20x20, Numbers in product = 5, Largest Product = 3318231678, Time required = 3ms
Grid size = 100x100, Numbers in product = 4, Largest Product = 862087461144, Time required = 41ms
Grid used (100x100) :

[[398, 456, 701, 383, 117, 296, 203, 115, 997, 635, 433, 595, 756, 544, 241, 332, 503, 519, 299, 410, 406, 627, 473, 180, 749, 146, 936, 808, 834, 844, 345, 438, 584, 912, 708, 450, 277, 186, 119, 249, 839, 667, 417, 840, 654, 590, 728, 978, 870, 714, 297, 188, 762, 929, 655, 746, 224, 103, 879, 387, 622, 760, 112, 703, 910, 227, 539, 729, 697, 134, 172, 555, 939, 579, 758, 213, 262, 955, 761, 195, 497, 887, 372, 820, 578, 147, 111, 613, 923, 292, 151, 484, 645, 715, 735, 400, 953, 280, 338, 408],
[685, 346, 887, 891, 653, 323, 338, 267, 815, 381, 701, 725, 423, 850, 973, 202, 724, 439, 256, 676, 394, 809, 484, 648, 613, 352, 296, 295, 123, 960, 981, 512, 612, 962, 610, 532, 860, 892, 120, 246, 799, 210, 646, 578, 905, 987, 637, 214, 364, 831, 329, 658, 250, 170, 911, 433, 403, 178, 953, 271, 619, 311, 657, 996, 227, 857, 717, 840, 965, 593, 633, 419, 395, 147, 241, 270, 133, 785, 730, 551, 907, 432, 400, 563, 768, 462, 783, 291, 878, 778, 763, 753, 594, 649, 959, 677, 399, 821, 868, 592],
[156, 765, 934, 555, 201, 961, 701, 464, 362, 332, 589, 686, 164, 999, 402, 219, 342, 967, 141, 623, 517, 356, 137, 985, 533, 965, 654, 221, 680, 371, 752, 269, 159, 328, 708, 630, 692, 690, 832, 449, 530, 178, 217, 772, 272, 843, 404, 617, 325, 598, 335, 663, 244, 755, 643, 627, 151, 845, 196, 291, 639, 665, 198, 732, 691, 162, 330, 444, 112, 242, 896, 913, 369, 492, 215, 933, 917, 359, 953, 534, 391, 302, 952, 817, 881, 411, 438, 331, 482, 487, 653, 320, 253, 582, 131, 804, 259, 412, 697, 861],
[164, 677, 602, 849, 569, 871, 665, 875, 998, 640, 383, 301, 373, 703, 105, 635, 611, 926, 571, 922, 101, 910, 336, 712, 136, 424, 566, 130, 157, 658, 393, 717, 146, 178, 325, 952, 909, 911, 729, 600, 297, 780, 673, 204, 915, 996, 708, 636, 960, 939, 561, 401, 483, 184, 670, 779, 348, 262, 388, 339, 243, 110, 967, 593, 987, 442, 296, 482, 258, 323, 777, 513, 201, 194, 977, 794, 491, 599, 535, 595, 830, 695, 964, 380, 237, 193, 588, 837, 487, 117, 784, 438, 200, 903, 461, 648, 575, 257, 572, 260],
[634, 361, 938, 925, 937, 550, 482, 984, 237, 964, 340, 551, 536, 991, 903, 757, 300, 731, 936, 349, 919, 615, 898, 815, 468, 619, 702, 481, 535, 951, 347, 542, 742, 881, 612, 560, 574, 497, 690, 772, 105, 637, 184, 371, 196, 671, 394, 233, 138, 621, 115, 519, 868, 324, 386, 756, 776, 242, 922, 583, 524, 259, 404, 106, 666, 955, 533, 498, 227, 943, 762, 186, 399, 249, 971, 433, 688, 736, 370, 317, 656, 785, 673, 782, 513, 561, 883, 200, 662, 178, 895, 479, 854, 373, 860, 761, 512, 672, 703, 734],
[837, 968, 534, 663, 941, 289, 660, 366, 335, 974, 123, 220, 866, 862, 233, 949, 399, 401, 598, 835, 100, 711, 965, 976, 685, 736, 707, 235, 513, 805, 163, 225, 425, 650, 884, 845, 280, 540, 191, 548, 133, 682, 883, 242, 386, 361, 199, 980, 704, 620, 126, 647, 184, 776, 998, 856, 995, 962, 717, 757, 269, 655, 358, 117, 932, 843, 912, 561, 723, 446, 327, 291, 940, 544, 116, 518, 375, 391, 114, 530, 957, 886, 190, 462, 238, 596, 343, 160, 542, 205, 948, 903, 517, 121, 356, 267, 811, 937, 292, 153],
[821, 892, 677, 498, 105, 257, 305, 217, 927, 781, 894, 714, 441, 493, 556, 327, 616, 553, 631, 602, 222, 950, 214, 168, 172, 691, 289, 940, 463, 879, 184, 685, 902, 702, 506, 337, 734, 164, 844, 124, 210, 338, 538, 129, 383, 518, 586, 362, 832, 258, 474, 662, 751, 369, 268, 869, 632, 719, 153, 709, 194, 613, 569, 279, 710, 568, 340, 895, 646, 345, 851, 840, 758, 155, 114, 249, 936, 920, 987, 957, 530, 364, 730, 483, 588, 757, 822, 648, 456, 220, 697, 255, 246, 494, 136, 919, 106, 120, 145, 546],
[327, 704, 972, 349, 347, 908, 886, 977, 907, 175, 856, 597, 965, 750, 114, 235, 162, 478, 966, 448, 495, 215, 242, 394, 616, 339, 178, 883, 356, 152, 237, 872, 474, 725, 692, 218, 302, 631, 995, 669, 909, 317, 163, 700, 460, 737, 666, 434, 619, 789, 407, 781, 796, 985, 109, 409, 334, 399, 889, 643, 900, 896, 612, 911, 147, 954, 283, 113, 530, 528, 760, 360, 376, 813, 817, 494, 723, 770, 374, 809, 188, 413, 131, 320, 947, 852, 766, 105, 922, 652, 497, 142, 837, 698, 855, 568, 247, 610, 582, 480],
[414, 199, 162, 358, 148, 134, 490, 426, 932, 382, 748, 976, 404, 626, 794, 219, 336, 826, 277, 796, 543, 797, 840, 681, 902, 624, 701, 572, 901, 319, 870, 398, 766, 583, 503, 522, 611, 385, 895, 272, 754, 798, 944, 814, 330, 591, 991, 736, 104, 675, 750, 207, 632, 174, 379, 920, 868, 917, 535, 477, 129, 813, 402, 310, 745, 613, 628, 855, 657, 179, 775, 998, 245, 326, 309, 135, 807, 703, 102, 915, 903, 433, 684, 259, 378, 476, 147, 792, 437, 444, 623, 322, 635, 819, 127, 743, 507, 669, 234, 575],
[645, 858, 453, 586, 276, 588, 713, 580, 245, 317, 274, 957, 493, 501, 303, 955, 335, 226, 761, 174, 624, 926, 888, 386, 681, 514, 638, 147, 742, 731, 903, 462, 502, 893, 774, 269, 444, 940, 892, 597, 634, 814, 229, 320, 395, 960, 724, 659, 720, 843, 346, 369, 752, 114, 560, 609, 741, 181, 549, 856, 357, 563, 214, 810, 946, 854, 536, 481, 312, 808, 642, 943, 701, 361, 785, 461, 625, 189, 788, 424, 372, 412, 927, 600, 505, 825, 136, 734, 702, 618, 183, 287, 506, 246, 323, 171, 861, 895, 925, 805],
[947, 579, 902, 124, 151, 810, 269, 767, 169, 860, 343, 159, 191, 330, 561, 430, 753, 209, 660, 819, 897, 861, 892, 172, 772, 157, 663, 176, 686, 167, 604, 428, 207, 627, 488, 973, 512, 937, 864, 978, 747, 544, 148, 142, 372, 623, 506, 221, 657, 895, 234, 968, 614, 621, 351, 849, 539, 409, 284, 119, 337, 837, 647, 939, 996, 800, 792, 120, 820, 109, 496, 903, 554, 472, 400, 775, 637, 251, 950, 402, 238, 606, 929, 955, 371, 436, 876, 118, 589, 553, 808, 644, 600, 570, 567, 514, 742, 664, 780, 419],
[257, 921, 720, 473, 799, 658, 335, 718, 274, 913, 239, 774, 883, 395, 897, 486, 794, 980, 561, 231, 560, 868, 244, 278, 210, 941, 115, 477, 388, 903, 809, 537, 905, 654, 442, 242, 610, 840, 364, 796, 282, 896, 638, 695, 103, 856, 721, 154, 841, 950, 931, 393, 382, 131, 323, 261, 483, 923, 358, 431, 818, 997, 461, 520, 289, 525, 730, 909, 249, 248, 689, 279, 195, 418, 596, 810, 414, 143, 443, 546, 661, 219, 439, 516, 129, 272, 757, 687, 581, 776, 671, 101, 675, 318, 298, 942, 877, 849, 644, 398],
[212, 649, 176, 701, 548, 163, 655, 686, 151, 127, 988, 507, 468, 504, 434, 297, 301, 725, 867, 656, 757, 729, 437, 453, 909, 169, 170, 597, 246, 177, 492, 155, 141, 979, 376, 515, 608, 392, 103, 562, 307, 286, 228, 314, 108, 330, 480, 743, 696, 727, 815, 451, 476, 684, 565, 378, 910, 194, 473, 445, 116, 479, 414, 635, 538, 424, 157, 536, 456, 702, 853, 906, 575, 869, 517, 249, 657, 341, 937, 117, 824, 474, 775, 518, 607, 784, 284, 672, 987, 819, 188, 978, 744, 120, 731, 534, 762, 402, 109, 430],
[440, 235, 182, 808, 886, 485, 977, 588, 516, 653, 323, 924, 970, 174, 676, 420, 531, 711, 762, 415, 156, 147, 811, 586, 320, 234, 407, 754, 669, 309, 455, 565, 667, 311, 504, 463, 435, 349, 355, 837, 853, 849, 859, 274, 508, 630, 285, 279, 374, 576, 919, 832, 242, 101, 575, 587, 989, 128, 705, 143, 901, 598, 981, 293, 310, 973, 551, 887, 154, 861, 595, 390, 682, 767, 566, 183, 253, 946, 818, 618, 606, 423, 450, 718, 223, 133, 617, 880, 935, 858, 945, 768, 679, 574, 622, 382, 176, 683, 141, 413],
[639, 183, 794, 584, 114, 325, 517, 290, 195, 822, 554, 769, 224, 940, 182, 651, 198, 690, 158, 410, 547, 642, 339, 851, 154, 858, 669, 364, 648, 244, 957, 592, 576, 423, 545, 400, 336, 871, 844, 886, 683, 945, 621, 212, 185, 559, 481, 367, 398, 351, 453, 922, 259, 755, 751, 232, 862, 375, 946, 975, 905, 179, 812, 392, 729, 633, 243, 611, 419, 284, 962, 302, 193, 780, 490, 981, 861, 870, 349, 468, 415, 772, 108, 452, 431, 530, 522, 649, 384, 933, 462, 953, 923, 857, 191, 699, 706, 617, 100, 436],
[707, 335, 754, 584, 294, 812, 671, 333, 775, 645, 533, 568, 947, 140, 358, 451, 636, 874, 383, 208, 597, 606, 927, 703, 833, 732, 603, 228, 201, 135, 749, 674, 323, 301, 360, 936, 869, 375, 792, 950, 456, 715, 448, 884, 320, 647, 243, 608, 789, 167, 374, 887, 853, 134, 818, 123, 432, 913, 508, 809, 604, 738, 303, 368, 806, 159, 288, 131, 626, 893, 569, 716, 267, 217, 693, 977, 341, 550, 232, 293, 280, 313, 331, 483, 237, 780, 425, 475, 969, 790, 880, 662, 863, 573, 962, 919, 314, 378, 572, 242],
[830, 978, 673, 530, 282, 943, 644, 769, 195, 631, 638, 384, 897, 498, 126, 373, 745, 458, 809, 902, 292, 228, 475, 239, 937, 567, 405, 474, 214, 144, 379, 461, 877, 173, 871, 540, 225, 238, 433, 310, 655, 999, 450, 932, 803, 919, 862, 275, 694, 328, 698, 378, 441, 519, 533, 810, 447, 385, 196, 759, 833, 606, 539, 702, 835, 557, 797, 300, 525, 579, 256, 777, 726, 597, 467, 104, 222, 179, 312, 549, 431, 761, 663, 658, 963, 985, 270, 890, 805, 255, 752, 703, 918, 127, 417, 515, 679, 844, 885, 423],
[836, 381, 544, 866, 980, 354, 953, 840, 703, 311, 613, 937, 286, 984, 464, 202, 649, 869, 121, 192, 562, 999, 534, 991, 141, 180, 297, 551, 386, 122, 165, 428, 831, 183, 591, 543, 779, 430, 432, 988, 694, 498, 198, 355, 392, 660, 745, 661, 316, 494, 383, 242, 221, 716, 615, 969, 750, 112, 777, 239, 822, 169, 877, 941, 884, 983, 867, 539, 926, 864, 717, 178, 175, 993, 139, 162, 368, 333, 566, 353, 482, 274, 153, 249, 281, 744, 919, 574, 728, 336, 137, 737, 171, 253, 741, 366, 309, 525, 196, 485],
[385, 690, 813, 908, 479, 956, 714, 497, 446, 747, 339, 178, 202, 555, 787, 639, 376, 711, 792, 321, 991, 795, 924, 282, 918, 471, 571, 922, 196, 169, 801, 412, 456, 492, 676, 912, 306, 516, 987, 338, 345, 458, 298, 188, 919, 238, 180, 493, 958, 469, 268, 829, 304, 418, 688, 881, 140, 967, 193, 244, 323, 592, 403, 549, 633, 811, 738, 274, 642, 743, 889, 838, 267, 216, 897, 821, 120, 831, 342, 941, 208, 368, 503, 258, 567, 524, 638, 770, 914, 496, 749, 350, 569, 512, 153, 192, 432, 600, 399, 718],
[369, 205, 187, 171, 623, 686, 681, 258, 744, 654, 735, 372, 851, 347, 774, 306, 506, 779, 525, 928, 960, 904, 272, 786, 241, 974, 805, 998, 836, 339, 380, 216, 327, 204, 522, 882, 813, 492, 868, 993, 938, 487, 147, 245, 304, 908, 493, 959, 371, 290, 547, 864, 825, 137, 970, 772, 222, 498, 173, 743, 160, 458, 373, 937, 148, 104, 604, 237, 649, 231, 628, 288, 360, 365, 198, 338, 701, 966, 621, 417, 259, 221, 859, 495, 367, 785, 428, 650, 580, 326, 947, 736, 824, 268, 831, 486, 821, 849, 740, 572],
[118, 800, 106, 789, 655, 693, 372, 996, 817, 596, 319, 551, 695, 653, 196, 893, 904, 190, 854, 515, 257, 467, 651, 599, 105, 646, 703, 874, 185, 331, 919, 466, 616, 158, 126, 325, 517, 530, 664, 877, 310, 744, 573, 509, 804, 645, 712, 794, 873, 327, 505, 173, 547, 116, 849, 286, 858, 278, 237, 328, 340, 501, 443, 282, 724, 736, 352, 436, 842, 886, 748, 542, 219, 383, 950, 178, 235, 249, 850, 777, 813, 151, 851, 705, 990, 381, 464, 119, 589, 584, 321, 345, 299, 528, 412, 587, 170, 341, 689, 912],
[397, 374, 943, 619, 321, 240, 583, 341, 190, 489, 775, 481, 402, 990, 920, 492, 843, 736, 872, 276, 631, 526, 704, 417, 237, 820, 647, 620, 543, 549, 835, 726, 651, 171, 152, 294, 975, 302, 390, 305, 227, 603, 648, 953, 912, 936, 614, 143, 517, 611, 185, 415, 298, 799, 714, 955, 438, 134, 754, 617, 888, 719, 383, 404, 931, 656, 100, 733, 930, 160, 490, 280, 382, 319, 777, 625, 774, 730, 570, 767, 527, 450, 456, 588, 216, 610, 251, 155, 982, 962, 605, 762, 833, 965, 703, 904, 541, 472, 214, 923],
[982, 717, 626, 495, 781, 210, 398, 791, 959, 493, 362, 419, 786, 286, 558, 453, 279, 215, 860, 270, 142, 218, 185, 848, 730, 877, 924, 805, 366, 259, 985, 610, 611, 222, 374, 968, 999, 160, 818, 674, 309, 615, 700, 408, 107, 606, 582, 221, 765, 464, 313, 654, 238, 105, 697, 946, 635, 966, 367, 403, 850, 890, 110, 859, 520, 886, 438, 813, 793, 708, 446, 792, 402, 474, 448, 244, 507, 769, 246, 951, 733, 514, 742, 217, 386, 689, 690, 180, 158, 163, 184, 970, 487, 534, 332, 858, 817, 473, 799, 942],
[553, 237, 511, 966, 618, 198, 265, 406, 271, 725, 471, 489, 582, 657, 803, 602, 327, 837, 318, 988, 972, 682, 548, 936, 154, 180, 856, 253, 995, 491, 401, 387, 212, 670, 274, 342, 111, 937, 820, 446, 349, 570, 317, 831, 117, 722, 656, 480, 396, 261, 447, 986, 397, 371, 419, 828, 547, 515, 254, 959, 814, 935, 900, 479, 388, 354, 493, 742, 560, 970, 168, 156, 420, 151, 331, 695, 197, 330, 369, 591, 140, 227, 671, 455, 400, 754, 200, 532, 233, 138, 429, 620, 919, 684, 266, 847, 404, 395, 745, 303],
[963, 959, 319, 687, 542, 940, 602, 466, 971, 813, 391, 340, 446, 370, 180, 417, 845, 849, 205, 366, 598, 159, 362, 328, 925, 425, 821, 354, 885, 508, 251, 837, 579, 603, 696, 556, 124, 641, 139, 858, 870, 839, 274, 564, 595, 474, 938, 310, 710, 965, 530, 226, 271, 575, 479, 998, 509, 622, 944, 929, 306, 233, 676, 252, 489, 387, 937, 395, 723, 179, 157, 133, 309, 601, 295, 694, 640, 791, 490, 706, 586, 767, 346, 322, 834, 663, 857, 760, 574, 664, 733, 154, 739, 129, 552, 493, 461, 104, 141, 770],
[278, 530, 483, 741, 935, 218, 339, 130, 750, 689, 783, 434, 107, 191, 938, 578, 317, 442, 926, 402, 376, 682, 584, 777, 923, 144, 154, 404, 601, 903, 787, 818, 614, 311, 613, 168, 377, 133, 717, 658, 915, 157, 837, 962, 573, 368, 751, 685, 920, 736, 381, 405, 416, 607, 243, 684, 359, 122, 785, 740, 496, 254, 481, 816, 476, 895, 247, 656, 266, 970, 315, 830, 921, 551, 797, 804, 621, 823, 944, 332, 134, 165, 312, 663, 410, 428, 488, 114, 933, 875, 574, 291, 773, 729, 213, 622, 575, 374, 419, 589],
[772, 337, 864, 350, 427, 983, 663, 296, 187, 934, 780, 290, 115, 408, 797, 329, 692, 452, 549, 635, 785, 805, 769, 861, 654, 445, 758, 596, 922, 624, 433, 743, 850, 799, 383, 313, 556, 160, 597, 880, 342, 935, 249, 832, 675, 377, 589, 870, 808, 176, 834, 393, 231, 521, 453, 730, 513, 567, 191, 689, 939, 563, 319, 574, 163, 365, 195, 722, 255, 613, 921, 281, 150, 836, 726, 906, 501, 141, 989, 515, 958, 247, 382, 339, 747, 458, 620, 134, 768, 843, 931, 709, 839, 798, 642, 522, 682, 164, 745, 454],
[316, 290, 186, 752, 790, 480, 886, 177, 644, 340, 506, 375, 919, 527, 567, 151, 956, 224, 763, 750, 749, 725, 736, 450, 563, 344, 157, 950, 888, 131, 315, 102, 751, 205, 666, 585, 562, 254, 475, 951, 819, 302, 198, 783, 329, 731, 444, 405, 136, 301, 146, 420, 220, 675, 134, 190, 188, 583, 283, 196, 381, 356, 439, 704, 953, 670, 324, 647, 626, 856, 621, 339, 969, 485, 968, 335, 850, 243, 187, 849, 510, 938, 487, 376, 605, 140, 429, 484, 831, 446, 915, 911, 161, 979, 578, 891, 572, 168, 130, 273],
[816, 177, 725, 369, 971, 622, 818, 636, 256, 906, 678, 833, 124, 784, 300, 510, 859, 772, 911, 388, 644, 978, 830, 614, 180, 543, 221, 133, 213, 973, 354, 145, 879, 386, 896, 513, 620, 807, 483, 144, 963, 559, 943, 768, 185, 720, 666, 969, 323, 707, 450, 558, 892, 884, 139, 904, 394, 135, 942, 409, 282, 347, 531, 102, 207, 659, 876, 820, 490, 458, 693, 316, 713, 504, 608, 311, 836, 134, 351, 313, 398, 322, 193, 443, 273, 219, 270, 479, 151, 813, 419, 783, 671, 710, 687, 561, 551, 795, 967, 117],
[276, 582, 968, 389, 445, 344, 376, 640, 922, 165, 694, 975, 472, 374, 939, 215, 751, 794, 250, 620, 341, 523, 627, 288, 666, 313, 534, 920, 821, 423, 318, 797, 426, 730, 167, 926, 354, 549, 247, 823, 295, 212, 398, 977, 422, 325, 982, 799, 282, 363, 528, 970, 334, 959, 140, 583, 895, 462, 270, 331, 471, 477, 863, 775, 428, 546, 572, 476, 899, 953, 947, 350, 569, 459, 681, 679, 611, 366, 219, 901, 135, 544, 800, 842, 919, 933, 211, 793, 788, 753, 395, 609, 512, 807, 533, 772, 886, 390, 443, 873],
[811, 269, 457, 210, 505, 506, 764, 324, 847, 319, 552, 327, 503, 224, 436, 958, 586, 374, 819, 833, 304, 112, 475, 373, 523, 730, 193, 826, 775, 789, 207, 307, 274, 423, 969, 334, 275, 967, 522, 113, 433, 862, 611, 382, 169, 695, 938, 341, 347, 375, 230, 870, 316, 716, 518, 622, 480, 150, 894, 823, 203, 994, 259, 921, 377, 656, 941, 298, 129, 971, 696, 965, 325, 462, 165, 978, 394, 666, 103, 144, 569, 667, 912, 702, 320, 225, 836, 186, 949, 972, 470, 782, 422, 448, 793, 490, 943, 485, 629, 758],
[427, 959, 886, 547, 943, 795, 501, 571, 690, 178, 564, 533, 241, 981, 551, 315, 297, 917, 330, 230, 448, 805, 437, 481, 508, 293, 428, 903, 561, 671, 880, 817, 552, 367, 676, 155, 900, 107, 800, 853, 904, 302, 915, 405, 110, 554, 343, 944, 956, 380, 518, 605, 822, 717, 909, 364, 934, 773, 116, 284, 860, 772, 108, 758, 941, 127, 102, 609, 182, 727, 457, 150, 473, 960, 691, 907, 377, 397, 119, 254, 971, 942, 967, 290, 813, 122, 801, 939, 634, 761, 503, 392, 403, 892, 402, 361, 619, 685, 893, 704],
[319, 335, 798, 272, 654, 582, 895, 846, 739, 688, 867, 732, 702, 963, 212, 588, 191, 392, 446, 852, 209, 862, 970, 351, 595, 998, 921, 720, 482, 410, 969, 346, 571, 889, 429, 203, 243, 563, 771, 729, 458, 102, 778, 470, 194, 878, 640, 104, 180, 413, 733, 598, 894, 706, 407, 699, 283, 492, 179, 914, 374, 291, 454, 661, 325, 678, 887, 585, 144, 133, 245, 822, 779, 251, 281, 372, 227, 337, 461, 836, 113, 811, 376, 876, 168, 825, 115, 300, 845, 464, 957, 380, 531, 162, 965, 805, 275, 217, 270, 578],
[171, 606, 147, 151, 764, 399, 520, 996, 326, 699, 807, 488, 414, 823, 472, 106, 917, 966, 355, 235, 685, 374, 598, 406, 380, 867, 175, 298, 321, 921, 564, 449, 415, 372, 530, 635, 190, 411, 535, 640, 746, 668, 691, 804, 524, 536, 458, 208, 329, 285, 732, 221, 250, 543, 569, 145, 402, 516, 447, 904, 798, 490, 433, 331, 501, 968, 220, 101, 154, 963, 114, 999, 584, 391, 537, 548, 230, 117, 259, 844, 616, 317, 377, 452, 703, 666, 432, 218, 269, 542, 634, 511, 523, 970, 822, 417, 953, 181, 782, 348],
[422, 136, 237, 418, 382, 951, 285, 561, 340, 352, 815, 308, 503, 594, 258, 824, 328, 912, 389, 713, 534, 969, 588, 565, 446, 883, 841, 892, 336, 140, 970, 160, 871, 225, 105, 949, 120, 550, 274, 798, 169, 176, 573, 979, 309, 551, 889, 745, 117, 325, 430, 988, 564, 595, 232, 484, 283, 786, 152, 619, 875, 445, 638, 523, 520, 816, 177, 587, 457, 123, 819, 307, 771, 766, 762, 407, 333, 219, 940, 137, 805, 555, 511, 794, 251, 702, 934, 610, 861, 202, 822, 357, 602, 348, 427, 167, 442, 562, 712, 659],
[704, 913, 181, 939, 397, 599, 578, 282, 312, 344, 287, 119, 427, 705, 461, 239, 285, 255, 149, 589, 139, 626, 362, 569, 168, 246, 195, 946, 699, 431, 669, 714, 545, 420, 498, 269, 797, 253, 999, 211, 637, 403, 511, 392, 341, 310, 858, 638, 166, 228, 751, 478, 666, 377, 629, 426, 893, 775, 927, 363, 620, 529, 693, 435, 214, 670, 624, 655, 554, 339, 856, 950, 163, 793, 436, 551, 398, 844, 528, 951, 553, 367, 917, 410, 177, 488, 182, 507, 614, 711, 457, 762, 382, 155, 726, 960, 262, 657, 776, 995],
[633, 459, 805, 491, 873, 621, 507, 225, 400, 830, 126, 996, 148, 133, 174, 812, 855, 159, 884, 252, 799, 163, 582, 531, 775, 406, 484, 262, 981, 595, 328, 645, 287, 462, 984, 902, 559, 158, 907, 387, 991, 761, 483, 641, 613, 861, 150, 578, 524, 543, 273, 829, 616, 970, 834, 748, 703, 548, 955, 377, 405, 880, 609, 441, 935, 652, 760, 468, 394, 542, 976, 809, 706, 570, 207, 831, 583, 420, 242, 628, 890, 527, 567, 913, 129, 292, 131, 637, 511, 397, 769, 987, 796, 423, 160, 533, 485, 998, 223, 638],
[863, 736, 243, 832, 623, 875, 436, 617, 604, 417, 337, 700, 286, 272, 891, 213, 479, 704, 239, 167, 766, 785, 983, 859, 253, 535, 659, 986, 214, 711, 515, 115, 616, 828, 982, 689, 777, 665, 770, 449, 222, 673, 908, 708, 618, 695, 148, 761, 967, 992, 816, 232, 370, 231, 978, 325, 345, 267, 683, 637, 485, 432, 529, 799, 523, 317, 154, 969, 570, 954, 734, 577, 431, 380, 934, 959, 932, 543, 640, 641, 439, 600, 296, 418, 629, 907, 562, 390, 584, 141, 985, 315, 327, 931, 262, 706, 916, 125, 511, 378],
[946, 263, 508, 570, 972, 487, 902, 614, 492, 151, 927, 432, 180, 239, 809, 777, 753, 350, 429, 283, 748, 355, 900, 665, 336, 813, 259, 545, 266, 825, 958, 331, 703, 826, 117, 201, 209, 982, 875, 218, 533, 877, 205, 112, 150, 924, 503, 975, 413, 575, 767, 210, 544, 416, 496, 721, 353, 583, 789, 854, 690, 671, 557, 998, 951, 928, 678, 294, 905, 333, 541, 990, 455, 178, 787, 461, 895, 821, 488, 841, 969, 563, 878, 261, 388, 368, 245, 911, 256, 475, 186, 694, 831, 156, 187, 538, 175, 661, 765, 955],
[388, 372, 235, 244, 284, 225, 406, 487, 954, 435, 612, 859, 396, 354, 688, 727, 402, 280, 240, 620, 242, 594, 560, 891, 188, 851, 644, 211, 571, 126, 900, 422, 563, 445, 811, 852, 592, 602, 651, 549, 646, 145, 143, 844, 368, 756, 308, 194, 500, 105, 414, 333, 817, 824, 467, 972, 771, 349, 458, 377, 970, 667, 522, 779, 880, 147, 829, 529, 398, 139, 140, 886, 581, 561, 711, 793, 732, 436, 640, 960, 365, 552, 948, 300, 652, 914, 663, 928, 499, 336, 570, 942, 287, 245, 513, 213, 352, 340, 618, 699],
[877, 744, 778, 597, 266, 749, 339, 320, 673, 395, 620, 966, 953, 588, 492, 960, 899, 370, 772, 141, 624, 493, 105, 231, 686, 236, 853, 871, 587, 102, 316, 736, 309, 738, 331, 838, 253, 273, 270, 739, 130, 851, 681, 707, 826, 641, 868, 817, 577, 149, 145, 269, 752, 992, 462, 197, 609, 423, 683, 259, 537, 359, 630, 502, 439, 670, 234, 613, 495, 453, 556, 592, 658, 225, 842, 525, 354, 349, 854, 175, 491, 173, 961, 811, 103, 267, 193, 902, 490, 503, 705, 524, 412, 793, 327, 830, 283, 308, 753, 751],
[425, 283, 792, 571, 945, 600, 850, 881, 165, 433, 222, 560, 867, 403, 790, 962, 677, 783, 342, 366, 849, 502, 996, 673, 225, 837, 282, 192, 695, 761, 942, 170, 714, 250, 484, 674, 518, 709, 507, 528, 634, 724, 647, 692, 989, 525, 175, 913, 145, 957, 882, 451, 585, 229, 906, 473, 109, 357, 270, 535, 877, 265, 610, 633, 759, 522, 253, 534, 774, 964, 301, 346, 147, 208, 605, 151, 319, 621, 689, 337, 572, 853, 355, 116, 218, 102, 126, 554, 465, 179, 111, 898, 936, 979, 928, 540, 632, 110, 919, 760],
[826, 264, 434, 706, 342, 643, 141, 332, 636, 344, 559, 797, 117, 843, 397, 236, 408, 238, 283, 514, 253, 523, 784, 512, 697, 148, 874, 780, 621, 265, 271, 582, 684, 573, 472, 262, 849, 846, 926, 623, 701, 900, 201, 634, 913, 641, 503, 593, 894, 930, 778, 622, 770, 346, 975, 493, 413, 714, 458, 235, 402, 186, 123, 949, 955, 881, 177, 424, 155, 941, 241, 428, 602, 992, 429, 749, 437, 777, 180, 305, 448, 557, 440, 501, 681, 304, 181, 850, 494, 292, 566, 338, 526, 538, 519, 277, 596, 279, 571, 793],
[395, 368, 300, 394, 698, 685, 592, 947, 203, 570, 269, 299, 614, 489, 594, 185, 126, 385, 997, 424, 538, 672, 561, 610, 143, 896, 864, 792, 979, 490, 953, 166, 255, 402, 930, 450, 238, 771, 377, 646, 149, 858, 933, 124, 393, 348, 929, 918, 863, 641, 993, 926, 634, 403, 607, 738, 898, 104, 887, 599, 495, 155, 925, 963, 916, 711, 506, 740, 182, 442, 478, 632, 328, 482, 215, 302, 883, 165, 787, 921, 507, 107, 709, 678, 957, 526, 315, 188, 298, 790, 293, 454, 834, 110, 551, 261, 878, 294, 700, 245],
[519, 706, 565, 825, 894, 883, 184, 748, 462, 551, 168, 457, 583, 688, 253, 977, 278, 715, 779, 850, 501, 616, 562, 989, 186, 922, 880, 598, 928, 505, 222, 843, 215, 601, 136, 437, 903, 694, 953, 426, 362, 368, 407, 130, 205, 438, 817, 842, 639, 645, 657, 245, 425, 134, 365, 609, 732, 897, 756, 731, 549, 512, 734, 352, 533, 255, 463, 871, 230, 644, 275, 846, 656, 767, 668, 349, 863, 140, 472, 659, 663, 311, 907, 934, 550, 493, 263, 260, 420, 494, 820, 314, 890, 624, 544, 523, 216, 410, 840, 174],
[270, 895, 437, 899, 138, 665, 874, 572, 878, 934, 157, 575, 783, 332, 770, 296, 135, 707, 670, 310, 689, 957, 210, 613, 323, 956, 601, 697, 283, 343, 261, 552, 379, 753, 822, 831, 429, 232, 274, 242, 280, 444, 705, 967, 819, 814, 644, 380, 717, 622, 443, 950, 945, 852, 623, 775, 290, 962, 404, 532, 693, 205, 103, 590, 439, 952, 872, 620, 505, 931, 745, 436, 971, 873, 524, 468, 786, 475, 172, 702, 772, 774, 536, 815, 510, 412, 905, 828, 643, 582, 610, 714, 126, 394, 514, 731, 639, 287, 879, 165],
[455, 811, 887, 747, 402, 711, 566, 463, 209, 708, 518, 755, 923, 603, 597, 498, 722, 403, 291, 538, 769, 101, 874, 608, 488, 219, 776, 203, 936, 814, 893, 851, 667, 112, 902, 624, 487, 508, 534, 672, 357, 482, 221, 192, 972, 353, 189, 715, 867, 196, 654, 731, 525, 612, 692, 926, 966, 110, 519, 782, 905, 213, 719, 842, 363, 677, 560, 130, 705, 146, 294, 701, 869, 789, 702, 185, 483, 648, 712, 153, 787, 649, 170, 334, 309, 360, 866, 447, 464, 710, 737, 596, 400, 709, 999, 707, 462, 425, 398, 473],
[225, 247, 227, 212, 856, 326, 214, 808, 164, 515, 322, 875, 104, 333, 938, 817, 258, 958, 643, 517, 338, 384, 179, 378, 683, 422, 927, 444, 389, 197, 920, 648, 577, 879, 831, 181, 915, 442, 823, 176, 852, 902, 888, 563, 372, 671, 616, 633, 473, 158, 532, 489, 269, 408, 423, 619, 451, 837, 900, 541, 991, 618, 481, 684, 537, 352, 692, 675, 932, 291, 925, 475, 913, 107, 440, 136, 208, 421, 667, 970, 331, 232, 199, 411, 918, 796, 556, 580, 502, 434, 791, 581, 354, 968, 674, 584, 694, 593, 117, 677],
[559, 930, 389, 708, 968, 255, 326, 836, 804, 894, 537, 124, 884, 858, 980, 256, 687, 435, 874, 704, 474, 485, 162, 457, 211, 442, 419, 333, 998, 443, 782, 700, 919, 909, 327, 828, 979, 505, 248, 205, 230, 830, 810, 344, 168, 601, 151, 996, 440, 511, 943, 555, 863, 220, 665, 184, 259, 719, 868, 573, 916, 210, 595, 622, 781, 336, 221, 535, 872, 759, 249, 228, 790, 140, 670, 638, 262, 733, 380, 322, 103, 438, 172, 101, 950, 450, 218, 363, 365, 859, 802, 814, 128, 773, 820, 643, 947, 845, 775, 369],
[725, 618, 345, 334, 315, 654, 989, 896, 292, 633, 875, 575, 738, 571, 920, 692, 376, 465, 129, 559, 202, 595, 260, 279, 214, 666, 272, 380, 926, 546, 842, 958, 241, 407, 318, 956, 549, 381, 765, 659, 373, 366, 852, 417, 148, 187, 331, 313, 126, 928, 625, 932, 234, 837, 382, 249, 556, 563, 862, 167, 561, 539, 321, 851, 518, 809, 829, 401, 984, 478, 394, 426, 104, 823, 469, 861, 312, 815, 255, 741, 901, 922, 415, 223, 342, 246, 419, 963, 486, 480, 466, 784, 495, 615, 369, 173, 678, 844, 198, 513],
[508, 612, 964, 142, 694, 463, 823, 914, 682, 559, 907, 609, 747, 727, 380, 975, 300, 377, 818, 734, 100, 725, 573, 465, 830, 744, 384, 903, 285, 797, 774, 494, 233, 571, 563, 764, 851, 521, 860, 128, 123, 517, 136, 296, 577, 435, 176, 379, 230, 834, 148, 366, 710, 268, 376, 390, 184, 304, 833, 738, 648, 286, 608, 590, 538, 634, 182, 466, 578, 276, 684, 655, 704, 915, 685, 790, 342, 659, 161, 280, 246, 275, 260, 650, 536, 462, 968, 385, 496, 382, 310, 315, 749, 961, 226, 611, 211, 730, 701, 430],
[811, 657, 752, 766, 419, 757, 727, 808, 732, 605, 285, 988, 467, 111, 497, 684, 755, 539, 127, 607, 136, 629, 778, 804, 949, 760, 853, 420, 721, 262, 411, 433, 356, 970, 944, 674, 118, 817, 210, 822, 889, 829, 138, 834, 297, 837, 900, 680, 596, 224, 984, 890, 216, 719, 619, 891, 267, 920, 547, 645, 902, 753, 580, 675, 864, 763, 391, 677, 743, 671, 909, 569, 946, 288, 990, 796, 597, 312, 334, 392, 426, 843, 435, 814, 878, 556, 815, 852, 182, 767, 291, 389, 740, 249, 940, 474, 828, 326, 244, 585],
[477, 600, 209, 422, 707, 413, 655, 914, 635, 530, 828, 841, 478, 425, 233, 834, 553, 998, 384, 232, 882, 957, 265, 803, 596, 253, 206, 711, 919, 412, 768, 681, 311, 154, 149, 592, 488, 430, 796, 393, 159, 776, 831, 189, 328, 522, 308, 446, 954, 359, 527, 994, 361, 780, 408, 414, 868, 409, 301, 670, 348, 246, 269, 296, 949, 540, 286, 812, 432, 765, 552, 121, 529, 666, 575, 762, 132, 677, 293, 877, 894, 111, 365, 261, 388, 499, 229, 405, 867, 485, 722, 599, 991, 400, 884, 176, 783, 833, 419, 988],
[633, 990, 737, 162, 363, 169, 317, 874, 392, 876, 725, 945, 979, 801, 263, 320, 125, 242, 609, 483, 543, 351, 230, 523, 531, 524, 418, 726, 582, 783, 429, 642, 964, 565, 601, 150, 286, 284, 975, 220, 906, 957, 882, 494, 585, 849, 821, 559, 602, 159, 978, 353, 676, 600, 232, 422, 285, 336, 477, 228, 156, 367, 667, 806, 388, 612, 733, 766, 816, 937, 165, 372, 237, 650, 447, 181, 265, 270, 419, 583, 973, 575, 611, 448, 748, 596, 280, 380, 756, 134, 891, 946, 948, 723, 144, 736, 639, 983, 985, 992],
[901, 683, 715, 394, 746, 784, 305, 476, 680, 692, 958, 289, 882, 175, 527, 838, 624, 269, 587, 415, 620, 849, 379, 703, 966, 607, 777, 826, 488, 102, 230, 479, 615, 934, 574, 503, 573, 402, 172, 978, 329, 785, 721, 569, 948, 982, 850, 853, 151, 937, 428, 180, 852, 264, 181, 858, 705, 711, 641, 706, 254, 697, 179, 187, 635, 399, 565, 737, 848, 242, 896, 972, 360, 404, 303, 800, 225, 976, 406, 551, 443, 383, 232, 844, 816, 285, 334, 146, 863, 970, 517, 486, 847, 147, 481, 182, 874, 886, 714, 218],
[418, 513, 151, 352, 682, 345, 693, 924, 952, 640, 394, 517, 631, 982, 469, 765, 948, 376, 278, 713, 949, 641, 375, 776, 630, 389, 554, 124, 812, 824, 694, 998, 915, 160, 676, 159, 444, 506, 983, 980, 666, 420, 317, 117, 604, 492, 885, 647, 906, 136, 440, 883, 709, 957, 925, 322, 748, 433, 135, 854, 153, 585, 866, 299, 996, 723, 270, 888, 651, 145, 167, 739, 841, 819, 843, 633, 644, 371, 696, 672, 659, 818, 285, 348, 778, 965, 846, 852, 512, 558, 732, 610, 712, 956, 650, 340, 577, 241, 763, 747],
[412, 981, 319, 166, 240, 420, 561, 993, 984, 541, 687, 577, 747, 498, 588, 965, 344, 318, 360, 760, 391, 144, 635, 245, 712, 529, 744, 148, 124, 117, 869, 387, 384, 396, 269, 372, 193, 718, 685, 851, 265, 646, 972, 650, 907, 434, 354, 111, 394, 895, 784, 587, 362, 449, 573, 679, 444, 949, 321, 503, 901, 717, 904, 826, 523, 831, 427, 229, 209, 569, 853, 242, 973, 621, 213, 558, 764, 812, 794, 190, 332, 593, 877, 827, 818, 618, 267, 534, 298, 682, 720, 105, 595, 918, 103, 214, 706, 620, 224, 609],
[299, 589, 411, 678, 723, 150, 277, 937, 873, 726, 507, 347, 289, 696, 224, 670, 243, 621, 575, 389, 614, 766, 836, 633, 775, 883, 355, 203, 767, 221, 671, 201, 774, 977, 191, 809, 279, 699, 462, 982, 469, 167, 993, 791, 354, 116, 627, 511, 913, 787, 346, 642, 901, 494, 690, 547, 997, 609, 816, 815, 658, 499, 113, 105, 981, 555, 776, 687, 380, 497, 554, 945, 546, 643, 477, 123, 543, 756, 515, 966, 283, 758, 584, 266, 230, 599, 327, 385, 276, 296, 866, 653, 949, 501, 529, 785, 157, 263, 960, 329],
[359, 117, 423, 657, 570, 932, 153, 465, 132, 533, 445, 957, 651, 807, 138, 164, 545, 303, 671, 770, 489, 139, 882, 949, 411, 960, 601, 590, 899, 328, 485, 950, 962, 507, 413, 889, 947, 921, 301, 228, 458, 729, 599, 534, 968, 480, 945, 669, 928, 446, 981, 999, 114, 187, 755, 308, 131, 870, 304, 717, 630, 167, 110, 307, 512, 595, 371, 133, 471, 196, 358, 382, 576, 268, 764, 522, 370, 472, 604, 632, 241, 641, 428, 116, 795, 718, 553, 456, 582, 121, 670, 725, 736, 230, 723, 357, 652, 242, 756, 667],
[155, 105, 168, 561, 149, 125, 721, 935, 551, 265, 376, 682, 920, 670, 218, 164, 472, 201, 589, 763, 618, 183, 634, 516, 390, 601, 675, 106, 996, 189, 115, 951, 137, 159, 148, 267, 259, 769, 839, 235, 541, 939, 401, 942, 312, 293, 688, 625, 653, 354, 171, 216, 397, 229, 454, 113, 975, 456, 305, 980, 557, 793, 902, 281, 367, 605, 664, 994, 834, 277, 416, 165, 289, 414, 505, 751, 724, 802, 970, 567, 217, 320, 554, 580, 373, 255, 334, 463, 319, 893, 992, 381, 978, 842, 535, 635, 871, 236, 449, 858],
[983, 764, 279, 431, 208, 598, 310, 821, 499, 758, 161, 648, 690, 767, 362, 652, 969, 658, 515, 370, 951, 623, 954, 736, 943, 786, 157, 184, 978, 761, 514, 870, 905, 944, 289, 339, 573, 720, 449, 885, 104, 996, 847, 507, 799, 876, 991, 286, 733, 583, 863, 493, 506, 242, 390, 638, 872, 897, 217, 791, 937, 622, 172, 360, 268, 760, 163, 252, 385, 352, 191, 192, 369, 982, 487, 308, 492, 953, 258, 886, 742, 299, 380, 817, 408, 488, 413, 827, 519, 640, 445, 894, 464, 922, 481, 394, 563, 864, 294, 402],
[544, 105, 838, 604, 428, 230, 938, 600, 490, 307, 693, 270, 945, 820, 533, 328, 422, 757, 864, 152, 549, 569, 296, 349, 524, 615, 999, 679, 442, 298, 485, 630, 746, 213, 898, 244, 207, 344, 289, 801, 464, 273, 556, 611, 642, 960, 546, 854, 721, 393, 160, 987, 147, 237, 958, 664, 314, 763, 817, 252, 424, 456, 294, 476, 933, 368, 193, 462, 518, 563, 725, 182, 181, 201, 121, 661, 894, 837, 924, 159, 108, 337, 673, 191, 216, 624, 553, 339, 936, 974, 488, 232, 623, 423, 378, 841, 793, 100, 124, 941],
[753, 684, 616, 620, 898, 713, 838, 144, 400, 357, 703, 685, 191, 726, 767, 816, 902, 491, 219, 242, 937, 148, 348, 326, 891, 894, 516, 836, 797, 850, 874, 642, 185, 585, 288, 657, 966, 571, 211, 246, 120, 473, 484, 999, 413, 530, 629, 521, 762, 173, 329, 887, 522, 155, 141, 184, 561, 397, 506, 100, 448, 327, 375, 672, 923, 425, 476, 562, 742, 259, 883, 748, 439, 142, 725, 913, 981, 853, 732, 356, 930, 749, 104, 147, 342, 350, 821, 793, 461, 268, 261, 755, 415, 782, 800, 555, 228, 232, 253, 856],
[819, 855, 927, 349, 790, 851, 178, 732, 430, 762, 740, 342, 953, 985, 339, 267, 730, 737, 305, 486, 792, 199, 314, 600, 744, 537, 593, 948, 161, 929, 890, 612, 110, 384, 351, 604, 785, 759, 640, 274, 636, 913, 134, 160, 482, 726, 308, 829, 810, 661, 627, 672, 203, 442, 944, 499, 324, 781, 982, 579, 115, 336, 286, 153, 616, 217, 128, 755, 718, 112, 963, 812, 895, 578, 999, 956, 443, 529, 479, 656, 703, 133, 920, 428, 618, 651, 801, 915, 679, 795, 150, 904, 776, 426, 159, 275, 520, 959, 870, 340],
[304, 614, 598, 920, 149, 463, 666, 765, 975, 359, 760, 685, 581, 717, 116, 526, 130, 568, 346, 429, 480, 518, 638, 141, 998, 153, 202, 392, 712, 857, 963, 328, 499, 246, 669, 852, 177, 981, 186, 197, 704, 931, 973, 528, 862, 315, 551, 502, 672, 173, 349, 333, 752, 816, 874, 658, 482, 182, 810, 266, 410, 979, 184, 841, 524, 474, 695, 965, 340, 883, 108, 902, 563, 262, 630, 307, 676, 925, 354, 389, 580, 693, 417, 732, 869, 802, 784, 501, 527, 536, 713, 285, 881, 433, 999, 406, 582, 634, 515, 161],
[577, 865, 224, 451, 895, 251, 146, 435, 444, 489, 411, 148, 459, 588, 666, 896, 557, 789, 584, 607, 590, 725, 973, 211, 638, 966, 363, 216, 315, 943, 231, 260, 442, 760, 939, 499, 375, 198, 493, 902, 699, 161, 914, 320, 874, 544, 708, 878, 338, 621, 520, 547, 850, 298, 188, 764, 135, 173, 841, 103, 119, 203, 181, 833, 353, 998, 538, 813, 219, 872, 339, 166, 840, 551, 815, 406, 340, 263, 535, 668, 831, 623, 898, 372, 439, 197, 399, 112, 153, 659, 515, 246, 190, 724, 529, 376, 889, 123, 494, 279],
[762, 710, 180, 853, 439, 667, 884, 129, 715, 174, 885, 437, 201, 499, 248, 148, 401, 589, 416, 638, 281, 596, 342, 666, 876, 935, 556, 229, 965, 580, 198, 844, 805, 213, 657, 922, 671, 984, 333, 931, 496, 218, 150, 444, 159, 836, 321, 419, 645, 586, 700, 238, 308, 684, 206, 643, 682, 860, 294, 956, 794, 567, 581, 792, 636, 977, 562, 171, 417, 699, 109, 293, 434, 364, 285, 341, 846, 423, 249, 678, 453, 999, 387, 128, 305, 691, 736, 261, 126, 195, 313, 787, 337, 277, 524, 631, 696, 228, 943, 289],
[443, 139, 464, 613, 780, 990, 377, 566, 564, 257, 972, 240, 839, 308, 778, 937, 721, 296, 987, 187, 649, 460, 128, 774, 301, 660, 639, 683, 247, 260, 427, 934, 963, 436, 110, 171, 691, 962, 287, 815, 498, 329, 280, 800, 704, 793, 410, 123, 158, 879, 729, 353, 892, 540, 394, 948, 659, 895, 521, 312, 702, 574, 118, 439, 717, 430, 825, 775, 866, 956, 289, 191, 407, 461, 632, 300, 228, 243, 106, 908, 840, 112, 637, 734, 980, 179, 293, 705, 911, 998, 777, 816, 508, 248, 143, 472, 197, 219, 387, 765],
[834, 620, 757, 497, 286, 449, 878, 727, 969, 888, 185, 550, 320, 240, 282, 371, 658, 667, 157, 379, 447, 267, 663, 528, 597, 145, 335, 213, 612, 319, 819, 820, 511, 411, 277, 124, 644, 170, 547, 748, 567, 103, 480, 780, 572, 774, 649, 401, 471, 982, 895, 462, 575, 537, 348, 603, 522, 198, 393, 283, 476, 828, 380, 120, 489, 488, 977, 614, 589, 635, 813, 438, 280, 509, 156, 265, 966, 944, 274, 712, 864, 608, 769, 871, 741, 419, 951, 826, 477, 962, 845, 210, 763, 687, 493, 690, 676, 397, 322, 859],
[226, 171, 840, 246, 295, 451, 365, 264, 554, 964, 501, 516, 876, 865, 214, 582, 249, 931, 358, 480, 952, 585, 992, 814, 828, 163, 725, 590, 841, 822, 135, 460, 726, 658, 897, 146, 825, 445, 138, 158, 141, 856, 234, 830, 255, 953, 199, 760, 812, 965, 950, 446, 120, 211, 450, 859, 206, 183, 981, 827, 461, 875, 657, 886, 884, 803, 644, 265, 148, 315, 923, 899, 940, 172, 155, 352, 283, 395, 325, 371, 980, 329, 719, 671, 289, 887, 536, 111, 263, 514, 933, 985, 441, 240, 435, 750, 640, 466, 360, 767],
[767, 820, 732, 131, 265, 704, 664, 130, 584, 872, 595, 905, 734, 474, 362, 487, 915, 355, 215, 564, 649, 436, 336, 706, 929, 833, 297, 914, 391, 960, 367, 670, 490, 430, 106, 337, 508, 774, 259, 492, 255, 736, 357, 951, 874, 838, 587, 726, 773, 875, 818, 794, 288, 338, 210, 926, 214, 240, 828, 822, 752, 463, 681, 958, 643, 651, 334, 746, 610, 695, 862, 279, 747, 702, 572, 364, 980, 233, 151, 882, 157, 437, 260, 197, 782, 278, 633, 127, 841, 865, 618, 160, 446, 476, 724, 895, 107, 431, 316, 217],
[828, 517, 128, 144, 964, 231, 137, 662, 664, 835, 714, 337, 830, 974, 556, 241, 752, 540, 689, 692, 737, 421, 943, 157, 423, 412, 323, 300, 532, 346, 179, 213, 786, 638, 387, 605, 630, 697, 612, 771, 406, 190, 397, 377, 990, 593, 881, 188, 709, 670, 132, 917, 702, 708, 194, 285, 682, 906, 451, 428, 127, 271, 982, 854, 507, 431, 712, 683, 847, 189, 685, 181, 225, 277, 999, 531, 153, 746, 978, 174, 844, 839, 845, 558, 242, 102, 720, 948, 922, 575, 341, 250, 305, 820, 680, 386, 564, 410, 897, 782],
[357, 709, 148, 762, 903, 988, 488, 989, 506, 238, 264, 931, 722, 518, 905, 660, 236, 827, 729, 766, 299, 231, 160, 854, 685, 874, 330, 805, 207, 815, 984, 468, 566, 837, 590, 771, 535, 575, 833, 430, 824, 519, 816, 835, 591, 801, 158, 448, 487, 228, 107, 108, 977, 512, 753, 151, 391, 725, 198, 981, 436, 141, 630, 459, 269, 793, 537, 485, 272, 951, 962, 674, 152, 769, 116, 536, 379, 819, 510, 102, 176, 690, 726, 342, 304, 551, 317, 851, 559, 868, 643, 800, 328, 908, 478, 234, 314, 495, 855, 743],
[795, 577, 698, 230, 373, 991, 321, 213, 832, 452, 901, 801, 977, 621, 125, 496, 866, 249, 860, 785, 120, 354, 355, 752, 239, 739, 396, 916, 168, 928, 491, 640, 258, 393, 404, 634, 149, 228, 513, 301, 759, 104, 412, 343, 857, 868, 768, 742, 210, 351, 121, 336, 925, 870, 798, 980, 694, 835, 408, 747, 495, 385, 433, 690, 130, 856, 111, 966, 701, 918, 996, 543, 388, 285, 237, 529, 812, 448, 682, 145, 148, 772, 834, 976, 661, 473, 843, 232, 779, 289, 192, 367, 256, 276, 695, 970, 512, 521, 692, 958],
[332, 535, 370, 667, 757, 501, 223, 184, 509, 270, 216, 975, 413, 461, 610, 375, 888, 688, 262, 487, 113, 492, 994, 577, 146, 463, 940, 690, 904, 963, 923, 232, 875, 438, 245, 520, 458, 118, 823, 235, 478, 341, 920, 766, 210, 756, 130, 657, 241, 414, 514, 479, 967, 537, 550, 961, 272, 728, 642, 647, 636, 924, 590, 984, 322, 430, 484, 927, 500, 157, 966, 933, 571, 976, 950, 194, 314, 760, 330, 265, 715, 859, 686, 806, 447, 764, 466, 681, 445, 389, 152, 829, 682, 134, 191, 869, 449, 488, 106, 567],
[571, 533, 102, 876, 863, 489, 289, 819, 178, 369, 379, 857, 976, 955, 297, 794, 106, 484, 979, 311, 736, 279, 691, 695, 991, 854, 413, 653, 446, 983, 891, 508, 218, 156, 847, 820, 562, 342, 725, 934, 731, 781, 360, 182, 920, 947, 541, 195, 747, 404, 442, 792, 486, 158, 838, 282, 620, 485, 217, 982, 665, 701, 660, 642, 149, 493, 760, 113, 415, 376, 612, 667, 633, 583, 703, 449, 398, 124, 685, 520, 868, 237, 534, 385, 777, 104, 986, 862, 809, 338, 516, 570, 814, 939, 588, 655, 371, 529, 129, 840],
[365, 221, 545, 950, 899, 423, 479, 886, 467, 869, 938, 906, 551, 501, 758, 305, 428, 303, 604, 339, 378, 642, 589, 877, 532, 617, 375, 318, 480, 833, 893, 863, 988, 821, 592, 351, 108, 457, 970, 446, 508, 322, 290, 945, 961, 488, 147, 959, 259, 271, 610, 687, 856, 852, 169, 320, 919, 426, 125, 538, 575, 393, 395, 660, 240, 954, 857, 510, 190, 186, 419, 849, 204, 593, 270, 228, 973, 477, 572, 136, 490, 667, 541, 129, 847, 297, 715, 671, 816, 371, 173, 248, 915, 792, 328, 300, 972, 968, 643, 898],
[966, 524, 255, 470, 652, 212, 738, 332, 234, 975, 519, 745, 722, 551, 461, 416, 763, 154, 729, 119, 501, 281, 351, 230, 241, 483, 905, 455, 368, 915, 284, 681, 768, 453, 884, 454, 432, 204, 937, 156, 420, 322, 922, 790, 404, 938, 364, 288, 610, 339, 507, 508, 911, 805, 901, 419, 974, 983, 450, 443, 463, 325, 414, 437, 181, 673, 753, 500, 716, 927, 571, 390, 231, 720, 445, 474, 712, 529, 456, 906, 870, 647, 534, 680, 538, 116, 666, 415, 174, 110, 907, 546, 976, 719, 473, 471, 877, 646, 596, 817],
[308, 987, 884, 100, 123, 199, 988, 890, 784, 910, 234, 420, 319, 559, 595, 675, 274, 561, 144, 415, 262, 570, 944, 446, 979, 808, 235, 215, 518, 829, 281, 940, 146, 143, 611, 820, 295, 208, 449, 889, 536, 976, 876, 411, 523, 509, 883, 445, 469, 362, 895, 296, 871, 289, 545, 377, 381, 906, 574, 932, 643, 214, 552, 573, 931, 576, 337, 382, 463, 477, 416, 657, 266, 246, 637, 242, 737, 404, 360, 427, 819, 555, 828, 526, 759, 609, 835, 501, 821, 959, 805, 717, 488, 866, 765, 140, 635, 606, 188, 198],
[855, 210, 259, 912, 236, 834, 261, 334, 663, 810, 389, 266, 883, 807, 643, 638, 728, 331, 505, 364, 457, 971, 653, 846, 824, 784, 837, 118, 242, 792, 228, 341, 160, 317, 555, 472, 608, 667, 594, 715, 418, 790, 838, 603, 982, 107, 689, 557, 808, 565, 725, 440, 573, 972, 679, 772, 830, 733, 272, 751, 193, 524, 650, 825, 162, 887, 577, 540, 244, 515, 661, 935, 456, 471, 116, 426, 683, 621, 943, 687, 811, 955, 724, 206, 178, 292, 528, 149, 302, 481, 517, 485, 278, 174, 404, 226, 347, 247, 355, 866],
[100, 224, 357, 658, 994, 334, 346, 542, 684, 319, 621, 725, 118, 216, 674, 851, 314, 967, 936, 441, 786, 677, 201, 636, 448, 561, 932, 117, 131, 962, 623, 202, 766, 229, 942, 722, 141, 381, 402, 119, 584, 738, 121, 982, 550, 717, 721, 639, 241, 963, 902, 850, 333, 400, 783, 116, 226, 383, 126, 256, 777, 580, 841, 885, 492, 209, 989, 199, 210, 861, 776, 683, 149, 503, 933, 362, 152, 750, 284, 566, 966, 945, 476, 287, 915, 301, 931, 360, 312, 269, 651, 325, 246, 436, 975, 887, 320, 853, 842, 463],
[310, 745, 797, 237, 434, 822, 974, 835, 861, 331, 129, 779, 767, 197, 605, 342, 276, 650, 984, 956, 427, 183, 393, 571, 521, 330, 449, 528, 267, 676, 301, 289, 802, 350, 262, 710, 381, 273, 916, 796, 227, 231, 814, 211, 920, 978, 810, 816, 925, 524, 482, 641, 728, 927, 813, 470, 811, 917, 843, 976, 380, 591, 558, 465, 785, 260, 581, 640, 828, 909, 135, 662, 732, 435, 287, 698, 106, 193, 550, 831, 933, 683, 880, 726, 600, 531, 361, 474, 278, 941, 652, 224, 433, 192, 996, 971, 242, 511, 887, 383],
[378, 604, 196, 696, 240, 250, 284, 953, 911, 968, 244, 856, 297, 392, 680, 785, 879, 140, 322, 796, 431, 576, 265, 381, 992, 472, 422, 510, 843, 857, 728, 423, 130, 989, 981, 975, 207, 840, 272, 443, 608, 755, 203, 356, 339, 797, 109, 436, 454, 376, 168, 152, 444, 720, 906, 293, 205, 225, 867, 917, 249, 897, 836, 128, 652, 504, 489, 236, 386, 161, 324, 996, 690, 709, 941, 425, 569, 708, 456, 714, 213, 965, 126, 202, 187, 630, 789, 760, 602, 631, 973, 531, 596, 199, 418, 976, 598, 739, 691, 136],
[268, 900, 713, 745, 754, 456, 657, 499, 145, 924, 420, 205, 289, 751, 760, 669, 353, 191, 548, 464, 560, 849, 860, 992, 913, 494, 475, 616, 683, 489, 431, 617, 978, 384, 156, 192, 639, 859, 680, 998, 163, 383, 853, 883, 890, 746, 598, 993, 960, 873, 906, 641, 521, 932, 635, 457, 615, 284, 261, 425, 594, 937, 178, 206, 588, 969, 954, 518, 445, 500, 896, 144, 314, 971, 986, 804, 628, 607, 171, 211, 781, 381, 655, 870, 892, 474, 619, 302, 347, 962, 149, 771, 938, 463, 482, 250, 786, 812, 301, 490],
[724, 764, 489, 955, 457, 349, 909, 639, 883, 847, 412, 891, 341, 289, 337, 586, 823, 869, 786, 218, 550, 498, 385, 370, 281, 536, 810, 375, 963, 456, 221, 933, 913, 672, 660, 392, 885, 568, 708, 122, 163, 323, 767, 698, 992, 710, 818, 254, 553, 957, 592, 732, 759, 682, 446, 716, 127, 437, 967, 467, 918, 593, 114, 862, 927, 641, 302, 895, 235, 718, 908, 804, 554, 696, 855, 613, 280, 305, 863, 301, 485, 523, 797, 495, 283, 304, 953, 316, 801, 938, 822, 578, 609, 871, 754, 317, 579, 135, 447, 671],
[388, 489, 552, 216, 294, 856, 437, 201, 547, 353, 336, 119, 860, 961, 333, 591, 731, 917, 762, 986, 884, 723, 978, 164, 260, 130, 661, 436, 440, 557, 320, 715, 519, 765, 251, 686, 612, 101, 617, 291, 199, 836, 773, 188, 256, 387, 108, 146, 820, 537, 950, 835, 613, 782, 502, 995, 135, 660, 745, 876, 392, 749, 334, 506, 788, 933, 416, 461, 561, 866, 937, 586, 712, 574, 795, 844, 672, 283, 611, 585, 405, 455, 287, 310, 919, 733, 648, 713, 434, 989, 551, 579, 647, 430, 915, 107, 553, 998, 882, 182],
[306, 925, 964, 309, 142, 324, 596, 136, 861, 759, 437, 690, 348, 788, 882, 292, 395, 721, 474, 366, 756, 827, 332, 175, 417, 695, 713, 237, 411, 754, 815, 271, 505, 927, 192, 913, 247, 284, 890, 116, 326, 535, 853, 765, 707, 539, 526, 562, 447, 488, 954, 174, 212, 855, 389, 347, 733, 992, 149, 294, 813, 597, 218, 835, 633, 814, 172, 949, 752, 579, 838, 550, 616, 435, 127, 851, 672, 446, 424, 593, 893, 457, 123, 510, 615, 462, 585, 884, 415, 966, 207, 961, 789, 905, 849, 267, 935, 624, 864, 910],
[983, 408, 943, 650, 805, 150, 623, 129, 371, 826, 250, 793, 621, 833, 429, 499, 676, 813, 765, 421, 733, 353, 568, 315, 420, 418, 467, 930, 955, 432, 980, 825, 194, 442, 373, 379, 967, 391, 767, 209, 144, 608, 737, 226, 868, 414, 931, 823, 147, 502, 854, 734, 754, 866, 688, 331, 428, 104, 666, 762, 575, 661, 845, 786, 287, 126, 350, 674, 136, 939, 578, 230, 696, 551, 463, 673, 396, 233, 346, 890, 121, 261, 602, 633, 239, 830, 175, 626, 599, 532, 266, 161, 778, 565, 718, 791, 769, 662, 385, 311],
[694, 987, 211, 319, 828, 913, 880, 647, 656, 216, 650, 315, 847, 757, 507, 651, 417, 231, 851, 392, 581, 557, 918, 453, 208, 568, 662, 403, 117, 133, 605, 848, 834, 164, 531, 784, 621, 533, 866, 932, 100, 726, 814, 810, 439, 914, 143, 695, 440, 119, 860, 282, 703, 198, 476, 802, 163, 644, 504, 799, 678, 330, 487, 735, 902, 985, 910, 710, 295, 393, 909, 724, 129, 485, 599, 977, 535, 915, 956, 946, 524, 986, 593, 430, 280, 566, 877, 438, 579, 290, 643, 253, 381, 827, 336, 609, 585, 754, 444, 241],
[119, 421, 379, 341, 699, 126, 906, 337, 600, 661, 325, 485, 200, 798, 981, 323, 713, 164, 822, 563, 547, 684, 759, 231, 775, 689, 697, 364, 135, 147, 799, 867, 647, 877, 170, 821, 614, 861, 539, 956, 318, 764, 866, 580, 851, 676, 542, 416, 905, 440, 989, 432, 168, 934, 929, 908, 890, 966, 292, 131, 481, 225, 185, 307, 441, 674, 350, 639, 417, 986, 142, 239, 106, 434, 716, 891, 536, 835, 843, 454, 506, 882, 755, 726, 368, 172, 474, 784, 187, 936, 719, 765, 107, 112, 863, 516, 398, 758, 152, 257],
[135, 727, 751, 998, 996, 457, 434, 362, 650, 354, 586, 360, 810, 318, 337, 172, 858, 651, 907, 764, 961, 761, 373, 499, 131, 982, 530, 522, 582, 537, 353, 206, 111, 980, 464, 967, 966, 736, 784, 923, 425, 645, 879, 365, 594, 495, 431, 697, 670, 740, 683, 546, 408, 973, 524, 733, 886, 689, 245, 593, 212, 208, 279, 717, 412, 954, 241, 795, 570, 845, 442, 231, 159, 323, 227, 771, 756, 357, 800, 146, 126, 539, 914, 681, 693, 626, 896, 205, 710, 791, 407, 311, 835, 680, 184, 838, 368, 108, 801, 314],
[399, 974, 427, 106, 920, 620, 290, 467, 726, 236, 204, 994, 823, 975, 411, 264, 611, 465, 701, 450, 564, 944, 496, 978, 868, 453, 124, 345, 228, 385, 276, 365, 122, 492, 302, 997, 840, 919, 892, 805, 721, 740, 816, 505, 710, 617, 732, 630, 143, 422, 983, 863, 193, 423, 502, 991, 817, 379, 367, 614, 768, 855, 751, 250, 924, 642, 918, 601, 112, 555, 382, 700, 815, 368, 178, 752, 989, 515, 197, 861, 764, 210, 301, 381, 872, 347, 867, 969, 853, 573, 284, 318, 932, 899, 589, 931, 490, 887, 330, 574],
[356, 630, 127, 484, 604, 119, 345, 807, 184, 814, 719, 257, 351, 465, 242, 748, 560, 358, 717, 597, 775, 907, 446, 696, 115, 403, 812, 235, 688, 146, 607, 623, 984, 177, 198, 658, 765, 296, 419, 231, 913, 728, 254, 562, 347, 439, 387, 734, 868, 298, 436, 584, 666, 519, 339, 350, 686, 754, 313, 320, 773, 461, 816, 583, 672, 895, 702, 892, 531, 897, 914, 277, 151, 911, 481, 598, 374, 631, 589, 221, 401, 262, 613, 145, 926, 731, 136, 988, 476, 348, 795, 995, 122, 961, 271, 996, 219, 951, 705, 904],
[991, 422, 712, 388, 967, 473, 464, 376, 100, 508, 631, 520, 581, 752, 155, 330, 661, 722, 645, 381, 460, 729, 873, 803, 513, 316, 433, 579, 207, 875, 353, 204, 402, 762, 380, 135, 501, 899, 852, 772, 128, 455, 408, 804, 697, 799, 289, 628, 977, 972, 690, 110, 179, 903, 719, 413, 246, 773, 495, 511, 401, 621, 739, 808, 623, 615, 860, 417, 789, 368, 409, 586, 441, 561, 504, 668, 533, 705, 837, 412, 226, 287, 702, 149, 219, 673, 106, 696, 139, 536, 646, 395, 866, 863, 902, 451, 382, 555, 218, 527],
[437, 134, 999, 744, 708, 933, 589, 459, 727, 273, 238, 816, 607, 423, 935, 906, 618, 342, 875, 907, 798, 903, 414, 552, 978, 282, 475, 821, 200, 189, 762, 651, 255, 735, 962, 836, 984, 510, 174, 622, 363, 611, 792, 787, 615, 676, 343, 826, 276, 911, 874, 261, 670, 583, 390, 249, 539, 346, 499, 320, 759, 297, 193, 714, 114, 805, 283, 807, 667, 530, 831, 910, 135, 272, 941, 139, 600, 345, 900, 761, 392, 304, 225, 231, 168, 920, 881, 922, 660, 996, 502, 608, 118, 486, 672, 183, 155, 830, 370, 209],
[928, 617, 956, 912, 209, 509, 299, 470, 239, 235, 938, 725, 378, 636, 673, 839, 190, 539, 790, 955, 577, 495, 764, 706, 415, 134, 436, 511, 804, 292, 340, 813, 937, 975, 283, 409, 963, 598, 196, 700, 986, 433, 575, 988, 987, 517, 284, 585, 982, 557, 172, 619, 960, 906, 411, 178, 727, 608, 738, 354, 510, 754, 206, 153, 298, 723, 314, 739, 117, 269, 379, 850, 163, 430, 824, 866, 974, 545, 753, 348, 207, 653, 550, 132, 792, 542, 901, 976, 720, 942, 687, 488, 384, 195, 674, 862, 848, 538, 499, 342],
[938, 831, 451, 493, 881, 184, 309, 749, 604, 784, 728, 661, 162, 678, 916, 652, 460, 663, 214, 900, 830, 247, 454, 143, 260, 589, 204, 487, 714, 629, 687, 164, 393, 274, 394, 310, 276, 769, 836, 250, 411, 429, 602, 958, 548, 873, 738, 282, 452, 347, 369, 218, 300, 733, 264, 943, 963, 519, 359, 291, 124, 514, 308, 766, 528, 206, 362, 926, 595, 470, 456, 116, 654, 561, 350, 495, 982, 775, 480, 994, 918, 457, 423, 516, 907, 623, 697, 858, 721, 647, 620, 748, 755, 781, 571, 952, 895, 142, 462, 421],
[644, 871, 341, 495, 348, 562, 565, 170, 255, 359, 835, 927, 857, 367, 673, 758, 523, 335, 568, 282, 851, 914, 517, 326, 490, 690, 291, 968, 793, 766, 953, 144, 177, 229, 576, 704, 455, 174, 398, 760, 574, 330, 312, 803, 456, 575, 650, 585, 319, 559, 952, 579, 571, 783, 555, 570, 910, 388, 417, 345, 249, 775, 493, 259, 544, 868, 810, 178, 734, 913, 842, 627, 487, 877, 505, 165, 664, 902, 106, 540, 356, 320, 524, 261, 159, 230, 408, 185, 582, 750, 334, 189, 160, 923, 167, 786, 558, 557, 504, 688],
[631, 890, 310, 540, 892, 550, 185, 747, 200, 878, 731, 261, 680, 210, 941, 667, 703, 874, 952, 163, 390, 343, 383, 943, 490, 903, 323, 399, 392, 902, 694, 613, 426, 917, 866, 106, 630, 561, 904, 853, 169, 827, 223, 368, 229, 296, 602, 598, 225, 788, 120, 962, 260, 656, 555, 305, 340, 638, 774, 999, 735, 257, 856, 739, 218, 129, 492, 485, 650, 387, 303, 586, 309, 119, 450, 220, 990, 187, 744, 152, 607, 812, 467, 868, 649, 597, 104, 599, 183, 275, 719, 204, 965, 280, 206, 192, 108, 117, 198, 331],
[790, 385, 526, 968, 280, 763, 813, 120, 893, 745, 636, 780, 353, 876, 619, 264, 803, 378, 590, 669, 259, 518, 804, 814, 134, 213, 450, 727, 493, 212, 252, 366, 460, 850, 793, 954, 809, 386, 209, 884, 138, 217, 132, 875, 239, 589, 877, 829, 534, 848, 434, 706, 562, 218, 942, 698, 324, 182, 774, 314, 743, 203, 419, 807, 869, 268, 432, 403, 187, 457, 594, 464, 831, 694, 267, 705, 468, 412, 970, 179, 564, 292, 969, 143, 379, 535, 963, 825, 949, 861, 759, 555, 628, 916, 121, 234, 752, 400, 936, 623]]
\$\endgroup\$
1
\$\begingroup\$

Scanning a direction is suboptimal. Each row requires \$O(mn)\$ multiplications; the optimal solution takes \$O(m)\$ multiplications and \$O(m - n)\$ divisions:

    setup: make a window of first N numbers
    lead_in: P is product of numbers in the window
    loop: shift window right
          if it still fits the row,
              divide the product by a number which left the window
              multiply the product by a number which entered the window

A special attention must be paid to zeroes. You don't need to compute the product as long as zero is in the window; just shift the window all the way past it.


DRY. productOrtho shall only deal with a single direction. Let the caller call it, transpose, and call again.

As a side note, I don't think transposing is worth the effort. A direction parameter to a (refactored) productOrtho looks like a good alternative.


All of the above applies to diagonals.

\$\endgroup\$
  • \$\begingroup\$ This is an mxm grid, so I think it needs O(m^2) multiplications instead of O(m^2n). \$\endgroup\$ – miracle173 Nov 4 '16 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.