graph.h

Go to the documentation of this file.

#define NUM_VERTICES 1000

unsigned offset[NUM_VERTICES+1]={
0, 3, 9, 16, 21, 24, 29, 35, 37, 46, 47, 49, 56, 56, 65, 68, 74, 74, 80, 82, 88, 89, 97, 104, 113, 115, 115, 117, 120, 127, 132, 141, 143, 145, 153, 162, 169, 172, 178, 179, 181, 190, 193, 194, 203, 207, 214, 222, 226, 231, 
231, 234, 240, 241, 241, 247, 250, 252, 252, 258, 259, 264, 269, 273, 280, 286, 291, 297, 306, 309, 316, 320, 325, 327, 332, 336, 343, 347, 351, 354, 354, 361, 369, 375, 383, 391, 395, 398, 399, 403, 412, 414, 414, 420, 428, 437, 439, 445, 451, 455, 
464, 469, 469, 473, 481, 488, 489, 496, 498, 505, 507, 509, 515, 516, 516, 522, 523, 528, 537, 541, 550, 550, 559, 560, 567, 574, 575, 576, 581, 590, 597, 604, 610, 617, 620, 626, 631, 637, 640, 649, 653, 661, 662, 664, 673, 676, 685, 685, 693, 701, 
706, 706, 715, 721, 724, 732, 737, 743, 744, 745, 750, 759, 767, 771, 779, 780, 780, 783, 783, 787, 791, 795, 799, 806, 812, 815, 816, 823, 828, 837, 843, 845, 846, 853, 861, 866, 873, 877, 878, 886, 891, 900, 907, 912, 915, 923, 931, 934, 935, 943, 
952, 958, 962, 965, 968, 971, 979, 985, 985, 989, 997, 1005, 1013, 1022, 1029, 1036, 1042, 1046, 1049, 1049, 1052, 1052, 1061, 1063, 1068, 1072, 1072, 1077, 1086, 1090, 1096, 1105, 1107, 1109, 1113, 1120, 1127, 1132, 1136, 1144, 1145, 1147, 1155, 1164, 1167, 1173, 1181, 1181, 1183, 1184, 
1184, 1189, 1190, 1191, 1191, 1199, 1204, 1204, 1210, 1214, 1220, 1222, 1227, 1235, 1241, 1243, 1251, 1255, 1262, 1264, 1268, 1268, 1274, 1276, 1285, 1294, 1294, 1302, 1303, 1306, 1307, 1308, 1308, 1311, 1315, 1315, 1318, 1327, 1328, 1337, 1343, 1352, 1355, 1358, 1366, 1366, 1371, 1377, 1383, 1387, 
1387, 1387, 1391, 1397, 1399, 1405, 1412, 1417, 1423, 1432, 1440, 1447, 1449, 1457, 1459, 1468, 1477, 1483, 1483, 1485, 1492, 1498, 1499, 1502, 1504, 1505, 1510, 1519, 1528, 1529, 1533, 1542, 1543, 1543, 1550, 1555, 1563, 1570, 1570, 1574, 1582, 1582, 1586, 1588, 1597, 1603, 1604, 1604, 1608, 1610, 
1612, 1614, 1614, 1619, 1624, 1626, 1635, 1635, 1637, 1645, 1648, 1656, 1656, 1660, 1660, 1669, 1670, 1679, 1685, 1687, 1692, 1696, 1700, 1709, 1718, 1721, 1727, 1727, 1732, 1732, 1734, 1743, 1747, 1750, 1755, 1756, 1763, 1767, 1770, 1771, 1775, 1781, 1790, 1794, 1796, 1798, 1804, 1808, 1809, 1811, 
1819, 1827, 1836, 1838, 1846, 1854, 1862, 1868, 1876, 1879, 1887, 1890, 1893, 1896, 1904, 1904, 1908, 1915, 1921, 1929, 1938, 1938, 1944, 1952, 1959, 1968, 1968, 1971, 1974, 1977, 1984, 1987, 1989, 1995, 2000, 2002, 2008, 2013, 2021, 2028, 2037, 2043, 2043, 2047, 2048, 2048, 2052, 2060, 2067, 2067, 
2075, 2081, 2083, 2087, 2094, 2103, 2106, 2115, 2117, 2125, 2128, 2128, 2129, 2136, 2144, 2153, 2154, 2159, 2163, 2172, 2174, 2179, 2186, 2190, 2199, 2208, 2212, 2217, 2226, 2229, 2234, 2241, 2241, 2249, 2250, 2259, 2268, 2275, 2283, 2285, 2290, 2293, 2297, 2306, 2306, 2308, 2308, 2309, 2318, 2324, 
2326, 2327, 2329, 2329, 2336, 2339, 2340, 2341, 2350, 2350, 2355, 2361, 2368, 2375, 2379, 2379, 2385, 2389, 2396, 2400, 2408, 2413, 2421, 2423, 2429, 2429, 2435, 2441, 2445, 2451, 2453, 2461, 2470, 2476, 2476, 2483, 2483, 2484, 2484, 2485, 2488, 2495, 2502, 2504, 2510, 2514, 2519, 2521, 2521, 2523, 
2532, 2532, 2541, 2550, 2554, 2559, 2560, 2560, 2563, 2570, 2578, 2586, 2592, 2592, 2596, 2602, 2609, 2615, 2615, 2624, 2631, 2636, 2645, 2652, 2660, 2665, 2668, 2671, 2679, 2682, 2689, 2698, 2701, 2708, 2716, 2723, 2727, 2728, 2737, 2737, 2746, 2754, 2762, 2767, 2775, 2779, 2782, 2789, 2790, 2793, 
2801, 2801, 2810, 2817, 2826, 2835, 2838, 2840, 2844, 2847, 2854, 2855, 2857, 2859, 2859, 2861, 2862, 2869, 2874, 2875, 2882, 2886, 2887, 2894, 2895, 2896, 2897, 2904, 2904, 2908, 2908, 2916, 2921, 2922, 2928, 2934, 2936, 2937, 2946, 2952, 2956, 2964, 2964, 2972, 2973, 2973, 2975, 2977, 2986, 2993, 
2998, 3004, 3008, 3014, 3017, 3024, 3033, 3040, 3044, 3053, 3054, 3061, 3061, 3067, 3067, 3075, 3080, 3083, 3092, 3096, 3097, 3102, 3106, 3107, 3112, 3117, 3121, 3130, 3138, 3141, 3149, 3154, 3156, 3158, 3160, 3167, 3167, 3170, 3174, 3180, 3183, 3189, 3192, 3195, 3199, 3203, 3206, 3215, 3222, 3224, 
3229, 3237, 3246, 3246, 3248, 3252, 3259, 3265, 3270, 3277, 3278, 3281, 3284, 3287, 3295, 3300, 3301, 3301, 3309, 3316, 3322, 3325, 3330, 3330, 3338, 3338, 3342, 3343, 3344, 3347, 3352, 3361, 3364, 3368, 3369, 3374, 3374, 3382, 3385, 3390, 3396, 3401, 3410, 3419, 3419, 3426, 3432, 3435, 3442, 3448, 
3449, 3454, 3454, 3460, 3465, 3465, 3473, 3474, 3476, 3478, 3484, 3493, 3494, 3494, 3498, 3500, 3507, 3511, 3511, 3514, 3516, 3524, 3524, 3527, 3534, 3534, 3534, 3537, 3541, 3550, 3552, 3559, 3563, 3565, 3570, 3572, 3576, 3580, 3583, 3591, 3597, 3597, 3605, 3614, 3616, 3618, 3621, 3622, 3630, 3633, 
3637, 3639, 3641, 3645, 3650, 3651, 3658, 3663, 3670, 3671, 3677, 3686, 3694, 3695, 3698, 3701, 3704, 3711, 3720, 3728, 3734, 3741, 3741, 3745, 3753, 3757, 3765, 3766, 3772, 3780, 3785, 3787, 3788, 3797, 3806, 3812, 3812, 3818, 3822, 3831, 3840, 3840, 3848, 3857, 3860, 3861, 3865, 3873, 3882, 3888, 
3895, 3902, 3905, 3912, 3913, 3915, 3917, 3918, 3923, 3923, 3932, 3932, 3936, 3936, 3937, 3940, 3947, 3951, 3952, 3953, 3956, 3956, 3959, 3961, 3962, 3969, 3974, 3980, 3985, 3989, 3991, 3993, 3994, 4001, 4003, 4007, 4008, 4014, 4019, 4026, 4034, 4039, 4048, 4050, 4057, 4060, 4066, 4070, 4077, 4086, 
4093, 4095, 4097, 4098, 4104, 4107, 4107, 4109, 4110, 4115, 4121, 4126, 4126, 4126, 4129, 4133, 4139, 4145, 4145, 4147, 4152, 4160, 4169, 4174, 4174, 4180, 4180, 4188, 4191, 4198, 4206, 4208, 4209, 4209, 4214, 4222, 4227, 4232, 4232, 4239, 4242, 4250, 4252, 4255, 4255, 4262, 4269, 4276, 4282, 4291, 
4292, 4293, 4302, 4302, 4310, 4319, 4327, 4335, 4335, 4338, 4345, 4345, 4351, 4360, 4362, 4363, 4370, 4377, 4386, 4393, 4399, 4401, 4408, 4409, 4414, 4422, 4430, 4434, 4439, 4445, 4450, 4456, 4464, 4468, 4476, 4484, 4487, 4495, 4502, 4507, 4509, 4513, 4518, 4518, 4523, 4530, 4533, 4535, 4542, 4544, 4545};

unsigned edges[4545]={
0, 236, 756, 885, 498, 695, 45, 509, 890, 410, 29, 52, 427, 758, 87, 875, 368, 1, 980, 661, 264, 959, 65, 471, 96, 549, 364, 980, 244, 429, 514, 643, 350, 344, 51, 234, 650, 791, 751, 166, 479, 992, 601, 113, 550, 865, 880, 683, 992, 701, 
621, 772, 273, 265, 297, 55, 358, 358, 898, 910, 103, 364, 577, 453, 437, 995, 20, 96, 274, 857, 108, 356, 19, 978, 718, 998, 295, 691, 466, 997, 204, 300, 365, 33, 998, 889, 711, 480, 998, 23, 588, 172, 284, 911, 714, 942, 789, 148, 256, 97, 
122, 588, 121, 102, 606, 24, 147, 507, 742, 60, 162, 2, 869, 797, 427, 851, 799, 141, 282, 130, 138, 392, 978, 358, 771, 52, 296, 662, 446, 611, 902, 659, 394, 680, 432, 309, 544, 11, 512, 399, 330, 884, 618, 458, 972, 648, 111, 971, 556, 407, 
82, 660, 568, 610, 933, 163, 763, 77, 624, 348, 959, 184, 654, 7, 954, 437, 312, 225, 345, 505, 150, 467, 397, 595, 26, 309, 791, 230, 274, 257, 348, 606, 816, 751, 753, 436, 564, 707, 822, 113, 405, 849, 250, 124, 761, 556, 258, 772, 738, 585, 
800, 228, 181, 999, 29, 322, 904, 74, 727, 909, 787, 980, 777, 338, 500, 355, 509, 318, 303, 680, 938, 128, 740, 660, 822, 606, 951, 523, 426, 523, 317, 398, 375, 195, 579, 314, 212, 567, 175, 994, 620, 975, 539, 69, 570, 667, 637, 839, 253, 0, 
831, 728, 393, 394, 207, 927, 154, 262, 575, 388, 25, 820, 362, 88, 813, 38, 499, 693, 360, 140, 693, 813, 215, 635, 505, 716, 119, 266, 971, 988, 751, 842, 612, 604, 289, 24, 174, 904, 560, 180, 929, 823, 433, 646, 816, 30, 529, 614, 554, 448, 
107, 152, 250, 994, 374, 553, 678, 912, 871, 877, 487, 394, 908, 892, 501, 947, 699, 897, 552, 959, 542, 904, 470, 835, 936, 201, 792, 409, 221, 929, 466, 386, 51, 556, 38, 650, 794, 922, 601, 378, 796, 318, 192, 600, 372, 423, 530, 967, 912, 268, 
581, 110, 902, 898, 61, 625, 24, 222, 568, 825, 255, 753, 347, 884, 545, 142, 187, 469, 754, 244, 298, 634, 596, 940, 335, 31, 71, 858, 52, 366, 182, 699, 974, 19, 22, 547, 191, 728, 239, 444, 131, 686, 745, 5, 92, 742, 373, 8, 686, 786, 
904, 553, 418, 391, 497, 703, 331, 455, 68, 917, 738, 880, 518, 54, 842, 999, 192, 226, 899, 873, 327, 746, 23, 423, 617, 829, 382, 327, 143, 17, 465, 122, 475, 264, 88, 162, 849, 176, 765, 520, 173, 936, 509, 742, 360, 35, 162, 937, 746, 231, 
169, 588, 14, 618, 564, 205, 864, 521, 143, 968, 287, 945, 851, 37, 139, 857, 525, 723, 133, 389, 852, 289, 545, 940, 140, 144, 436, 652, 917, 906, 461, 850, 610, 593, 157, 475, 707, 687, 294, 138, 162, 561, 597, 800, 645, 347, 7, 660, 424, 578, 
349, 520, 976, 707, 407, 175, 584, 846, 370, 216, 883, 90, 553, 219, 310, 479, 276, 950, 499, 870, 995, 351, 397, 962, 297, 502, 46, 835, 169, 922, 570, 494, 697, 352, 690, 597, 265, 579, 184, 103, 610, 951, 845, 320, 286, 539, 516, 959, 948, 137, 
764, 634, 655, 55, 272, 522, 827, 204, 47, 614, 296, 418, 762, 504, 362, 133, 249, 665, 902, 775, 996, 668, 964, 241, 987, 6, 364, 393, 812, 81, 803, 814, 424, 203, 778, 445, 851, 626, 595, 433, 255, 227, 427, 843, 816, 439, 798, 719, 542, 957, 
773, 611, 469, 325, 599, 454, 356, 273, 931, 749, 551, 692, 674, 220, 28, 288, 612, 718, 56, 225, 297, 20, 999, 547, 579, 280, 173, 324, 374, 111, 88, 937, 79, 87, 226, 282, 45, 191, 8, 292, 715, 175, 420, 762, 912, 203, 834, 410, 541, 443, 
52, 625, 988, 104, 686, 878, 281, 870, 217, 983, 193, 308, 112, 486, 229, 964, 748, 386, 653, 890, 792, 485, 276, 15, 267, 200, 535, 219, 337, 969, 765, 269, 329, 840, 86, 194, 980, 852, 35, 70, 883, 432, 417, 846, 5, 829, 373, 81, 298, 373, 
134, 297, 99, 781, 294, 678, 957, 41, 78, 725, 58, 244, 620, 603, 694, 702, 901, 36, 626, 604, 858, 865, 731, 558, 261, 941, 327, 67, 408, 110, 925, 85, 562, 995, 649, 292, 816, 490, 370, 579, 277, 320, 292, 932, 793, 541, 668, 149, 499, 284, 
160, 455, 670, 694, 266, 906, 677, 809, 735, 723, 438, 339, 388, 784, 367, 873, 564, 777, 940, 165, 937, 911, 924, 603, 432, 609, 38, 795, 627, 147, 838, 364, 52, 301, 367, 917, 543, 820, 64, 202, 125, 659, 775, 280, 911, 767, 807, 193, 433, 645, 
664, 942, 178, 396, 866, 320, 37, 194, 993, 909, 193, 624, 312, 3, 713, 293, 430, 278, 242, 371, 488, 17, 560, 619, 475, 597, 287, 433, 496, 917, 250, 880, 38, 446, 22, 123, 617, 215, 371, 25, 436, 508, 776, 6, 63, 306, 948, 88, 168, 49, 
452, 504, 139, 685, 736, 765, 802, 179, 308, 536, 947, 988, 406, 649, 548, 291, 92, 980, 279, 638, 867, 851, 885, 439, 640, 747, 596, 143, 503, 990, 16, 959, 421, 211, 267, 246, 981, 599, 836, 601, 940, 394, 960, 510, 230, 233, 196, 15, 421, 583, 
550, 551, 53, 235, 70, 845, 760, 335, 311, 764, 522, 558, 701, 118, 876, 963, 782, 204, 329, 578, 721, 199, 938, 431, 232, 571, 913, 24, 348, 609, 200, 739, 180, 841, 160, 615, 461, 881, 432, 756, 432, 647, 84, 321, 143, 96, 25, 353, 118, 743, 
977, 501, 489, 925, 835, 424, 745, 884, 584, 61, 29, 985, 30, 665, 658, 684, 124, 920, 811, 528, 737, 416, 7, 723, 597, 527, 94, 452, 773, 237, 369, 584, 831, 978, 307, 420, 561, 253, 452, 679, 378, 33, 95, 47, 669, 697, 921, 112, 514, 349, 
472, 459, 75, 364, 516, 613, 14, 608, 281, 667, 431, 807, 688, 518, 819, 638, 553, 82, 220, 294, 521, 886, 152, 276, 915, 83, 360, 970, 567, 837, 993, 56, 149, 963, 556, 71, 727, 782, 614, 963, 482, 603, 864, 446, 891, 873, 715, 852, 418, 465, 
699, 418, 551, 272, 377, 702, 367, 374, 821, 957, 325, 180, 537, 535, 216, 623, 687, 43, 768, 143, 78, 321, 911, 654, 23, 803, 850, 121, 322, 10, 765, 808, 814, 458, 504, 981, 317, 406, 236, 655, 468, 786, 979, 459, 611, 162, 794, 639, 681, 277, 
127, 766, 557, 913, 762, 131, 412, 789, 493, 734, 142, 313, 668, 111, 486, 886, 163, 390, 173, 597, 890, 46, 126, 848, 977, 532, 527, 730, 674, 971, 540, 808, 652, 101, 604, 156, 201, 0, 236, 756, 885, 498, 695, 45, 509, 890, 410, 29, 52, 427, 
758, 87, 875, 368, 1, 980, 661, 264, 959, 65, 471, 96, 549, 364, 980, 244, 429, 514, 643, 350, 344, 51, 234, 650, 791, 751, 166, 479, 992, 601, 113, 550, 865, 880, 683, 992, 701, 621, 772, 273, 265, 297, 55, 358, 358, 898, 910, 103, 364, 577, 
453, 437, 995, 20, 96, 274, 857, 108, 356, 19, 978, 718, 998, 295, 691, 466, 997, 204, 300, 365, 33, 998, 889, 711, 480, 998, 23, 588, 172, 284, 911, 714, 942, 789, 148, 256, 97, 122, 588, 121, 102, 606, 24, 147, 507, 742, 60, 162, 2, 869, 
797, 427, 851, 799, 141, 282, 130, 138, 392, 978, 358, 771, 52, 296, 662, 446, 611, 902, 659, 394, 680, 432, 309, 544, 11, 512, 399, 330, 884, 618, 458, 972, 648, 111, 971, 556, 407, 82, 660, 568, 610, 933, 163, 763, 77, 624, 348, 959, 184, 654, 
7, 954, 437, 312, 225, 345, 505, 150, 467, 397, 595, 26, 309, 791, 230, 274, 257, 348, 606, 816, 751, 753, 436, 564, 707, 822, 113, 405, 849, 250, 124, 761, 556, 258, 772, 738, 585, 800, 228, 181, 999, 29, 322, 904, 74, 727, 909, 787, 980, 777, 
338, 500, 355, 509, 318, 303, 680, 938, 128, 740, 660, 822, 606, 951, 523, 426, 523, 317, 398, 375, 195, 579, 314, 212, 567, 175, 994, 620, 975, 539, 69, 570, 667, 637, 839, 253, 0, 831, 728, 393, 394, 207, 927, 154, 262, 575, 388, 25, 820, 362, 
88, 813, 38, 499, 693, 360, 140, 693, 813, 215, 635, 505, 716, 119, 266, 971, 988, 751, 842, 612, 604, 289, 24, 174, 904, 560, 180, 929, 823, 433, 646, 816, 30, 529, 614, 554, 448, 107, 152, 250, 994, 374, 553, 678, 912, 871, 877, 487, 394, 908, 
892, 501, 947, 699, 897, 552, 959, 542, 904, 470, 835, 936, 201, 792, 409, 221, 929, 466, 386, 51, 556, 38, 650, 794, 922, 601, 378, 796, 318, 192, 600, 372, 423, 530, 967, 912, 268, 581, 110, 902, 898, 61, 625, 24, 222, 568, 825, 255, 753, 347, 
884, 545, 142, 187, 469, 754, 244, 298, 634, 596, 940, 335, 31, 71, 858, 52, 366, 182, 699, 974, 19, 22, 547, 191, 728, 239, 444, 131, 686, 745, 5, 92, 742, 373, 8, 686, 786, 904, 553, 418, 391, 497, 703, 331, 455, 68, 917, 738, 880, 518, 
54, 842, 999, 192, 226, 899, 873, 327, 746, 23, 423, 617, 829, 382, 327, 143, 17, 465, 122, 475, 264, 88, 162, 849, 176, 765, 520, 173, 936, 509, 742, 360, 35, 162, 937, 746, 231, 169, 588, 14, 618, 564, 205, 864, 521, 143, 968, 287, 945, 851, 
37, 139, 857, 525, 723, 133, 389, 852, 289, 545, 940, 140, 144, 436, 652, 917, 906, 461, 850, 610, 593, 157, 475, 707, 687, 294, 138, 162, 561, 597, 800, 645, 347, 7, 660, 424, 578, 349, 520, 976, 707, 407, 175, 584, 846, 370, 216, 883, 90, 553, 
219, 310, 479, 276, 950, 499, 870, 995, 351, 397, 962, 297, 502, 46, 835, 169, 922, 570, 494, 697, 352, 690, 597, 265, 579, 184, 103, 610, 951, 845, 320, 286, 539, 516, 959, 948, 137, 764, 634, 655, 55, 272, 522, 827, 204, 47, 614, 296, 418, 762, 
504, 362, 133, 249, 665, 902, 775, 996, 668, 964, 241, 987, 6, 364, 393, 812, 81, 803, 814, 424, 203, 778, 445, 851, 626, 595, 433, 255, 227, 427, 843, 816, 439, 798, 719, 542, 957, 773, 611, 469, 325, 599, 454, 356, 273, 931, 749, 551, 692, 674, 
220, 28, 288, 612, 718, 56, 225, 297, 20, 999, 547, 579, 280, 173, 324, 374, 111, 88, 937, 79, 87, 226, 282, 45, 191, 8, 292, 715, 175, 420, 762, 912, 203, 834, 410, 541, 443, 52, 625, 988, 104, 686, 878, 281, 870, 217, 983, 193, 308, 112, 
486, 229, 964, 748, 386, 653, 890, 792, 485, 276, 15, 267, 200, 535, 219, 337, 969, 765, 269, 329, 840, 86, 194, 980, 852, 35, 70, 883, 432, 417, 846, 5, 829, 373, 81, 298, 373, 134, 297, 99, 781, 294, 678, 957, 41, 78, 725, 58, 244, 620, 
603, 694, 702, 901, 36, 626, 604, 858, 865, 731, 558, 261, 941, 327, 67, 408, 110, 925, 85, 562, 995, 649, 292, 816, 490, 370, 579, 277, 320, 292, 932, 793, 541, 668, 149, 499, 284, 160, 455, 670, 694, 266, 906, 677, 809, 735, 723, 438, 339, 388, 
784, 367, 873, 564, 777, 940, 165, 937, 911, 924, 603, 432, 609, 38, 795, 627, 147, 838, 364, 52, 301, 367, 917, 543, 820, 64, 202, 125, 659, 775, 280, 911, 767, 807, 193, 433, 645, 664, 942, 178, 396, 866, 320, 37, 194, 993, 909, 193, 624, 312, 
3, 713, 293, 430, 278, 242, 371, 488, 17, 560, 619, 475, 597, 287, 433, 496, 917, 250, 880, 38, 446, 22, 123, 617, 215, 371, 25, 436, 508, 776, 6, 63, 306, 948, 88, 168, 49, 452, 504, 139, 685, 736, 765, 802, 179, 308, 536, 947, 988, 406, 
649, 548, 291, 92, 980, 279, 638, 867, 851, 885, 439, 640, 747, 596, 143, 503, 990, 16, 959, 421, 211, 267, 246, 981, 599, 836, 601, 940, 394, 960, 510, 230, 233, 196, 15, 421, 583, 550, 551, 53, 235, 70, 845, 760, 335, 311, 764, 522, 558, 701, 
118, 876, 963, 782, 204, 329, 578, 721, 199, 938, 431, 232, 571, 913, 24, 348, 609, 200, 739, 180, 841, 160, 615, 461, 881, 432, 756, 432, 647, 84, 321, 143, 96, 25, 353, 118, 743, 977, 501, 489, 925, 835, 424, 745, 884, 584, 61, 29, 985, 30, 
665, 658, 684, 124, 920, 811, 528, 737, 416, 7, 723, 597, 527, 94, 452, 773, 237, 369, 584, 831, 978, 307, 420, 561, 253, 452, 679, 378, 33, 95, 47, 669, 697, 921, 112, 514, 349, 472, 459, 75, 364, 516, 613, 14, 608, 281, 667, 431, 807, 688, 
518, 819, 638, 553, 82, 220, 294, 521, 886, 152, 276, 915, 83, 360, 970, 567, 837, 993, 56, 149, 963, 556, 71, 727, 782, 614, 963, 482, 603, 864, 446, 891, 873, 715, 852, 418, 465, 699, 418, 551, 272, 377, 702, 367, 374, 821, 957, 325, 180, 537, 
535, 216, 623, 687, 43, 768, 143, 78, 321, 911, 654, 23, 803, 850, 121, 322, 10, 765, 808, 814, 458, 504, 981, 317, 406, 236, 655, 468, 786, 979, 459, 611, 162, 794, 639, 681, 277, 127, 766, 557, 913, 762, 131, 412, 789, 493, 734, 142, 313, 668, 
111, 486, 886, 163, 390, 173, 597, 890, 46, 126, 848, 977, 532, 527, 730, 674, 971, 540, 808, 652, 101, 604, 156, 0, 236, 756, 885, 498, 695, 45, 509, 890, 410, 29, 52, 427, 758, 87, 875, 368, 1, 980, 661, 264, 959, 65, 471, 96, 549, 364, 
980, 244, 429, 514, 643, 350, 344, 51, 234, 650, 791, 751, 166, 479, 992, 601, 113, 550, 865, 880, 683, 992, 701, 621, 772, 273, 265, 297, 55, 358, 358, 898, 910, 103, 364, 577, 453, 437, 995, 20, 96, 274, 857, 108, 356, 19, 978, 718, 998, 295, 
691, 466, 997, 204, 300, 365, 33, 998, 889, 711, 480, 998, 23, 588, 172, 284, 911, 714, 942, 789, 148, 256, 97, 122, 588, 121, 102, 606, 24, 147, 507, 742, 60, 162, 2, 869, 797, 427, 851, 799, 141, 282, 130, 138, 392, 978, 358, 771, 52, 296, 
662, 446, 611, 902, 659, 394, 680, 432, 309, 544, 11, 512, 399, 330, 884, 618, 458, 972, 648, 111, 971, 556, 407, 82, 660, 568, 610, 933, 163, 763, 77, 624, 348, 959, 184, 654, 7, 954, 437, 312, 225, 345, 505, 150, 467, 397, 595, 26, 309, 791, 
230, 274, 257, 348, 606, 816, 751, 753, 436, 564, 707, 822, 113, 405, 849, 250, 124, 761, 556, 258, 772, 738, 585, 800, 228, 181, 999, 29, 322, 904, 74, 727, 909, 787, 980, 777, 338, 500, 355, 509, 318, 303, 680, 938, 128, 740, 660, 822, 606, 951, 
523, 426, 523, 317, 398, 375, 195, 579, 314, 212, 567, 175, 994, 620, 975, 539, 69, 570, 667, 637, 839, 253, 0, 831, 728, 393, 394, 207, 927, 154, 262, 575, 388, 25, 820, 362, 88, 813, 38, 499, 693, 360, 140, 693, 813, 215, 635, 505, 716, 119, 
266, 971, 988, 751, 842, 612, 604, 289, 24, 174, 904, 560, 180, 929, 823, 433, 646, 816, 30, 529, 614, 554, 448, 107, 152, 250, 994, 374, 553, 678, 912, 871, 877, 487, 394, 908, 892, 501, 947, 699, 897, 552, 959, 542, 904, 470, 835, 936, 201, 792, 
409, 221, 929, 466, 386, 51, 556, 38, 650, 794, 922, 601, 378, 796, 318, 192, 600, 372, 423, 530, 967, 912, 268, 581, 110, 902, 898, 61, 625, 24, 222, 568, 825, 255, 753, 347, 884, 545, 142, 187, 469, 754, 244, 298, 634, 596, 940, 335, 31, 71, 
858, 52, 366, 182, 699, 974, 19, 22, 547, 191, 728, 239, 444, 131, 686, 745, 5, 92, 742, 373, 8, 686, 786, 904, 553, 418, 391, 497, 703, 331, 455, 68, 917, 738, 880, 518, 54, 842, 999, 192, 226, 899, 873, 327, 746, 23, 423, 617, 829, 382, 
327, 143, 17, 465, 122, 475, 264, 88, 162, 849, 176, 765, 520, 173, 936, 509, 742, 360, 35, 162, 937, 746, 231, 169, 588, 14, 618, 564, 205, 864, 521, 143, 968, 287, 945, 851, 37, 139, 857, 525, 723, 133, 389, 852, 289, 545, 940, 140, 144, 436, 
652, 917, 906, 461, 850, 610, 593, 157, 475, 707, 687, 294, 138, 162, 561, 597, 800, 645, 347, 7, 660, 424, 578, 349, 520, 976, 707, 407, 175, 584, 846, 370, 216, 883, 90, 553, 219, 310, 479, 276, 950, 499, 870, 995, 351, 397, 962, 297, 502, 46, 
835, 169, 922, 570, 494, 697, 352, 690, 597, 265, 579, 184, 103, 610, 951, 845, 320, 286, 539, 516, 959, 948, 137, 764, 634, 655, 55, 272, 522, 827, 204, 47, 614, 296, 418, 762, 504, 362, 133, 249, 665, 902, 775, 996, 668, 964, 241, 987, 6, 364, 
393, 812, 81, 803, 814, 424, 203, 778, 445, 851, 626, 595, 433, 255, 227, 427, 843, 816, 439, 798, 719, 542, 957, 773, 611, 469, 325, 599, 454, 356, 273, 931, 749, 551, 692, 674, 220, 28, 288, 612, 718, 56, 225, 297, 20, 999, 547, 579, 280, 173, 
324, 374, 111, 88, 937, 79, 87, 226, 282, 45, 191, 8, 292, 715, 175, 420, 762, 912, 203, 834, 410, 541, 443, 52, 625, 988, 104, 686, 878, 281, 870, 217, 983, 193, 308, 112, 486, 229, 964, 748, 386, 653, 890, 792, 485, 276, 15, 267, 200, 535, 
219, 337, 969, 765, 269, 329, 840, 86, 194, 980, 852, 35, 70, 883, 432, 417, 846, 5, 829, 373, 81, 298, 373, 134, 297, 99, 781, 294, 678, 957, 41, 78, 725, 58, 244, 620, 603, 694, 702, 901, 36, 626, 604, 858, 865, 731, 558, 261, 941, 327, 
67, 408, 110, 925, 85, 562, 995, 649, 292, 816, 490, 370, 579, 277, 320, 292, 932, 793, 541, 668, 149, 499, 284, 160, 455, 670, 694, 266, 906, 677, 809, 735, 723, 438, 339, 388, 784, 367, 873, 564, 777, 940, 165, 937, 911, 924, 603, 432, 609, 38, 
795, 627, 147, 838, 364, 52, 301, 367, 917, 543, 820, 64, 202, 125, 659, 775, 280, 911, 767, 807, 193, 433, 645, 664, 942, 178, 396, 866, 320, 37, 194, 993, 909, 193, 624, 312, 3, 713, 293, 430, 278, 242, 371, 488, 17, 560, 619, 475, 597, 287, 
433, 496, 917, 250, 880, 38, 446, 22, 123, 617, 215, 371, 25, 436, 508, 776, 6, 63, 306, 948, 88, 168, 49, 452, 504, 139, 685, 736, 765, 802, 179, 308, 536, 947, 988, 406, 649, 548, 291, 92, 980, 279, 638, 867, 851, 885, 439, 640, 747, 596, 
143, 503, 990, 16, 959, 421, 211, 267, 246, 981, 599, 836, 601, 940, 394, 960, 510, 230, 233, 196, 15, 421, 583, 550, 551, 53, 235, 70, 845, 760, 335, 311, 764, 522, 558, 701, 118, 876, 963, 782, 204, 329, 578, 721, 199, 938, 431, 232, 571, 913, 
24, 348, 609, 200, 739, 180, 841, 160, 615, 461, 881, 432, 756, 432, 647, 84, 321, 143, 96, 25, 353, 118, 743, 977, 501, 489, 925, 835, 424, 745, 884, 584, 61, 29, 985, 30, 665, 658, 684, 124, 920, 811, 528, 737, 416, 7, 723, 597, 527, 94, 
452, 773, 237, 369, 584, 831, 978, 307, 420, 561, 253, 452, 679, 378, 33, 95, 47, 669, 697, 921, 112, 514, 349, 472, 459, 75, 364, 516, 613, 14, 608, 281, 667, 431, 807, 688, 518, 819, 638, 553, 82, 220, 294, 521, 886, 152, 276, 915, 83, 360, 
970, 567, 837, 993, 56, 149, 963, 556, 71, 727, 782, 614, 963, 482, 603, 864, 446, 891, 873, 715, 852, 418, 465, 699, 418, 551, 272, 377, 702, 367, 374, 821, 957, 325, 180, 537, 535, 216, 623, 687, 43, 768, 143, 78, 321, 911, 654, 23, 803, 850, 
121, 322, 10, 765, 808, 814, 458, 504, 981, 317, 406, 236, 655, 468, 786, 979, 459, 611, 162, 794, 639, 681, 277, 127, 766, 557, 913, 762, 131, 412, 789, 493, 734, 142, 313, 668, 111, 486, 886, 163, 390, 173, 597, 890, 46, 126, 848, 977, 532, 527, 
730, 674, 971, 540, 808, 652, 101, 604, 156, 0, 236, 756, 885, 498, 695, 45, 509, 890, 410, 29, 52, 427, 758, 87, 875, 368, 1, 980, 661, 264, 959, 65, 471, 96, 549, 364, 980, 244, 429, 514, 643, 350, 344, 51, 234, 650, 791, 751, 166, 479, 
992, 601, 113, 550, 865, 880, 683, 992, 701, 621, 772, 273, 265, 297, 55, 358, 358, 898, 910, 103, 364, 577, 453, 437, 995, 20, 96, 274, 857, 108, 356, 19, 978, 718, 998, 295, 691, 466, 997, 204, 300, 365, 33, 998, 889, 711, 480, 998, 23, 588, 
172, 284, 911, 714, 942, 789, 148, 256, 97, 122, 588, 121, 102, 606, 24, 147, 507, 742, 60, 162, 2, 869, 797, 427, 851, 799, 141, 282, 130, 138, 392, 978, 358, 771, 52, 296, 662, 446, 611, 902, 659, 394, 680, 432, 309, 544, 11, 512, 399, 330, 
884, 618, 458, 972, 648, 111, 971, 556, 407, 82, 660, 568, 610, 933, 163, 763, 77, 624, 348, 959, 184, 654, 7, 954, 437, 312, 225, 345, 505, 150, 467, 397, 595, 26, 309, 791, 230, 274, 257, 348, 606, 816, 751, 753, 436, 564, 707, 822, 113, 405, 
849, 250, 124, 761, 556, 258, 772, 738, 585, 800, 228, 181, 999, 29, 322, 904, 74, 727, 909, 787, 980, 777, 338, 500, 355, 509, 318, 303, 680, 938, 128, 740, 660, 822, 606, 951, 523, 426, 523, 317, 398, 375, 195, 579, 314, 212, 567, 175, 994, 620, 
975, 539, 69, 570, 667, 637, 839, 253, 0, 831, 728, 393, 394, 207, 927, 154, 262, 575, 388, 25, 820, 362, 88, 813, 38, 499, 693, 360, 140, 693, 813, 215, 635, 505, 716, 119, 266, 971, 988, 751, 842, 612, 604, 289, 24, 174, 904, 560, 180, 929, 
823, 433, 646, 816, 30, 529, 614, 554, 448, 107, 152, 250, 994, 374, 553, 678, 912, 871, 877, 487, 394, 908, 892, 501, 947, 699, 897, 552, 959, 542, 904, 470, 835, 936, 201, 792, 409, 221, 929, 466, 386, 51, 556, 38, 650, 794, 922, 601, 378, 796, 
318, 192, 600, 372, 423, 530, 967, 912, 268, 581, 110, 902, 898, 61, 625, 24, 222, 568, 825, 255, 753, 347, 884, 545, 142, 187, 469, 754, 244, 298, 634, 596, 940, 335, 31, 71, 858, 52, 366, 182, 699, 974, 19, 22, 547, 191, 728, 239, 444, 131, 
686, 745, 5, 92, 742, 373, 8, 686, 786, 904, 553, 418, 391, 497, 703, 331, 455, 68, 917, 738, 880, 518, 54, 842, 999, 192, 226, 899, 873, 327, 746, 23, 423, 617, 829, 382, 327, 143, 17, 465, 122, 475, 264, 88, 162, 849, 176, 765, 520, 173, 
936, 509, 742, 360, 35, 162, 937, 746, 231, 169, 588, 14, 618, 564, 205, 864, 521, 143, 968, 287, 945, 851, 37, 139, 857, 525, 723, 133, 389, 852, 289, 545, 940, 140, 144, 436, 652, 917, 906, 461, 850, 610, 593, 157, 475, 707, 687, 294, 138, 162, 
561, 597, 800, 645, 347, 7, 660, 424, 578, 349, 520, 976, 707, 407, 175, 584, 846, 370, 216, 883, 90, 553, 219, 310, 479, 276, 950, 499, 870, 995, 351, 397, 962, 297, 502, 46, 835, 169, 922, 570, 494, 697, 352, 690, 597, 265, 579, 184, 103, 610, 
951, 845, 320, 286, 539, 516, 959, 948, 137, 764, 634, 655, 55, 272, 522, 827, 204, 47, 614, 296, 418, 762, 504, 362, 133, 249, 665, 902, 775, 996, 668, 964, 241, 987, 6, 364, 393, 812, 81, 803, 814, 424, 203, 778, 445, 851, 626, 595, 433, 255, 
227, 427, 843, 816, 439, 798, 719, 542, 957, 773, 611, 469, 325, 599, 454, 356, 273, 931, 749, 551, 692, 674, 220, 28, 288, 612, 718, 56, 225, 297, 20, 999, 547, 579, 280, 173, 324, 374, 111, 88, 937, 79, 87, 226, 282, 45, 191, 8, 292, 715, 
175, 420, 762, 912, 203, 834, 410, 541, 443, 52, 625, 988, 104, 686, 878, 281, 870, 217, 983, 193, 308, 112, 486, 229, 964, 748, 386, 653, 890, 792, 485, 276, 15, 267, 200, 535, 219, 337, 969, 765, 269, 329, 840, 86, 194, 980, 852, 35, 70, 883, 
432, 417, 846, 5, 829, 373, 81, 298, 373, 134, 297, 99, 781, 294, 678, 957, 41, 78, 725, 58, 244, 620, 603, 694, 702, 901, 36, 626, 604, 858, 865, 731, 558, 261, 941, 327, 67, 408, 110, 925, 85, 562, 995, 649, 292, 816, 490, 370, 579, 277, 
320, 292, 932, 793, 541, 668, 149, 499, 284, 160, 455, 670, 694, 266, 906, 677, 809, 735, 723, 438, 339, 388, 784, 367, 873, 564, 777, 940, 165, 937, 911, 924, 603, 432, 609, 38, 795, 627, 147, 838, 364, 52, 301, 367, 917, 543, 820, 64, 202, 125, 
659, 775, 280, 911, 767, 807, 193, 433, 645, 664, 942, 178, 396, 866, 320, 37, 194, 993, 909, 193, 624, 312, 3, 713, 293, 430, 278, 242, 371, 488, 17, 560, 619, 475, 597, 287, 433, 496, 917, 250, 880, 38, 446, 22, 123, 617, 215, 371, 25, 436, 
508, 776, 6, 63, 306, 948, 88, 168, 49, 452, 504, 139, 685, 736, 765, 802, 179, 308, 536, 947, 988, 406, 649, 548, 291, 92, 980, 279, 638, 867, 851, 885, 439, 640, 747, 596, 143, 503, 990, 16, 959, 421, 211, 267, 246, 981, 599, 836, 601, 940, 
394, 960, 510, 230, 233, 196, 15, 421, 583, 550, 551, 53, 235, 70, 845, 760, 335, 311, 764, 522, 558, 701, 118, 876, 963, 782, 204, 329, 578, 721, 199, 938, 431, 232, 571, 913, 24, 348, 609, 200, 739, 180, 841, 160, 615, 461, 881, 432, 756, 432, 
647, 84, 321, 143, 96, 25, 353, 118, 743, 977, 501, 489, 925, 835, 424, 745, 884, 584, 61, 29, 985, 30, 665, 658, 684, 124, 920, 811, 528, 737, 416, 7, 723, 597, 527, 94, 452, 773, 237, 369, 584, 831, 978, 307, 420, 561, 253, 452, 679, 378, 
33, 95, 47, 669, 697, 921, 112, 514, 349, 472, 459, 75, 364, 516, 613, 14, 608, 281, 667, 431, 807, 688, 518, 819, 638, 553, 82, 220, 294, 521, 886, 152, 276, 915, 83, 360, 970, 567, 837, 993, 56, 149, 963, 556, 71, 727, 782, 614, 963, 482, 
603, 864, 446, 891, 873, 715, 852, 418, 465, 699, 418, 551, 272, 377, 702, 367, 374, 821, 957, 325, 180, 537, 535, 216, 623, 687, 43, 768, 143, 78, 321, 911, 654, 23, 803, 850, 121, 322, 10, 765, 808, 814, 458, 504, 981, 317, 406, 236, 655, 468, 
786, 979, 459, 611, 162, 794, 639, 681, 277, 127, 766, 557, 913, 762, 131, 412, 789, 493, 734, 142, 313, 668, 111, 486, 886, 163, 390, 173, 597, 890, 46, 126, 848, 977, 532, 527, 730, 674, 971, 540, 808, 652, 101, 604, 156};