#define R 500 #define C 500 #define NNZ 2399 const double val[2399] = { 566, 508, 850, 780, 944, 598, 772, 880, 764, 656, 138, 757, 929, 234, 168, 629, 639, 434, 849, 793, 203, 811, 250, 770, 322, 535, 826, 609, 899, 926, 211, 755, 900, 691, 386, 821, 454, 791, 849, 256, 821, 29, 679, 944, 55, 689, 453, 631, 799, 854, 545, 97, 337, 258, 695, 667, 581, 104, 491, 517, 761, 369, 316, 42, 86, 432, 954, 736, 333, 321, 184, 920, 258, 949, 604, 907, 70, 453, 796, 102, 3, 105, 371, 388, 153, 908, 176, 567, 334, 973, 911, 323, 681, 300, 265, 711, 871, 870, 463, 969, 535, 688, 276, 908, 384, 988, 256, 416, 258, 523, 80, 911, 241, 191, 411, 127, 894, 259, 664, 129, 609, 146, 763, 109, 369, 881, 878, 224, 635, 498, 460, 363, 481, 222, 761, 489, 753, 62, 261, 389, 351, 189, 319, 557, 5, 485, 806, 119, 366, 85, 123, 918, 66, 205, 786, 313, 555, 22, 760, 904, 255, 912, 950, 676, 342, 736, 251, 170, 923, 790, 312, 716, 648, 57, 676, 972, 250, 215, 792, 798, 915, 61, 381, 897, 686, 568, 393, 969, 893, 205, 721, 684, 38, 667, 704, 750, 364, 123, 158, 892, 306, 409, 188, 394, 554, 602, 59, 9, 987, 897, 332, 873, 770, 632, 434, 598, 599, 207, 211, 410, 768, 708, 462, 687, 300, 864, 839, 183, 21, 282, 990, 578, 952, 42, 149, 235, 777, 156, 568, 400, 783, 238, 390, 108, 422, 392, 414, 338, 524, 535, 893, 160, 163, 798, 836, 662, 181, 946, 774, 113, 438, 721, 631, 577, 739, 62, 928, 523, 352, 603, 974, 291, 47, 875, 260, 754, 13, 890, 989, 104, 22, 36, 803, 39, 241, 95, 589, 603, 230, 471, 978, 617, 603, 652, 21, 755, 294, 753, 609, 494, 93, 387, 243, 128, 777, 636, 303, 665, 761, 355, 611, 605, 627, 834, 616, 59, 109, 268, 638, 117, 338, 89, 95, 4, 64, 575, 300, 783, 453, 878, 939, 984, 338, 344, 138, 291, 440, 748, 277, 628, 511, 894, 68, 412, 958, 540, 672, 935, 316, 519, 4, 613, 501, 908, 984, 820, 424, 726, 592, 526, 869, 330, 419, 28, 540, 143, 279, 79, 712, 760, 306, 806, 507, 807, 716, 729, 163, 151, 256, 873, 90, 374, 89, 122, 819, 253, 961, 62, 208, 830, 365, 231, 905, 961, 340, 928, 911, 83, 118, 864, 310, 699, 138, 221, 928, 130, 775, 425, 783, 519, 852, 187, 795, 772, 627, 709, 81, 264, 359, 149, 692, 178, 247, 51, 869, 30, 659, 190, 494, 80, 531, 883, 557, 170, 759, 331, 588, 939, 953, 407, 453, 223, 919, 147, 666, 165, 204, 924, 178, 361, 766, 455, 232, 86, 194, 536, 942, 671, 595, 420, 543, 490, 570, 547, 273, 465, 776, 845, 753, 591, 22, 320, 569, 964, 701, 483, 100, 757, 514, 850, 50, 451, 993, 79, 79, 790, 410, 409, 494, 245, 881, 676, 484, 821, 183, 45, 343, 76, 423, 855, 188, 16, 355, 159, 255, 705, 147, 400, 997, 264, 831, 644, 390, 395, 485, 457, 879, 478, 900, 187, 699, 559, 681, 947, 137, 637, 150, 700, 729, 166, 120, 325, 841, 956, 74, 576, 532, 396, 157, 327, 601, 707, 681, 813, 593, 452, 45, 936, 466, 706, 546, 265, 769, 71, 862, 37, 764, 111, 468, 844, 693, 740, 128, 19, 579, 894, 928, 160, 787, 438, 814, 274, 675, 128, 451, 626, 879, 931, 894, 57, 181, 839, 121, 728, 410, 793, 292, 566, 472, 893, 579, 986, 159, 585, 34, 485, 279, 634, 353, 626, 504, 574, 19, 54, 489, 829, 768, 246, 421, 116, 267, 801, 299, 279, 397, 331, 396, 11, 80, 682, 752, 101, 832, 673, 521, 42, 883, 663, 905, 284, 218, 59, 888, 86, 623, 878, 117, 157, 70, 309, 877, 803, 529, 666, 274, 192, 667, 558, 938, 383, 542, 237, 377, 674, 783, 638, 609, 419, 359, 309, 53, 65, 277, 526, 853, 659, 263, 280, 332, 940, 336, 748, 645, 227, 475, 945, 924, 845, 253, 798, 49, 241, 761, 379, 423, 680, 837, 116, 378, 416, 553, 802, 839, 339, 424, 40, 101, 744, 934, 119, 217, 478, 850, 998, 513, 320, 966, 306, 774, 442, 417, 646, 652, 15, 637, 199, 653, 516, 380, 983, 281, 196, 973, 604, 378, 824, 773, 835, 724, 450, 321, 446, 778, 935, 296, 752, 27, 824, 933, 145, 708, 691, 433, 627, 511, 619, 415, 263, 680, 880, 201, 700, 440, 579, 545, 445, 483, 499, 953, 518, 77, 237, 980, 923, 809, 532, 877, 965, 865, 597, 773, 378, 177, 101, 899, 448, 430, 217, 403, 21, 837, 410, 345, 606, 373, 179, 310, 634, 894, 512, 289, 946, 243, 725, 458, 680, 579, 304, 199, 721, 22, 452, 761, 945, 547, 418, 137, 209, 622, 174, 468, 223, 525, 84, 470, 266, 812, 950, 18, 983, 319, 843, 423, 862, 469, 957, 919, 387, 900, 382, 561, 337, 711, 352, 206, 737, 412, 40, 17, 851, 825, 910, 839, 207, 879, 588, 77, 867, 255, 577, 1, 609, 473, 88, 249, 491, 180, 594, 872, 870, 528, 68, 31, 208, 854, 190, 32, 200, 225, 322, 869, 425, 62, 653, 919, 138, 246, 501, 995, 133, 852, 903, 694, 482, 818, 820, 922, 839, 870, 391, 880, 478, 602, 774, 989, 139, 457, 114, 282, 632, 245, 452, 987, 920, 134, 94, 409, 124, 389, 36, 434, 885, 486, 269, 510, 487, 644, 122, 773, 13, 326, 369, 252, 407, 599, 182, 319, 229, 684, 895, 760, 703, 982, 282, 645, 835, 415, 182, 792, 681, 113, 659, 312, 998, 954, 655, 588, 3, 268, 125, 832, 346, 832, 972, 488, 709, 491, 913, 441, 187, 177, 90, 55, 959, 126, 73, 409, 606, 732, 985, 833, 381, 542, 559, 375, 829, 50, 432, 549, 996, 517, 3, 366, 33, 737, 451, 111, 380, 362, 884, 511, 199, 262, 647, 531, 717, 810, 675, 946, 614, 425, 282, 31, 436, 695, 701, 653, 629, 284, 109, 237, 909, 269, 495, 386, 327, 620, 947, 782, 663, 471, 818, 517, 768, 494, 249, 815, 725, 822, 614, 324, 22, 675, 118, 143, 929, 498, 368, 469, 482, 964, 554, 999, 265, 686, 782, 754, 247, 125, 960, 808, 788, 647, 623, 615, 727, 573, 813, 200, 371, 141, 733, 450, 515, 940, 304, 13, 522, 489, 948, 906, 529, 500, 98, 719, 174, 269, 170, 609, 789, 169, 645, 514, 438, 254, 103, 938, 306, 608, 367, 889, 667, 621, 276, 346, 736, 210, 13, 356, 914, 377, 613, 714, 949, 386, 770, 738, 310, 382, 145, 163, 470, 34, 855, 951, 672, 192, 942, 936, 429, 906, 378, 159, 665, 208, 223, 575, 977, 937, 81, 24, 484, 941, 128, 544, 811, 905, 110, 707, 806, 996, 509, 283, 493, 846, 466, 356, 807, 993, 616, 790, 163, 7, 931, 661, 353, 499, 186, 309, 107, 556, 104, 702, 61, 963, 255, 279, 454, 941, 817, 447, 786, 788, 372, 919, 14, 113, 41, 412, 744, 372, 282, 648, 248, 484, 830, 104, 742, 425, 802, 216, 561, 103, 781, 602, 201, 317, 408, 461, 91, 691, 168, 850, 935, 171, 929, 482, 790, 701, 81, 556, 85, 342, 703, 99, 937, 556, 14, 203, 974, 200, 145, 276, 408, 174, 573, 775, 893, 448, 21, 389, 813, 62, 134, 911, 119, 138, 201, 200, 105, 0, 958, 439, 635, 723, 930, 361, 745, 251, 608, 179, 19, 170, 405, 461, 643, 517, 379, 481, 899, 896, 396, 675, 536, 978, 513, 459, 454, 704, 398, 5, 786, 45, 843, 674, 758, 919, 250, 655, 980, 789, 55, 467, 459, 284, 1, 951, 447, 729, 756, 581, 992, 961, 744, 531, 169, 484, 346, 289, 18, 143, 653, 221, 669, 537, 565, 552, 874, 502, 352, 458, 183, 975, 521, 272, 336, 930, 129, 678, 670, 821, 692, 463, 175, 958, 110, 393, 123, 174, 768, 70, 942, 237, 787, 788, 462, 471, 160, 526, 579, 835, 889, 764, 878, 532, 151, 390, 607, 272, 49, 166, 399, 950, 566, 866, 446, 188, 552, 984, 530, 711, 541, 357, 30, 212, 675, 750, 746, 67, 55, 184, 788, 27, 314, 650, 403, 24, 72, 872, 260, 313, 446, 235, 275, 422, 727, 779, 192, 215, 92, 534, 619, 192, 502, 139, 125, 921, 953, 463, 909, 961, 191, 281, 619, 978, 221, 841, 540, 959, 422, 610, 323, 162, 642, 817, 961, 699, 955, 341, 480, 379, 28, 150, 386, 447, 871, 491, 632, 759, 785, 827, 50, 877, 771, 397, 67, 827, 448, 627, 85, 830, 646, 353, 304, 671, 963, 764, 58, 136, 838, 597, 932, 212, 558, 276, 73, 926, 403, 946, 268, 779, 559, 887, 213, 436, 529, 929, 295, 76, 78, 982, 105, 688, 420, 105, 815, 572, 172, 584, 412, 314, 219, 182, 238, 789, 877, 844, 62, 124, 711, 787, 315, 954, 296, 453, 842, 681, 282, 945, 132, 695, 443, 837, 92, 545, 363, 253, 515, 341, 409, 817, 578, 868, 542, 805, 508, 987, 286, 451, 157, 58, 126, 707, 874, 501, 982, 986, 382, 41, 829, 616, 895, 505, 627, 795, 555, 774, 968, 377, 762, 317, 742, 635, 481, 850, 989, 438, 72, 210, 611, 451, 521, 454, 85, 277, 797, 147, 31, 74, 621, 119, 180, 571, 234, 358, 131, 70, 857, 330, 438, 379, 166, 33, 920, 139, 316, 776, 266, 284, 247, 949, 689, 857, 534, 355, 648, 302, 840, 847, 958, 2, 602, 455, 372, 229, 370, 417, 221, 792, 91, 217, 154, 508, 45, 317, 33, 819, 48, 243, 601, 291, 613, 242, 333, 505, 537, 301, 299, 466, 927, 92, 775, 212, 985, 173, 32, 595, 643, 416, 911, 959, 252, 832, 808, 907, 761, 548, 551, 664, 728, 190, 280, 384, 822, 715, 834, 191, 437, 241, 529, 268, 38, 151, 14, 269, 679, 357, 110, 200, 393, 837, 212, 46, 336, 193, 291, 985, 975, 524, 149, 599, 424, 141, 729, 703, 238, 589, 660, 263, 319, 946, 238, 368, 728, 660, 168, 66, 679, 500, 359, 281, 159, 189, 608, 793, 204, 706, 72, 77, 660, 751, 38, 154, 437, 76, 264, 859, 216, 156, 983, 886, 802, 924, 144, 995, 643, 614, 295, 229, 125, 29, 106, 625, 27, 203, 327, 995, 123, 975, 379, 576, 258, 186, 545, 719, 530, 832, 867, 144, 146, 619, 623, 110, 218, 779, 481, 281, 826, 771, 569, 907, 342, 317, 353, 5, 360, 421, 70, 130, 42, 514, 648, 409, 909, 401, 487, 72, 580, 4, 76, 515, 382, 64, 193, 212, 20, 604, 478, 901, 784, 277, 761, 681, 429, 470, 57, 648, 609, 997, 71, 745, 876, 41, 946, 522, 339, 247, 221, 962, 110, 844, 679, 416, 522, 429, 767, 5, 819, 450, 66, 644, 722, 937, 539, 977, 727, 846, 973, 391, 699, 656, 496, 444, 173, 415, 717, 463, 935, 954, 248, 450, 892, 733, 537, 434, 920, 671, 223, 891, 252, 313, 122, 393, 156, 131, 595, 81, 71, 936, 906, 590, 187, 810, 812, 639, 626, 233, 335, 341, 253, 956, 363, 995, 971, 810, 478, 206, 382, 874, 580, 308, 178, 734, 834, 576, 938, 126, 877, 939, 274, 793, 364, 64, 347, 470, 975, 22, 14, 297, 674, 400, 8, 274, 842, 128, 102, 183, 978, 687, 614, 545, 770, 18, 353, 892, 301, 327, 497, 271, 822, 509, 154, 588, 543, 561, 632, 90, 413, 29, 462, 925, 667, 203, 846, 271, 353, 647, 434, 888, 392, 82, 445, 865, 709, 515, 382, 799, 672, 975, 466, 482, 168, 10, 150, 317, 606, 550, 166, 672, 522, 968, 605, 945, 949, 506, 353, 905, 660, 906, 490, 74, 493, 82, 47, 526, 850, 257, 308, 227, 343, 95, 260, 539, 593, 197, 304, 384, 589, 179, 553, 389, 851, 731, 831, 711, 357, 554, 982, 2, 351, 879, 42, 400, 205, 228, 328, 820, 275, 850, 320, 253, 621, 873, 842, 846, 108, 180, 300, 514, 658, 211, 373, 301, 202, 930, 489, 581, 815, 175, 738, 551, 711, 609, 343, 606, 123, 411, 851, 207, 742, 296, 741, 184, 175, 497, 32, 550, 37, 970, 526, 430, 575, 242, 934, 283, 965, 561, 702, 750, 902, 964, 711, 92, 670, 243, 188, 481, 460, 556, 886, 890, 502, 473, 8, 288, 57, 356, 721, 112, 817, 282, 123, 680, 344, 21, 935, 60, 287, 444, 267, 30, 447, 310, 922, 284, 442, 651, 454, 924, 771, 611, 852, 986, 367, 399, 115, 370, 326, 765, 323, 640, 906, 242, 526, 876, 899, 624, 166, 796, 252, 431, 99, 626, 870, 928, 935, 229, 286, 20, 648, 539, 533, 379, 64, 179, 317, 896, 293, 144, 971, 401, 720, 986, 286, 277, 828, 671, 66, 566, 461, 847, 904, 318, 59, 621, 958, 590, 905, 849, 718, 338, 342, 730, 22, 944, 544, 25, 348, 39, 719, 705, 596, 908, 805, 594, 7, 47, 744, 148, 177, 476, 866, 849, 88, 246, 438, 523, 156, 886, 758, 605, 39, 209, 29, 678, 98, 879, 286, 447, 105, 832, 303, 190, 164, 969, 222, 995, 331, 492, 399, 824, 14, 405, 831, 597, 670, 857, 120, 873, 171, 890, 905, 637, 115, 605, 336, 114, 828, 284, 303, 883, 158, 494, 153, 549, 232, 556, 695, 58, 29, 504, 252, 77, 35, 646, 137, 448, 400, 468, 237, 258, 857, 150, 981, 756, 616, 138, 188, 386, 721, 370, 71, 911, 73, 967, 568, 504, 164, 770, 100, 179, 753, 551, 67, 657, 652, 243, 444, 398, 865, 772, 427, 338, 592, 63, 536, 519, 721, 83, 212, 451, 148, 117, 98, 888, 61, 734, 672, 502, 723, 783, 345, 338, 740, 909, 505, 839, 975, 654, 804, 611, 69, 11, 523, 629, 404, 856, 620, 442, 578, 574, 149, 135, 970, 938, 492, 713, 886, 639, 454, 376, 594, 374, 530, 634, 168, 566, 809, 268, 110, 766, 381, 754, 592, 582, 283, 0, 298, 246, 854, 1, 663, 430, 801, 700, 519, 357, 169, 8, 136, 246, 613, 300, 148, 884, 563, 392, 99, 846, 824, 322, 293, 341, 555, 193, 718, 570, 822, 222, 854, 12, 226, 16, 516, 920, 639, 838, 670, 529, 485, 959, 912, 543, 706, 877, 863, 852, 351, 912, 640, 705, 697, 687, 241, 287, 290, 930, 964, 1 }; const int idx[2399] = { 220, 336, 347, 422, 44, 128, 145, 234, 259, 315, 64, 103, 378, 469, 477, 33, 108, 126, 173, 196, 328, 331, 52, 55, 109, 306, 337, 412, 443, 364, 456, 487, 496, 299, 23, 259, 67, 196, 409, 51, 77, 147, 301, 362, 26, 106, 239, 39, 81, 118, 187, 290, 339, 395, 443, 36, 45, 195, 210, 244, 273, 22, 92, 215, 306, 364, 66, 216, 5, 25, 145, 171, 330, 401, 412, 75, 148, 180, 204, 231, 432, 443, 100, 232, 400, 467, 114, 284, 300, 330, 370, 49, 135, 183, 191, 268, 423, 491, 104, 280, 393, 442, 443, 461, 136, 175, 205, 216, 466, 5, 85, 429, 491, 0, 36, 78, 95, 161, 169, 219, 231, 250, 336, 341, 360, 495, 59, 134, 213, 319, 409, 93, 104, 256, 223, 226, 8, 115, 185, 216, 320, 399, 461, 14, 60, 87, 93, 134, 170, 391, 399, 416, 455, 3, 86, 99, 304, 471, 488, 0, 102, 132, 179, 303, 312, 313, 320, 389, 279, 473, 180, 303, 310, 326, 7, 136, 239, 256, 276, 350, 21, 32, 79, 209, 270, 314, 463, 87, 134, 188, 212, 418, 13, 76, 124, 179, 409, 411, 19, 299, 207, 266, 329, 468, 29, 45, 265, 310, 384, 429, 480, 191, 347, 61, 66, 219, 228, 277, 289, 308, 402, 409, 133, 382, 488, 18, 310, 439, 206, 257, 290, 356, 443, 43, 140, 184, 187, 278, 286, 341, 354, 126, 201, 208, 239, 454, 485, 40, 87, 222, 367, 398, 457, 299, 423, 440, 44, 115, 126, 147, 291, 411, 64, 480, 1, 67, 80, 91, 163, 239, 42, 350, 361, 427, 67, 169, 270, 15, 44, 223, 378, 452, 471, 31, 67, 274, 292, 457, 58, 107, 183, 222, 347, 407, 27, 65, 84, 208, 273, 385, 441, 43, 97, 226, 305, 360, 492, 26, 88, 284, 369, 476, 21, 48, 478, 230, 312, 409, 475, 42, 53, 78, 259, 268, 489, 3, 37, 60, 141, 132, 150, 157, 328, 353, 357, 422, 466, 480, 154, 455, 295, 411, 249, 320, 359, 381, 401, 451, 210, 231, 253, 323, 330, 5, 55, 79, 105, 298, 496, 160, 229, 425, 30, 63, 115, 129, 280, 458, 31, 68, 254, 360, 420, 490, 2, 172, 180, 209, 223, 228, 265, 357, 369, 380, 443, 453, 483, 36, 110, 129, 135, 246, 305, 36, 211, 239, 254, 392, 403, 494, 255, 332, 485, 110, 360, 498, 0, 11, 37, 106, 182, 308, 14, 41, 75, 218, 256, 259, 294, 462, 218, 231, 248, 392, 427, 21, 234, 406, 29, 171, 248, 255, 352, 34, 57, 122, 173, 254, 308, 380, 393, 278, 28, 62, 129, 296, 455, 474, 15, 47, 128, 133, 300, 390, 459, 468, 35, 48, 70, 287, 299, 318, 22, 108, 171, 195, 460, 496, 188, 21, 31, 86, 338, 420, 422, 486, 495, 245, 445, 22, 85, 92, 337, 381, 387, 7, 9, 231, 425, 430, 56, 196, 344, 354, 377, 91, 107, 177, 221, 295, 321, 5, 35, 48, 90, 290, 432, 447, 51, 322, 324, 364, 482, 59, 303, 334, 444, 450, 55, 125, 319, 380, 394, 431, 82, 112, 157, 187, 261, 326, 347, 366, 18, 124, 490, 8, 218, 291, 35, 132, 322, 425, 147, 150, 242, 472, 186, 195, 201, 216, 251, 458, 33, 46, 153, 297, 298, 311, 322, 399, 426, 65, 230, 9, 32, 69, 391, 70, 126, 147, 222, 86, 261, 412, 183, 474, 110, 125, 172, 185, 402, 363, 403, 462, 40, 274, 386, 449, 333, 340, 421, 424, 410, 30, 86, 262, 374, 23, 72, 9, 47, 86, 93, 286, 304, 402, 420, 118, 265, 276, 283, 455, 20, 36, 391, 115, 137, 305, 334, 10, 188, 237, 271, 393, 422, 497, 21, 30, 99, 109, 175, 198, 467, 3, 19, 63, 82, 115, 149, 265, 24, 151, 217, 252, 307, 421, 146, 333, 381, 434, 32, 311, 361, 93, 142, 152, 395, 422, 467, 91, 181, 244, 294, 332, 390, 97, 177, 296, 323, 428, 27, 215, 318, 66, 193, 216, 333, 416, 127, 171, 209, 219, 333, 377, 401, 9, 103, 129, 135, 290, 438, 33, 107, 221, 351, 392, 406, 91, 170, 182, 313, 419, 465, 28, 74, 175, 231, 270, 30, 34, 240, 253, 63, 133, 337, 369, 416, 255, 445, 145, 350, 416, 183, 257, 414, 136, 164, 255, 300, 434, 438, 447, 60, 157, 396, 412, 25, 343, 42, 105, 361, 472, 34, 74, 136, 436, 474, 94, 177, 205, 225, 227, 319, 23, 245, 383, 426, 31, 190, 215, 228, 324, 416, 7, 12, 260, 470, 13, 290, 9, 44, 117, 166, 186, 260, 361, 372, 224, 241, 369, 1, 87, 297, 457, 29, 98, 118, 158, 226, 286, 74, 167, 241, 328, 370, 412, 454, 1, 37, 183, 228, 311, 336, 345, 413, 430, 446, 211, 327, 375, 84, 195, 219, 430, 447, 195, 384, 50, 93, 224, 349, 479, 6, 56, 105, 118, 170, 286, 468, 466, 153, 224, 240, 400, 444, 63, 158, 196, 237, 284, 296, 405, 407, 480, 26, 56, 233, 428, 370, 398, 491, 159, 184, 488, 131, 134, 138, 276, 344, 372, 428, 494, 269, 486, 136, 139, 163, 201, 253, 272, 374, 398, 487, 307, 375, 487, 168, 284, 346, 420, 451, 134, 175, 284, 88, 105, 286, 448, 96, 117, 177, 240, 285, 325, 455, 51, 228, 298, 421, 150, 433, 182, 362, 410, 58, 262, 352, 439, 43, 70, 134, 278, 152, 210, 283, 310, 333, 334, 469, 20, 42, 69, 222, 283, 320, 330, 376, 218, 285, 413, 434, 5, 175, 180, 265, 440, 474, 241, 255, 377, 479, 307, 317, 457, 0, 232, 342, 496, 25, 292, 105, 169, 208, 300, 439, 21, 65, 120, 249, 273, 191, 302, 376, 56, 92, 240, 371, 391, 446, 489, 84, 241, 322, 473, 475, 16, 92, 214, 239, 50, 158, 175, 452, 51, 360, 25, 39, 90, 99, 133, 408, 491, 430, 12, 64, 76, 189, 481, 128, 306, 442, 77, 276, 337, 356, 380, 389, 445, 61, 158, 194, 445, 303, 398, 143, 163, 199, 343, 236, 246, 340, 382, 446, 38, 154, 196, 202, 266, 367, 369, 117, 136, 250, 272, 413, 481, 0, 199, 205, 412, 39, 177, 198, 369, 448, 91, 153, 167, 187, 203, 265, 328, 218, 222, 261, 413, 419, 447, 128, 228, 498, 0, 148, 198, 486, 497, 50, 398, 457, 283, 460, 43, 116, 246, 248, 305, 447, 106, 131, 317, 126, 199, 235, 293, 34, 108, 226, 3, 108, 129, 155, 174, 162, 239, 490, 124, 214, 346, 469, 497, 274, 316, 122, 144, 149, 290, 337, 362, 371, 466, 67, 248, 276, 332, 360, 387, 405, 31, 56, 65, 90, 200, 64, 176, 203, 215, 236, 240, 337, 383, 198, 411, 431, 36, 90, 350, 356, 497, 33, 120, 130, 183, 409, 493, 8, 35, 254, 277, 321, 341, 388, 423, 497, 143, 163, 391, 446, 492, 9, 270, 42, 52, 116, 396, 456, 478, 491, 143, 148, 286, 328, 384, 35, 127, 351, 452, 7, 46, 259, 35, 290, 370, 420, 104, 258, 278, 340, 481, 169, 264, 368, 232, 471, 1, 135, 211, 152, 174, 177, 187, 292, 411, 430, 461, 4, 92, 205, 237, 247, 333, 53, 91, 289, 334, 425, 491, 118, 175, 490, 36, 361, 33, 186, 213, 471, 3, 73, 163, 409, 235, 384, 410, 470, 480, 59, 469, 97, 344, 372, 33, 107, 179, 397, 470, 291, 340, 361, 385, 25, 111, 158, 331, 471, 28, 87, 307, 69, 105, 159, 284, 311, 312, 359, 465, 17, 133, 302, 324, 274, 325, 421, 252, 4, 96, 409, 206, 246, 288, 58, 81, 150, 226, 232, 380, 168, 229, 367, 210, 248, 405, 420, 163, 212, 320, 340, 448, 68, 222, 439, 494, 70, 94, 116, 471, 284, 380, 13, 26, 120, 276, 394, 432, 492, 281, 297, 300, 355, 29, 32, 156, 182, 467, 203, 234, 420, 429, 210, 224, 248, 273, 326, 349, 37, 202, 377, 380, 43, 55, 139, 141, 170, 232, 292, 322, 77, 214, 241, 279, 326, 18, 46, 55, 107, 227, 238, 250, 146, 168, 402, 444, 459, 487, 495, 6, 121, 256, 303, 457, 461, 69, 122, 193, 204, 240, 347, 412, 418, 476, 169, 187, 400, 97, 290, 364, 394, 153, 184, 187, 9, 13, 65, 89, 120, 221, 484, 6, 120, 180, 419, 15, 86, 104, 193, 276, 324, 437, 443, 62, 97, 193, 288, 315, 318, 414, 24, 170, 189, 196, 216, 228, 270, 420, 214, 407, 466, 2, 77, 127, 188, 230, 310, 464, 469, 80, 204, 138, 171, 252, 424, 0, 95, 363, 395, 408, 430, 96, 143, 289, 97, 183, 341, 399, 460, 84, 243, 498, 28, 65, 77, 84, 139, 147, 171, 214, 256, 348, 408, 444, 449, 457, 120, 342, 38, 217, 465, 8, 212, 268, 346, 486, 491, 49, 77, 90, 222, 291, 383, 130, 405, 431, 473, 78, 290, 351, 189, 304, 498, 336, 10, 219, 257, 402, 437, 65, 69, 168, 198, 65, 241, 242, 290, 360, 402, 254, 256, 398, 407, 66, 97, 164, 222, 316, 390, 429, 24, 81, 133, 207, 313, 67, 108, 204, 303, 494, 43, 194, 198, 285, 294, 347, 356, 394, 83, 92, 147, 167, 386, 20, 225, 400, 172, 363, 99, 64, 373, 377, 6, 63, 206, 107, 149, 230, 428, 41, 56, 77, 78, 311, 413, 476, 477, 81, 130, 145, 167, 247, 416, 56, 289, 339, 27, 47, 132, 309, 392, 36, 55, 73, 352, 358, 25, 58, 352, 430, 58, 171, 221, 334, 379, 453, 288, 479, 109, 134, 143, 174, 285, 313, 468, 495, 258, 289, 334, 382, 483, 46, 136, 264, 417, 458, 36, 59, 88, 173, 310, 316, 354, 471, 46, 225, 262, 335, 364, 468, 121, 341, 349, 7, 14, 21, 99, 135, 142, 207, 209, 272, 294, 456, 491, 208, 248, 321, 43, 129, 188, 362, 191, 279, 294, 307, 324, 362, 140, 422, 56, 169, 188, 232, 328, 449, 14, 134, 369, 375, 48, 164, 224, 260, 20, 93, 157, 219, 262, 274, 362, 473, 484, 103, 125, 140, 174, 175, 191, 226, 358, 408, 450, 20, 94, 289, 310, 311, 448, 478, 36, 175, 185, 337, 391, 48, 72, 184, 233, 345, 485, 231, 242, 339, 451, 456, 152, 158, 398, 458, 488, 151, 240, 357, 1, 33, 139, 141, 177, 223, 289, 479, 90, 115, 461, 480, 24, 26, 44, 72, 213, 361, 445, 34, 119, 470, 19, 56, 405, 464, 47, 112, 163, 235, 342, 462, 103, 192, 225, 23, 458, 68, 270, 363, 422, 427, 449, 450, 477, 105, 131, 139, 198, 212, 413, 429, 435, 43, 278, 19, 113, 192, 327, 347, 44, 67, 160, 225, 263, 330, 344, 158, 274, 303, 317, 350, 379, 409, 33, 53, 217, 273, 304, 352, 461, 495, 101, 168, 370, 395, 458, 156, 301, 319, 324, 347, 73, 127, 253, 272, 128, 212, 237, 257, 351, 77, 106, 216, 270, 368, 371, 400, 223, 355, 384, 30, 268, 307, 368, 79, 300, 317, 327, 15, 376, 31, 80, 160, 206, 227, 103, 231, 435, 481, 499, 182, 186, 189, 442, 7, 59, 65, 117, 225, 298, 304, 364, 457, 489, 186, 198, 265, 309, 336, 391, 457, 314, 418, 81, 133, 186, 190, 227, 258, 277, 419, 492, 82, 222, 239, 315, 71, 92, 122, 220, 252, 272, 311, 391, 433, 97, 137, 244, 267, 426, 34, 202, 234, 426, 428, 51, 109, 267, 377, 382, 107, 166, 203, 337, 0, 127, 247, 404, 64, 94, 373, 430, 448, 17, 37, 57, 102, 352, 354, 114, 174, 193, 241, 284, 74, 94, 213, 238, 475, 476, 140, 247, 280, 302, 328, 49, 197, 201, 222, 280, 457, 167, 445, 465, 478, 499, 25, 215, 438, 8, 129, 153, 171, 316, 328, 158, 215, 303, 328, 353, 479, 62, 251, 271, 4, 119, 262, 303, 311, 405, 419, 277, 461, 236, 248, 445, 15, 108, 227, 309, 362, 378, 424, 78, 94, 109, 118, 124, 247, 253, 315, 478, 13, 154, 170, 331, 365, 386, 264, 268, 300, 305, 429, 463, 499, 52, 105, 135, 181, 111, 156, 183, 231, 350, 388, 461, 291, 360, 80, 106, 138, 197, 242, 255, 260, 381, 415, 447, 499, 41, 266, 341, 391, 410, 448, 495, 58, 146, 286, 351, 419, 436, 464, 483, 251, 252, 444, 492, 184, 200, 57, 75, 170, 186, 187, 275, 314, 364, 407, 162, 173, 232, 211, 355, 445, 448, 308, 98, 280, 397, 431, 112, 122, 157, 209, 338, 388, 429, 112, 213, 349, 470, 69, 70, 119, 222, 251, 453, 81, 173, 482, 105, 147, 10, 229, 462, 467, 98, 421, 479, 203, 498, 499, 93, 130, 142, 270, 278, 336, 419, 73, 134, 142, 177, 192, 335, 490, 45, 140, 143, 195, 274, 284, 324, 56, 94, 171, 28, 135, 258, 277, 284, 333, 370, 421, 432, 465, 31, 46, 222, 331, 387, 432, 18, 56, 82, 95, 258, 261, 356, 378, 484, 60, 285, 298, 347, 0, 200, 307, 372, 2, 89, 201, 291, 298, 382, 455, 121, 145, 155, 47, 226, 236, 396, 398, 137, 311, 381, 429, 45, 109, 141, 173, 207, 464, 471, 499, 37, 45, 268, 447, 496, 41, 163, 387, 484, 30, 48, 91, 146, 261, 313, 401, 11, 78, 122, 144, 450, 499, 75, 82, 131, 218, 257, 285, 294, 362, 442, 213, 255, 291, 492, 63, 80, 282, 418, 1, 60, 87, 102, 111, 180, 272, 281, 324, 380, 458, 185, 216, 475, 12, 62, 109, 143, 195, 257, 271, 324, 385, 410, 226, 330, 404, 54, 158, 374, 221, 320, 340, 86, 93, 236, 94, 159, 238, 242, 318, 356, 40, 75, 168, 211, 294, 32, 164, 174, 198, 421, 13, 102, 314, 379, 418, 439, 485, 6, 53, 104, 123, 208, 436, 452, 59, 141, 204, 402, 498, 134, 335, 429, 240, 391, 461, 14, 16, 46, 371, 376, 37, 172, 227, 343, 397, 435, 39, 136, 202, 262, 339, 445, 474, 145, 272, 342, 121, 127, 12, 125, 155, 186, 234, 64, 96, 97, 108, 213, 350, 410, 485, 35, 56, 57, 167, 169, 399, 478, 60, 103, 307, 92, 104, 150, 211, 260, 8, 64, 73, 222, 273, 423, 179, 184, 190, 193, 265, 271, 305, 318, 344, 14, 75, 124, 317, 343, 404, 4, 141, 167, 212, 496 }; const double x[500] = { 737, 519, 538, 486, 557, 31, 651, 101, 310, 729, 721, 164, 577, 411, 104, 891, 988, 370, 788, 898, 576, 674, 7, 10, 91, 253, 9, 54, 105, 36, 799, 188, 651, 92, 766, 394, 8, 823, 242, 334, 639, 462, 111, 847, 919, 681, 392, 657, 358, 203, 453, 897, 965, 316, 759, 894, 893, 44, 743, 736, 970, 473, 229, 120, 485, 174, 405, 514, 984, 200, 723, 867, 259, 997, 191, 340, 75, 763, 579, 216, 154, 331, 338, 184, 786, 56, 235, 880, 810, 544, 522, 358, 219, 566, 632, 422, 636, 760, 657, 117, 138, 228, 163, 336, 572, 722, 438, 280, 234, 454, 967, 148, 325, 142, 790, 3, 497, 770, 936, 101, 696, 108, 255, 140, 320, 29, 36, 228, 468, 24, 183, 844, 513, 856, 102, 9, 526, 50, 73, 366, 599, 246, 662, 473, 651, 568, 575, 972, 352, 341, 897, 15, 73, 764, 768, 879, 886, 906, 718, 621, 529, 282, 339, 165, 137, 999, 215, 33, 639, 999, 906, 210, 62, 655, 996, 675, 552, 333, 176, 426, 891, 638, 571, 715, 18, 708, 795, 26, 31, 250, 18, 949, 183, 968, 394, 580, 766, 686, 162, 134, 185, 943, 919, 577, 539, 180, 750, 285, 591, 881, 381, 118, 852, 696, 617, 941, 767, 592, 650, 74, 961, 881, 891, 71, 905, 575, 598, 523, 477, 561, 948, 762, 570, 773, 146, 894, 203, 610, 471, 669, 189, 473, 650, 606, 385, 288, 360, 648, 115, 836, 139, 530, 248, 331, 286, 849, 812, 356, 884, 33, 57, 147, 297, 826, 916, 581, 0, 918, 81, 12, 956, 309, 550, 15, 243, 294, 893, 290, 227, 826, 843, 789, 744, 494, 742, 643, 126, 861, 444, 506, 417, 215, 246, 9, 244, 283, 595, 635, 494, 612, 737, 311, 896, 834, 222, 121, 595, 680, 309, 729, 263, 142, 804, 262, 343, 179, 649, 118, 360, 536, 669, 429, 359, 667, 313, 671, 506, 951, 461, 291, 359, 237, 727, 143, 968, 769, 97, 842, 752, 803, 299, 154, 384, 23, 567, 339, 778, 492, 116, 320, 967, 526, 66, 761, 908, 345, 885, 193, 894, 547, 124, 18, 254, 947, 192, 111, 384, 204, 338, 574, 749, 816, 717, 457, 353, 163, 979, 896, 679, 342, 932, 100, 216, 531, 320, 122, 594, 956, 638, 450, 733, 643, 293, 891, 633, 901, 815, 676, 307, 144, 286, 106, 182, 605, 575, 129, 390, 212, 843, 225, 544, 468, 203, 223, 862, 795, 36, 348, 743, 528, 904, 126, 802, 82, 156, 369, 986, 332, 977, 570, 421, 345, 401, 480, 63, 518, 667, 31, 909, 552, 994, 314, 891, 642, 439, 132, 670, 402, 263, 140, 549, 905, 712, 299, 986, 86, 709, 786, 47, 679, 864, 13, 140, 659, 479, 838, 988, 846, 855, 367, 935, 657, 453, 400, 851, 749, 500, 673, 523, 708, 568, 76, 18, 589, 689, 195, 504, 402, 835, 705, 187, 615, 482, 160, 609, 761, 907, 294, 538, 545 }; const int ptr[501] = { 0, 4, 8, 10, 15, 22, 29, 33, 34, 36, 39, 44, 44, 47, 55, 61, 66, 68, 75, 82, 86, 91, 98, 104, 109, 113, 126, 131, 134, 136, 143, 153, 159, 168, 170, 174, 176, 180, 187, 192, 198, 200, 204, 211, 213, 222, 225, 228, 233, 241, 247, 253, 256, 262, 264, 270, 274, 277, 283, 288, 294, 301, 307, 312, 315, 319, 325, 329, 332, 338, 340, 342, 348, 353, 359, 362, 366, 368, 374, 387, 393, 400, 403, 406, 412, 420, 425, 428, 433, 441, 442, 448, 456, 462, 468, 469, 477, 479, 485, 490, 495, 501, 508, 513, 518, 524, 532, 535, 538, 542, 546, 552, 561, 563, 567, 571, 574, 576, 581, 584, 588, 592, 593, 597, 599, 607, 612, 615, 619, 626, 633, 640, 646, 650, 653, 659, 665, 670, 673, 678, 685, 691, 697, 703, 708, 712, 717, 719, 722, 725, 732, 736, 738, 742, 747, 753, 757, 763, 767, 769, 769, 777, 780, 784, 790, 797, 807, 810, 813, 815, 817, 822, 829, 830, 835, 844, 848, 851, 854, 862, 864, 873, 876, 881, 884, 888, 895, 899, 901, 904, 908, 912, 919, 927, 931, 937, 941, 944, 948, 950, 955, 960, 963, 970, 975, 979, 983, 985, 992, 993, 998, 1001, 1008, 1012, 1014, 1018, 1023, 1030, 1036, 1040, 1045, 1052, 1058, 1061, 1066, 1069, 1071, 1077, 1080, 1084, 1087, 1090, 1092, 1095, 1100, 1102, 1110, 1117, 1122, 1130, 1133, 1138, 1142, 1144, 1146, 1153, 1158, 1160, 1167, 1172, 1176, 1179, 1183, 1188, 1191, 1193, 1196, 1204, 1210, 1216, 1219, 1221, 1225, 1229, 1234, 1236, 1239, 1244, 1248, 1253, 1256, 1264, 1268, 1271, 1272, 1275, 1278, 1284, 1287, 1291, 1296, 1300, 1304, 1306, 1313, 1317, 1322, 1326, 1332, 1336, 1344, 1349, 1356, 1363, 1368, 1369, 1378, 1381, 1385, 1388, 1395, 1399, 1407, 1414, 1422, 1425, 1433, 1435, 1438, 1439, 1445, 1448, 1450, 1453, 1456, 1470, 1472, 1475, 1481, 1487, 1491, 1494, 1497, 1498, 1503, 1507, 1513, 1517, 1524, 1529, 1534, 1542, 1547, 1550, 1550, 1552, 1553, 1556, 1559, 1563, 1571, 1577, 1580, 1585, 1590, 1594, 1598, 1600, 1602, 1610, 1615, 1620, 1628, 1634, 1637, 1649, 1652, 1656, 1662, 1664, 1670, 1674, 1678, 1687, 1697, 1704, 1709, 1715, 1720, 1725, 1728, 1736, 1740, 1747, 1750, 1754, 1760, 1763, 1765, 1773, 1781, 1783, 1788, 1795, 1802, 1810, 1815, 1820, 1824, 1829, 1836, 1839, 1843, 1847, 1849, 1854, 1859, 1863, 1873, 1880, 1882, 1891, 1895, 1899, 1904, 1909, 1914, 1919, 1923, 1927, 1932, 1938, 1943, 1949, 1954, 1960, 1965, 1968, 1974, 1980, 1983, 1990, 1992, 1995, 2002, 2011, 2017, 2024, 2028, 2035, 2037, 2048, 2055, 2063, 2067, 2069, 2078, 2081, 2085, 2086, 2090, 2097, 2101, 2107, 2110, 2112, 2116, 2119, 2122, 2129, 2136, 2143, 2146, 2156, 2162, 2171, 2175, 2179, 2186, 2189, 2194, 2198, 2206, 2211, 2215, 2222, 2228, 2237, 2241, 2245, 2256, 2259, 2269, 2272, 2275, 2278, 2279, 2281, 2287, 2292, 2297, 2304, 2311, 2316, 2319, 2322, 2327, 2333, 2340, 2343, 2345, 2350, 2358, 2365, 2365, 2368, 2373, 2379, 2388, 2394, 2399 }; const double verify_data[500] = { 1636962, 1714376, 142636, 1151015, 1672341, 2790420, 1447201, 422892, 30953, 1030287, 1335188, 0, 605334, 2278445, 858848, 245423, 950882, 705076, 1312024, 1084284, 1837558, 1201746, 2360392, 1488940, 688178, 2632122, 1481444, 660854, 346453, 982949, 1400599, 1093225, 2856372, 1078398, 1074402, 579548, 1820752, 2638601, 2072665, 749887, 687788, 478788, 1482258, 1207317, 1397243, 794364, 1002505, 1651686, 1028801, 1189726, 1513197, 1214956, 738475, 633771, 1207042, 680857, 899314, 2277406, 773143, 1986687, 907216, 907940, 1539019, 1043338, 681730, 219905, 1397298, 2184201, 1537202, 266744, 563005, 1827909, 1105928, 2286680, 887533, 343193, 238910, 1678393, 2600003, 417502, 1551071, 798273, 398719, 2056881, 1296314, 917292, 190534, 882078, 1979139, 50621, 1048185, 1967771, 1911887, 1895897, 23343, 2658748, 285864, 1027049, 975769, 2488413, 832738, 844130, 1379856, 1785889, 2463463, 782430, 982466, 609500, 706251, 1981399, 1861430, 2146667, 250104, 1166284, 1295022, 189599, 855191, 1005718, 969658, 707377, 561273, 86496, 717937, 97767, 1893638, 779229, 429727, 99564, 1863565, 2267656, 950026, 780700, 581248, 393282, 2134865, 1244700, 1894843, 954212, 1439102, 779512, 1459287, 881497, 2202043, 1447401, 1249637, 765168, 488244, 837127, 1236555, 2281259, 1995666, 25783, 534020, 1486259, 1268571, 875283, 744594, 1410335, 757320, 0, 1922627, 399058, 1490594, 1475527, 1587557, 1695667, 644546, 536038, 224304, 414120, 2029077, 3930385, 377416, 1059074, 1960417, 1439575, 368749, 460183, 2479302, 105204, 1426355, 649313, 2194338, 918200, 1591449, 2229266, 434520, 684504, 1009270, 222922, 600674, 1011867, 1321434, 836127, 2493805, 1448674, 1269364, 1304961, 98554, 2423810, 1570229, 302458, 2806045, 1534004, 1463827, 1085011, 120989, 1701753, 110302, 938429, 1186733, 2255246, 425960, 376311, 341394, 1061333, 2025091, 522270, 598604, 1000824, 2254049, 1857539, 346425, 1345187, 550497, 1251096, 943720, 681558, 555972, 779590, 299796, 1445763, 459865, 774572, 489448, 2407693, 1574903, 1630452, 1907397, 555045, 1902494, 1172223, 142555, 445864, 1376151, 1200389, 327553, 1548402, 1106503, 888650, 41081, 1245270, 845610, 1232215, 387441, 434475, 1204003, 1333189, 1672468, 567827, 11392, 631046, 1299298, 719608, 714169, 362247, 1308257, 530903, 398202, 885445, 2606806, 1354354, 438760, 194928, 712863, 1010340, 2245646, 376041, 876890, 1683404, 955032, 1065455, 925034, 1731713, 1152271, 2093865, 1221433, 629438, 2054936, 2643313, 1322567, 1492288, 1844514, 1802382, 871, 1350044, 967406, 756881, 574442, 1295864, 1815978, 2822668, 2201377, 2729436, 616018, 2318346, 332717, 289665, 97812, 1881483, 1003188, 702530, 409314, 645118, 3645947, 723792, 503126, 1609036, 1647277, 587437, 735899, 666552, 27354, 1045106, 397951, 1087090, 1173872, 1629962, 1334261, 1855668, 2856970, 1341188, 336968, 0, 521349, 53118, 881926, 154917, 942966, 1237636, 820836, 579583, 1436861, 2025006, 634434, 829152, 298073, 205380, 1622350, 1171051, 848451, 2417009, 2016092, 390510, 2721874, 359761, 309038, 1061522, 297026, 1311767, 305305, 854945, 1773244, 2656339, 896058, 1069160, 1552917, 1421821, 440874, 216699, 1654864, 521705, 807422, 1242602, 1329872, 308130, 526463, 27937, 1450630, 1621987, 799154, 1378289, 2519996, 1149046, 579937, 1841561, 1895047, 1009234, 1922198, 2570006, 409696, 442495, 277484, 979605, 1392287, 1023715, 1881778, 2432703, 2297384, 542451, 1368100, 833048, 1038108, 742376, 1542317, 2230186, 1249077, 884020, 1286059, 1102407, 1651393, 1787846, 1370154, 2734166, 2935249, 447485, 736859, 828966, 1547038, 765990, 1427773, 255456, 134871, 1597546, 2173052, 1187286, 2364828, 1220233, 1760369, 75080, 2799969, 1363310, 2347168, 272279, 33698, 1192053, 342501, 356092, 136578, 1701048, 2216796, 1340150, 1852854, 580862, 407410, 1860346, 200649, 954363, 955621, 2234154, 2007706, 646339, 2712491, 1259244, 2368138, 1550431, 1160903, 987838, 650293, 833228, 368144, 1998925, 1733716, 1050000, 1061635, 1144649, 1260205, 851043, 1417512, 2826918, 1059350, 1522135, 1039943, 703837, 1035006, 19505, 211545, 1461101, 1238659, 1414306, 1151385, 2169011, 1101116, 1118290, 335296, 1502266, 1405699, 1762457, 530338, 246108, 484583, 2164048, 1614511, 0, 1446940, 575450, 2043329, 2057251, 774670, 1084124 };