diff options
| author | Todd C. Miller <millert@cvs.openbsd.org> | 2017-05-19 04:08:01 +0000 |
|---|---|---|
| committer | Todd C. Miller <millert@cvs.openbsd.org> | 2017-05-19 04:08:01 +0000 |
| commit | 90a86389cb2104af827e019dbedea80d01a7a721 (patch) | |
| tree | c6f3132fbeeb0374a3497d52f65253d69897c5a5 /regress/lib/libc/qsort | |
| parent | fbd7ba509b0fdee0b7f1841eb85085ffdebee5e0 (diff) | |
Add input targeted at the Bentley and McIrlroy quicksort generated
by McIlroy's "A Killer Adversary for Quicksort". This results in
quadratic behavior and the test aborts before completion.
Diffstat (limited to 'regress/lib/libc/qsort')
| -rw-r--r-- | regress/lib/libc/qsort/qsort_test.c | 1395 |
1 files changed, 1389 insertions, 6 deletions
diff --git a/regress/lib/libc/qsort/qsort_test.c b/regress/lib/libc/qsort/qsort_test.c index f8507ce88c6..4de6730864e 100644 --- a/regress/lib/libc/qsort/qsort_test.c +++ b/regress/lib/libc/qsort/qsort_test.c @@ -22,11 +22,12 @@ /* * Test program based on Bentley & McIlroy's "Engineering a Sort Function". - * Additional tests include the "median of three" killer from - * David R. Musser's "Introspective Sorting and Selection Algorithms" - * and 4.4BSD qsort killer input from - * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html * Uses mergesort(3) to check the results. + * + * Additional "killer" input taken from: + * David R. Musser's "Introspective Sorting and Selection Algorithms" + * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html + * M. D. McIlroy's "A Killer Adversary for Quicksort" targeting B & M qsort */ enum distribution { @@ -35,6 +36,7 @@ enum distribution { STAGGER, PLATEAU, SHUFFLE, + BM_KILLER, BSD_KILLER, MED3_KILLER, INVALID @@ -47,6 +49,1324 @@ static size_t max_compares; static size_t abrt_compares; static sigjmp_buf cmpjmp; +/* + * Bentley and McIlroy "killer" input generated by from McIlroy's + * "A Killer Adversary for Quicksort" program. + */ +static const int bmkiller_100[] = { + 0, 28, 90, 87, 6, 15, 75, 77, 10, 33, 64, 80, + 1, 31, 16, 25, 7, 39, 52, 11, 21, 79, 70, 99, + 17, 26, 36, 92, 89, 95, 22, 81, 86, 82, 27, 37, + 46, 83, 32, 41, 76, 54, 84, 38, 56, 47, 42, 85, + 59, 72, 2, 48, 8, 96, 12, 63, 57, 18, 67, 78, + 23, 58, 3, 53, 9, 13, 66, 19, 68, 43, 24, 29, + 49, 34, 74, 40, 44, 88, 50, 94, 62, 55, 65, 60, + 69, 71, 73, 4, 14, 20, 30, 35, 45, 51, 61, 91, + 93, 97, 98, 5 +}; + +static const int bmkiller_1023[] = { + 0, 956, 731, 129, 6, 15, 687, 133, 10, 643, 684, 853, + 443, 691, 16, 25, 692, 773, 20, 833, 269, 953, 449, 144, + 26, 35, 983, 275, 882, 149, 31, 920, 972, 459, 915, 36, + 46, 285, 539, 160, 41, 698, 663, 813, 164, 47, 56, 702, + 652, 51, 295, 910, 469, 535, 743, 57, 66, 783, 714, 61, + 835, 300, 819, 540, 180, 67, 76, 971, 673, 545, 185, 72, + 708, 618, 885, 200, 77, 87, 316, 551, 403, 82, 712, 922, + 978, 961, 88, 97, 986, 205, 92, 674, 624, 757, 490, 717, + 98, 107, 718, 628, 561, 754, 103, 794, 1012, 500, 924, 108, + 118, 938, 1011, 231, 113, 968, 341, 792, 226, 119, 128, 723, + 232, 123, 694, 347, 510, 580, 851, 1, 138, 728, 751, 7, + 357, 735, 11, 576, 987, 139, 148, 994, 17, 581, 830, 21, + 733, 367, 802, 767, 27, 159, 649, 586, 770, 154, 32, 372, + 925, 263, 37, 169, 739, 740, 42, 779, 378, 883, 592, 48, + 170, 179, 52, 868, 536, 375, 175, 814, 58, 778, 448, 62, + 190, 393, 611, 746, 68, 749, 665, 546, 780, 191, 73, 906, + 303, 195, 78, 669, 552, 607, 83, 201, 210, 820, 304, 89, + 675, 409, 93, 556, 787, 211, 220, 99, 869, 617, 613, 216, + 996, 104, 952, 890, 221, 109, 423, 623, 899, 114, 759, 825, + 907, 334, 120, 241, 764, 124, 236, 896, 685, 798, 727, 130, + 242, 251, 134, 989, 577, 339, 247, 140, 804, 905, 345, 252, + 262, 145, 732, 349, 257, 150, 450, 587, 638, 155, 272, 774, + 916, 267, 161, 700, 593, 165, 360, 273, 282, 936, 171, 277, + 465, 980, 884, 597, 176, 283, 292, 931, 181, 603, 452, 288, + 186, 475, 839, 998, 293, 192, 865, 658, 196, 298, 784, 481, + 962, 933, 202, 313, 845, 206, 308, 942, 485, 908, 212, 396, + 314, 323, 790, 491, 217, 401, 319, 941, 222, 947, 416, 324, + 227, 501, 683, 762, 329, 233, 726, 1005, 237, 335, 344, 795, + 421, 243, 511, 949, 634, 679, 680, 248, 354, 800, 855, 253, + 771, 516, 990, 258, 432, 355, 364, 999, 264, 644, 437, 268, + 805, 993, 834, 831, 365, 274, 532, 695, 278, 370, 861, 944, + 736, 284, 376, 385, 811, 591, 380, 289, 781, 840, 654, 294, + 386, 395, 815, 299, 705, 886, 391, 866, 305, 895, 609, 309, + 406, 1007, 943, 842, 315, 821, 557, 844, 479, 407, 320, 871, + 619, 411, 325, 563, 973, 724, 330, 417, 426, 937, 493, 336, + 573, 921, 340, 720, 721, 427, 436, 826, 346, 725, 995, 350, + 876, 583, 874, 803, 356, 447, 969, 690, 519, 442, 361, 588, + 992, 514, 366, 457, 836, 520, 371, 817, 594, 954, 696, 377, + 458, 467, 381, 782, 991, 737, 463, 387, 951, 880, 777, 468, + 478, 392, 755, 979, 473, 397, 926, 967, 550, 402, 488, 846, + 957, 483, 408, 959, 930, 412, 707, 489, 498, 892, 864, 418, + 974, 625, 422, 756, 796, 499, 508, 428, 1013, 761, 893, 504, + 852, 433, 875, 668, 509, 438, 639, 2, 897, 8, 856, 12, + 807, 877, 18, 529, 22, 453, 524, 28, 809, 881, 33, 637, + 530, 38, 862, 43, 464, 828, 49, 902, 53, 747, 932, 59, + 474, 63, 841, 648, 69, 480, 666, 74, 484, 79, 560, 867, + 84, 555, 90, 940, 94, 494, 612, 100, 570, 872, 105, 565, + 681, 110, 1000, 115, 505, 571, 121, 1008, 125, 797, 627, 131, + 515, 135, 911, 633, 141, 521, 900, 146, 525, 151, 963, 697, + 156, 531, 162, 601, 166, 889, 596, 172, 701, 955, 177, 541, + 602, 182, 887, 187, 964, 653, 193, 1003, 197, 788, 903, 203, + 622, 207, 827, 664, 213, 562, 850, 218, 566, 223, 632, 982, + 228, 572, 234, 854, 238, 823, 988, 244, 642, 927, 249, 582, + 860, 254, 3, 259, 9, 13, 265, 898, 19, 23, 689, 29, + 1010, 279, 34, 704, 39, 44, 748, 290, 50, 54, 608, 1004, + 60, 64, 306, 70, 310, 709, 75, 80, 870, 85, 321, 91, + 95, 326, 101, 331, 824, 106, 337, 111, 116, 879, 799, 122, + 126, 351, 1017, 132, 136, 914, 142, 362, 730, 147, 152, 918, + 157, 699, 163, 167, 382, 173, 659, 388, 178, 1022, 183, 188, + 789, 398, 194, 198, 934, 715, 204, 208, 413, 214, 958, 419, + 219, 224, 946, 229, 429, 235, 239, 434, 245, 439, 928, 250, + 444, 255, 260, 745, 454, 266, 270, 460, 810, 276, 280, 706, + 286, 470, 710, 291, 296, 808, 301, 716, 307, 311, 965, 317, + 766, 495, 322, 977, 327, 332, 912, 506, 338, 342, 776, 939, + 348, 352, 522, 358, 526, 741, 363, 368, 786, 373, 537, 379, + 383, 542, 389, 547, 752, 394, 553, 399, 404, 891, 901, 410, + 414, 567, 1019, 420, 424, 768, 430, 578, 772, 435, 440, 1002, + 445, 838, 451, 455, 598, 461, 812, 604, 466, 1001, 471, 476, + 818, 614, 482, 486, 793, 843, 492, 496, 629, 502, 849, 635, + 507, 512, 948, 517, 645, 523, 527, 650, 533, 655, 848, 538, + 660, 543, 548, 1006, 670, 554, 558, 676, 858, 564, 568, 829, + 574, 686, 1018, 579, 584, 859, 589, 970, 595, 599, 923, 605, + 985, 711, 610, 1015, 615, 620, 984, 722, 626, 630, 975, 913, + 636, 640, 738, 646, 742, 997, 651, 656, 917, 661, 753, 667, + 671, 758, 677, 763, 1009, 682, 769, 4, 14, 24, 30, 40, + 45, 55, 65, 71, 81, 86, 96, 102, 112, 117, 127, 137, + 143, 153, 158, 168, 174, 184, 189, 199, 209, 215, 225, 230, + 240, 246, 256, 261, 271, 281, 287, 297, 302, 312, 318, 328, + 333, 343, 353, 359, 369, 374, 384, 390, 400, 405, 415, 425, + 431, 441, 446, 456, 462, 472, 477, 487, 497, 503, 513, 518, + 528, 534, 544, 549, 559, 569, 575, 585, 590, 600, 606, 616, + 621, 631, 641, 647, 657, 662, 672, 678, 688, 693, 703, 713, + 719, 729, 734, 744, 750, 760, 765, 775, 785, 791, 801, 806, + 816, 822, 832, 837, 847, 857, 863, 873, 878, 888, 894, 904, + 909, 919, 929, 935, 945, 950, 960, 966, 976, 981, 1014, 1016, + 1020, 1021, 5 +}; + +static const int bmkiller_1024[] = { + 0, 260, 732, 130, 6, 16, 770, 685, 444, 752, 11, 688, + 266, 808, 577, 17, 26, 693, 774, 21, 834, 270, 954, 450, + 145, 27, 36, 984, 276, 883, 150, 32, 921, 973, 460, 916, + 37, 47, 286, 540, 161, 42, 699, 664, 814, 165, 48, 57, + 703, 653, 52, 296, 911, 470, 536, 744, 58, 67, 784, 715, + 62, 836, 301, 820, 541, 181, 68, 77, 972, 674, 546, 186, + 73, 709, 619, 886, 201, 78, 88, 317, 552, 404, 83, 713, + 923, 979, 962, 89, 98, 987, 206, 93, 675, 625, 758, 491, + 718, 99, 108, 719, 629, 562, 755, 104, 795, 1013, 501, 925, + 109, 119, 939, 1012, 232, 114, 969, 342, 793, 227, 120, 129, + 724, 233, 124, 695, 348, 511, 581, 852, 1, 139, 729, 7, + 134, 358, 736, 692, 12, 988, 140, 149, 995, 18, 582, 831, + 22, 734, 368, 803, 768, 28, 160, 650, 587, 771, 155, 33, + 373, 926, 264, 38, 170, 740, 741, 43, 780, 379, 884, 593, + 49, 171, 180, 53, 869, 537, 376, 176, 815, 59, 779, 449, + 63, 191, 394, 612, 747, 69, 750, 666, 547, 781, 192, 74, + 907, 304, 196, 79, 670, 553, 608, 84, 202, 211, 821, 305, + 90, 676, 410, 94, 557, 788, 212, 221, 100, 870, 618, 614, + 217, 997, 105, 953, 891, 222, 110, 424, 624, 900, 115, 760, + 826, 908, 335, 121, 242, 765, 125, 237, 897, 686, 799, 728, + 131, 243, 252, 135, 990, 578, 340, 248, 141, 805, 906, 346, + 253, 263, 146, 733, 350, 258, 151, 451, 588, 639, 156, 273, + 775, 917, 268, 162, 701, 594, 166, 361, 274, 283, 937, 172, + 278, 466, 981, 885, 598, 177, 284, 293, 932, 182, 604, 453, + 289, 187, 476, 840, 999, 294, 193, 866, 659, 197, 299, 785, + 482, 963, 934, 203, 314, 846, 207, 309, 943, 486, 909, 213, + 397, 315, 324, 791, 492, 218, 402, 320, 942, 223, 948, 417, + 325, 228, 502, 684, 763, 330, 234, 727, 1006, 238, 336, 345, + 796, 422, 244, 512, 950, 635, 680, 681, 249, 355, 801, 856, + 254, 772, 517, 991, 259, 433, 356, 365, 1000, 265, 645, 438, + 269, 806, 994, 835, 832, 366, 275, 533, 696, 279, 371, 862, + 945, 737, 285, 377, 386, 812, 592, 381, 290, 782, 841, 655, + 295, 387, 396, 816, 300, 706, 887, 392, 867, 306, 896, 610, + 310, 407, 1008, 944, 843, 316, 822, 558, 845, 480, 408, 321, + 872, 620, 412, 326, 564, 974, 725, 331, 418, 427, 938, 494, + 337, 574, 922, 341, 721, 722, 428, 437, 827, 347, 726, 996, + 351, 877, 584, 875, 804, 357, 448, 970, 691, 520, 443, 362, + 589, 993, 515, 367, 458, 837, 521, 372, 818, 595, 955, 697, + 378, 459, 468, 382, 783, 992, 738, 464, 388, 952, 881, 778, + 469, 479, 393, 756, 980, 474, 398, 927, 968, 551, 403, 489, + 847, 958, 484, 409, 960, 931, 413, 708, 490, 499, 893, 865, + 419, 975, 626, 423, 757, 797, 500, 509, 429, 1014, 762, 894, + 505, 853, 434, 876, 669, 510, 439, 640, 2, 898, 8, 857, + 854, 13, 878, 19, 530, 23, 454, 525, 29, 810, 882, 34, + 638, 531, 39, 863, 44, 465, 829, 50, 903, 54, 748, 933, + 60, 475, 64, 842, 649, 70, 481, 667, 75, 485, 80, 561, + 868, 85, 556, 91, 941, 95, 495, 613, 101, 571, 873, 106, + 566, 682, 111, 1001, 116, 506, 572, 122, 1009, 126, 798, 628, + 132, 516, 136, 912, 634, 142, 522, 901, 147, 526, 152, 964, + 698, 157, 532, 163, 602, 167, 890, 597, 173, 702, 956, 178, + 542, 603, 183, 888, 188, 965, 654, 194, 1004, 198, 789, 904, + 204, 623, 208, 828, 665, 214, 563, 851, 219, 567, 224, 633, + 983, 229, 573, 235, 855, 239, 824, 989, 245, 643, 928, 250, + 583, 861, 255, 957, 3, 9, 644, 14, 899, 20, 24, 690, + 30, 1011, 280, 35, 705, 40, 45, 749, 291, 51, 55, 609, + 1005, 61, 65, 307, 71, 311, 710, 76, 81, 871, 86, 322, + 92, 96, 327, 102, 332, 825, 107, 338, 112, 117, 880, 800, + 123, 127, 352, 1018, 133, 137, 915, 143, 363, 731, 148, 153, + 919, 158, 700, 164, 168, 383, 174, 660, 389, 179, 1023, 184, + 189, 790, 399, 195, 199, 935, 716, 205, 209, 414, 215, 959, + 420, 220, 225, 947, 230, 430, 236, 240, 435, 246, 440, 929, + 251, 445, 256, 261, 746, 455, 267, 271, 461, 811, 277, 281, + 707, 287, 471, 711, 292, 297, 809, 302, 717, 308, 312, 966, + 318, 767, 496, 323, 978, 328, 333, 913, 507, 339, 343, 777, + 940, 349, 353, 523, 359, 527, 742, 364, 369, 787, 374, 538, + 380, 384, 543, 390, 548, 753, 395, 554, 400, 405, 892, 902, + 411, 415, 568, 1020, 421, 425, 769, 431, 579, 773, 436, 441, + 1003, 446, 839, 452, 456, 599, 462, 813, 605, 467, 1002, 472, + 477, 819, 615, 483, 487, 794, 844, 493, 497, 630, 503, 850, + 636, 508, 513, 949, 518, 646, 524, 528, 651, 534, 656, 849, + 539, 661, 544, 549, 1007, 671, 555, 559, 677, 859, 565, 569, + 830, 575, 687, 1019, 580, 585, 860, 590, 971, 596, 600, 924, + 606, 986, 712, 611, 1016, 616, 621, 985, 723, 627, 631, 976, + 914, 637, 641, 739, 647, 743, 998, 652, 657, 918, 662, 754, + 668, 672, 759, 678, 764, 1010, 683, 4, 10, 15, 25, 31, + 41, 46, 56, 66, 72, 82, 87, 97, 103, 113, 118, 128, + 138, 144, 154, 159, 169, 175, 185, 190, 200, 210, 216, 226, + 231, 241, 247, 257, 262, 272, 282, 288, 298, 303, 313, 319, + 329, 334, 344, 354, 360, 370, 375, 385, 391, 401, 406, 416, + 426, 432, 442, 447, 457, 463, 473, 478, 488, 498, 504, 514, + 519, 529, 535, 545, 550, 560, 570, 576, 586, 591, 601, 607, + 617, 622, 632, 642, 648, 658, 663, 673, 679, 689, 694, 704, + 714, 720, 730, 735, 745, 751, 761, 766, 776, 786, 792, 802, + 807, 817, 823, 833, 838, 848, 858, 864, 874, 879, 889, 895, + 905, 910, 920, 930, 936, 946, 951, 961, 967, 977, 982, 1015, + 1017, 1021, 1022, 5 +}; + +static const int bmkiller_1025[] = { + 0, 588, 777, 130, 6, 16, 688, 260, 444, 418, 11, 882, + 265, 928, 577, 17, 26, 774, 901, 21, 690, 270, 454, 530, + 145, 27, 36, 693, 160, 31, 937, 280, 992, 1007, 917, 37, + 46, 698, 286, 540, 263, 42, 986, 291, 535, 784, 47, 57, + 608, 656, 834, 52, 703, 296, 739, 278, 58, 67, 972, 702, + 62, 614, 301, 475, 550, 190, 68, 77, 709, 307, 546, 186, + 73, 713, 669, 1000, 201, 78, 88, 317, 561, 196, 83, 892, + 824, 797, 299, 89, 98, 719, 206, 93, 327, 675, 495, 908, + 718, 99, 108, 795, 414, 103, 998, 332, 501, 571, 217, 109, + 118, 896, 830, 970, 222, 114, 724, 685, 506, 912, 119, 129, + 348, 581, 233, 124, 800, 352, 798, 237, 1, 139, 729, 7, + 134, 358, 726, 927, 12, 765, 140, 149, 734, 18, 582, 859, + 22, 902, 695, 996, 767, 150, 28, 780, 964, 32, 155, 916, + 373, 980, 38, 161, 170, 740, 268, 165, 43, 379, 536, 602, + 48, 171, 180, 744, 53, 175, 389, 706, 542, 59, 885, 181, + 63, 815, 393, 612, 781, 69, 968, 399, 547, 782, 191, 74, + 670, 712, 304, 79, 750, 404, 700, 84, 202, 211, 754, 305, + 90, 925, 409, 94, 622, 715, 212, 221, 999, 100, 618, 674, + 104, 760, 929, 794, 319, 110, 232, 938, 633, 891, 227, 115, + 825, 872, 852, 120, 242, 1024, 796, 125, 435, 989, 974, 894, + 131, 243, 252, 135, 340, 247, 805, 440, 141, 643, 721, 253, + 262, 770, 146, 733, 1006, 258, 151, 935, 694, 433, 156, 273, + 455, 653, 523, 162, 775, 944, 166, 862, 274, 283, 932, 376, + 172, 465, 1010, 176, 598, 449, 284, 293, 182, 747, 654, 453, + 289, 785, 187, 849, 543, 294, 192, 821, 1013, 837, 197, 923, + 481, 941, 811, 203, 314, 791, 207, 309, 757, 486, 710, 213, + 406, 315, 324, 942, 947, 218, 900, 496, 966, 223, 489, 325, + 334, 228, 502, 684, 484, 330, 234, 507, 679, 238, 335, 345, + 1003, 764, 422, 244, 856, 512, 248, 680, 346, 355, 801, 254, + 350, 808, 517, 1015, 639, 259, 356, 365, 806, 264, 645, 438, + 361, 269, 803, 835, 943, 366, 275, 533, 650, 279, 371, 952, + 945, 869, 285, 377, 386, 812, 592, 381, 290, 1001, 933, 919, + 295, 387, 396, 816, 300, 391, 788, 548, 922, 306, 478, 397, + 310, 953, 758, 926, 474, 402, 316, 997, 979, 320, 407, 417, + 564, 725, 326, 412, 822, 568, 870, 551, 331, 427, 826, 494, + 336, 574, 823, 911, 341, 722, 428, 437, 877, 347, 686, 853, + 351, 832, 773, 1014, 804, 357, 448, 1005, 691, 520, 443, 362, + 589, 1021, 515, 367, 458, 883, 521, 372, 956, 595, 772, 746, + 378, 459, 468, 382, 638, 463, 605, 867, 890, 388, 903, 469, + 392, 842, 609, 756, 809, 398, 948, 615, 751, 963, 479, 403, + 960, 907, 868, 408, 847, 620, 934, 413, 490, 499, 893, 556, + 419, 955, 625, 423, 766, 906, 500, 509, 429, 630, 762, 1011, + 505, 857, 434, 895, 759, 510, 439, 949, 2, 897, 8, 954, + 880, 13, 1016, 450, 19, 863, 23, 525, 651, 29, 742, 33, + 460, 531, 39, 464, 593, 44, 887, 49, 470, 787, 54, 541, + 60, 958, 64, 841, 818, 70, 480, 975, 75, 607, 485, 80, + 671, 85, 965, 491, 91, 850, 95, 924, 562, 101, 873, 105, + 566, 681, 111, 763, 793, 116, 572, 121, 878, 511, 126, 1008, + 132, 516, 136, 921, 634, 142, 522, 860, 147, 526, 587, 152, + 697, 157, 838, 532, 163, 884, 167, 597, 995, 173, 783, 177, + 649, 603, 183, 888, 664, 188, 978, 193, 789, 552, 198, 613, + 204, 557, 208, 828, 741, 214, 563, 723, 219, 567, 623, 224, + 855, 229, 573, 628, 235, 728, 239, 939, 578, 245, 898, 249, + 583, 861, 255, 957, 3, 9, 644, 14, 991, 594, 20, 24, + 276, 904, 30, 34, 705, 40, 604, 749, 45, 50, 659, 55, + 1009, 61, 65, 665, 71, 1012, 311, 76, 619, 81, 86, 321, + 624, 92, 96, 909, 629, 102, 106, 337, 112, 635, 342, 117, + 122, 914, 127, 990, 133, 137, 983, 143, 363, 984, 148, 368, + 153, 158, 737, 655, 164, 168, 383, 660, 174, 178, 993, 184, + 666, 790, 189, 194, 865, 199, 716, 205, 209, 676, 215, 962, + 420, 220, 424, 225, 230, 430, 736, 236, 240, 940, 731, 246, + 250, 445, 256, 696, 451, 261, 266, 701, 271, 461, 277, 281, + 707, 287, 471, 711, 292, 476, 297, 302, 717, 918, 308, 312, + 492, 959, 318, 322, 950, 328, 727, 831, 333, 338, 732, 343, + 1004, 349, 353, 738, 359, 836, 527, 364, 778, 369, 374, 537, + 748, 380, 384, 752, 886, 390, 394, 553, 400, 846, 558, 405, + 410, 969, 415, 967, 421, 425, 768, 431, 579, 931, 436, 584, + 441, 446, 1020, 779, 452, 456, 599, 813, 462, 466, 982, 472, + 910, 819, 477, 482, 844, 487, 994, 493, 497, 799, 503, 829, + 636, 508, 640, 513, 518, 646, 810, 524, 528, 814, 839, 534, + 538, 661, 544, 820, 667, 549, 554, 976, 559, 677, 565, 569, + 854, 575, 687, 1019, 580, 692, 585, 590, 985, 840, 596, 600, + 708, 845, 606, 610, 973, 616, 851, 1002, 621, 626, 875, 631, + 913, 637, 641, 881, 647, 988, 743, 652, 866, 657, 662, 753, + 871, 668, 672, 981, 876, 678, 682, 769, 4, 10, 15, 25, + 35, 41, 51, 56, 66, 72, 82, 87, 97, 107, 113, 123, + 128, 138, 144, 154, 159, 169, 179, 185, 195, 200, 210, 216, + 226, 231, 241, 251, 257, 267, 272, 282, 288, 298, 303, 313, + 323, 329, 339, 344, 354, 360, 370, 375, 385, 395, 401, 411, + 416, 426, 432, 442, 447, 457, 467, 473, 483, 488, 498, 504, + 514, 519, 529, 539, 545, 555, 560, 570, 576, 586, 591, 601, + 611, 617, 627, 632, 642, 648, 658, 663, 673, 683, 689, 699, + 704, 714, 720, 730, 735, 745, 755, 761, 771, 776, 786, 792, + 802, 807, 817, 827, 833, 843, 848, 858, 864, 874, 879, 889, + 899, 905, 915, 920, 930, 936, 946, 951, 961, 971, 977, 987, + 1017, 1018, 1022, 1023, 5 +}; + +static const int bmkiller_4095[] = { + 0, 1026, 3946, 3997, 6, 15, 3585, 1411, 10, 3878, 1030, 2052, + 3080, 520, 16, 25, 3077, 3507, 20, 2567, 2761, 2057, 1765, 2757, + 26, 35, 2739, 2352, 3330, 3656, 31, 2744, 2356, 2072, 2315, 36, + 46, 3226, 2067, 2545, 41, 3083, 3332, 2573, 3654, 47, 56, 2749, + 3211, 51, 3592, 1061, 1786, 2320, 2767, 57, 66, 3087, 570, 61, + 1071, 3954, 3338, 1790, 565, 67, 76, 2755, 3230, 1796, 1777, 72, + 2759, 2596, 3428, 3711, 77, 87, 1082, 2948, 4087, 82, 3093, 1087, + 3906, 1462, 88, 97, 2765, 3600, 92, 1092, 2592, 2093, 1806, 592, + 98, 107, 3604, 1098, 3524, 2783, 103, 3098, 2607, 3597, 611, 108, + 118, 1108, 3764, 3337, 113, 2770, 3660, 2113, 2360, 119, 128, 3103, + 2355, 123, 3358, 2393, 3348, 2108, 3227, 129, 138, 2775, 2940, 133, + 3725, 1123, 1832, 3880, 3664, 139, 148, 2780, 1129, 3812, 633, 144, + 3108, 3353, 3602, 3124, 149, 159, 3246, 1842, 643, 154, 4001, 2618, + 2134, 2581, 160, 169, 2786, 3995, 164, 3462, 3603, 2129, 1848, 663, + 170, 179, 2790, 2413, 3121, 3237, 175, 3118, 3544, 2144, 3606, 180, + 190, 3813, 2139, 2808, 185, 3615, 2628, 3257, 674, 191, 200, 2796, + 1849, 195, 4052, 1170, 2154, 2391, 2823, 201, 210, 2800, 2974, 205, + 1180, 3914, 1873, 2149, 3935, 211, 220, 3667, 2639, 2392, 704, 216, + 2806, 3139, 3852, 3456, 221, 231, 1190, 1883, 714, 226, 3129, 1195, + 3454, 4045, 232, 241, 3545, 715, 236, 1201, 3612, 2165, 1889, 1561, + 242, 251, 2811, 1205, 2994, 3461, 247, 2816, 1211, 1899, 2171, 252, + 262, 1215, 3885, 2834, 257, 3549, 3272, 2185, 745, 263, 272, 2821, + 3675, 267, 2668, 2454, 1909, 2180, 1167, 273, 282, 3938, 3729, 277, + 3915, 1231, 2195, 3937, 3155, 283, 292, 2827, 1236, 3625, 2665, 288, + 2831, 3467, 3464, 3827, 293, 303, 1246, 3152, 3782, 298, 3555, 3026, + 2206, 1602, 304, 313, 2837, 786, 308, 2674, 3553, 2201, 1930, 781, + 314, 323, 3857, 3031, 3689, 3130, 319, 3822, 2680, 1940, 1208, 324, + 334, 2480, 2211, 3547, 329, 2842, 3685, 2682, 1622, 335, 344, 3626, + 1627, 339, 3389, 1277, 1950, 2857, 808, 345, 354, 2847, 3476, 349, + 1287, 2490, 3566, 2221, 3477, 355, 364, 2852, 3042, 2463, 3627, 360, + 3894, 2695, 3475, 2459, 365, 375, 1298, 3994, 3471, 370, 3165, 1303, + 3479, 3491, 376, 385, 2858, 3012, 380, 1308, 2700, 2237, 3788, 2884, + 386, 395, 2862, 1314, 1976, 849, 391, 3170, 2510, 3633, 1663, 396, + 406, 1324, 2474, 859, 401, 4022, 3745, 1986, 3169, 407, 416, 2868, + 3694, 411, 3896, 3751, 1992, 2252, 879, 417, 426, 2872, 3190, 421, + 2521, 1339, 2267, 1996, 880, 427, 436, 3636, 1345, 3570, 2890, 432, + 2878, 3639, 3638, 899, 437, 447, 3924, 3051, 3697, 442, 4008, 2531, + 2278, 2504, 448, 457, 3186, 2499, 452, 3837, 3313, 2273, 3750, 3299, + 458, 467, 2883, 2537, 2017, 920, 463, 2888, 2541, 2288, 2280, 468, + 478, 3647, 2283, 930, 473, 3580, 2736, 2027, 1719, 479, 488, 2893, + 931, 483, 2915, 1386, 2033, 2509, 3586, 489, 498, 3196, 3572, 493, + 1396, 3948, 2743, 2037, 951, 499, 508, 2899, 2746, 2043, 3309, 504, + 2903, 3430, 3500, 3053, 509, 519, 1406, 1, 2916, 514, 3201, 7, + 3649, 962, 11, 529, 2909, 1353, 524, 1417, 17, 2309, 2053, 21, + 530, 539, 4064, 1421, 27, 1756, 535, 3206, 1427, 3843, 32, 540, + 550, 1431, 37, 3319, 545, 2914, 42, 2329, 3930, 551, 560, 48, + 1002, 555, 52, 2578, 2074, 2324, 997, 561, 58, 2919, 1003, 62, + 3432, 1447, 2339, 2078, 68, 571, 580, 2924, 1452, 2084, 73, 576, + 3217, 2946, 78, 3987, 581, 591, 83, 3092, 2778, 586, 3596, 89, + 2350, 1033, 93, 601, 2930, 4049, 596, 99, 3231, 2345, 2094, 3202, + 602, 104, 2934, 2598, 3437, 109, 607, 4016, 4032, 114, 2568, 612, + 622, 3349, 120, 2571, 617, 124, 3517, 2789, 2952, 623, 632, 130, + 3084, 627, 134, 1493, 2370, 3532, 3224, 140, 642, 2944, 1074, 637, + 1503, 145, 2120, 2365, 1069, 150, 652, 3848, 3445, 155, 1455, 648, + 2950, 2812, 161, 3970, 653, 165, 1514, 2130, 4011, 658, 171, 1519, + 3526, 1838, 664, 673, 176, 1843, 668, 1524, 181, 2381, 2136, 1096, + 186, 683, 2955, 1530, 4048, 192, 679, 2960, 196, 3669, 1115, 684, + 694, 1540, 202, 3773, 689, 206, 3672, 2401, 3884, 695, 212, 2965, + 3114, 699, 3886, 2640, 217, 2396, 3964, 705, 222, 3728, 3109, 709, + 227, 1555, 2161, 2608, 2983, 233, 724, 2971, 237, 3128, 1137, 720, + 2975, 243, 3536, 1879, 725, 735, 3370, 248, 1147, 730, 3955, 253, + 2422, 3936, 736, 258, 2981, 3608, 740, 3149, 264, 2417, 2177, 268, + 746, 755, 4094, 3268, 3138, 274, 751, 3262, 278, 2187, 3125, 756, + 766, 284, 2427, 4028, 761, 2986, 2844, 289, 1178, 767, 776, 294, + 4002, 771, 3732, 299, 2197, 3731, 4030, 777, 305, 2991, 2643, 309, + 1612, 2675, 2851, 2437, 315, 787, 796, 2996, 2855, 3821, 320, 792, + 3682, 3018, 325, 2658, 797, 807, 330, 3858, 1218, 802, 3273, 336, + 3551, 1935, 340, 817, 3002, 1219, 812, 1633, 346, 2453, 2218, 350, + 818, 827, 3006, 1637, 356, 3028, 823, 3278, 1643, 2228, 361, 828, + 838, 1647, 366, 1951, 833, 3688, 371, 2473, 1249, 839, 848, 377, + 3024, 843, 381, 2701, 2238, 2468, 1600, 387, 858, 3016, 3687, 853, + 3893, 392, 2483, 2679, 3039, 397, 868, 3739, 1668, 402, 1972, 864, + 3022, 4029, 408, 2689, 869, 412, 1678, 3296, 3156, 874, 3793, 418, + 2494, 2886, 422, 889, 3293, 1290, 884, 428, 3642, 2489, 3291, 1285, + 890, 433, 3027, 2722, 2264, 438, 895, 3032, 2726, 443, 1641, 900, + 910, 3701, 449, 3746, 905, 453, 3963, 2274, 3493, 911, 459, 3037, + 3050, 915, 3497, 1709, 464, 3922, 1312, 921, 469, 3303, 3747, 925, + 474, 2906, 3980, 2284, 1671, 480, 940, 3043, 484, 3634, 3409, 936, + 3047, 2911, 490, 3290, 941, 494, 1730, 3195, 2715, 946, 500, 1735, + 3898, 3060, 952, 961, 505, 3181, 956, 1740, 510, 2525, 3835, 4058, + 515, 971, 3703, 1746, 2305, 521, 967, 3314, 525, 3705, 2922, 972, + 982, 531, 3802, 1363, 977, 3058, 3708, 536, 2896, 983, 992, 541, + 3644, 987, 3757, 546, 2321, 2540, 1383, 993, 552, 3063, 2059, 556, + 2768, 1771, 2555, 2325, 1384, 562, 1012, 3068, 566, 2331, 2065, 1008, + 3324, 572, 3710, 1403, 1013, 1023, 3090, 577, 3968, 1018, 3807, 582, + 2566, 4071, 1024, 587, 3074, 3512, 1028, 3436, 593, 2561, 2341, 597, + 1034, 1043, 3078, 2784, 603, 1424, 1039, 3334, 2788, 2576, 608, 1044, + 1054, 3875, 613, 1434, 1049, 3662, 618, 3442, 2953, 1055, 1064, 624, + 1435, 1059, 628, 1818, 2362, 3706, 2100, 1065, 634, 3088, 3766, 638, + 1828, 3242, 2959, 2366, 644, 1075, 1084, 3769, 2962, 2372, 649, 1080, + 3094, 3911, 654, 3218, 1085, 1095, 659, 3236, 3234, 1090, 3345, 665, + 3598, 1466, 669, 1105, 3973, 2077, 1100, 675, 3355, 2597, 2382, 2973, + 1106, 680, 3099, 1853, 3668, 685, 1111, 3104, 1859, 690, 2603, 1116, + 1126, 1863, 696, 3228, 1121, 700, 3726, 2617, 2141, 1127, 1136, 706, + 1506, 1131, 710, 2825, 4034, 2612, 1501, 716, 1146, 3673, 1507, 1141, + 3131, 721, 2408, 2797, 3365, 726, 1156, 3115, 1884, 731, 3127, 1152, + 3119, 3775, 737, 4019, 1157, 741, 1894, 2418, 2167, 1162, 747, 3738, + 2638, 1537, 1168, 1177, 752, 3132, 1172, 2999, 757, 2633, 2424, 3958, + 762, 1187, 4082, 2845, 3546, 768, 1183, 4026, 772, 2648, 2419, 1188, + 1198, 3473, 778, 2978, 1193, 782, 3548, 3005, 3265, 1199, 788, 3683, + 3253, 1203, 3736, 1925, 793, 2824, 3780, 1209, 798, 3135, 1578, 1213, + 803, 3632, 2449, 2653, 1573, 809, 1228, 3140, 813, 3621, 1888, 1224, + 4073, 819, 3619, 3474, 1229, 1239, 1946, 824, 3680, 1234, 3381, 829, + 3623, 3369, 1240, 834, 3146, 3961, 1244, 1956, 840, 2669, 2465, 844, + 1250, 1259, 3150, 1962, 3282, 850, 1255, 3386, 854, 2475, 1619, 1260, + 1270, 860, 3942, 1928, 1265, 3693, 3163, 865, 2864, 1271, 1280, 870, + 2859, 1275, 3574, 875, 2485, 2684, 3274, 1281, 881, 3160, 4023, 885, + 3834, 1987, 2699, 3631, 891, 1291, 1300, 3744, 1993, 3992, 896, 1296, + 3166, 3569, 901, 3406, 1301, 1311, 906, 3921, 1651, 1306, 3699, 912, + 2710, 3289, 916, 1321, 3402, 3691, 1316, 3648, 922, 2705, 2506, 926, + 1322, 1331, 3171, 4009, 932, 3489, 1327, 3176, 3652, 2516, 937, 1332, + 1342, 2912, 942, 3306, 1337, 3759, 947, 3504, 1682, 1343, 1352, 953, + 2511, 1347, 957, 2034, 2526, 2895, 2291, 963, 1362, 3412, 3049, 1357, + 2044, 968, 3067, 2725, 4037, 973, 1372, 3187, 3071, 978, 1712, 1368, + 3191, 3400, 984, 3698, 1373, 988, 2054, 3704, 1722, 1378, 3417, 994, + 3756, 3577, 998, 1393, 3197, 1723, 1388, 1004, 4047, 2741, 3926, 2316, + 1394, 1009, 3934, 2069, 2552, 1014, 1399, 3422, 2075, 1019, 2747, 1404, + 1414, 2079, 1025, 3810, 1409, 1029, 3715, 2562, 1753, 1415, 1035, 3427, + 3996, 1419, 3100, 3091, 1040, 2756, 2293, 1425, 1045, 3207, 3874, 1429, + 1050, 2095, 2771, 2572, 3929, 1056, 1444, 3212, 1060, 3714, 3097, 1440, + 3433, 3666, 1066, 3221, 1445, 1070, 2110, 3339, 3325, 1450, 1076, 2963, + 2782, 2357, 1456, 1465, 1081, 1794, 1460, 3106, 1086, 2777, 3435, 1789, + 1091, 1475, 3222, 2969, 2593, 1097, 1471, 3905, 1101, 2792, 3073, 1476, + 1486, 1107, 2787, 3716, 1481, 3443, 3235, 1112, 2378, 1487, 1496, 1117, + 2383, 1491, 3605, 1122, 2609, 3877, 1816, 1497, 1128, 3232, 3240, 1132, + 2151, 3122, 3539, 2613, 2104, 1138, 1516, 4083, 1142, 2619, 3771, 1512, + 3238, 1148, 3988, 2123, 1517, 1527, 2162, 1153, 3350, 1522, 3453, 1158, + 3670, 3723, 1528, 1163, 3730, 3535, 1532, 2172, 1169, 2813, 2629, 1173, + 1538, 1547, 3243, 2178, 1179, 1857, 1543, 3248, 3004, 3777, 1184, 1548, + 1558, 2188, 1189, 1867, 1553, 3734, 1194, 2833, 3457, 1559, 1568, 1200, + 3818, 1563, 1204, 3010, 2650, 2828, 1887, 1569, 1210, 4077, 3266, 1214, + 4035, 2203, 2843, 2654, 1220, 1579, 1588, 3259, 2209, 2660, 1225, 1584, + 3263, 3783, 1230, 1907, 1589, 1599, 1235, 3380, 3916, 1594, 3740, 1241, + 2854, 3008, 1245, 1609, 3269, 3003, 1604, 1251, 3560, 2849, 2670, 3831, + 1610, 1256, 4051, 3030, 3481, 1261, 1615, 3478, 3396, 1266, 2856, 1620, + 1630, 3484, 1272, 1938, 1625, 1276, 3168, 3565, 2476, 1631, 1640, 1282, + 1939, 1635, 1286, 2250, 2874, 3013, 3287, 1292, 1650, 3279, 3960, 1645, + 2260, 1297, 2696, 2869, 1959, 1302, 1660, 3284, 3178, 1307, 3561, 1656, + 3791, 3646, 1313, 3792, 1661, 1317, 2270, 2706, 3692, 1666, 1323, 2275, + 3695, 1970, 1672, 1681, 1328, 3983, 1676, 2281, 1333, 2885, 2712, 2507, + 1338, 1691, 3294, 2285, 3800, 1344, 1687, 3494, 1348, 3945, 2891, 1692, + 1702, 2295, 1354, 3397, 1697, 1358, 3798, 2905, 3307, 1703, 1364, 3300, + 2010, 1707, 3199, 3072, 1369, 2900, 2005, 1713, 1374, 3304, 2011, 1717, + 1379, 2311, 2737, 3183, 2532, 1385, 1732, 4042, 1389, 3416, 3419, 1728, + 3310, 1395, 4076, 3584, 1733, 1743, 2326, 1400, 3210, 1738, 3801, 1405, + 2926, 2041, 1744, 1410, 3509, 3966, 1748, 3215, 1416, 2921, 2753, 1420, + 1754, 1763, 3315, 3804, 3426, 1426, 1759, 3320, 1430, 2763, 3967, 1764, + 1774, 1436, 2931, 3075, 1769, 3515, 3803, 1441, 3869, 1775, 1784, 1446, + 3842, 1779, 3808, 1451, 2773, 3998, 3713, 1785, 1457, 3519, 2082, 1461, + 2367, 3107, 3772, 2941, 1467, 1795, 1804, 3331, 3661, 3085, 1472, 1800, + 3335, 3244, 1477, 3762, 1805, 1815, 1482, 3589, 3763, 1810, 3525, 1488, + 4012, 2594, 1492, 1825, 3341, 2599, 1820, 2388, 1498, 2957, 2794, 1502, + 1826, 1835, 3820, 2394, 1508, 2604, 1831, 3530, 3255, 2804, 1513, 1836, + 1846, 2404, 1518, 2361, 1841, 3346, 1523, 2977, 3849, 1847, 1856, 1529, + 3447, 1851, 1533, 3133, 2814, 2972, 4070, 1539, 1866, 3351, 3444, 1861, + 3977, 1544, 2987, 3112, 3451, 1549, 1876, 3356, 2425, 1554, 2145, 1872, + 3540, 3677, 1560, 2635, 1877, 1564, 3617, 3957, 2155, 1882, 3991, 1570, + 2998, 3956, 1574, 1897, 3362, 3854, 1892, 1580, 3819, 2993, 4057, 2175, + 1898, 1585, 3366, 3154, 2840, 1590, 1903, 3550, 3158, 1595, 3618, 1908, + 1918, 3786, 1601, 3823, 1913, 1605, 3276, 2850, 2186, 1919, 1611, 3372, + 2432, 1923, 3379, 2466, 1616, 3778, 3826, 1929, 1621, 3376, 3147, 1933, + 1626, 3890, 3283, 2860, 4079, 1632, 1948, 3986, 1636, 3748, 2216, 1944, + 3382, 3979, 1642, 3162, 1949, 1646, 2486, 3483, 2226, 1954, 1652, 2491, + 3742, 2692, 1960, 1969, 1657, 2227, 1964, 2497, 1662, 3029, 3962, 3394, + 1667, 1979, 3387, 2501, 2881, 1673, 1975, 3392, 1677, 4081, 3035, 1980, + 1990, 1683, 3985, 2707, 1985, 3796, 3707, 1688, 2257, 1991, 2000, 1693, + 4044, 1995, 3316, 1698, 2897, 3044, 3405, 2001, 1704, 4010, 3635, 1708, + 3200, 2527, 3059, 2901, 2723, 1714, 2020, 3403, 1718, 2907, 2727, 2016, + 3407, 1724, 3752, 3193, 2021, 2031, 2542, 1729, 3643, 2026, 3900, 1734, + 3070, 3318, 2032, 1739, 3413, 2298, 2036, 3322, 1745, 3065, 2917, 1749, + 2042, 2051, 3965, 3216, 1755, 3503, 2047, 2, 3220, 8, 1760, 12, + 2062, 3845, 18, 4063, 22, 3418, 1770, 28, 2758, 2063, 33, 1776, + 4014, 38, 1780, 43, 2938, 3760, 49, 2073, 53, 3423, 3653, 59, + 2583, 63, 4039, 2942, 69, 2083, 2092, 74, 3811, 79, 1801, 2088, + 84, 3343, 90, 3323, 94, 2103, 1811, 100, 3219, 2098, 105, 1817, + 3767, 110, 1821, 115, 3434, 3516, 121, 1827, 125, 3101, 2958, 131, + 2114, 135, 3438, 2610, 141, 1837, 2119, 146, 3850, 151, 3354, 2124, + 156, 2620, 162, 2371, 166, 1852, 3817, 172, 4090, 2135, 177, 1858, + 4066, 182, 1862, 187, 3908, 3116, 193, 1868, 197, 3448, 2815, 203, + 3678, 207, 2984, 4003, 213, 1878, 2164, 218, 2641, 223, 2820, 2160, + 228, 3855, 234, 2411, 238, 1893, 4091, 244, 3538, 2170, 249, 3556, + 3142, 254, 2176, 259, 1904, 3816, 265, 3733, 269, 3137, 3000, 275, + 1914, 279, 3459, 3277, 285, 1920, 2191, 290, 1924, 295, 3144, 2196, + 300, 4017, 306, 2442, 310, 1934, 3384, 316, 3385, 2207, 321, 3469, + 2443, 326, 3941, 331, 1945, 3931, 337, 2217, 341, 3628, 3824, 347, + 1955, 351, 3025, 3157, 357, 1961, 2236, 362, 1965, 367, 4074, 2232, + 372, 1971, 378, 3557, 382, 2247, 2702, 388, 3891, 2242, 393, 1981, + 3865, 398, 2248, 403, 3485, 3741, 409, 2713, 413, 3173, 3041, 419, + 2258, 423, 4068, 2717, 429, 2002, 2263, 434, 2006, 439, 3179, 2268, + 444, 2012, 450, 4027, 454, 3490, 3870, 460, 2898, 2279, 465, 2022, + 2514, 470, 3415, 475, 3061, 3188, 481, 2289, 485, 3495, 2515, 491, + 3755, 495, 3203, 3301, 501, 2299, 2308, 506, 2748, 511, 2048, 2304, + 516, 3901, 522, 4080, 526, 2319, 2058, 532, 2923, 2314, 537, 2064, + 3214, 542, 2068, 547, 3506, 3832, 553, 3431, 557, 3209, 3082, 563, + 2330, 567, 3510, 3876, 573, 4069, 2335, 578, 3847, 583, 2089, 2340, + 588, 3344, 594, 4060, 598, 3659, 2099, 604, 3971, 2351, 609, 2105, + 3588, 614, 2109, 619, 3102, 3328, 625, 2115, 629, 3520, 2586, 635, + 2799, 639, 3770, 3229, 645, 2125, 2380, 650, 3724, 655, 3721, 2376, + 660, 3460, 666, 3529, 670, 2140, 2810, 676, 3910, 2386, 681, 2146, + 3814, 686, 2150, 691, 3853, 3674, 697, 2156, 701, 3245, 4089, 707, + 2402, 711, 3531, 2826, 717, 2166, 2407, 722, 3374, 727, 2627, 2412, + 732, 2836, 738, 2967, 742, 2181, 3679, 748, 3368, 2423, 753, 3541, + 3363, 758, 3790, 763, 2192, 3260, 769, 2433, 773, 4053, 3613, 779, + 2202, 783, 3275, 3148, 789, 2208, 2452, 794, 2212, 799, 2649, 2448, + 804, 3785, 810, 3554, 814, 2222, 3939, 820, 2659, 2458, 825, 3395, + 3286, 830, 2464, 835, 2233, 3860, 841, 3833, 845, 3281, 4062, 851, + 2243, 855, 3923, 3401, 861, 2249, 2479, 866, 2253, 871, 3629, 2484, + 876, 2259, 882, 3564, 886, 3562, 3492, 892, 2690, 2495, 897, 2269, + 2865, 902, 4061, 907, 3185, 3399, 913, 2505, 917, 3567, 3482, 923, + 2908, 927, 3499, 3189, 933, 2290, 2524, 938, 2294, 943, 2720, 2520, + 948, 2300, 954, 4020, 958, 2535, 2918, 964, 2730, 2530, 969, 2310, + 3839, 974, 2536, 979, 3578, 2731, 985, 2929, 989, 3317, 3205, 995, + 2546, 999, 3582, 2933, 1005, 3927, 2551, 1010, 2939, 1015, 2336, 2556, + 1020, 2943, 3, 4050, 9, 13, 2346, 1036, 19, 23, 1041, 29, + 3851, 1046, 34, 1051, 39, 44, 1057, 2577, 50, 54, 2936, 1067, + 60, 64, 3347, 70, 1077, 2587, 75, 80, 2964, 85, 2377, 91, + 95, 3657, 101, 3873, 1102, 106, 2387, 111, 116, 2602, 1113, 122, + 126, 1118, 2397, 132, 136, 2802, 142, 2403, 1133, 147, 152, 1139, + 157, 1143, 163, 167, 1149, 173, 2623, 1154, 178, 1159, 183, 188, + 1164, 3917, 194, 198, 1174, 2428, 204, 208, 3134, 214, 1185, 2434, + 219, 224, 2438, 229, 3378, 235, 239, 2444, 245, 3735, 4067, 250, + 3015, 255, 260, 3373, 1221, 266, 270, 1226, 3690, 276, 280, 2664, + 286, 3559, 1242, 291, 296, 2469, 301, 1252, 307, 311, 1257, 317, + 4007, 1262, 322, 1267, 327, 332, 1273, 3036, 338, 342, 3288, 1283, + 348, 352, 3919, 358, 1293, 2496, 363, 368, 2500, 373, 3175, 379, + 383, 3052, 389, 2875, 1318, 394, 3872, 399, 404, 2711, 1329, 410, + 414, 1334, 3867, 420, 424, 3404, 430, 2721, 1349, 435, 440, 1355, + 445, 1359, 451, 455, 1365, 461, 2740, 1370, 466, 1375, 471, 476, + 1380, 2547, 482, 486, 1390, 2751, 492, 496, 3841, 502, 1401, 2557, + 507, 512, 2752, 517, 3650, 523, 527, 3806, 533, 3425, 3329, 538, + 2762, 543, 548, 3595, 1437, 554, 558, 1442, 2582, 564, 568, 2772, + 574, 2588, 1458, 579, 584, 3909, 589, 1468, 595, 599, 1473, 605, + 2947, 1478, 610, 1483, 615, 620, 1489, 2793, 626, 630, 3907, 1499, + 636, 640, 3607, 646, 1509, 2803, 651, 656, 3610, 661, 2624, 667, + 671, 3862, 677, 3722, 1534, 682, 2634, 687, 692, 2818, 1545, 698, + 702, 1550, 2644, 708, 712, 3361, 718, 3145, 1565, 723, 728, 1571, + 733, 1575, 739, 743, 1581, 749, 2839, 1586, 754, 1591, 759, 764, + 1596, 3159, 770, 774, 1606, 4065, 780, 784, 3787, 790, 1617, 2681, + 795, 800, 2685, 805, 3390, 811, 815, 2691, 821, 3920, 3019, 826, + 4038, 831, 836, 3616, 1653, 842, 846, 1658, 3180, 852, 856, 2880, + 862, 4021, 1674, 867, 872, 2716, 877, 1684, 883, 887, 1689, 893, + 3502, 1694, 898, 1699, 903, 908, 1705, 2732, 914, 918, 3795, 1715, + 924, 928, 4075, 934, 1725, 2742, 939, 944, 3590, 949, 3794, 955, + 959, 3882, 965, 3579, 1750, 970, 3903, 975, 980, 2927, 1761, 986, + 990, 1766, 3952, 996, 1000, 4006, 1006, 2937, 1781, 1011, 1016, 1787, + 1021, 1791, 1027, 1031, 1797, 1037, 2956, 1802, 1042, 1807, 1047, 1052, + 1812, 3676, 1058, 1062, 1822, 2798, 1068, 1072, 3932, 1078, 1833, 3247, + 1083, 1088, 2968, 1093, 2809, 1099, 1103, 3252, 1109, 3533, 4004, 1114, + 2819, 1119, 1124, 3258, 1869, 1130, 1134, 1874, 2829, 1140, 1144, 2988, + 1150, 2835, 1890, 1155, 1160, 3940, 1165, 1900, 1171, 1175, 1905, 1181, + 3904, 1910, 1186, 1915, 1191, 1196, 1921, 3009, 1202, 1206, 3859, 1931, + 1212, 1216, 3563, 1222, 1941, 2866, 1227, 1232, 2870, 1237, 3153, 1243, + 1247, 2876, 1253, 3391, 1966, 1258, 3864, 1263, 1268, 3034, 1977, 1274, + 1278, 1982, 3040, 1284, 1288, 3982, 1294, 3797, 1997, 1299, 1304, 2003, + 1309, 2007, 1315, 1319, 2013, 1325, 3055, 2018, 1330, 2023, 1335, 1340, + 2028, 3899, 1346, 1350, 2038, 3950, 1356, 1360, 3194, 1366, 2049, 2928, + 1371, 1376, 2932, 1381, 3514, 1387, 1391, 3081, 1397, 3844, 3651, 1402, + 3340, 1407, 1412, 3518, 2085, 1418, 1422, 2090, 3719, 1428, 1432, 3096, + 1438, 4085, 2106, 1443, 1448, 3111, 1453, 2116, 1459, 1463, 2121, 1469, + 3972, 2126, 1474, 2131, 1479, 1484, 2137, 2979, 1490, 1494, 3534, 2147, + 1500, 1504, 4078, 1510, 2157, 2989, 1515, 1520, 3371, 1525, 3611, 1531, + 1535, 3375, 1541, 3463, 2182, 1546, 3889, 1551, 1556, 3143, 2193, 1562, + 1566, 2198, 3014, 1572, 1576, 3620, 1582, 3020, 2213, 1587, 1592, 2219, + 1597, 2223, 1603, 1607, 2229, 1613, 3172, 2234, 1618, 2239, 1623, 1628, + 2244, 3978, 1634, 1638, 2254, 3045, 1644, 1648, 3829, 1654, 2265, 3838, + 1659, 1664, 3184, 1669, 3056, 1675, 1679, 3754, 1685, 3641, 3576, 1690, + 3066, 1695, 1700, 3709, 2301, 1706, 1710, 2306, 3076, 1716, 1720, 3204, + 1726, 3989, 2322, 1731, 1736, 3086, 1741, 2332, 1747, 1751, 2337, 1757, + 3879, 2342, 1762, 2347, 1767, 1772, 2353, 3225, 1778, 1782, 4054, 2363, + 1788, 1792, 3601, 1798, 2373, 3113, 1803, 1808, 3117, 1813, 3913, 1819, + 1823, 3123, 1829, 3720, 2398, 1834, 3458, 1839, 1844, 3250, 2409, 1850, + 1854, 2414, 3256, 1860, 1864, 4084, 1870, 3468, 2429, 1875, 1880, 2435, + 1885, 2439, 1891, 1895, 2445, 1901, 3271, 2450, 1906, 2455, 1911, 1916, + 2460, 3164, 1922, 1926, 2470, 3981, 1932, 1936, 3976, 1942, 2481, 3174, + 1947, 1952, 3895, 1957, 3637, 1963, 1967, 3297, 1973, 4043, 3571, 1978, + 3925, 1983, 1988, 3828, 2517, 1994, 1998, 2522, 3505, 2004, 2008, 3312, + 2014, 3999, 2538, 2019, 2024, 3327, 2029, 2548, 2035, 2039, 2553, 2045, + 3718, 2558, 2050, 2563, 2055, 2060, 2569, 3949, 2066, 2070, 3658, 2579, + 2076, 2080, 4072, 2086, 2589, 3440, 2091, 2096, 4013, 2101, 3241, 2107, + 2111, 3776, 2117, 3450, 2614, 2122, 3251, 2127, 2132, 3359, 2625, 2138, + 2142, 2630, 3261, 2148, 2152, 3805, 2158, 3267, 2645, 2163, 2168, 2651, + 2173, 2655, 2179, 2183, 2661, 2189, 3388, 2666, 2194, 2671, 2199, 2204, + 2676, 4055, 2210, 2214, 2686, 3292, 2220, 2224, 4033, 2230, 2697, 3298, + 2235, 2240, 3302, 2245, 3866, 2251, 2255, 3308, 2261, 3749, 4040, 2266, + 3410, 2271, 2276, 3581, 2733, 2282, 2286, 2738, 3587, 2292, 2296, 3420, + 2302, 3591, 2754, 2307, 2312, 3333, 2317, 2764, 2323, 2327, 2769, 2333, + 3522, 2774, 2338, 2779, 2343, 2348, 2785, 3441, 2354, 2358, 3523, 2795, + 2364, 2368, 3779, 2374, 2805, 3360, 2379, 2384, 3364, 2389, 3892, 2395, + 2399, 3883, 2405, 3975, 2830, 2410, 3622, 2415, 2420, 3466, 2841, 2426, + 2430, 2846, 3472, 2436, 2440, 3888, 2446, 3863, 2861, 2451, 2456, 2867, + 2461, 2871, 2467, 2471, 2877, 2477, 3487, 2882, 2482, 2887, 2487, 2492, + 2892, 3411, 2498, 2502, 2902, 3947, 2508, 2512, 3944, 2518, 2913, 3421, + 2523, 2528, 4024, 2533, 3761, 2539, 2543, 3513, 2549, 3951, 3594, 2554, + 3663, 2559, 2564, 3765, 2949, 2570, 2574, 2954, 3446, 2580, 2584, 3528, + 2590, 3452, 2970, 2595, 2600, 3543, 2605, 2980, 2611, 2615, 2985, 2621, + 4059, 2990, 2626, 2995, 2631, 2636, 3001, 3684, 2642, 2646, 3781, 3011, + 2652, 2656, 4036, 2662, 3021, 4018, 2667, 2672, 3868, 2677, 3488, 2683, + 2687, 3700, 2693, 3993, 3046, 2698, 3498, 2703, 2708, 3575, 3057, 2714, + 2718, 3062, 3508, 2724, 2728, 3836, 2734, 4, 14, 24, 30, 40, + 45, 55, 65, 71, 81, 86, 96, 102, 112, 117, 127, 137, + 143, 153, 158, 168, 174, 184, 189, 199, 209, 215, 225, 230, + 240, 246, 256, 261, 271, 281, 287, 297, 302, 312, 318, 328, + 333, 343, 353, 359, 369, 374, 384, 390, 400, 405, 415, 425, + 431, 441, 446, 456, 462, 472, 477, 487, 497, 503, 513, 518, + 528, 534, 544, 549, 559, 569, 575, 585, 590, 600, 606, 616, + 621, 631, 641, 647, 657, 662, 672, 678, 688, 693, 703, 713, + 719, 729, 734, 744, 750, 760, 765, 775, 785, 791, 801, 806, + 816, 822, 832, 837, 847, 857, 863, 873, 878, 888, 894, 904, + 909, 919, 929, 935, 945, 950, 960, 966, 976, 981, 991, 1001, + 1007, 1017, 1022, 1032, 1038, 1048, 1053, 1063, 1073, 1079, 1089, 1094, + 1104, 1110, 1120, 1125, 1135, 1145, 1151, 1161, 1166, 1176, 1182, 1192, + 1197, 1207, 1217, 1223, 1233, 1238, 1248, 1254, 1264, 1269, 1279, 1289, + 1295, 1305, 1310, 1320, 1326, 1336, 1341, 1351, 1361, 1367, 1377, 1382, + 1392, 1398, 1408, 1413, 1423, 1433, 1439, 1449, 1454, 1464, 1470, 1480, + 1485, 1495, 1505, 1511, 1521, 1526, 1536, 1542, 1552, 1557, 1567, 1577, + 1583, 1593, 1598, 1608, 1614, 1624, 1629, 1639, 1649, 1655, 1665, 1670, + 1680, 1686, 1696, 1701, 1711, 1721, 1727, 1737, 1742, 1752, 1758, 1768, + 1773, 1783, 1793, 1799, 1809, 1814, 1824, 1830, 1840, 1845, 1855, 1865, + 1871, 1881, 1886, 1896, 1902, 1912, 1917, 1927, 1937, 1943, 1953, 1958, + 1968, 1974, 1984, 1989, 1999, 2009, 2015, 2025, 2030, 2040, 2046, 2056, + 2061, 2071, 2081, 2087, 2097, 2102, 2112, 2118, 2128, 2133, 2143, 2153, + 2159, 2169, 2174, 2184, 2190, 2200, 2205, 2215, 2225, 2231, 2241, 2246, + 2256, 2262, 2272, 2277, 2287, 2297, 2303, 2313, 2318, 2328, 2334, 2344, + 2349, 2359, 2369, 2375, 2385, 2390, 2400, 2406, 2416, 2421, 2431, 2441, + 2447, 2457, 2462, 2472, 2478, 2488, 2493, 2503, 2513, 2519, 2529, 2534, + 2544, 2550, 2560, 2565, 2575, 2585, 2591, 2601, 2606, 2616, 2622, 2632, + 2637, 2647, 2657, 2663, 2673, 2678, 2688, 2694, 2704, 2709, 2719, 2729, + 2735, 2745, 2750, 2760, 2766, 2776, 2781, 2791, 2801, 2807, 2817, 2822, + 2832, 2838, 2848, 2853, 2863, 2873, 2879, 2889, 2894, 2904, 2910, 2920, + 2925, 2935, 2945, 2951, 2961, 2966, 2976, 2982, 2992, 2997, 3007, 3017, + 3023, 3033, 3038, 3048, 3054, 3064, 3069, 3079, 3089, 3095, 3105, 3110, + 3120, 3126, 3136, 3141, 3151, 3161, 3167, 3177, 3182, 3192, 3198, 3208, + 3213, 3223, 3233, 3239, 3249, 3254, 3264, 3270, 3280, 3285, 3295, 3305, + 3311, 3321, 3326, 3336, 3342, 3352, 3357, 3367, 3377, 3383, 3393, 3398, + 3408, 3414, 3424, 3429, 3439, 3449, 3455, 3465, 3470, 3480, 3486, 3496, + 3501, 3511, 3521, 3527, 3537, 3542, 3552, 3558, 3568, 3573, 3583, 3593, + 3599, 3609, 3614, 3624, 3630, 3640, 3645, 3655, 3665, 3671, 3681, 3686, + 3696, 3702, 3712, 3717, 3727, 3737, 3743, 3753, 3758, 3768, 3774, 3784, + 3789, 3799, 3809, 3815, 3825, 3830, 3840, 3846, 3856, 3861, 3871, 3881, + 3887, 3897, 3902, 3912, 3918, 3928, 3933, 3943, 3953, 3959, 3969, 3974, + 3984, 3990, 4000, 4005, 4015, 4025, 4031, 4041, 4046, 4056, 4086, 4088, + 4092, 4093, 5 +}; + +static const int bmkiller_4096[] = { + 0, 4051, 3947, 3998, 6, 16, 2735, 1031, 3081, 3202, 11, 3586, + 2347, 2063, 530, 17, 26, 3078, 3508, 21, 2568, 2762, 2058, 1766, + 2758, 27, 36, 2740, 2353, 3331, 3657, 32, 2745, 2357, 2073, 2316, + 37, 47, 3227, 2068, 2546, 42, 3084, 3333, 2574, 3655, 48, 57, + 2750, 3212, 52, 3593, 1062, 1787, 2321, 2768, 58, 67, 3088, 571, + 62, 1072, 3955, 3339, 1791, 566, 68, 77, 2756, 3231, 1797, 1778, + 73, 2760, 2597, 3429, 3712, 78, 88, 1083, 2949, 4088, 83, 3094, + 1088, 3907, 1463, 89, 98, 2766, 3601, 93, 1093, 2593, 2094, 1807, + 593, 99, 108, 3605, 1099, 3525, 2784, 104, 3099, 2608, 3598, 612, + 109, 119, 1109, 3765, 3338, 114, 2771, 3661, 2114, 2361, 120, 129, + 3104, 2356, 124, 3359, 2394, 3349, 2109, 3228, 130, 139, 2776, 2941, + 134, 3726, 1124, 1833, 3881, 3665, 140, 149, 2781, 1130, 3813, 634, + 145, 3109, 3354, 3603, 3125, 150, 160, 3247, 1843, 644, 155, 4002, + 2619, 2135, 2582, 161, 170, 2787, 3996, 165, 3463, 3604, 2130, 1849, + 664, 171, 180, 2791, 2414, 3122, 3238, 176, 3119, 3545, 2145, 3607, + 181, 191, 3814, 2140, 2809, 186, 3616, 2629, 3258, 675, 192, 201, + 2797, 1850, 196, 4053, 1171, 2155, 2392, 2824, 202, 211, 2801, 2975, + 206, 1181, 3915, 1874, 2150, 3936, 212, 221, 3668, 2640, 2393, 705, + 217, 2807, 3140, 3853, 3457, 222, 232, 1191, 1884, 715, 227, 3130, + 1196, 3455, 4046, 233, 242, 3546, 716, 237, 1202, 3613, 2166, 1890, + 1562, 243, 252, 2812, 1206, 2995, 3462, 248, 2817, 1212, 1900, 2172, + 253, 263, 1216, 3886, 2835, 258, 3550, 3273, 2186, 746, 264, 273, + 2822, 3676, 268, 2669, 2455, 1910, 2181, 1168, 274, 283, 3939, 3730, + 278, 3916, 1232, 2196, 3938, 3156, 284, 293, 2828, 1237, 3626, 2666, + 289, 2832, 3468, 3465, 3828, 294, 304, 1247, 3153, 3783, 299, 3556, + 3027, 2207, 1603, 305, 314, 2838, 787, 309, 2675, 3554, 2202, 1931, + 782, 315, 324, 3858, 3032, 3690, 3131, 320, 3823, 2681, 1941, 1209, + 325, 335, 2481, 2212, 3548, 330, 2843, 3686, 2683, 1623, 336, 345, + 3627, 1628, 340, 3390, 1278, 1951, 2858, 809, 346, 355, 2848, 3477, + 350, 1288, 2491, 3567, 2222, 3478, 356, 365, 2853, 3043, 2464, 3628, + 361, 3895, 2696, 3476, 2460, 366, 376, 1299, 3995, 3472, 371, 3166, + 1304, 3480, 3492, 377, 386, 2859, 3013, 381, 1309, 2701, 2238, 3789, + 2885, 387, 396, 2863, 1315, 1977, 850, 392, 3171, 2511, 3634, 1664, + 397, 407, 1325, 2475, 860, 402, 4023, 3746, 1987, 3170, 408, 417, + 2869, 3695, 412, 3897, 3752, 1993, 2253, 880, 418, 427, 2873, 3191, + 422, 2522, 1340, 2268, 1997, 881, 428, 437, 3637, 1346, 3571, 2891, + 433, 2879, 3640, 3639, 900, 438, 448, 3925, 3052, 3698, 443, 4009, + 2532, 2279, 2505, 449, 458, 3187, 2500, 453, 3838, 3314, 2274, 3751, + 3300, 459, 468, 2884, 2538, 2018, 921, 464, 2889, 2542, 2289, 2281, + 469, 479, 3648, 2284, 931, 474, 3581, 2737, 2028, 1720, 480, 489, + 2894, 932, 484, 2916, 1387, 2034, 2510, 3587, 490, 499, 3197, 3573, + 494, 1397, 3949, 2744, 2038, 952, 500, 509, 2900, 2747, 2044, 3310, + 505, 2904, 3431, 3501, 3054, 510, 520, 1407, 1, 2917, 515, 7, + 1412, 3650, 963, 521, 12, 2910, 1354, 525, 1418, 18, 2310, 2054, + 22, 531, 540, 4065, 1422, 28, 1757, 536, 3207, 1428, 3844, 33, + 541, 551, 1432, 38, 3320, 546, 2915, 43, 2330, 3931, 552, 561, + 49, 1003, 556, 53, 2579, 2075, 2325, 998, 562, 59, 2920, 1004, + 63, 3433, 1448, 2340, 2079, 69, 572, 581, 2925, 1453, 2085, 74, + 577, 3218, 2947, 79, 3988, 582, 592, 84, 3093, 2779, 587, 3597, + 90, 2351, 1034, 94, 602, 2931, 4050, 597, 100, 3232, 2346, 2095, + 3203, 603, 105, 2935, 2599, 3438, 110, 608, 4017, 4033, 115, 2569, + 613, 623, 3350, 121, 2572, 618, 125, 3518, 2790, 2953, 624, 633, + 131, 3085, 628, 135, 1494, 2371, 3533, 3225, 141, 643, 2945, 1075, + 638, 1504, 146, 2121, 2366, 1070, 151, 653, 3849, 3446, 156, 1456, + 649, 2951, 2813, 162, 3971, 654, 166, 1515, 2131, 4012, 659, 172, + 1520, 3527, 1839, 665, 674, 177, 1844, 669, 1525, 182, 2382, 2137, + 1097, 187, 684, 2956, 1531, 4049, 193, 680, 2961, 197, 3670, 1116, + 685, 695, 1541, 203, 3774, 690, 207, 3673, 2402, 3885, 696, 213, + 2966, 3115, 700, 3887, 2641, 218, 2397, 3965, 706, 223, 3729, 3110, + 710, 228, 1556, 2162, 2609, 2984, 234, 725, 2972, 238, 3129, 1138, + 721, 2976, 244, 3537, 1880, 726, 736, 3371, 249, 1148, 731, 3956, + 254, 2423, 3937, 737, 259, 2982, 3609, 741, 3150, 265, 2418, 2178, + 269, 747, 756, 4095, 3269, 3139, 275, 752, 3263, 279, 2188, 3126, + 757, 767, 285, 2428, 4029, 762, 2987, 2845, 290, 1179, 768, 777, + 295, 4003, 772, 3733, 300, 2198, 3732, 4031, 778, 306, 2992, 2644, + 310, 1613, 2676, 2852, 2438, 316, 788, 797, 2997, 2856, 3822, 321, + 793, 3683, 3019, 326, 2659, 798, 808, 331, 3859, 1219, 803, 3274, + 337, 3552, 1936, 341, 818, 3003, 1220, 813, 1634, 347, 2454, 2219, + 351, 819, 828, 3007, 1638, 357, 3029, 824, 3279, 1644, 2229, 362, + 829, 839, 1648, 367, 1952, 834, 3689, 372, 2474, 1250, 840, 849, + 378, 3025, 844, 382, 2702, 2239, 2469, 1601, 388, 859, 3017, 3688, + 854, 3894, 393, 2484, 2680, 3040, 398, 869, 3740, 1669, 403, 1973, + 865, 3023, 4030, 409, 2690, 870, 413, 1679, 3297, 3157, 875, 3794, + 419, 2495, 2887, 423, 890, 3294, 1291, 885, 429, 3643, 2490, 3292, + 1286, 891, 434, 3028, 2723, 2265, 439, 896, 3033, 2727, 444, 1642, + 901, 911, 3702, 450, 3747, 906, 454, 3964, 2275, 3494, 912, 460, + 3038, 3051, 916, 3498, 1710, 465, 3923, 1313, 922, 470, 3304, 3748, + 926, 475, 2907, 3981, 2285, 1672, 481, 941, 3044, 485, 3635, 3410, + 937, 3048, 2912, 491, 3291, 942, 495, 1731, 3196, 2716, 947, 501, + 1736, 3899, 3061, 953, 962, 506, 3182, 957, 1741, 511, 2526, 3836, + 4059, 516, 972, 3704, 1747, 2306, 522, 968, 3315, 526, 3706, 2923, + 973, 983, 532, 3803, 1364, 978, 3059, 3709, 537, 2897, 984, 993, + 542, 3645, 988, 3758, 547, 2322, 2541, 1384, 994, 553, 3064, 2060, + 557, 2769, 1772, 2556, 2326, 1385, 563, 1013, 3069, 567, 2332, 2066, + 1009, 3325, 573, 3711, 1404, 1014, 1024, 3091, 578, 3969, 1019, 3808, + 583, 2567, 4072, 1025, 588, 3075, 3513, 1029, 3437, 594, 2562, 2342, + 598, 1035, 1044, 3079, 2785, 604, 1425, 1040, 3335, 2789, 2577, 609, + 1045, 1055, 3876, 614, 1435, 1050, 3663, 619, 3443, 2954, 1056, 1065, + 625, 1436, 1060, 629, 1819, 2363, 3707, 2101, 1066, 635, 3089, 3767, + 639, 1829, 3243, 2960, 2367, 645, 1076, 1085, 3770, 2963, 2373, 650, + 1081, 3095, 3912, 655, 3219, 1086, 1096, 660, 3237, 3235, 1091, 3346, + 666, 3599, 1467, 670, 1106, 3974, 2078, 1101, 676, 3356, 2598, 2383, + 2974, 1107, 681, 3100, 1854, 3669, 686, 1112, 3105, 1860, 691, 2604, + 1117, 1127, 1864, 697, 3229, 1122, 701, 3727, 2618, 2142, 1128, 1137, + 707, 1507, 1132, 711, 2826, 4035, 2613, 1502, 717, 1147, 3674, 1508, + 1142, 3132, 722, 2409, 2798, 3366, 727, 1157, 3116, 1885, 732, 3128, + 1153, 3120, 3776, 738, 4020, 1158, 742, 1895, 2419, 2168, 1163, 748, + 3739, 2639, 1538, 1169, 1178, 753, 3133, 1173, 3000, 758, 2634, 2425, + 3959, 763, 1188, 4083, 2846, 3547, 769, 1184, 4027, 773, 2649, 2420, + 1189, 1199, 3474, 779, 2979, 1194, 783, 3549, 3006, 3266, 1200, 789, + 3684, 3254, 1204, 3737, 1926, 794, 2825, 3781, 1210, 799, 3136, 1579, + 1214, 804, 3633, 2450, 2654, 1574, 810, 1229, 3141, 814, 3622, 1889, + 1225, 4074, 820, 3620, 3475, 1230, 1240, 1947, 825, 3681, 1235, 3382, + 830, 3624, 3370, 1241, 835, 3147, 3962, 1245, 1957, 841, 2670, 2466, + 845, 1251, 1260, 3151, 1963, 3283, 851, 1256, 3387, 855, 2476, 1620, + 1261, 1271, 861, 3943, 1929, 1266, 3694, 3164, 866, 2865, 1272, 1281, + 871, 2860, 1276, 3575, 876, 2486, 2685, 3275, 1282, 882, 3161, 4024, + 886, 3835, 1988, 2700, 3632, 892, 1292, 1301, 3745, 1994, 3993, 897, + 1297, 3167, 3570, 902, 3407, 1302, 1312, 907, 3922, 1652, 1307, 3700, + 913, 2711, 3290, 917, 1322, 3403, 3692, 1317, 3649, 923, 2706, 2507, + 927, 1323, 1332, 3172, 4010, 933, 3490, 1328, 3177, 3653, 2517, 938, + 1333, 1343, 2913, 943, 3307, 1338, 3760, 948, 3505, 1683, 1344, 1353, + 954, 2512, 1348, 958, 2035, 2527, 2896, 2292, 964, 1363, 3413, 3050, + 1358, 2045, 969, 3068, 2726, 4038, 974, 1373, 3188, 3072, 979, 1713, + 1369, 3192, 3401, 985, 3699, 1374, 989, 2055, 3705, 1723, 1379, 3418, + 995, 3757, 3578, 999, 1394, 3198, 1724, 1389, 1005, 4048, 2742, 3927, + 2317, 1395, 1010, 3935, 2070, 2553, 1015, 1400, 3423, 2076, 1020, 2748, + 1405, 1415, 2080, 1026, 3811, 1410, 1030, 3716, 2563, 1754, 1416, 1036, + 3428, 3997, 1420, 3101, 3092, 1041, 2757, 2294, 1426, 1046, 3208, 3875, + 1430, 1051, 2096, 2772, 2573, 3930, 1057, 1445, 3213, 1061, 3715, 3098, + 1441, 3434, 3667, 1067, 3222, 1446, 1071, 2111, 3340, 3326, 1451, 1077, + 2964, 2783, 2358, 1457, 1466, 1082, 1795, 1461, 3107, 1087, 2778, 3436, + 1790, 1092, 1476, 3223, 2970, 2594, 1098, 1472, 3906, 1102, 2793, 3074, + 1477, 1487, 1108, 2788, 3717, 1482, 3444, 3236, 1113, 2379, 1488, 1497, + 1118, 2384, 1492, 3606, 1123, 2610, 3878, 1817, 1498, 1129, 3233, 3241, + 1133, 2152, 3123, 3540, 2614, 2105, 1139, 1517, 4084, 1143, 2620, 3772, + 1513, 3239, 1149, 3989, 2124, 1518, 1528, 2163, 1154, 3351, 1523, 3454, + 1159, 3671, 3724, 1529, 1164, 3731, 3536, 1533, 2173, 1170, 2814, 2630, + 1174, 1539, 1548, 3244, 2179, 1180, 1858, 1544, 3249, 3005, 3778, 1185, + 1549, 1559, 2189, 1190, 1868, 1554, 3735, 1195, 2834, 3458, 1560, 1569, + 1201, 3819, 1564, 1205, 3011, 2651, 2829, 1888, 1570, 1211, 4078, 3267, + 1215, 4036, 2204, 2844, 2655, 1221, 1580, 1589, 3260, 2210, 2661, 1226, + 1585, 3264, 3784, 1231, 1908, 1590, 1600, 1236, 3381, 3917, 1595, 3741, + 1242, 2855, 3009, 1246, 1610, 3270, 3004, 1605, 1252, 3561, 2850, 2671, + 3832, 1611, 1257, 4052, 3031, 3482, 1262, 1616, 3479, 3397, 1267, 2857, + 1621, 1631, 3485, 1273, 1939, 1626, 1277, 3169, 3566, 2477, 1632, 1641, + 1283, 1940, 1636, 1287, 2251, 2875, 3014, 3288, 1293, 1651, 3280, 3961, + 1646, 2261, 1298, 2697, 2870, 1960, 1303, 1661, 3285, 3179, 1308, 3562, + 1657, 3792, 3647, 1314, 3793, 1662, 1318, 2271, 2707, 3693, 1667, 1324, + 2276, 3696, 1971, 1673, 1682, 1329, 3984, 1677, 2282, 1334, 2886, 2713, + 2508, 1339, 1692, 3295, 2286, 3801, 1345, 1688, 3495, 1349, 3946, 2892, + 1693, 1703, 2296, 1355, 3398, 1698, 1359, 3799, 2906, 3308, 1704, 1365, + 3301, 2011, 1708, 3200, 3073, 1370, 2901, 2006, 1714, 1375, 3305, 2012, + 1718, 1380, 2312, 2738, 3184, 2533, 1386, 1733, 4043, 1390, 3417, 3420, + 1729, 3311, 1396, 4077, 3585, 1734, 1744, 2327, 1401, 3211, 1739, 3802, + 1406, 2927, 2042, 1745, 1411, 3510, 3967, 1749, 3216, 1417, 2922, 2754, + 1421, 1755, 1764, 3316, 3805, 3427, 1427, 1760, 3321, 1431, 2764, 3968, + 1765, 1775, 1437, 2932, 3076, 1770, 3516, 3804, 1442, 3870, 1776, 1785, + 1447, 3843, 1780, 3809, 1452, 2774, 3999, 3714, 1786, 1458, 3520, 2083, + 1462, 2368, 3108, 3773, 2942, 1468, 1796, 1805, 3332, 3662, 3086, 1473, + 1801, 3336, 3245, 1478, 3763, 1806, 1816, 1483, 3590, 3764, 1811, 3526, + 1489, 4013, 2595, 1493, 1826, 3342, 2600, 1821, 2389, 1499, 2958, 2795, + 1503, 1827, 1836, 3821, 2395, 1509, 2605, 1832, 3531, 3256, 2805, 1514, + 1837, 1847, 2405, 1519, 2362, 1842, 3347, 1524, 2978, 3850, 1848, 1857, + 1530, 3448, 1852, 1534, 3134, 2815, 2973, 4071, 1540, 1867, 3352, 3445, + 1862, 3978, 1545, 2988, 3113, 3452, 1550, 1877, 3357, 2426, 1555, 2146, + 1873, 3541, 3678, 1561, 2636, 1878, 1565, 3618, 3958, 2156, 1883, 3992, + 1571, 2999, 3957, 1575, 1898, 3363, 3855, 1893, 1581, 3820, 2994, 4058, + 2176, 1899, 1586, 3367, 3155, 2841, 1591, 1904, 3551, 3159, 1596, 3619, + 1909, 1919, 3787, 1602, 3824, 1914, 1606, 3277, 2851, 2187, 1920, 1612, + 3373, 2433, 1924, 3380, 2467, 1617, 3779, 3827, 1930, 1622, 3377, 3148, + 1934, 1627, 3891, 3284, 2861, 4080, 1633, 1949, 3987, 1637, 3749, 2217, + 1945, 3383, 3980, 1643, 3163, 1950, 1647, 2487, 3484, 2227, 1955, 1653, + 2492, 3743, 2693, 1961, 1970, 1658, 2228, 1965, 2498, 1663, 3030, 3963, + 3395, 1668, 1980, 3388, 2502, 2882, 1674, 1976, 3393, 1678, 4082, 3036, + 1981, 1991, 1684, 3986, 2708, 1986, 3797, 3708, 1689, 2258, 1992, 2001, + 1694, 4045, 1996, 3317, 1699, 2898, 3045, 3406, 2002, 1705, 4011, 3636, + 1709, 3201, 2528, 3060, 2902, 2724, 1715, 2021, 3404, 1719, 2908, 2728, + 2017, 3408, 1725, 3753, 3194, 2022, 2032, 2543, 1730, 3644, 2027, 3901, + 1735, 3071, 3319, 2033, 1740, 3414, 2299, 2037, 3323, 1746, 3066, 2918, + 1750, 2043, 2052, 3966, 3217, 1756, 3504, 2048, 2, 3221, 8, 1761, + 2053, 13, 3846, 19, 4064, 23, 3419, 1771, 29, 2759, 2064, 34, + 1777, 4015, 39, 1781, 44, 2939, 3761, 50, 2074, 54, 3424, 3654, + 60, 2584, 64, 4040, 2943, 70, 2084, 2093, 75, 3812, 80, 1802, + 2089, 85, 3344, 91, 3324, 95, 2104, 1812, 101, 3220, 2099, 106, + 1818, 3768, 111, 1822, 116, 3435, 3517, 122, 1828, 126, 3102, 2959, + 132, 2115, 136, 3439, 2611, 142, 1838, 2120, 147, 3851, 152, 3355, + 2125, 157, 2621, 163, 2372, 167, 1853, 3818, 173, 4091, 2136, 178, + 1859, 4067, 183, 1863, 188, 3909, 3117, 194, 1869, 198, 3449, 2816, + 204, 3679, 208, 2985, 4004, 214, 1879, 2165, 219, 2642, 224, 2821, + 2161, 229, 3856, 235, 2412, 239, 1894, 4092, 245, 3539, 2171, 250, + 3557, 3143, 255, 2177, 260, 1905, 3817, 266, 3734, 270, 3138, 3001, + 276, 1915, 280, 3460, 3278, 286, 1921, 2192, 291, 1925, 296, 3145, + 2197, 301, 4018, 307, 2443, 311, 1935, 3385, 317, 3386, 2208, 322, + 3470, 2444, 327, 3942, 332, 1946, 3932, 338, 2218, 342, 3629, 3825, + 348, 1956, 352, 3026, 3158, 358, 1962, 2237, 363, 1966, 368, 4075, + 2233, 373, 1972, 379, 3558, 383, 2248, 2703, 389, 3892, 2243, 394, + 1982, 3866, 399, 2249, 404, 3486, 3742, 410, 2714, 414, 3174, 3042, + 420, 2259, 424, 4069, 2718, 430, 2003, 2264, 435, 2007, 440, 3180, + 2269, 445, 2013, 451, 4028, 455, 3491, 3871, 461, 2899, 2280, 466, + 2023, 2515, 471, 3416, 476, 3062, 3189, 482, 2290, 486, 3496, 2516, + 492, 3756, 496, 3204, 3302, 502, 2300, 2309, 507, 2749, 512, 2049, + 2305, 517, 3902, 523, 4081, 527, 2320, 2059, 533, 2924, 2315, 538, + 2065, 3215, 543, 2069, 548, 3507, 3833, 554, 3432, 558, 3210, 3083, + 564, 2331, 568, 3511, 3877, 574, 4070, 2336, 579, 3848, 584, 2090, + 2341, 589, 3345, 595, 4061, 599, 3660, 2100, 605, 3972, 2352, 610, + 2106, 3589, 615, 2110, 620, 3103, 3329, 626, 2116, 630, 3521, 2587, + 636, 2800, 640, 3771, 3230, 646, 2126, 2381, 651, 3725, 656, 3722, + 2377, 661, 3461, 667, 3530, 671, 2141, 2811, 677, 3911, 2387, 682, + 2147, 3815, 687, 2151, 692, 3854, 3675, 698, 2157, 702, 3246, 4090, + 708, 2403, 712, 3532, 2827, 718, 2167, 2408, 723, 3375, 728, 2628, + 2413, 733, 2837, 739, 2968, 743, 2182, 3680, 749, 3369, 2424, 754, + 3542, 3364, 759, 3791, 764, 2193, 3261, 770, 2434, 774, 4054, 3614, + 780, 2203, 784, 3276, 3149, 790, 2209, 2453, 795, 2213, 800, 2650, + 2449, 805, 3786, 811, 3555, 815, 2223, 3940, 821, 2660, 2459, 826, + 3396, 3287, 831, 2465, 836, 2234, 3861, 842, 3834, 846, 3282, 4063, + 852, 2244, 856, 3924, 3402, 862, 2250, 2480, 867, 2254, 872, 3630, + 2485, 877, 2260, 883, 3565, 887, 3563, 3493, 893, 2691, 2496, 898, + 2270, 2866, 903, 4062, 908, 3186, 3400, 914, 2506, 918, 3568, 3483, + 924, 2909, 928, 3500, 3190, 934, 2291, 2525, 939, 2295, 944, 2721, + 2521, 949, 2301, 955, 4021, 959, 2536, 2919, 965, 2731, 2531, 970, + 2311, 3840, 975, 2537, 980, 3579, 2732, 986, 2930, 990, 3318, 3206, + 996, 2547, 1000, 3583, 2934, 1006, 3928, 2552, 1011, 2940, 1016, 2337, + 2557, 1021, 2944, 1027, 3, 9, 3879, 14, 1037, 20, 24, 1042, + 30, 3852, 1047, 35, 1052, 40, 45, 1058, 2578, 51, 55, 2937, + 1068, 61, 65, 3348, 71, 1078, 2588, 76, 81, 2965, 86, 2378, + 92, 96, 3658, 102, 3874, 1103, 107, 2388, 112, 117, 2603, 1114, + 123, 127, 1119, 2398, 133, 137, 2803, 143, 2404, 1134, 148, 153, + 1140, 158, 1144, 164, 168, 1150, 174, 2624, 1155, 179, 1160, 184, + 189, 1165, 3918, 195, 199, 1175, 2429, 205, 209, 3135, 215, 1186, + 2435, 220, 225, 2439, 230, 3379, 236, 240, 2445, 246, 3736, 4068, + 251, 3016, 256, 261, 3374, 1222, 267, 271, 1227, 3691, 277, 281, + 2665, 287, 3560, 1243, 292, 297, 2470, 302, 1253, 308, 312, 1258, + 318, 4008, 1263, 323, 1268, 328, 333, 1274, 3037, 339, 343, 3289, + 1284, 349, 353, 3920, 359, 1294, 2497, 364, 369, 2501, 374, 3176, + 380, 384, 3053, 390, 2876, 1319, 395, 3873, 400, 405, 2712, 1330, + 411, 415, 1335, 3868, 421, 425, 3405, 431, 2722, 1350, 436, 441, + 1356, 446, 1360, 452, 456, 1366, 462, 2741, 1371, 467, 1376, 472, + 477, 1381, 2548, 483, 487, 1391, 2752, 493, 497, 3842, 503, 1402, + 2558, 508, 513, 2753, 518, 3651, 524, 528, 3807, 534, 3426, 3330, + 539, 2763, 544, 549, 3596, 1438, 555, 559, 1443, 2583, 565, 569, + 2773, 575, 2589, 1459, 580, 585, 3910, 590, 1469, 596, 600, 1474, + 606, 2948, 1479, 611, 1484, 616, 621, 1490, 2794, 627, 631, 3908, + 1500, 637, 641, 3608, 647, 1510, 2804, 652, 657, 3611, 662, 2625, + 668, 672, 3863, 678, 3723, 1535, 683, 2635, 688, 693, 2819, 1546, + 699, 703, 1551, 2645, 709, 713, 3362, 719, 3146, 1566, 724, 729, + 1572, 734, 1576, 740, 744, 1582, 750, 2840, 1587, 755, 1592, 760, + 765, 1597, 3160, 771, 775, 1607, 4066, 781, 785, 3788, 791, 1618, + 2682, 796, 801, 2686, 806, 3391, 812, 816, 2692, 822, 3921, 3020, + 827, 4039, 832, 837, 3617, 1654, 843, 847, 1659, 3181, 853, 857, + 2881, 863, 4022, 1675, 868, 873, 2717, 878, 1685, 884, 888, 1690, + 894, 3503, 1695, 899, 1700, 904, 909, 1706, 2733, 915, 919, 3796, + 1716, 925, 929, 4076, 935, 1726, 2743, 940, 945, 3591, 950, 3795, + 956, 960, 3883, 966, 3580, 1751, 971, 3904, 976, 981, 2928, 1762, + 987, 991, 1767, 3953, 997, 1001, 4007, 1007, 2938, 1782, 1012, 1017, + 1788, 1022, 1792, 1028, 1032, 1798, 1038, 2957, 1803, 1043, 1808, 1048, + 1053, 1813, 3677, 1059, 1063, 1823, 2799, 1069, 1073, 3933, 1079, 1834, + 3248, 1084, 1089, 2969, 1094, 2810, 1100, 1104, 3253, 1110, 3534, 4005, + 1115, 2820, 1120, 1125, 3259, 1870, 1131, 1135, 1875, 2830, 1141, 1145, + 2989, 1151, 2836, 1891, 1156, 1161, 3941, 1166, 1901, 1172, 1176, 1906, + 1182, 3905, 1911, 1187, 1916, 1192, 1197, 1922, 3010, 1203, 1207, 3860, + 1932, 1213, 1217, 3564, 1223, 1942, 2867, 1228, 1233, 2871, 1238, 3154, + 1244, 1248, 2877, 1254, 3392, 1967, 1259, 3865, 1264, 1269, 3035, 1978, + 1275, 1279, 1983, 3041, 1285, 1289, 3983, 1295, 3798, 1998, 1300, 1305, + 2004, 1310, 2008, 1316, 1320, 2014, 1326, 3056, 2019, 1331, 2024, 1336, + 1341, 2029, 3900, 1347, 1351, 2039, 3951, 1357, 1361, 3195, 1367, 2050, + 2929, 1372, 1377, 2933, 1382, 3515, 1388, 1392, 3082, 1398, 3845, 3652, + 1403, 3341, 1408, 1413, 3519, 2086, 1419, 1423, 2091, 3720, 1429, 1433, + 3097, 1439, 4086, 2107, 1444, 1449, 3112, 1454, 2117, 1460, 1464, 2122, + 1470, 3973, 2127, 1475, 2132, 1480, 1485, 2138, 2980, 1491, 1495, 3535, + 2148, 1501, 1505, 4079, 1511, 2158, 2990, 1516, 1521, 3372, 1526, 3612, + 1532, 1536, 3376, 1542, 3464, 2183, 1547, 3890, 1552, 1557, 3144, 2194, + 1563, 1567, 2199, 3015, 1573, 1577, 3621, 1583, 3021, 2214, 1588, 1593, + 2220, 1598, 2224, 1604, 1608, 2230, 1614, 3173, 2235, 1619, 2240, 1624, + 1629, 2245, 3979, 1635, 1639, 2255, 3046, 1645, 1649, 3830, 1655, 2266, + 3839, 1660, 1665, 3185, 1670, 3057, 1676, 1680, 3755, 1686, 3642, 3577, + 1691, 3067, 1696, 1701, 3710, 2302, 1707, 1711, 2307, 3077, 1717, 1721, + 3205, 1727, 3990, 2323, 1732, 1737, 3087, 1742, 2333, 1748, 1752, 2338, + 1758, 3880, 2343, 1763, 2348, 1768, 1773, 2354, 3226, 1779, 1783, 4055, + 2364, 1789, 1793, 3602, 1799, 2374, 3114, 1804, 1809, 3118, 1814, 3914, + 1820, 1824, 3124, 1830, 3721, 2399, 1835, 3459, 1840, 1845, 3251, 2410, + 1851, 1855, 2415, 3257, 1861, 1865, 4085, 1871, 3469, 2430, 1876, 1881, + 2436, 1886, 2440, 1892, 1896, 2446, 1902, 3272, 2451, 1907, 2456, 1912, + 1917, 2461, 3165, 1923, 1927, 2471, 3982, 1933, 1937, 3977, 1943, 2482, + 3175, 1948, 1953, 3896, 1958, 3638, 1964, 1968, 3298, 1974, 4044, 3572, + 1979, 3926, 1984, 1989, 3829, 2518, 1995, 1999, 2523, 3506, 2005, 2009, + 3313, 2015, 4000, 2539, 2020, 2025, 3328, 2030, 2549, 2036, 2040, 2554, + 2046, 3719, 2559, 2051, 2564, 2056, 2061, 2570, 3950, 2067, 2071, 3659, + 2580, 2077, 2081, 4073, 2087, 2590, 3441, 2092, 2097, 4014, 2102, 3242, + 2108, 2112, 3777, 2118, 3451, 2615, 2123, 3252, 2128, 2133, 3360, 2626, + 2139, 2143, 2631, 3262, 2149, 2153, 3806, 2159, 3268, 2646, 2164, 2169, + 2652, 2174, 2656, 2180, 2184, 2662, 2190, 3389, 2667, 2195, 2672, 2200, + 2205, 2677, 4056, 2211, 2215, 2687, 3293, 2221, 2225, 4034, 2231, 2698, + 3299, 2236, 2241, 3303, 2246, 3867, 2252, 2256, 3309, 2262, 3750, 4041, + 2267, 3411, 2272, 2277, 3582, 2734, 2283, 2287, 2739, 3588, 2293, 2297, + 3421, 2303, 3592, 2755, 2308, 2313, 3334, 2318, 2765, 2324, 2328, 2770, + 2334, 3523, 2775, 2339, 2780, 2344, 2349, 2786, 3442, 2355, 2359, 3524, + 2796, 2365, 2369, 3780, 2375, 2806, 3361, 2380, 2385, 3365, 2390, 3893, + 2396, 2400, 3884, 2406, 3976, 2831, 2411, 3623, 2416, 2421, 3467, 2842, + 2427, 2431, 2847, 3473, 2437, 2441, 3889, 2447, 3864, 2862, 2452, 2457, + 2868, 2462, 2872, 2468, 2472, 2878, 2478, 3488, 2883, 2483, 2888, 2488, + 2493, 2893, 3412, 2499, 2503, 2903, 3948, 2509, 2513, 3945, 2519, 2914, + 3422, 2524, 2529, 4025, 2534, 3762, 2540, 2544, 3514, 2550, 3952, 3595, + 2555, 3664, 2560, 2565, 3766, 2950, 2571, 2575, 2955, 3447, 2581, 2585, + 3529, 2591, 3453, 2971, 2596, 2601, 3544, 2606, 2981, 2612, 2616, 2986, + 2622, 4060, 2991, 2627, 2996, 2632, 2637, 3002, 3685, 2643, 2647, 3782, + 3012, 2653, 2657, 4037, 2663, 3022, 4019, 2668, 2673, 3869, 2678, 3489, + 2684, 2688, 3701, 2694, 3994, 3047, 2699, 3499, 2704, 2709, 3576, 3058, + 2715, 2719, 3063, 3509, 2725, 2729, 3837, 4, 10, 15, 25, 31, + 41, 46, 56, 66, 72, 82, 87, 97, 103, 113, 118, 128, + 138, 144, 154, 159, 169, 175, 185, 190, 200, 210, 216, 226, + 231, 241, 247, 257, 262, 272, 282, 288, 298, 303, 313, 319, + 329, 334, 344, 354, 360, 370, 375, 385, 391, 401, 406, 416, + 426, 432, 442, 447, 457, 463, 473, 478, 488, 498, 504, 514, + 519, 529, 535, 545, 550, 560, 570, 576, 586, 591, 601, 607, + 617, 622, 632, 642, 648, 658, 663, 673, 679, 689, 694, 704, + 714, 720, 730, 735, 745, 751, 761, 766, 776, 786, 792, 802, + 807, 817, 823, 833, 838, 848, 858, 864, 874, 879, 889, 895, + 905, 910, 920, 930, 936, 946, 951, 961, 967, 977, 982, 992, + 1002, 1008, 1018, 1023, 1033, 1039, 1049, 1054, 1064, 1074, 1080, 1090, + 1095, 1105, 1111, 1121, 1126, 1136, 1146, 1152, 1162, 1167, 1177, 1183, + 1193, 1198, 1208, 1218, 1224, 1234, 1239, 1249, 1255, 1265, 1270, 1280, + 1290, 1296, 1306, 1311, 1321, 1327, 1337, 1342, 1352, 1362, 1368, 1378, + 1383, 1393, 1399, 1409, 1414, 1424, 1434, 1440, 1450, 1455, 1465, 1471, + 1481, 1486, 1496, 1506, 1512, 1522, 1527, 1537, 1543, 1553, 1558, 1568, + 1578, 1584, 1594, 1599, 1609, 1615, 1625, 1630, 1640, 1650, 1656, 1666, + 1671, 1681, 1687, 1697, 1702, 1712, 1722, 1728, 1738, 1743, 1753, 1759, + 1769, 1774, 1784, 1794, 1800, 1810, 1815, 1825, 1831, 1841, 1846, 1856, + 1866, 1872, 1882, 1887, 1897, 1903, 1913, 1918, 1928, 1938, 1944, 1954, + 1959, 1969, 1975, 1985, 1990, 2000, 2010, 2016, 2026, 2031, 2041, 2047, + 2057, 2062, 2072, 2082, 2088, 2098, 2103, 2113, 2119, 2129, 2134, 2144, + 2154, 2160, 2170, 2175, 2185, 2191, 2201, 2206, 2216, 2226, 2232, 2242, + 2247, 2257, 2263, 2273, 2278, 2288, 2298, 2304, 2314, 2319, 2329, 2335, + 2345, 2350, 2360, 2370, 2376, 2386, 2391, 2401, 2407, 2417, 2422, 2432, + 2442, 2448, 2458, 2463, 2473, 2479, 2489, 2494, 2504, 2514, 2520, 2530, + 2535, 2545, 2551, 2561, 2566, 2576, 2586, 2592, 2602, 2607, 2617, 2623, + 2633, 2638, 2648, 2658, 2664, 2674, 2679, 2689, 2695, 2705, 2710, 2720, + 2730, 2736, 2746, 2751, 2761, 2767, 2777, 2782, 2792, 2802, 2808, 2818, + 2823, 2833, 2839, 2849, 2854, 2864, 2874, 2880, 2890, 2895, 2905, 2911, + 2921, 2926, 2936, 2946, 2952, 2962, 2967, 2977, 2983, 2993, 2998, 3008, + 3018, 3024, 3034, 3039, 3049, 3055, 3065, 3070, 3080, 3090, 3096, 3106, + 3111, 3121, 3127, 3137, 3142, 3152, 3162, 3168, 3178, 3183, 3193, 3199, + 3209, 3214, 3224, 3234, 3240, 3250, 3255, 3265, 3271, 3281, 3286, 3296, + 3306, 3312, 3322, 3327, 3337, 3343, 3353, 3358, 3368, 3378, 3384, 3394, + 3399, 3409, 3415, 3425, 3430, 3440, 3450, 3456, 3466, 3471, 3481, 3487, + 3497, 3502, 3512, 3522, 3528, 3538, 3543, 3553, 3559, 3569, 3574, 3584, + 3594, 3600, 3610, 3615, 3625, 3631, 3641, 3646, 3656, 3666, 3672, 3682, + 3687, 3697, 3703, 3713, 3718, 3728, 3738, 3744, 3754, 3759, 3769, 3775, + 3785, 3790, 3800, 3810, 3816, 3826, 3831, 3841, 3847, 3857, 3862, 3872, + 3882, 3888, 3898, 3903, 3913, 3919, 3929, 3934, 3944, 3954, 3960, 3970, + 3975, 3985, 3991, 4001, 4006, 4016, 4026, 4032, 4042, 4047, 4057, 4087, + 4089, 4093, 4094, 5 +}; + +static const int bmkiller_4097[] = { + 0, 1027, 3081, 3842, 6, 16, 3586, 2562, 2749, 3587, 11, 3515, + 2950, 3418, 530, 17, 26, 2740, 1417, 21, 1041, 2567, 3843, 2755, + 2731, 27, 36, 3906, 1428, 31, 2572, 1047, 2073, 3205, 3952, 37, + 46, 2745, 1052, 3598, 1432, 42, 2750, 2578, 4050, 3654, 47, 57, + 2363, 2330, 2579, 52, 3088, 3721, 4015, 2920, 58, 67, 3852, 571, + 62, 1072, 2960, 3339, 1791, 566, 68, 77, 2756, 3231, 1797, 1777, + 73, 2760, 2597, 3883, 1782, 78, 88, 2965, 1802, 3093, 83, 3596, + 3237, 3429, 1463, 89, 98, 3605, 3726, 93, 2971, 1093, 2104, 2341, + 593, 99, 108, 2766, 2783, 103, 1103, 2598, 3434, 3880, 3770, 109, + 118, 2770, 3242, 3350, 607, 114, 3813, 1113, 4002, 613, 119, 129, + 2394, 2109, 3443, 124, 2776, 1119, 3112, 2794, 130, 139, 3601, 2610, + 134, 1124, 2618, 2124, 1832, 628, 140, 149, 3109, 1129, 1838, 634, + 145, 2781, 1134, 4044, 3818, 150, 160, 1140, 1843, 644, 155, 2786, + 2619, 4009, 2126, 161, 170, 3115, 3527, 165, 1150, 2804, 3445, 2582, + 664, 171, 180, 2791, 4093, 175, 3878, 1155, 2145, 4013, 665, 181, + 190, 3119, 1160, 3815, 2630, 186, 2797, 2996, 2631, 684, 191, 201, + 2424, 3613, 1535, 196, 2801, 2634, 3862, 4003, 202, 211, 3125, 2975, + 206, 3822, 2429, 1874, 2150, 2966, 212, 221, 2807, 2639, 2393, 705, + 217, 3129, 3775, 3455, 1551, 222, 232, 2439, 3619, 715, 227, 3546, + 3736, 4085, 1556, 233, 242, 2812, 716, 237, 2445, 1201, 1894, 2412, + 1561, 243, 252, 3135, 3134, 247, 1212, 3145, 3823, 2831, 736, 253, + 262, 2817, 1216, 2798, 3618, 258, 2822, 1222, 3460, 3259, 263, 273, + 2455, 2181, 3732, 268, 3140, 1227, 3986, 747, 274, 283, 4031, 3991, + 278, 1232, 2460, 1915, 3542, 2629, 284, 293, 2828, 1237, 2191, 1592, + 289, 2832, 1243, 3153, 2847, 294, 304, 1247, 2197, 2671, 299, 3556, + 3488, 3465, 2992, 305, 314, 3150, 787, 309, 1257, 2675, 1935, 2434, + 782, 315, 324, 2838, 788, 319, 2480, 1263, 1941, 3482, 2855, 325, + 334, 2842, 1268, 2444, 3477, 330, 3627, 2486, 1946, 2650, 335, 345, + 3037, 3271, 3788, 340, 2848, 3892, 3629, 818, 346, 355, 3943, 1633, + 350, 1288, 2691, 3293, 2222, 3478, 356, 365, 4076, 2875, 2464, 823, + 361, 2853, 3570, 3476, 829, 366, 376, 3863, 3864, 3278, 371, 2858, + 2501, 3480, 1654, 377, 386, 3747, 2876, 381, 3499, 1309, 1976, 3691, + 844, 387, 396, 2863, 859, 391, 1319, 2706, 1982, 3695, 854, 397, + 406, 3958, 4053, 2475, 3554, 402, 2869, 1329, 1987, 2882, 407, 417, + 3504, 2253, 3297, 412, 2873, 1335, 3046, 1679, 418, 427, 3646, 2717, + 422, 1340, 3640, 2268, 4008, 881, 428, 437, 2879, 1345, 2263, 1689, + 433, 3752, 1350, 3794, 900, 438, 448, 1356, 2269, 2727, 443, 3576, + 2532, 3490, 1993, 449, 458, 2884, 3047, 453, 1366, 4065, 4025, 2505, + 3038, 459, 468, 3642, 3647, 463, 2542, 1371, 2289, 3498, 916, 469, + 478, 2889, 1376, 2515, 922, 474, 2894, 3078, 2739, 2907, 479, 489, + 2548, 4088, 932, 484, 3927, 2742, 4048, 3900, 490, 499, 3197, 3899, + 494, 3421, 3084, 3324, 2038, 952, 500, 509, 2900, 2747, 3503, 3648, + 505, 2904, 4012, 3649, 4079, 510, 520, 2753, 1, 1741, 515, 7, + 2762, 3501, 963, 521, 12, 3948, 1751, 525, 3094, 18, 2320, 4024, + 22, 531, 540, 2910, 3068, 535, 28, 3513, 3506, 32, 3653, 541, + 550, 2914, 38, 2546, 993, 546, 3953, 1438, 43, 1767, 551, 561, + 48, 2325, 1003, 556, 53, 1443, 3087, 1772, 562, 59, 4068, 1004, + 63, 1448, 2932, 2340, 2079, 69, 572, 581, 3217, 1453, 2085, 74, + 577, 2925, 1459, 79, 2557, 582, 592, 84, 2090, 3232, 587, 2930, + 90, 3660, 1034, 94, 602, 3222, 3518, 597, 1473, 100, 3517, 2944, + 104, 603, 612, 2935, 3848, 110, 2788, 1479, 2361, 3907, 3763, 115, + 622, 3228, 1484, 120, 1808, 618, 2941, 125, 3524, 2955, 623, 633, + 131, 3593, 2795, 135, 2945, 3908, 3996, 3089, 141, 643, 4075, 1075, + 638, 1504, 146, 3608, 2120, 1070, 151, 653, 2951, 3446, 156, 1456, + 649, 3238, 2813, 162, 3218, 654, 166, 2624, 2131, 3599, 659, 3607, + 172, 3670, 2969, 176, 674, 2956, 2978, 669, 182, 1525, 2392, 3104, + 1097, 675, 187, 3243, 1849, 679, 192, 2814, 3884, 3669, 197, 685, + 694, 2961, 2635, 203, 1111, 690, 207, 1545, 3532, 1117, 695, 213, + 2640, 2397, 3665, 700, 3248, 218, 3128, 1870, 706, 223, 3673, 2826, + 710, 228, 2645, 2162, 2609, 1132, 234, 725, 2972, 238, 2407, 1138, + 721, 2976, 1566, 244, 3812, 726, 248, 1572, 2413, 1148, 731, 254, + 2835, 3537, 2414, 737, 746, 259, 3369, 741, 1582, 264, 2182, 2623, + 1168, 269, 756, 2982, 3273, 751, 275, 1587, 2433, 279, 1169, 757, + 766, 2986, 285, 3452, 1905, 762, 3920, 3160, 290, 1188, 767, 777, + 295, 3942, 3004, 772, 300, 2850, 3889, 3253, 778, 306, 3269, 3626, + 310, 3386, 2676, 2203, 2438, 3684, 316, 797, 3683, 320, 2644, 1209, + 793, 2997, 326, 3548, 3690, 798, 808, 2686, 331, 1219, 803, 3002, + 336, 3552, 1936, 809, 341, 4070, 1220, 813, 2866, 347, 2223, 3555, + 351, 819, 828, 3007, 3620, 357, 1644, 3020, 2229, 2660, 1240, 362, + 838, 3632, 1648, 367, 3146, 834, 3013, 372, 2234, 3749, 839, 849, + 378, 2469, 1957, 382, 3017, 1659, 3830, 1251, 850, 388, 3740, 1967, + 392, 1664, 3487, 2484, 2680, 398, 860, 869, 3023, 1669, 2479, 403, + 865, 3638, 1675, 408, 3963, 870, 880, 413, 2485, 2887, 875, 3793, + 419, 3562, 3161, 423, 890, 3028, 1291, 885, 429, 2891, 2264, 3494, + 1286, 891, 434, 3924, 1292, 895, 439, 1695, 2270, 2700, 444, 901, + 910, 3033, 1700, 450, 1998, 906, 454, 2733, 2275, 2701, 911, 921, + 460, 2870, 3051, 464, 3304, 3997, 3701, 1322, 470, 931, 3999, 3839, + 926, 1720, 475, 3874, 2510, 1672, 480, 941, 3044, 4023, 485, 1327, + 937, 3048, 3207, 491, 1333, 942, 495, 4091, 2721, 3801, 947, 501, + 2748, 3573, 2918, 953, 962, 506, 4083, 957, 3212, 511, 2536, 3063, + 1348, 516, 972, 3054, 1363, 967, 522, 2922, 3578, 526, 1358, 973, + 982, 3058, 3427, 532, 3301, 978, 536, 1761, 4071, 1713, 983, 542, + 2764, 2541, 3757, 988, 3064, 547, 3328, 3076, 994, 552, 3718, 2933, + 998, 557, 3712, 2556, 2326, 1385, 563, 1013, 3325, 567, 2551, 3082, + 1009, 3069, 573, 3988, 1404, 1014, 1024, 1788, 578, 2076, 1019, 3074, + 583, 3879, 1744, 1025, 588, 3331, 3637, 1029, 1798, 594, 3589, 3650, + 598, 1035, 1044, 3079, 3092, 1039, 604, 1803, 2577, 608, 1420, 1045, + 1054, 3335, 614, 3807, 1426, 1050, 3085, 3677, 619, 3525, 1055, 1065, + 624, 2763, 1436, 1060, 629, 2958, 4027, 2767, 1066, 635, 3341, 3441, + 639, 3652, 3935, 3868, 2367, 645, 1076, 1085, 3095, 2963, 2373, 650, + 1081, 3345, 3912, 655, 3438, 1086, 1096, 660, 2378, 3107, 1091, 3936, + 666, 3885, 1467, 670, 1106, 3100, 2974, 1101, 4040, 676, 2608, 3603, + 680, 1107, 1116, 3351, 2948, 686, 1860, 3658, 4054, 3535, 3229, 691, + 1126, 3105, 1864, 696, 1497, 1122, 3110, 701, 3604, 4029, 1127, 1137, + 707, 2613, 1507, 711, 3356, 1875, 4030, 2152, 717, 1147, 3992, 1508, + 1142, 1880, 722, 2628, 2408, 3959, 727, 1157, 3116, 1885, 732, 3977, + 1153, 3120, 1891, 738, 3722, 1158, 742, 1895, 2419, 3256, 1163, 3679, + 748, 3609, 1538, 752, 1178, 3366, 2173, 1173, 758, 2999, 3614, 4080, + 1852, 1179, 763, 3126, 2183, 1183, 768, 1911, 2649, 3893, 773, 1189, + 1198, 3130, 1916, 779, 3979, 1194, 783, 3010, 3853, 3676, 1199, 789, + 2856, 2834, 3011, 1204, 3136, 794, 4084, 3464, 1210, 799, 3890, 1579, + 1214, 804, 2861, 2450, 2654, 1574, 810, 1229, 4046, 814, 3957, 1889, + 1225, 3141, 3029, 820, 2446, 1230, 824, 2871, 2839, 3381, 1235, 830, + 3559, 3624, 2220, 1241, 1250, 835, 3392, 1245, 2877, 840, 2470, 2845, + 1601, 845, 1260, 3151, 3560, 1255, 851, 3030, 3895, 855, 3373, 1261, + 1270, 3694, 861, 3166, 1615, 1266, 3157, 1977, 866, 1621, 1271, 1281, + 871, 2685, 3019, 1276, 876, 1983, 3400, 3403, 1282, 882, 3745, 3042, + 886, 1988, 2892, 2491, 2860, 1636, 892, 1301, 3167, 896, 2695, 1642, + 1297, 3835, 902, 3866, 3407, 1302, 1312, 2004, 907, 1652, 1307, 3700, + 912, 3634, 2702, 1313, 917, 3172, 3692, 1317, 2014, 923, 2511, 3289, + 927, 1323, 1332, 3750, 3194, 933, 2912, 2019, 2517, 3294, 1673, 938, + 1342, 3177, 2024, 943, 3062, 1338, 3182, 948, 2522, 1692, 1343, 1353, + 954, 3191, 2292, 958, 3925, 3066, 3934, 3398, 1354, 964, 3413, 3050, + 968, 2923, 3808, 3509, 2726, 974, 1364, 1373, 3188, 3071, 2897, 979, + 1369, 3192, 3968, 984, 2307, 1374, 1384, 989, 3201, 1723, 1379, 4049, + 995, 3645, 2312, 999, 1394, 4041, 1724, 1389, 1005, 2065, 2552, 2916, + 2317, 1395, 1010, 3198, 3422, 1399, 1015, 3804, 2558, 3591, 1020, 1405, + 1414, 3202, 2080, 1026, 3762, 1410, 1030, 2086, 2563, 3316, 1415, 1425, + 1036, 2757, 3215, 1040, 3208, 2091, 3334, 1755, 1046, 1435, 3811, 3220, + 1430, 2096, 1051, 2772, 4034, 3711, 1056, 1445, 3433, 2101, 1061, 2348, + 1441, 3213, 2107, 1067, 3940, 1446, 1071, 2111, 2773, 3103, 1451, 1077, + 2964, 3767, 3520, 1457, 1466, 1082, 1795, 1461, 2121, 1087, 3661, 2938, + 1790, 1092, 1476, 3223, 1796, 1471, 1098, 2127, 2793, 1102, 3662, 1477, + 1486, 3444, 2132, 1108, 3245, 1482, 1112, 3730, 3606, 3805, 1487, 1118, + 2980, 3590, 3974, 1492, 3233, 1123, 3773, 1826, 1498, 1128, 3990, 2389, + 1502, 1133, 3123, 3540, 2614, 2105, 1139, 1517, 3239, 1143, 2968, 1831, + 1513, 3454, 1149, 3671, 1837, 1518, 1528, 3668, 1154, 3724, 1523, 3731, + 1159, 3777, 2409, 1529, 1164, 3244, 4058, 1533, 3376, 1170, 2824, 3965, + 1174, 1539, 1548, 3459, 1867, 1543, 1180, 3138, 3916, 1184, 1862, 1549, + 1558, 3249, 1190, 2979, 2140, 1554, 3254, 2193, 1195, 2146, 1559, 1569, + 1200, 2829, 4019, 1564, 1205, 2199, 3375, 2436, 1570, 1211, 3790, 3149, + 1215, 2204, 3784, 2844, 2655, 1221, 1580, 1589, 3260, 2209, 2661, 1226, + 1585, 3264, 2214, 1231, 1908, 1590, 1600, 1236, 2666, 3159, 1595, 3956, + 1242, 3681, 2177, 1246, 1610, 3475, 3854, 1605, 2230, 1252, 3686, 3009, + 1256, 1611, 1620, 3270, 3824, 1262, 3397, 2235, 2865, 3279, 1924, 1267, + 1630, 3274, 2240, 1272, 1930, 1626, 4063, 1277, 3171, 3489, 1631, 1641, + 1283, 3284, 1940, 1287, 3280, 3174, 4077, 3148, 1293, 1651, 3485, 3743, + 1646, 3571, 1298, 3689, 2696, 1960, 1303, 1661, 3791, 3179, 1308, 3792, + 1657, 3285, 3983, 1314, 3388, 1662, 1318, 3056, 2707, 2497, 1667, 3290, + 1324, 3696, 1971, 1328, 1682, 4045, 2508, 1677, 1334, 2281, 2896, 3565, + 3164, 1683, 1339, 3295, 3566, 1687, 1344, 3926, 3955, 3699, 1349, 1693, + 1702, 3796, 2296, 1355, 2001, 1698, 1359, 2302, 3798, 2523, 1703, 1365, + 3072, 2901, 2011, 1708, 3305, 1370, 3416, 2528, 1714, 1375, 4086, 2012, + 1718, 1380, 3077, 2738, 3184, 2533, 1386, 1733, 3311, 1390, 2911, 2539, + 1729, 3802, 2323, 1396, 3061, 1734, 1400, 2327, 2917, 3516, 1739, 1406, + 3849, 3706, 2042, 1745, 1754, 1411, 3323, 1749, 2337, 1416, 2758, 3320, + 2294, 1421, 1764, 3901, 3329, 1759, 1427, 2343, 2937, 1431, 3204, 1765, + 1774, 3321, 1437, 3659, 2564, 1770, 3326, 3226, 1442, 3714, 1775, 1785, + 1447, 4051, 3227, 1780, 1452, 3950, 4066, 3424, 1786, 1458, 3931, 2083, + 1462, 2368, 3108, 2779, 2942, 2078, 1468, 1805, 3332, 1472, 3086, 3073, + 1801, 3336, 1478, 4022, 2335, 1806, 1816, 3118, 1483, 3764, 1811, 3772, + 1488, 3717, 4014, 1817, 1493, 3821, 3436, 1821, 3855, 1499, 2799, 3225, + 1503, 1827, 1836, 3342, 2605, 1509, 2399, 3246, 2805, 3973, 2356, 1514, + 1846, 3346, 3729, 1519, 2119, 1842, 3976, 1524, 2810, 2125, 1847, 1857, + 1530, 2973, 3448, 1534, 3352, 2415, 3544, 2625, 1858, 1540, 3817, 3258, + 1544, 2420, 3266, 2988, 3113, 1550, 1868, 1877, 3541, 2425, 2983, 1555, + 1873, 3357, 2430, 1560, 3856, 1878, 1888, 1565, 2989, 2156, 1883, 3362, + 1571, 4043, 2990, 1575, 1898, 3547, 3938, 1893, 1581, 3379, 2840, 3127, + 2176, 1899, 1586, 3367, 3787, 1903, 1591, 2451, 2846, 3133, 1596, 1909, + 1918, 3551, 2456, 1602, 2662, 1914, 1606, 3165, 2851, 2196, 1919, 1929, + 1612, 3382, 3827, 1616, 3377, 3282, 3961, 2428, 1622, 1939, 3557, 3469, + 1934, 3170, 1627, 3698, 3014, 3470, 1632, 1949, 3383, 3287, 1637, 2217, + 1945, 3561, 3693, 1643, 3390, 1950, 1647, 3292, 3154, 2227, 1955, 1653, + 3180, 4082, 3860, 1961, 1970, 1658, 2228, 1965, 3298, 1663, 3040, 3919, + 3395, 1668, 1980, 3567, 3865, 1975, 1674, 3797, 3947, 1678, 2248, 1981, + 1990, 3393, 2512, 1684, 3834, 1986, 1688, 2518, 3748, 3981, 1991, 1694, + 3196, 3045, 2713, 1996, 3572, 1699, 4078, 2259, 2002, 1704, 4062, 2724, + 2006, 1709, 3703, 3060, 2902, 3751, 1715, 2021, 3404, 1719, 3055, 2728, + 2017, 3408, 1725, 3585, 3870, 2022, 2032, 2543, 1730, 3319, 2027, 3803, + 1735, 3753, 3496, 2033, 1740, 3582, 2299, 2037, 2553, 1746, 3758, 3417, + 1750, 2043, 2052, 3414, 2300, 2047, 1756, 2559, 2, 1760, 8, 2053, + 2062, 13, 1766, 3761, 19, 2058, 23, 3526, 1771, 29, 2063, 33, + 1776, 3505, 39, 2068, 1781, 44, 3845, 49, 2074, 1787, 54, 3431, + 60, 2584, 64, 3814, 2943, 70, 2084, 2093, 75, 3911, 2949, 80, + 2089, 85, 3531, 1807, 91, 2094, 95, 1812, 2954, 101, 2099, 105, + 1818, 3768, 111, 1822, 2114, 116, 3451, 121, 3536, 1828, 126, 3946, + 132, 2115, 136, 3439, 2371, 142, 2615, 3354, 147, 3235, 2366, 152, + 2134, 157, 3674, 1848, 163, 2130, 167, 1853, 4081, 173, 2135, 177, + 1859, 3117, 183, 1863, 3449, 188, 3616, 193, 1869, 2155, 198, 3365, + 204, 2636, 208, 3132, 2984, 214, 1879, 2165, 219, 2641, 1884, 224, + 2161, 229, 2646, 1890, 235, 2166, 239, 2652, 2995, 245, 2171, 249, + 1900, 3778, 255, 1904, 2186, 260, 3782, 265, 1910, 3734, 270, 3978, + 276, 2187, 280, 3858, 3828, 286, 1920, 2667, 291, 3820, 1925, 296, + 2206, 301, 2672, 1931, 307, 2202, 311, 4056, 3387, 317, 2207, 321, + 3288, 3267, 327, 2212, 3962, 332, 4020, 337, 2218, 1951, 342, 4039, + 348, 1956, 352, 3026, 3158, 358, 1962, 2237, 363, 1966, 3739, 368, + 2233, 373, 3984, 1972, 379, 2238, 383, 3303, 3746, 389, 2243, 393, + 3410, 3789, 399, 2249, 2258, 404, 3406, 409, 3309, 1992, 414, 3964, + 420, 1997, 424, 3486, 3980, 430, 2003, 4038, 435, 2007, 3869, 440, + 2278, 445, 2013, 3896, 451, 2274, 455, 2734, 2018, 461, 2279, 465, + 2023, 3189, 471, 2284, 2028, 476, 3949, 481, 2290, 2034, 486, 2516, + 492, 2744, 496, 3067, 3302, 502, 2044, 2309, 507, 2048, 3199, 512, + 2305, 517, 2054, 3657, 523, 2310, 527, 2759, 2059, 533, 2315, 537, + 2064, 3876, 543, 2321, 2069, 548, 2929, 553, 2769, 2075, 558, 3510, + 564, 2331, 568, 3511, 2940, 574, 3344, 2775, 579, 3709, 3588, 584, + 2350, 589, 2780, 2095, 595, 2346, 599, 2100, 3098, 605, 2351, 609, + 2106, 3338, 615, 2110, 3521, 620, 4069, 625, 2362, 2116, 630, 2587, + 636, 2800, 640, 3725, 3230, 646, 2372, 2381, 651, 3806, 3877, 656, + 2377, 661, 3461, 2136, 667, 2382, 671, 2141, 3343, 677, 2387, 681, + 2147, 3886, 687, 2151, 2402, 692, 3937, 697, 2157, 2821, 702, 3349, + 708, 2403, 712, 3675, 3539, 718, 2167, 3462, 723, 3971, 2172, 728, + 2422, 733, 3781, 2178, 739, 2418, 743, 2841, 3139, 749, 2423, 753, + 2188, 3261, 759, 2192, 3680, 764, 3622, 769, 2198, 2443, 774, 3474, + 780, 2852, 784, 3276, 3364, 790, 2208, 2453, 795, 2857, 2213, 800, + 2449, 805, 2862, 2219, 811, 2454, 815, 2868, 3277, 821, 2459, 825, + 3396, 3825, 831, 2465, 2474, 836, 4007, 841, 2878, 2239, 846, 3472, + 852, 2244, 856, 3558, 3688, 862, 2250, 2883, 867, 2254, 2681, 872, + 2494, 877, 2888, 2260, 883, 2490, 887, 3644, 3495, 893, 2495, 897, + 3412, 3833, 903, 2500, 3568, 908, 4006, 913, 2506, 2280, 918, 3483, + 924, 2285, 928, 3756, 3190, 934, 2291, 2525, 939, 2295, 3401, 944, + 2521, 949, 2301, 3836, 955, 2526, 959, 3508, 2306, 965, 2531, 969, + 2311, 3840, 975, 2537, 2316, 980, 2732, 985, 3514, 2322, 990, 3420, + 996, 2547, 1000, 3583, 3710, 1006, 2332, 3595, 1011, 2336, 2752, 1016, + 2566, 1021, 2342, 3902, 3, 9, 1031, 14, 2347, 1037, 20, 24, + 2352, 3333, 30, 34, 2357, 40, 3663, 1057, 45, 50, 1062, 55, + 1068, 61, 65, 3348, 71, 1078, 2588, 76, 1083, 81, 86, 1088, + 2593, 92, 96, 2383, 1099, 102, 106, 2388, 112, 1109, 2603, 117, + 122, 3850, 127, 2398, 133, 137, 2803, 143, 2985, 2404, 148, 3442, + 153, 158, 1144, 4017, 164, 168, 3545, 2991, 174, 178, 3611, 184, + 2638, 1165, 189, 194, 1171, 199, 1175, 205, 209, 1181, 215, 1185, + 2435, 220, 1191, 225, 230, 1196, 3917, 236, 240, 2659, 1206, 246, + 250, 3016, 256, 3982, 3272, 261, 266, 2669, 271, 4064, 277, 281, + 2665, 287, 3894, 2466, 292, 2670, 297, 302, 3283, 1253, 308, 312, + 2476, 3861, 318, 322, 2690, 328, 4035, 1273, 333, 338, 1278, 343, + 1284, 349, 353, 3630, 359, 1294, 2496, 364, 1299, 369, 374, 1304, + 2710, 380, 384, 2507, 1315, 390, 394, 3057, 400, 1325, 2711, 405, + 410, 3405, 415, 2716, 421, 425, 3704, 431, 2722, 2527, 436, 3581, + 441, 446, 1360, 3314, 452, 456, 2538, 2741, 462, 466, 3415, 472, + 2737, 1381, 477, 482, 1387, 487, 1391, 493, 497, 1397, 503, 1401, + 3716, 508, 1407, 513, 518, 1412, 3875, 524, 528, 2568, 1422, 534, + 538, 2573, 544, 3655, 3667, 549, 554, 3099, 559, 2583, 565, 569, + 2782, 575, 2589, 3523, 580, 2778, 585, 590, 2594, 1469, 596, 600, + 2599, 3664, 606, 610, 2604, 616, 4074, 1489, 621, 626, 1494, 631, + 1500, 637, 641, 3355, 647, 1510, 2620, 652, 1515, 657, 662, 1520, + 2809, 668, 672, 3887, 1531, 678, 682, 3550, 688, 1541, 2819, 693, + 698, 4018, 703, 2825, 709, 713, 3263, 719, 3742, 2651, 724, 3847, + 729, 734, 1576, 3783, 740, 744, 3156, 3905, 750, 754, 3733, 760, + 2854, 1597, 765, 770, 1603, 775, 1607, 781, 785, 1613, 791, 1617, + 2682, 796, 1623, 801, 806, 1628, 4059, 812, 816, 2692, 1638, 822, + 826, 3176, 832, 3492, 3617, 837, 842, 2885, 847, 3181, 853, 857, + 2881, 863, 3187, 2712, 868, 2886, 873, 878, 3493, 1685, 884, 888, + 2723, 3897, 894, 898, 2906, 904, 3998, 1705, 909, 914, 1710, 919, + 1716, 925, 929, 3702, 935, 1726, 2743, 940, 1731, 945, 950, 1736, + 2926, 956, 960, 2754, 1747, 966, 970, 3597, 976, 1757, 2927, 981, + 986, 3928, 991, 2768, 997, 1001, 4096, 1007, 2774, 2947, 1012, 3091, + 1017, 1022, 1792, 3932, 1028, 1032, 2784, 2957, 1038, 1042, 2789, 1048, + 2953, 1813, 1053, 1058, 1819, 1063, 1823, 1069, 1073, 1829, 1079, 1833, + 3612, 1084, 1839, 1089, 1094, 1844, 4004, 1100, 1104, 2815, 1854, 1110, + 1114, 2820, 1120, 3727, 3361, 1125, 1130, 3678, 1135, 2830, 1141, 1145, + 2998, 1151, 3859, 2836, 1156, 2994, 1161, 1166, 4037, 1901, 1172, 1176, + 3628, 3549, 1182, 1186, 3737, 1192, 3832, 1921, 1197, 1202, 1926, 1207, + 1932, 1213, 1217, 3564, 1223, 1942, 2867, 1228, 1947, 1233, 1238, 1952, + 3025, 1244, 1248, 4010, 1963, 1254, 1258, 3300, 1264, 1973, 3035, 1269, + 1274, 3922, 1279, 3041, 1285, 1289, 3873, 1295, 3310, 2898, 1300, 3631, + 1305, 1310, 2008, 3966, 1316, 1320, 2908, 3315, 1326, 1330, 3185, 1336, + 3070, 2029, 1341, 1346, 2035, 1351, 2039, 1357, 1361, 2045, 1367, 2049, + 2928, 1372, 2055, 1377, 1382, 2060, 4033, 1388, 1392, 2939, 2070, 1398, + 1402, 4036, 1408, 3914, 3519, 1413, 1418, 3101, 1423, 3719, 1429, 1433, + 3097, 1439, 3909, 2959, 1444, 3102, 1449, 1454, 3530, 2117, 1460, 1464, + 2970, 3933, 1470, 1474, 3122, 1480, 3236, 2137, 1485, 1490, 2142, 1495, + 2148, 1501, 1505, 3774, 1511, 2158, 3372, 1516, 2163, 1521, 1526, 2168, + 3142, 1532, 1536, 3000, 2179, 1542, 1546, 3005, 1552, 2189, 3143, 1557, + 1562, 3621, 1567, 3015, 1573, 1577, 4021, 1583, 3021, 3163, 1588, 3479, + 1593, 1598, 2224, 3636, 1604, 1608, 3031, 3173, 1614, 1618, 3036, 1624, + 3169, 2245, 1629, 1634, 2251, 1639, 2255, 1645, 1649, 2261, 1655, 2265, + 3052, 1660, 2271, 1665, 1670, 2276, 3307, 1676, 1680, 3755, 2286, 1686, + 1690, 3195, 1696, 3799, 3308, 1701, 1706, 3423, 1711, 3708, 1717, 1721, + 3214, 1727, 3428, 3083, 1732, 3210, 1737, 1742, 3930, 2333, 1748, 1752, + 3720, 3760, 1758, 1762, 3809, 1768, 3989, 2353, 1773, 1778, 2358, 1783, + 2364, 1789, 1793, 3602, 1799, 2374, 3114, 1804, 2379, 1809, 1814, 2384, + 3241, 1820, 1824, 3124, 2395, 1830, 1834, 3735, 1840, 2405, 3251, 1845, + 1850, 3993, 1855, 3257, 1861, 1865, 4052, 1871, 3741, 3144, 1876, 3819, + 1881, 1886, 2440, 3891, 1892, 1896, 3155, 3786, 1902, 1906, 3374, 1912, + 3286, 2461, 1917, 1922, 2467, 1927, 2471, 1933, 1937, 2477, 1943, 2481, + 3175, 1948, 2487, 1953, 1958, 2492, 3904, 1964, 1968, 3186, 2502, 1974, + 1978, 3500, 1984, 3643, 3829, 1989, 1994, 3317, 1999, 3200, 2005, 2009, + 3313, 2015, 3206, 4092, 2020, 3318, 2025, 2030, 3211, 2549, 2036, 2040, + 3216, 3969, 2046, 2050, 3221, 2056, 4000, 2569, 2061, 2066, 2574, 2071, + 2580, 2077, 2081, 3846, 2087, 2590, 3776, 2092, 2595, 2097, 2102, 2600, + 3358, 2108, 2112, 3247, 2611, 2118, 2122, 3252, 2128, 2621, 3359, 2133, + 2138, 3771, 2143, 3262, 2149, 2153, 4061, 2159, 3370, 3268, 2164, 3945, + 2169, 2174, 2656, 3941, 2180, 2184, 3380, 3389, 2190, 2194, 4055, 2200, + 3385, 2677, 2205, 2210, 2683, 2215, 2687, 2221, 2225, 2693, 2231, 2697, + 3299, 2236, 2703, 2241, 2246, 2708, 3838, 2252, 2256, 3577, 2718, 2262, + 2266, 3411, 2272, 3871, 4073, 2277, 2282, 4067, 2287, 3967, 2293, 2297, + 3430, 2303, 3592, 3330, 2308, 3426, 2313, 2318, 3715, 2765, 2324, 2328, + 3340, 3765, 2334, 2338, 3881, 2344, 3910, 2785, 2349, 2354, 2790, 2359, + 2796, 2365, 2369, 3780, 2375, 2806, 3360, 2380, 2811, 2385, 2390, 2816, + 3457, 2396, 2400, 3371, 2827, 2406, 2410, 3623, 2416, 2837, 3467, 2421, + 2426, 3994, 2431, 3473, 2437, 2441, 3685, 2447, 3633, 3391, 2452, 4072, + 2457, 2462, 2872, 4028, 2468, 2472, 3402, 3639, 2478, 2482, 3987, 2488, + 3502, 2893, 2493, 2498, 2899, 2503, 2903, 2509, 2513, 2909, 2519, 2913, + 3844, 2524, 2919, 2529, 2534, 2924, 4087, 2540, 2544, 3432, 2934, 2550, + 2554, 3437, 2560, 3972, 3766, 2565, 2570, 3533, 2575, 3447, 2581, 2585, + 3529, 2591, 3453, 4060, 2596, 3534, 2601, 2606, 3458, 2981, 2612, 2616, + 3463, 4005, 2622, 2626, 3468, 2632, 3915, 3001, 2637, 2642, 3006, 2647, + 3012, 2653, 2657, 3918, 2663, 3022, 3484, 2668, 3027, 2673, 2678, 3032, + 3574, 2684, 2688, 3921, 3043, 2694, 2698, 3705, 2704, 3053, 3575, 2709, + 2714, 3837, 2719, 3580, 2725, 2729, 3951, 2735, 4, 10, 15, 25, + 35, 41, 51, 56, 66, 72, 82, 87, 97, 107, 113, 123, + 128, 138, 144, 154, 159, 169, 179, 185, 195, 200, 210, 216, + 226, 231, 241, 251, 257, 267, 272, 282, 288, 298, 303, 313, + 323, 329, 339, 344, 354, 360, 370, 375, 385, 395, 401, 411, + 416, 426, 432, 442, 447, 457, 467, 473, 483, 488, 498, 504, + 514, 519, 529, 539, 545, 555, 560, 570, 576, 586, 591, 601, + 611, 617, 627, 632, 642, 648, 658, 663, 673, 683, 689, 699, + 704, 714, 720, 730, 735, 745, 755, 761, 771, 776, 786, 792, + 802, 807, 817, 827, 833, 843, 848, 858, 864, 874, 879, 889, + 899, 905, 915, 920, 930, 936, 946, 951, 961, 971, 977, 987, + 992, 1002, 1008, 1018, 1023, 1033, 1043, 1049, 1059, 1064, 1074, 1080, + 1090, 1095, 1105, 1115, 1121, 1131, 1136, 1146, 1152, 1162, 1167, 1177, + 1187, 1193, 1203, 1208, 1218, 1224, 1234, 1239, 1249, 1259, 1265, 1275, + 1280, 1290, 1296, 1306, 1311, 1321, 1331, 1337, 1347, 1352, 1362, 1368, + 1378, 1383, 1393, 1403, 1409, 1419, 1424, 1434, 1440, 1450, 1455, 1465, + 1475, 1481, 1491, 1496, 1506, 1512, 1522, 1527, 1537, 1547, 1553, 1563, + 1568, 1578, 1584, 1594, 1599, 1609, 1619, 1625, 1635, 1640, 1650, 1656, + 1666, 1671, 1681, 1691, 1697, 1707, 1712, 1722, 1728, 1738, 1743, 1753, + 1763, 1769, 1779, 1784, 1794, 1800, 1810, 1815, 1825, 1835, 1841, 1851, + 1856, 1866, 1872, 1882, 1887, 1897, 1907, 1913, 1923, 1928, 1938, 1944, + 1954, 1959, 1969, 1979, 1985, 1995, 2000, 2010, 2016, 2026, 2031, 2041, + 2051, 2057, 2067, 2072, 2082, 2088, 2098, 2103, 2113, 2123, 2129, 2139, + 2144, 2154, 2160, 2170, 2175, 2185, 2195, 2201, 2211, 2216, 2226, 2232, + 2242, 2247, 2257, 2267, 2273, 2283, 2288, 2298, 2304, 2314, 2319, 2329, + 2339, 2345, 2355, 2360, 2370, 2376, 2386, 2391, 2401, 2411, 2417, 2427, + 2432, 2442, 2448, 2458, 2463, 2473, 2483, 2489, 2499, 2504, 2514, 2520, + 2530, 2535, 2545, 2555, 2561, 2571, 2576, 2586, 2592, 2602, 2607, 2617, + 2627, 2633, 2643, 2648, 2658, 2664, 2674, 2679, 2689, 2699, 2705, 2715, + 2720, 2730, 2736, 2746, 2751, 2761, 2771, 2777, 2787, 2792, 2802, 2808, + 2818, 2823, 2833, 2843, 2849, 2859, 2864, 2874, 2880, 2890, 2895, 2905, + 2915, 2921, 2931, 2936, 2946, 2952, 2962, 2967, 2977, 2987, 2993, 3003, + 3008, 3018, 3024, 3034, 3039, 3049, 3059, 3065, 3075, 3080, 3090, 3096, + 3106, 3111, 3121, 3131, 3137, 3147, 3152, 3162, 3168, 3178, 3183, 3193, + 3203, 3209, 3219, 3224, 3234, 3240, 3250, 3255, 3265, 3275, 3281, 3291, + 3296, 3306, 3312, 3322, 3327, 3337, 3347, 3353, 3363, 3368, 3378, 3384, + 3394, 3399, 3409, 3419, 3425, 3435, 3440, 3450, 3456, 3466, 3471, 3481, + 3491, 3497, 3507, 3512, 3522, 3528, 3538, 3543, 3553, 3563, 3569, 3579, + 3584, 3594, 3600, 3610, 3615, 3625, 3635, 3641, 3651, 3656, 3666, 3672, + 3682, 3687, 3697, 3707, 3713, 3723, 3728, 3738, 3744, 3754, 3759, 3769, + 3779, 3785, 3795, 3800, 3810, 3816, 3826, 3831, 3841, 3851, 3857, 3867, + 3872, 3882, 3888, 3898, 3903, 3913, 3923, 3929, 3939, 3944, 3954, 3960, + 3970, 3975, 3985, 3995, 4001, 4011, 4016, 4026, 4032, 4042, 4047, 4057, + 4089, 4090, 4094, 4095, 5 +}; + static int cmp(const void *v1, const void *v2) { @@ -93,6 +1413,7 @@ static void fill_test_array(int *x, int n, int dist, int m) { int i, j, k; + const int *bmk; switch (dist) { case SAWTOOTH: @@ -115,6 +1436,35 @@ fill_test_array(int *x, int n, int dist, int m) for (i = 0, j = 0, k = 1; i < n; i++) x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); break; + case BM_KILLER: + switch (n) { + case 100: + bmk = bmkiller_100; + break; + case 1023: + bmk = bmkiller_1023; + break; + case 1024: + bmk = bmkiller_1024; + break; + case 1025: + bmk = bmkiller_1025; + break; + case 4095: + bmk = bmkiller_4095; + break; + case 4096: + bmk = bmkiller_4096; + break; + case 4097: + bmk = bmkiller_4097; + break; + default: + err(1, "unexpected array length %d", n); + } + for (i = 0; i < n; i++) + x[i] = bmk[i]; + break; case BSD_KILLER: /* 4.4BSD insertion sort optimization killer, Mats Linander */ k = n / 2; @@ -263,6 +1613,39 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) return ret; } +/* + * Like test_distribution() but because the input is tailored to cause + * quicksort to go quadratic we don't perturb the input. + */ +static int +test_killer(int dist, int n, int *x, int *y, int *z) +{ + int i, ret = 0; + + /* Fill in x[] with "killer" input */ + fill_test_array(x, n, dist, 0); + + /* Make a copy of x[] */ + for (i = 0; i < n; i++) + y[i] = z[i] = x[i]; + compares = 0; + if (sigsetjmp(cmpjmp, 1) != 0) { + warnx("qsort aborted: %zu compares, dist %d, n: %d", + compares, dist, n); + ret = 1; + } else { + qsort(y, n, sizeof(y[0]), cmp_checked); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); + /* For killer input we don't check max_compares. */ + compares = 0; + if (check_result("killer", y, z, dist, 0, n) != 0) + ret = 1; + } + + return ret; +} + static int run_tests(int n) { @@ -290,10 +1673,10 @@ run_tests(int n) for (dist = SAWTOOTH; dist != INVALID; dist++) { switch (dist) { + case BM_KILLER: case BSD_KILLER: case MED3_KILLER: - /* 'm' not used. */ - if (test_distribution(dist, 0, n, x, y, z) != 0) + if (test_killer(dist, n, x, y, z) != 0) ret = 1; break; default: |