diff options
| author | Yunsup Lee <yunsup@cs.berkeley.edu> | 2013-04-29 18:44:21 -0700 |
|---|---|---|
| committer | Yunsup Lee <yunsup@cs.berkeley.edu> | 2013-04-29 18:44:21 -0700 |
| commit | 23507d668862dff15a898f20e109a46c6e95780d (patch) | |
| tree | a3b620e117c1ded337e9508042e353c62a1a97a8 /benchmarks/spmv | |
| parent | f8ea498f79ab4d6495f2966d1e5c3dd42f567752 (diff) | |
| download | riscv-tests-23507d668862dff15a898f20e109a46c6e95780d.zip riscv-tests-23507d668862dff15a898f20e109a46c6e95780d.tar.gz riscv-tests-23507d668862dff15a898f20e109a46c6e95780d.tar.bz2 | |
benchmarks initial commit
Diffstat (limited to 'benchmarks/spmv')
| -rw-r--r-- | benchmarks/spmv/bmark.mk | 29 | ||||
| -rw-r--r-- | benchmarks/spmv/dataset1.h | 23022 | ||||
| -rw-r--r-- | benchmarks/spmv/spmv_gendata.scala | 48 | ||||
| -rw-r--r-- | benchmarks/spmv/spmv_main.c | 123 |
4 files changed, 23222 insertions, 0 deletions
diff --git a/benchmarks/spmv/bmark.mk b/benchmarks/spmv/bmark.mk new file mode 100644 index 0000000..5ab9cc0 --- /dev/null +++ b/benchmarks/spmv/bmark.mk @@ -0,0 +1,29 @@ +#======================================================================= +# UCB CS250 Makefile fragment for benchmarks +#----------------------------------------------------------------------- +# +# Each benchmark directory should have its own fragment which +# essentially lists what the source files are and how to link them +# into an riscv and/or host executable. All variables should include +# the benchmark name as a prefix so that they are unique. +# + +spmv_c_src = \ + spmv_main.c \ + +spmv_riscv_src = \ + crt.S \ + +spmv_c_objs = $(patsubst %.c, %.o, $(spmv_c_src)) +spmv_riscv_objs = $(patsubst %.S, %.o, $(spmv_riscv_src)) + +spmv_host_bin = spmv.host +$(spmv_host_bin) : $(spmv_c_src) + $(HOST_COMP) $^ -o $(spmv_host_bin) + +spmv_riscv_bin = spmv.riscv +$(spmv_riscv_bin) : $(spmv_c_objs) $(spmv_riscv_objs) + $(RISCV_LINK) $(spmv_c_objs) $(spmv_riscv_objs) -o $(spmv_riscv_bin) + +junk += $(spmv_c_objs) $(spmv_riscv_objs) \ + $(spmv_host_bin) $(spmv_riscv_bin) diff --git a/benchmarks/spmv/dataset1.h b/benchmarks/spmv/dataset1.h new file mode 100644 index 0000000..ebdf7ff --- /dev/null +++ b/benchmarks/spmv/dataset1.h @@ -0,0 +1,23022 @@ +#define R 1000 +#define C 1000 +#define NNZ 10004 +const double val[10004] = { + 658, + 279, + 587, + 255, + 359, + 844, + 905, + 456, + 897, + 837, + 652, + 398, + 885, + 21, + 669, + 738, + 365, + 928, + 713, + 771, + 536, + 987, + 917, + 823, + 544, + 40, + 80, + 636, + 263, + 929, + 757, + 677, + 151, + 500, + 875, + 720, + 205, + 292, + 859, + 980, + 97, + 608, + 813, + 840, + 397, + 765, + 294, + 718, + 751, + 7, + 482, + 166, + 653, + 172, + 187, + 79, + 228, + 857, + 540, + 760, + 509, + 190, + 396, + 765, + 37, + 85, + 866, + 981, + 999, + 793, + 921, + 664, + 208, + 856, + 528, + 782, + 318, + 170, + 521, + 691, + 726, + 996, + 947, + 326, + 825, + 77, + 823, + 752, + 266, + 834, + 196, + 58, + 430, + 764, + 807, + 568, + 665, + 583, + 178, + 250, + 273, + 654, + 487, + 504, + 729, + 338, + 866, + 981, + 852, + 842, + 785, + 13, + 588, + 44, + 432, + 408, + 374, + 761, + 653, + 752, + 684, + 6, + 357, + 703, + 447, + 966, + 457, + 738, + 646, + 646, + 217, + 522, + 839, + 417, + 506, + 801, + 233, + 929, + 487, + 353, + 660, + 751, + 738, + 512, + 566, + 130, + 61, + 128, + 698, + 467, + 362, + 867, + 639, + 289, + 371, + 427, + 650, + 16, + 878, + 967, + 369, + 517, + 161, + 330, + 294, + 396, + 606, + 638, + 171, + 602, + 531, + 14, + 968, + 15, + 193, + 225, + 863, + 171, + 254, + 714, + 256, + 873, + 353, + 35, + 910, + 849, + 658, + 546, + 389, + 239, + 355, + 540, + 494, + 968, + 319, + 590, + 608, + 445, + 806, + 51, + 117, + 401, + 314, + 280, + 334, + 44, + 17, + 107, + 108, + 650, + 807, + 385, + 748, + 942, + 719, + 110, + 630, + 559, + 717, + 375, + 963, + 45, + 403, + 476, + 408, + 732, + 87, + 874, + 635, + 119, + 190, + 949, + 777, + 201, + 503, + 658, + 777, + 564, + 830, + 122, + 929, + 68, + 11, + 354, + 395, + 213, + 766, + 40, + 995, + 577, + 514, + 568, + 56, + 439, + 91, + 148, + 612, + 717, + 157, + 538, + 682, + 190, + 571, + 847, + 275, + 190, + 824, + 985, + 29, + 426, + 173, + 898, + 297, + 156, + 936, + 1, + 455, + 812, + 173, + 131, + 376, + 947, + 596, + 783, + 800, + 361, + 798, + 598, + 710, + 86, + 149, + 457, + 129, + 437, + 352, + 933, + 320, + 709, + 167, + 793, + 46, + 49, + 305, + 704, + 577, + 855, + 336, + 978, + 206, + 662, + 230, + 93, + 898, + 368, + 422, + 689, + 351, + 87, + 465, + 576, + 33, + 884, + 675, + 548, + 116, + 730, + 385, + 483, + 340, + 809, + 938, + 342, + 576, + 887, + 479, + 455, + 820, + 521, + 320, + 488, + 506, + 591, + 901, + 505, + 525, + 5, + 133, + 705, + 561, + 285, + 95, + 918, + 410, + 578, + 347, + 375, + 735, + 624, + 491, + 494, + 931, + 655, + 819, + 883, + 328, + 527, + 194, + 580, + 584, + 837, + 700, + 681, + 249, + 643, + 958, + 363, + 316, + 397, + 638, + 261, + 459, + 960, + 636, + 458, + 84, + 797, + 696, + 782, + 831, + 419, + 393, + 649, + 312, + 811, + 703, + 70, + 688, + 285, + 39, + 617, + 935, + 495, + 392, + 143, + 734, + 166, + 406, + 464, + 732, + 709, + 379, + 143, + 527, + 514, + 709, + 130, + 965, + 632, + 448, + 836, + 62, + 567, + 600, + 520, + 519, + 16, + 394, + 705, + 438, + 548, + 696, + 140, + 573, + 509, + 968, + 935, + 165, + 868, + 577, + 451, + 865, + 304, + 777, + 828, + 147, + 704, + 821, + 641, + 783, + 376, + 757, + 391, + 170, + 592, + 235, + 920, + 846, + 683, + 249, + 697, + 253, + 386, + 244, + 889, + 607, + 768, + 88, + 836, + 259, + 945, + 33, + 352, + 70, + 83, + 996, + 791, + 18, + 599, + 488, + 43, + 582, + 993, + 692, + 841, + 558, + 530, + 350, + 187, + 295, + 215, + 869, + 593, + 385, + 722, + 724, + 282, + 681, + 534, + 788, + 836, + 378, + 825, + 93, + 539, + 120, + 794, + 384, + 798, + 505, + 833, + 27, + 181, + 951, + 966, + 498, + 375, + 22, + 545, + 62, + 816, + 119, + 712, + 813, + 783, + 655, + 832, + 143, + 501, + 519, + 43, + 760, + 17, + 896, + 96, + 390, + 121, + 458, + 736, + 649, + 227, + 778, + 283, + 657, + 434, + 214, + 123, + 929, + 548, + 206, + 993, + 463, + 824, + 369, + 260, + 868, + 645, + 857, + 184, + 198, + 349, + 652, + 522, + 23, + 208, + 968, + 290, + 770, + 109, + 978, + 513, + 298, + 675, + 306, + 866, + 927, + 822, + 495, + 653, + 134, + 702, + 147, + 366, + 947, + 65, + 586, + 412, + 638, + 760, + 541, + 118, + 551, + 574, + 85, + 736, + 999, + 917, + 478, + 35, + 629, + 963, + 898, + 826, + 113, + 298, + 606, + 568, + 152, + 926, + 277, + 984, + 549, + 279, + 839, + 348, + 672, + 278, + 94, + 455, + 590, + 843, + 85, + 222, + 901, + 621, + 30, + 880, + 914, + 27, + 974, + 399, + 873, + 968, + 870, + 479, + 696, + 964, + 929, + 499, + 121, + 812, + 933, + 799, + 506, + 412, + 712, + 791, + 426, + 835, + 488, + 910, + 522, + 332, + 967, + 380, + 61, + 5, + 282, + 119, + 22, + 136, + 436, + 730, + 341, + 687, + 371, + 19, + 893, + 20, + 327, + 221, + 221, + 966, + 354, + 198, + 985, + 56, + 305, + 691, + 980, + 12, + 790, + 64, + 484, + 621, + 214, + 332, + 898, + 898, + 318, + 416, + 445, + 350, + 317, + 336, + 714, + 788, + 541, + 890, + 42, + 111, + 596, + 164, + 424, + 448, + 666, + 362, + 429, + 617, + 910, + 917, + 970, + 526, + 321, + 551, + 481, + 83, + 46, + 146, + 569, + 856, + 85, + 192, + 724, + 378, + 299, + 13, + 422, + 411, + 552, + 569, + 100, + 849, + 484, + 906, + 47, + 532, + 742, + 415, + 228, + 897, + 715, + 807, + 329, + 244, + 312, + 903, + 758, + 34, + 172, + 18, + 917, + 700, + 108, + 611, + 567, + 616, + 572, + 174, + 925, + 553, + 903, + 268, + 544, + 998, + 708, + 133, + 717, + 584, + 517, + 608, + 680, + 597, + 316, + 470, + 764, + 530, + 221, + 405, + 133, + 406, + 506, + 56, + 458, + 721, + 935, + 356, + 130, + 99, + 395, + 117, + 34, + 881, + 231, + 214, + 248, + 458, + 246, + 632, + 471, + 279, + 385, + 594, + 855, + 305, + 30, + 542, + 144, + 509, + 548, + 364, + 171, + 386, + 382, + 616, + 997, + 28, + 361, + 855, + 449, + 992, + 956, + 439, + 569, + 383, + 523, + 852, + 337, + 112, + 24, + 902, + 352, + 542, + 231, + 664, + 411, + 457, + 572, + 52, + 760, + 88, + 907, + 345, + 284, + 636, + 219, + 975, + 713, + 231, + 888, + 49, + 624, + 179, + 579, + 401, + 694, + 984, + 905, + 673, + 414, + 773, + 165, + 349, + 436, + 128, + 186, + 487, + 17, + 552, + 833, + 98, + 424, + 791, + 220, + 352, + 75, + 470, + 405, + 679, + 939, + 792, + 653, + 142, + 226, + 208, + 629, + 429, + 55, + 455, + 362, + 210, + 765, + 693, + 113, + 656, + 824, + 441, + 191, + 50, + 957, + 99, + 27, + 582, + 461, + 279, + 299, + 492, + 678, + 452, + 640, + 349, + 758, + 298, + 903, + 361, + 333, + 339, + 60, + 824, + 773, + 184, + 621, + 66, + 49, + 228, + 608, + 523, + 591, + 533, + 234, + 566, + 291, + 646, + 93, + 42, + 810, + 154, + 846, + 426, + 32, + 828, + 360, + 917, + 182, + 50, + 40, + 182, + 19, + 127, + 614, + 951, + 662, + 591, + 140, + 110, + 685, + 549, + 6, + 346, + 766, + 689, + 743, + 414, + 135, + 61, + 548, + 363, + 915, + 462, + 526, + 405, + 524, + 192, + 754, + 796, + 616, + 98, + 341, + 786, + 778, + 929, + 6, + 388, + 293, + 513, + 148, + 298, + 311, + 29, + 456, + 960, + 560, + 895, + 121, + 511, + 141, + 732, + 762, + 774, + 261, + 287, + 314, + 801, + 320, + 173, + 616, + 356, + 783, + 256, + 129, + 513, + 212, + 293, + 168, + 813, + 279, + 65, + 784, + 360, + 921, + 320, + 177, + 923, + 385, + 142, + 380, + 772, + 929, + 718, + 277, + 61, + 620, + 575, + 772, + 356, + 414, + 775, + 392, + 523, + 760, + 192, + 905, + 606, + 134, + 695, + 784, + 540, + 63, + 939, + 941, + 887, + 217, + 290, + 893, + 206, + 662, + 63, + 102, + 74, + 943, + 288, + 8, + 254, + 131, + 420, + 841, + 79, + 139, + 362, + 221, + 915, + 6, + 28, + 417, + 846, + 996, + 794, + 522, + 391, + 513, + 715, + 87, + 449, + 801, + 823, + 16, + 485, + 874, + 8, + 601, + 885, + 146, + 886, + 318, + 235, + 390, + 561, + 869, + 640, + 860, + 433, + 651, + 145, + 149, + 682, + 612, + 580, + 946, + 572, + 155, + 736, + 898, + 774, + 81, + 882, + 286, + 362, + 982, + 788, + 658, + 452, + 889, + 688, + 384, + 948, + 342, + 402, + 777, + 403, + 547, + 123, + 187, + 394, + 470, + 978, + 234, + 461, + 127, + 349, + 476, + 927, + 837, + 997, + 494, + 167, + 920, + 911, + 84, + 432, + 339, + 87, + 841, + 535, + 972, + 671, + 395, + 445, + 681, + 494, + 737, + 492, + 96, + 84, + 261, + 871, + 91, + 696, + 960, + 346, + 430, + 796, + 326, + 272, + 982, + 25, + 927, + 923, + 528, + 924, + 215, + 789, + 691, + 898, + 811, + 189, + 284, + 856, + 200, + 278, + 436, + 354, + 114, + 978, + 648, + 797, + 437, + 916, + 220, + 449, + 740, + 179, + 484, + 470, + 332, + 178, + 65, + 807, + 860, + 180, + 421, + 148, + 563, + 253, + 691, + 121, + 837, + 851, + 341, + 948, + 563, + 635, + 780, + 148, + 567, + 713, + 118, + 877, + 505, + 519, + 975, + 504, + 745, + 190, + 958, + 134, + 898, + 723, + 546, + 781, + 46, + 760, + 530, + 572, + 163, + 227, + 886, + 408, + 586, + 4, + 901, + 233, + 753, + 720, + 203, + 575, + 748, + 443, + 207, + 838, + 492, + 290, + 223, + 256, + 715, + 830, + 432, + 97, + 99, + 477, + 725, + 574, + 91, + 746, + 731, + 615, + 629, + 437, + 320, + 843, + 559, + 13, + 902, + 779, + 564, + 689, + 207, + 599, + 726, + 598, + 606, + 148, + 58, + 115, + 536, + 319, + 279, + 944, + 485, + 699, + 948, + 13, + 895, + 766, + 582, + 559, + 998, + 250, + 788, + 869, + 877, + 23, + 647, + 488, + 164, + 845, + 344, + 545, + 307, + 991, + 0, + 805, + 152, + 412, + 534, + 323, + 614, + 415, + 865, + 847, + 210, + 743, + 122, + 943, + 594, + 320, + 268, + 154, + 253, + 816, + 347, + 768, + 953, + 982, + 606, + 131, + 813, + 92, + 339, + 5, + 707, + 517, + 526, + 469, + 537, + 89, + 141, + 537, + 557, + 190, + 659, + 87, + 659, + 401, + 367, + 414, + 460, + 34, + 96, + 895, + 740, + 694, + 352, + 537, + 592, + 877, + 137, + 922, + 915, + 99, + 216, + 969, + 716, + 44, + 869, + 856, + 853, + 352, + 556, + 216, + 426, + 231, + 259, + 172, + 67, + 694, + 488, + 311, + 712, + 767, + 279, + 962, + 265, + 615, + 141, + 454, + 711, + 384, + 452, + 135, + 90, + 391, + 787, + 665, + 528, + 296, + 824, + 820, + 455, + 885, + 301, + 155, + 647, + 6, + 973, + 627, + 663, + 922, + 969, + 799, + 698, + 523, + 404, + 784, + 422, + 128, + 103, + 233, + 601, + 812, + 281, + 600, + 336, + 11, + 743, + 288, + 925, + 181, + 228, + 508, + 308, + 3, + 141, + 711, + 602, + 71, + 868, + 255, + 307, + 24, + 862, + 567, + 134, + 74, + 755, + 947, + 111, + 812, + 42, + 295, + 650, + 859, + 78, + 128, + 462, + 308, + 290, + 372, + 166, + 111, + 364, + 469, + 591, + 127, + 56, + 840, + 758, + 781, + 756, + 548, + 658, + 412, + 851, + 134, + 233, + 432, + 257, + 138, + 210, + 184, + 986, + 51, + 806, + 442, + 711, + 243, + 571, + 861, + 550, + 111, + 798, + 138, + 316, + 746, + 549, + 276, + 458, + 866, + 335, + 334, + 178, + 191, + 473, + 452, + 764, + 487, + 525, + 273, + 457, + 902, + 888, + 519, + 203, + 891, + 497, + 998, + 535, + 382, + 673, + 787, + 112, + 846, + 836, + 898, + 681, + 607, + 546, + 863, + 639, + 896, + 281, + 845, + 305, + 410, + 835, + 985, + 245, + 781, + 208, + 337, + 248, + 205, + 264, + 198, + 305, + 665, + 351, + 609, + 186, + 444, + 589, + 130, + 292, + 668, + 617, + 611, + 111, + 80, + 9, + 267, + 275, + 135, + 201, + 926, + 789, + 835, + 221, + 290, + 297, + 93, + 437, + 892, + 921, + 994, + 748, + 321, + 23, + 394, + 725, + 377, + 581, + 57, + 219, + 461, + 54, + 183, + 506, + 889, + 920, + 714, + 639, + 836, + 585, + 787, + 929, + 597, + 307, + 678, + 35, + 296, + 46, + 459, + 368, + 342, + 200, + 609, + 265, + 11, + 315, + 10, + 29, + 32, + 339, + 250, + 974, + 736, + 834, + 281, + 332, + 656, + 530, + 384, + 96, + 544, + 775, + 208, + 375, + 230, + 31, + 589, + 385, + 130, + 718, + 82, + 909, + 267, + 482, + 503, + 875, + 824, + 488, + 837, + 757, + 19, + 121, + 129, + 531, + 712, + 76, + 183, + 137, + 764, + 617, + 846, + 64, + 65, + 775, + 593, + 526, + 53, + 923, + 142, + 330, + 153, + 199, + 71, + 584, + 423, + 770, + 318, + 965, + 493, + 953, + 238, + 416, + 471, + 978, + 436, + 501, + 505, + 264, + 789, + 199, + 241, + 800, + 168, + 34, + 291, + 399, + 972, + 890, + 462, + 670, + 628, + 19, + 204, + 99, + 751, + 742, + 231, + 397, + 5, + 204, + 886, + 763, + 706, + 218, + 775, + 730, + 231, + 425, + 118, + 778, + 886, + 537, + 364, + 691, + 19, + 114, + 195, + 665, + 675, + 359, + 653, + 185, + 76, + 351, + 221, + 695, + 147, + 1, + 109, + 790, + 749, + 299, + 358, + 11, + 581, + 511, + 614, + 950, + 916, + 923, + 764, + 245, + 487, + 508, + 471, + 71, + 482, + 614, + 660, + 834, + 875, + 433, + 470, + 650, + 753, + 828, + 360, + 551, + 946, + 215, + 358, + 689, + 468, + 280, + 98, + 363, + 451, + 20, + 842, + 913, + 105, + 575, + 798, + 199, + 612, + 778, + 959, + 295, + 322, + 760, + 963, + 854, + 191, + 629, + 165, + 420, + 127, + 515, + 858, + 783, + 487, + 499, + 534, + 451, + 373, + 116, + 973, + 576, + 184, + 587, + 765, + 975, + 945, + 960, + 801, + 802, + 793, + 32, + 608, + 312, + 533, + 916, + 92, + 625, + 661, + 374, + 967, + 332, + 554, + 259, + 838, + 475, + 765, + 833, + 74, + 39, + 780, + 446, + 132, + 270, + 583, + 378, + 677, + 805, + 921, + 723, + 624, + 67, + 434, + 875, + 847, + 149, + 881, + 104, + 729, + 327, + 239, + 791, + 22, + 717, + 647, + 118, + 353, + 791, + 129, + 253, + 60, + 938, + 533, + 408, + 994, + 849, + 789, + 764, + 797, + 687, + 892, + 203, + 880, + 903, + 946, + 294, + 830, + 698, + 297, + 478, + 305, + 452, + 258, + 30, + 799, + 756, + 793, + 937, + 775, + 14, + 383, + 276, + 481, + 215, + 317, + 879, + 52, + 628, + 654, + 429, + 753, + 848, + 606, + 629, + 748, + 832, + 335, + 733, + 90, + 396, + 690, + 482, + 54, + 12, + 306, + 535, + 750, + 116, + 524, + 383, + 475, + 214, + 178, + 784, + 798, + 563, + 935, + 806, + 949, + 53, + 694, + 273, + 124, + 284, + 619, + 45, + 521, + 715, + 851, + 132, + 424, + 438, + 319, + 538, + 981, + 802, + 986, + 340, + 600, + 353, + 980, + 637, + 505, + 17, + 280, + 855, + 237, + 432, + 184, + 955, + 538, + 935, + 480, + 421, + 580, + 423, + 928, + 926, + 930, + 732, + 210, + 351, + 346, + 469, + 100, + 288, + 353, + 788, + 232, + 130, + 79, + 360, + 870, + 439, + 47, + 661, + 595, + 636, + 52, + 389, + 986, + 159, + 454, + 317, + 961, + 915, + 76, + 342, + 895, + 53, + 396, + 15, + 66, + 139, + 310, + 636, + 549, + 440, + 926, + 132, + 734, + 726, + 696, + 332, + 229, + 896, + 486, + 316, + 840, + 403, + 557, + 963, + 67, + 401, + 318, + 13, + 109, + 745, + 296, + 653, + 711, + 718, + 2, + 951, + 853, + 130, + 22, + 879, + 878, + 759, + 466, + 520, + 25, + 403, + 952, + 914, + 29, + 133, + 156, + 467, + 435, + 896, + 78, + 488, + 55, + 739, + 861, + 521, + 904, + 498, + 748, + 703, + 489, + 21, + 377, + 322, + 248, + 818, + 176, + 531, + 564, + 1, + 694, + 362, + 876, + 165, + 881, + 325, + 475, + 810, + 181, + 30, + 455, + 255, + 673, + 320, + 600, + 602, + 568, + 974, + 350, + 826, + 212, + 504, + 91, + 21, + 317, + 275, + 775, + 422, + 278, + 795, + 826, + 818, + 377, + 295, + 165, + 496, + 753, + 425, + 554, + 243, + 964, + 169, + 281, + 109, + 884, + 334, + 692, + 641, + 411, + 352, + 66, + 765, + 196, + 508, + 696, + 866, + 369, + 725, + 838, + 82, + 62, + 300, + 637, + 29, + 108, + 859, + 222, + 768, + 442, + 891, + 38, + 523, + 158, + 856, + 949, + 852, + 145, + 630, + 686, + 109, + 577, + 371, + 673, + 807, + 224, + 169, + 148, + 890, + 329, + 653, + 720, + 898, + 771, + 65, + 712, + 735, + 606, + 578, + 836, + 17, + 498, + 31, + 275, + 54, + 494, + 831, + 255, + 266, + 574, + 693, + 418, + 226, + 351, + 867, + 287, + 717, + 708, + 104, + 131, + 863, + 474, + 600, + 323, + 235, + 80, + 710, + 719, + 924, + 168, + 168, + 979, + 24, + 755, + 935, + 78, + 386, + 41, + 546, + 155, + 306, + 366, + 814, + 445, + 883, + 504, + 332, + 920, + 265, + 484, + 591, + 98, + 981, + 576, + 392, + 905, + 927, + 715, + 264, + 598, + 847, + 753, + 329, + 350, + 983, + 179, + 993, + 810, + 809, + 155, + 508, + 564, + 896, + 733, + 734, + 714, + 637, + 560, + 186, + 751, + 601, + 636, + 361, + 916, + 10, + 542, + 258, + 286, + 756, + 471, + 858, + 97, + 373, + 699, + 1, + 707, + 260, + 900, + 145, + 979, + 143, + 487, + 427, + 863, + 472, + 638, + 672, + 309, + 980, + 332, + 480, + 26, + 184, + 40, + 723, + 102, + 856, + 785, + 298, + 816, + 525, + 160, + 897, + 421, + 697, + 122, + 571, + 372, + 138, + 892, + 370, + 805, + 754, + 113, + 993, + 448, + 471, + 423, + 96, + 331, + 419, + 144, + 172, + 987, + 170, + 788, + 400, + 346, + 139, + 676, + 380, + 257, + 350, + 89, + 592, + 501, + 664, + 19, + 957, + 462, + 302, + 430, + 880, + 869, + 99, + 70, + 356, + 931, + 751, + 43, + 531, + 790, + 559, + 455, + 64, + 846, + 139, + 685, + 876, + 166, + 361, + 28, + 876, + 223, + 147, + 928, + 619, + 734, + 870, + 738, + 393, + 293, + 722, + 301, + 936, + 566, + 57, + 881, + 398, + 796, + 134, + 566, + 932, + 756, + 860, + 638, + 546, + 33, + 144, + 29, + 628, + 254, + 764, + 604, + 357, + 987, + 552, + 400, + 663, + 874, + 727, + 586, + 988, + 684, + 867, + 343, + 733, + 349, + 534, + 976, + 708, + 998, + 871, + 564, + 271, + 105, + 397, + 40, + 884, + 62, + 43, + 361, + 451, + 188, + 520, + 953, + 709, + 796, + 522, + 365, + 263, + 807, + 14, + 439, + 395, + 800, + 614, + 831, + 675, + 532, + 95, + 332, + 538, + 318, + 526, + 1, + 689, + 111, + 487, + 370, + 203, + 211, + 642, + 549, + 158, + 206, + 298, + 846, + 87, + 717, + 363, + 83, + 200, + 769, + 504, + 670, + 536, + 349, + 294, + 441, + 239, + 721, + 400, + 355, + 212, + 120, + 623, + 664, + 94, + 116, + 126, + 904, + 947, + 938, + 152, + 542, + 464, + 735, + 926, + 112, + 590, + 1, + 209, + 102, + 237, + 258, + 552, + 427, + 808, + 319, + 631, + 769, + 884, + 24, + 132, + 697, + 878, + 344, + 335, + 391, + 384, + 27, + 533, + 900, + 96, + 279, + 121, + 998, + 558, + 987, + 848, + 426, + 191, + 925, + 623, + 850, + 163, + 184, + 819, + 881, + 279, + 850, + 517, + 178, + 727, + 603, + 152, + 657, + 412, + 17, + 120, + 241, + 718, + 785, + 921, + 237, + 982, + 936, + 745, + 810, + 507, + 207, + 267, + 17, + 967, + 133, + 73, + 627, + 20, + 158, + 69, + 829, + 769, + 457, + 436, + 986, + 723, + 248, + 784, + 704, + 146, + 408, + 0, + 170, + 209, + 720, + 958, + 149, + 321, + 919, + 924, + 223, + 35, + 326, + 196, + 513, + 992, + 884, + 467, + 877, + 695, + 432, + 281, + 722, + 633, + 209, + 616, + 140, + 93, + 274, + 31, + 401, + 971, + 177, + 946, + 782, + 271, + 934, + 159, + 416, + 861, + 9, + 607, + 415, + 747, + 444, + 487, + 701, + 191, + 88, + 850, + 580, + 93, + 59, + 309, + 477, + 613, + 974, + 126, + 348, + 256, + 573, + 578, + 865, + 805, + 280, + 90, + 858, + 924, + 455, + 681, + 307, + 581, + 714, + 156, + 224, + 534, + 198, + 63, + 489, + 144, + 123, + 288, + 500, + 221, + 618, + 674, + 233, + 440, + 788, + 569, + 70, + 472, + 166, + 12, + 979, + 722, + 929, + 108, + 736, + 666, + 525, + 631, + 554, + 287, + 742, + 65, + 324, + 248, + 710, + 489, + 834, + 199, + 338, + 851, + 793, + 960, + 761, + 383, + 891, + 973, + 943, + 853, + 422, + 178, + 600, + 890, + 732, + 384, + 431, + 476, + 237, + 104, + 622, + 839, + 904, + 805, + 512, + 57, + 17, + 630, + 378, + 32, + 996, + 247, + 209, + 254, + 119, + 396, + 565, + 630, + 782, + 633, + 138, + 318, + 112, + 545, + 743, + 616, + 663, + 89, + 367, + 495, + 845, + 127, + 597, + 434, + 129, + 692, + 109, + 168, + 953, + 668, + 590, + 177, + 578, + 46, + 707, + 413, + 115, + 788, + 513, + 243, + 935, + 953, + 58, + 584, + 64, + 569, + 367, + 978, + 249, + 290, + 125, + 183, + 852, + 485, + 847, + 895, + 835, + 25, + 289, + 995, + 226, + 156, + 980, + 520, + 656, + 255, + 37, + 852, + 719, + 493, + 473, + 900, + 417, + 647, + 363, + 759, + 778, + 735, + 349, + 627, + 525, + 255, + 13, + 58, + 399, + 222, + 70, + 304, + 663, + 158, + 152, + 788, + 103, + 693, + 274, + 873, + 116, + 837, + 876, + 367, + 272, + 778, + 65, + 363, + 625, + 696, + 809, + 16, + 491, + 615, + 196, + 88, + 0, + 204, + 418, + 203, + 952, + 205, + 240, + 962, + 899, + 872, + 222, + 961, + 363, + 920, + 659, + 935, + 943, + 198, + 385, + 475, + 298, + 936, + 22, + 204, + 947, + 776, + 911, + 581, + 661, + 340, + 433, + 188, + 622, + 117, + 154, + 150, + 388, + 214, + 513, + 625, + 875, + 779, + 262, + 972, + 396, + 803, + 396, + 991, + 976, + 900, + 387, + 371, + 522, + 162, + 234, + 733, + 314, + 331, + 666, + 44, + 205, + 66, + 422, + 780, + 978, + 661, + 775, + 647, + 511, + 670, + 515, + 88, + 714, + 579, + 133, + 499, + 837, + 506, + 904, + 172, + 248, + 476, + 836, + 898, + 514, + 396, + 852, + 568, + 706, + 533, + 54, + 72, + 167, + 493, + 809, + 588, + 792, + 34, + 325, + 827, + 878, + 440, + 708, + 348, + 589, + 708, + 271, + 577, + 857, + 999, + 547, + 579, + 502, + 298, + 330, + 790, + 687, + 99, + 245, + 721, + 264, + 826, + 487, + 501, + 783, + 194, + 469, + 991, + 653, + 87, + 946, + 556, + 707, + 104, + 879, + 160, + 15, + 1, + 95, + 323, + 870, + 521, + 897, + 840, + 699, + 410, + 751, + 42, + 342, + 802, + 547, + 862, + 168, + 5, + 561, + 488, + 170, + 237, + 655, + 179, + 909, + 847, + 536, + 360, + 44, + 371, + 9, + 473, + 253, + 400, + 563, + 683, + 471, + 625, + 823, + 414, + 590, + 312, + 407, + 971, + 929, + 614, + 705, + 249, + 69, + 348, + 527, + 915, + 978, + 728, + 593, + 641, + 627, + 144, + 653, + 818, + 763, + 116, + 676, + 611, + 451, + 203, + 589, + 62, + 984, + 165, + 631, + 42, + 873, + 56, + 256, + 459, + 134, + 722, + 235, + 798, + 291, + 977, + 646, + 36, + 156, + 546, + 113, + 96, + 964, + 156, + 570, + 366, + 718, + 816, + 726, + 385, + 188, + 184, + 154, + 921, + 821, + 329, + 928, + 176, + 688, + 942, + 204, + 240, + 423, + 498, + 422, + 115, + 696, + 1, + 850, + 309, + 733, + 628, + 595, + 930, + 467, + 888, + 638, + 448, + 895, + 10, + 938, + 848, + 116, + 193, + 390, + 415, + 330, + 359, + 115, + 371, + 432, + 229, + 264, + 141, + 162, + 491, + 397, + 2, + 141, + 761, + 471, + 68, + 55, + 628, + 593, + 891, + 84, + 808, + 740, + 196, + 196, + 511, + 901, + 324, + 464, + 627, + 461, + 900, + 995, + 118, + 486, + 960, + 709, + 451, + 432, + 997, + 785, + 480, + 20, + 351, + 25, + 955, + 40, + 788, + 56, + 254, + 329, + 601, + 293, + 704, + 639, + 743, + 983, + 177, + 722, + 193, + 708, + 34, + 202, + 364, + 404, + 487, + 436, + 867, + 906, + 442, + 472, + 718, + 610, + 366, + 991, + 639, + 821, + 604, + 618, + 538, + 266, + 781, + 958, + 542, + 744, + 116, + 604, + 835, + 310, + 847, + 277, + 138, + 979, + 930, + 962, + 3, + 641, + 976, + 673, + 928, + 851, + 456, + 963, + 604, + 336, + 360, + 467, + 374, + 536, + 56, + 729, + 272, + 563, + 205, + 301, + 583, + 329, + 632, + 151, + 678, + 100, + 234, + 74, + 315, + 289, + 759, + 313, + 854, + 558, + 997, + 905, + 186, + 261, + 863, + 607, + 41, + 70, + 234, + 147, + 448, + 619, + 179, + 65, + 716, + 309, + 858, + 408, + 143, + 61, + 760, + 308, + 115, + 116, + 233, + 598, + 170, + 675, + 117, + 147, + 511, + 935, + 857, + 761, + 397, + 692, + 940, + 606, + 235, + 50, + 297, + 219, + 216, + 501, + 489, + 22, + 792, + 878, + 722, + 293, + 667, + 71, + 663, + 870, + 294, + 596, + 885, + 140, + 169, + 325, + 8, + 107, + 780, + 536, + 320, + 652, + 975, + 155, + 371, + 901, + 716, + 175, + 240, + 296, + 355, + 416, + 277, + 187, + 178, + 977, + 254, + 679, + 799, + 428, + 123, + 66, + 195, + 143, + 700, + 648, + 653, + 570, + 363, + 942, + 352, + 981, + 175, + 815, + 618, + 479, + 760, + 663, + 298, + 944, + 716, + 925, + 796, + 312, + 509, + 365, + 165, + 945, + 52, + 787, + 270, + 663, + 358, + 452, + 103, + 809, + 345, + 62, + 545, + 863, + 116, + 952, + 951, + 810, + 297, + 884, + 386, + 683, + 991, + 161, + 48, + 267, + 672, + 558, + 977, + 2, + 827, + 848, + 293, + 860, + 247, + 564, + 141, + 285, + 134, + 736, + 604, + 789, + 441, + 723, + 714, + 911, + 957, + 597, + 510, + 547, + 274, + 761, + 684, + 747, + 652, + 536, + 114, + 555, + 176, + 743, + 923, + 442, + 629, + 984, + 703, + 957, + 620, + 822, + 47, + 186, + 669, + 17, + 168, + 377, + 271, + 562, + 420, + 799, + 820, + 73, + 439, + 884, + 919, + 306, + 164, + 749, + 123, + 830, + 461, + 452, + 353, + 589, + 305, + 907, + 949, + 288, + 733, + 975, + 454, + 821, + 394, + 329, + 776, + 69, + 134, + 808, + 888, + 663, + 594, + 378, + 691, + 175, + 951, + 234, + 635, + 969, + 838, + 443, + 447, + 399, + 563, + 442, + 750, + 523, + 909, + 889, + 768, + 390, + 61, + 896, + 865, + 534, + 72, + 558, + 267, + 678, + 930, + 662, + 655, + 15, + 153, + 885, + 631, + 724, + 475, + 919, + 691, + 260, + 925, + 49, + 798, + 761, + 314, + 497, + 116, + 789, + 548, + 1, + 258, + 388, + 137, + 467, + 706, + 580, + 717, + 110, + 290, + 513, + 408, + 639, + 72, + 629, + 772, + 67, + 460, + 612, + 46, + 88, + 330, + 790, + 854, + 708, + 610, + 334, + 180, + 901, + 718, + 647, + 281, + 135, + 80, + 583, + 591, + 828, + 405, + 843, + 30, + 709, + 657, + 329, + 53, + 351, + 336, + 445, + 249, + 761, + 14, + 187, + 628, + 154, + 381, + 915, + 589, + 911, + 849, + 515, + 39, + 58, + 17, + 790, + 825, + 446, + 99, + 674, + 155, + 407, + 324, + 888, + 447, + 662, + 324, + 588, + 659, + 898, + 234, + 12, + 418, + 514, + 833, + 149, + 241, + 655, + 350, + 256, + 869, + 127, + 629, + 236, + 334, + 940, + 175, + 685, + 224, + 243, + 866, + 979, + 495, + 375, + 525, + 869, + 524, + 894, + 919, + 4, + 184, + 348, + 75, + 892, + 379, + 899, + 177, + 709, + 762, + 356, + 612, + 992, + 723, + 47, + 227, + 317, + 542, + 703, + 279, + 969, + 946, + 473, + 208, + 60, + 872, + 674, + 116, + 360, + 616, + 976, + 253, + 862, + 119, + 649, + 710, + 851, + 690, + 448, + 714, + 152, + 489, + 62, + 833, + 207, + 594, + 100, + 375, + 9, + 497, + 111, + 442, + 116, + 818, + 749, + 177, + 898, + 403, + 243, + 228, + 741, + 680, + 393, + 292, + 726, + 628, + 149, + 127, + 525, + 320, + 404, + 831, + 842, + 852, + 367, + 849, + 66, + 448, + 978, + 941, + 165, + 565, + 960, + 631, + 220, + 220, + 154, + 584, + 841, + 386, + 582, + 233, + 22, + 608, + 508, + 454, + 503, + 267, + 660, + 899, + 404, + 660, + 451, + 86, + 966, + 694, + 133, + 320, + 811, + 966, + 556, + 377, + 653, + 244, + 718, + 255, + 748, + 6, + 237, + 11, + 668, + 411, + 351, + 360, + 833, + 91, + 414, + 264, + 447, + 816, + 962, + 197, + 774, + 504, + 426, + 161, + 42, + 714, + 130, + 699, + 64, + 307, + 15, + 719, + 917, + 452, + 573, + 184, + 297, + 10, + 249, + 628, + 440, + 761, + 170, + 588, + 537, + 318, + 130, + 207, + 376, + 696, + 203, + 202, + 790, + 737, + 133, + 966, + 24, + 127, + 820, + 109, + 53, + 185, + 38, + 946, + 96, + 352, + 529, + 349, + 678, + 309, + 51, + 680, + 881, + 489, + 940, + 962, + 163, + 900, + 797, + 461, + 431, + 973, + 204, + 597, + 681, + 483, + 903, + 351, + 885, + 646, + 358, + 891, + 564, + 405, + 989, + 656, + 628, + 749, + 23, + 243, + 407, + 178, + 22, + 132, + 883, + 365, + 471, + 941, + 762, + 226, + 403, + 87, + 231, + 589, + 543, + 346, + 737, + 817, + 261, + 857, + 869, + 996, + 27, + 280, + 595, + 538, + 113, + 628, + 587, + 677, + 641, + 421, + 176, + 262, + 399, + 786, + 970, + 330, + 936, + 633, + 690, + 156, + 855, + 313, + 550, + 707, + 201, + 910, + 556, + 248, + 34, + 432, + 547, + 622, + 737, + 233, + 941, + 694, + 526, + 409, + 458, + 133, + 900, + 248, + 670, + 109, + 802, + 295, + 233, + 117, + 923, + 139, + 855, + 382, + 757, + 399, + 462, + 115, + 447, + 444, + 53, + 235, + 163, + 232, + 333, + 335, + 219, + 625, + 95, + 674, + 879, + 204, + 460, + 370, + 829, + 943, + 420, + 10, + 538, + 863, + 694, + 537, + 124, + 406, + 294, + 131, + 306, + 420, + 12, + 385, + 107, + 33, + 153, + 815, + 899, + 989, + 845, + 875, + 772, + 172, + 308, + 285, + 1, + 721, + 487, + 495, + 310, + 222, + 950, + 874, + 211, + 837, + 723, + 834, + 407, + 327, + 658, + 647, + 1, + 278, + 524, + 266, + 906, + 312, + 955, + 632, + 631, + 515, + 440, + 334, + 122, + 559, + 72, + 785, + 431, + 621, + 61, + 584, + 588, + 594, + 16, + 217, + 50, + 831, + 188, + 52, + 393, + 993, + 495, + 848, + 480, + 456, + 370, + 424, + 777, + 718, + 39, + 186, + 466, + 773, + 185, + 508, + 464, + 989, + 135, + 971, + 470, + 682, + 443, + 97, + 124, + 838, + 135, + 186, + 427, + 544, + 719, + 411, + 244, + 64, + 273, + 568, + 160, + 173, + 273, + 185, + 826, + 238, + 841, + 840, + 553, + 33, + 758, + 873, + 162, + 707, + 158, + 166, + 714, + 461, + 573, + 566, + 256, + 903, + 798, + 242, + 561, + 763, + 334, + 164, + 781, + 73, + 309, + 228, + 71, + 643, + 774, + 672, + 507, + 676, + 406, + 695, + 623, + 993, + 729, + 898, + 324, + 420, + 903, + 599, + 622, + 129, + 694, + 716, + 742, + 632, + 89, + 740, + 417, + 606, + 494, + 697, + 697, + 655, + 30, + 87, + 617, + 604, + 101, + 537, + 566, + 828, + 969, + 570, + 993, + 883, + 127, + 625, + 985, + 804, + 553, + 874, + 758, + 396, + 875, + 133, + 224, + 853, + 877, + 710, + 782, + 155, + 923, + 416, + 794, + 663, + 200, + 30, + 689, + 77, + 218, + 632, + 849, + 60, + 270, + 446, + 419, + 697, + 980, + 892, + 935, + 24, + 717, + 178, + 471, + 497, + 209, + 743, + 284, + 3, + 813, + 234, + 76, + 527, + 145, + 684, + 742, + 500, + 832, + 533, + 780, + 226, + 800, + 897, + 102, + 309, + 994, + 775, + 888, + 944, + 243, + 54, + 17, + 107, + 929, + 52, + 244, + 843, + 553, + 701, + 236, + 53, + 909, + 972, + 753, + 927, + 796, + 81, + 679, + 394, + 649, + 991, + 973, + 903, + 797, + 321, + 763, + 37, + 991, + 544, + 268, + 236, + 10, + 923, + 443, + 394, + 720, + 76, + 434, + 280, + 314, + 91, + 934, + 848, + 217, + 697, + 646, + 53, + 647, + 723, + 154, + 894, + 943, + 217, + 641, + 64, + 987, + 58, + 98, + 191, + 819, + 510, + 708, + 33, + 747, + 400, + 513, + 360, + 526, + 173, + 733, + 234, + 759, + 525, + 485, + 463, + 382, + 261, + 826, + 870, + 999, + 655, + 564, + 947, + 334, + 479, + 963, + 641, + 647, + 554, + 497, + 688, + 818, + 941, + 20, + 235, + 523, + 847, + 527, + 290, + 535, + 244, + 312, + 703, + 779, + 768, + 732, + 734, + 759, + 228, + 671, + 245, + 304, + 191, + 808, + 502, + 219, + 948, + 24, + 398, + 268, + 540, + 243, + 691, + 966, + 768, + 631, + 38, + 446, + 446, + 697, + 82, + 824, + 893, + 696, + 553, + 563, + 502, + 25, + 34, + 648, + 753, + 857, + 8, + 341, + 801, + 913, + 802, + 177, + 805, + 155, + 242, + 920, + 148, + 139, + 517, + 413, + 252, + 225, + 766, + 663, + 767, + 179, + 615, + 212, + 299, + 424, + 125, + 155, + 717, + 263, + 174, + 390, + 849, + 645, + 242, + 572, + 768, + 821, + 739, + 12, + 398, + 617, + 875, + 957, + 14, + 791, + 633, + 539, + 221, + 80, + 487, + 467, + 88, + 234, + 770, + 816, + 947, + 220, + 967, + 942, + 344, + 993, + 79, + 388, + 415, + 886, + 335, + 967, + 560, + 486, + 606, + 49, + 114, + 582, + 891, + 544, + 623, + 858, + 875, + 986, + 486, + 549, + 196, + 198, + 108, + 152, + 545, + 430, + 569, + 122, + 123, + 386, + 163, + 269, + 400, + 774, + 65, + 689, + 802, + 35, + 629, + 738, + 662, + 930, + 494, + 45, + 816, + 412, + 401, + 728, + 336, + 584, + 876, + 14, + 27, + 12, + 224, + 482, + 304, + 852, + 352, + 163, + 300, + 545, + 554, + 958, + 621, + 872, + 192, + 450, + 400, + 195, + 339, + 916, + 344, + 341, + 814, + 450, + 292, + 783, + 818, + 573, + 187, + 992, + 219, + 103, + 894, + 857, + 262, + 204, + 570, + 30, + 293, + 454, + 72, + 568, + 273, + 112, + 923, + 247, + 251, + 780, + 590, + 349, + 311, + 856, + 583, + 566, + 965, + 74, + 260, + 523, + 413, + 892, + 640, + 718, + 646, + 244, + 2, + 440, + 492, + 906, + 619, + 94, + 124, + 732, + 250, + 906, + 669, + 903, + 885, + 494, + 972, + 619, + 414, + 627, + 131, + 249, + 528, + 447, + 992, + 345, + 940, + 765, + 238, + 131, + 900, + 327, + 554, + 975, + 547, + 630, + 428, + 673, + 144, + 690, + 200, + 148, + 405, + 29, + 680, + 559, + 896, + 321, + 736, + 540, + 197, + 154, + 373, + 221, + 78, + 134, + 443, + 514, + 40, + 577, + 529, + 205, + 83, + 366, + 475, + 703, + 166, + 31, + 340, + 803, + 940, + 181, + 134, + 520, + 159, + 99, + 168, + 404, + 343, + 317, + 298, + 715, + 303, + 990, + 32, + 999, + 653, + 151, + 913, + 449, + 884, + 571, + 139, + 806, + 296, + 375, + 476, + 206, + 45, + 991, + 607, + 5, + 851, + 283, + 642, + 396, + 370, + 25, + 24, + 418, + 679, + 469, + 607, + 355, + 600, + 83, + 32, + 787, + 834, + 972, + 351, + 948, + 356, + 270, + 606, + 322, + 279, + 966, + 138, + 832, + 428, + 306, + 889, + 828, + 34, + 449, + 879, + 205, + 227, + 67, + 132, + 845, + 506, + 317, + 867, + 353, + 804, + 532, + 41, + 157, + 400, + 691, + 424, + 812, + 523, + 232, + 584, + 885, + 556, + 504, + 985, + 322, + 969, + 371, + 391, + 98, + 941, + 26, + 178, + 774, + 463, + 997, + 240, + 265, + 783, + 393, + 970, + 984, + 767, + 198, + 352, + 641, + 75, + 295, + 130, + 103, + 967, + 755, + 140, + 35, + 36, + 632, + 140, + 31, + 343, + 311, + 875, + 957, + 214, + 594, + 102, + 708, + 704, + 42, + 385, + 66, + 207, + 462, + 7, + 629, + 996, + 45, + 239, + 67, + 320, + 572, + 870, + 745, + 491, + 347, + 526, + 400, + 699, + 754, + 976, + 956, + 954, + 794, + 539, + 303, + 659, + 358, + 240, + 499, + 659, + 623, + 633, + 84, + 969, + 47, + 38, + 147, + 473, + 237, + 108, + 223, + 587, + 983, + 835, + 709, + 650, + 654, + 290, + 457, + 508, + 179, + 41, + 861, + 141, + 415, + 338, + 134, + 768, + 896, + 332, + 774, + 619, + 168, + 326, + 995, + 974, + 888, + 405, + 863, + 48, + 321, + 634, + 321, + 270, + 859, + 323, + 320, + 737, + 558, + 628, + 600, + 523, + 806, + 90, + 149, + 997, + 588, + 708, + 940, + 616, + 975, + 302, + 113, + 670, + 369, + 987, + 171, + 900, + 669, + 758, + 668, + 439, + 111, + 749, + 85, + 423, + 868, + 299, + 854, + 861, + 512, + 673, + 594, + 180, + 719, + 880, + 377, + 927, + 123, + 93, + 351, + 135, + 116, + 681, + 353, + 159, + 981, + 788, + 232, + 670, + 43, + 414, + 383, + 448, + 113, + 401, + 103, + 514, + 158, + 22, + 537, + 72, + 392, + 763, + 35, + 420, + 434, + 526, + 732, + 53, + 193, + 681, + 185, + 586, + 476, + 362, + 274, + 409, + 658, + 165, + 767, + 233, + 389, + 776, + 179, + 432, + 84, + 27, + 691, + 946, + 470, + 906, + 144, + 423, + 226, + 616, + 247, + 503, + 52, + 921, + 450, + 596, + 634, + 189, + 640, + 812, + 892, + 964, + 903, + 866, + 914, + 506, + 858, + 104, + 335, + 545, + 557, + 515, + 707, + 797, + 965, + 331, + 927, + 376, + 757, + 886, + 154, + 827, + 675, + 744, + 712, + 717, + 977, + 168, + 49, + 739, + 407, + 50, + 224, + 180, + 317, + 364, + 594, + 696, + 318, + 336, + 734, + 293, + 497, + 469, + 988, + 653, + 241, + 114, + 982, + 927, + 708, + 609, + 851, + 256, + 225, + 51, + 194, + 14, + 282, + 557, + 892, + 905, + 457, + 759, + 466, + 622, + 351, + 245, + 5, + 449, + 80, + 548, + 213, + 711, + 458, + 106, + 713, + 94, + 587, + 650, + 853, + 41, + 578, + 515, + 946, + 3, + 758, + 437, + 935, + 967, + 284, + 783, + 525, + 306, + 820, + 175, + 216, + 350, + 866, + 535, + 369, + 843, + 642, + 848, + 648, + 44, + 796, + 390, + 983, + 292, + 352, + 992, + 122, + 715, + 123, + 2, + 83, + 193, + 711, + 329, + 242, + 453, + 600, + 770, + 969, + 90, + 259, + 71, + 253, + 311, + 865, + 679, + 120, + 409, + 329, + 113, + 636, + 784, + 548, + 5, + 162, + 555, + 82, + 479, + 168, + 984, + 802, + 681, + 497, + 996, + 382, + 339, + 55, + 947, + 117, + 162, + 275, + 493, + 410, + 234, + 69, + 54, + 817, + 985, + 639, + 479, + 362, + 394, + 939, + 494, + 462, + 642, + 301, + 983, + 350, + 923, + 244, + 565, + 587, + 811, + 130, + 2, + 249, + 56, + 722, + 814, + 940, + 346, + 233, + 575, + 764, + 917, + 981, + 350, + 589, + 969, + 834, + 506, + 623, + 448, + 515, + 715, + 397, + 395, + 174, + 196, + 337, + 713, + 560, + 686, + 836, + 837, + 544, + 582, + 586, + 883, + 968, + 810, + 164, + 568, + 109, + 333, + 703, + 3, + 719, + 500, + 530, + 11, + 628, + 164, + 246, + 446, + 472, + 883, + 142, + 978, + 127, + 127, + 837, + 156, + 66, + 142, + 382, + 852, + 608, + 956, + 287, + 553, + 284, + 347, + 23, + 358, + 964, + 746, + 894, + 32, + 258, + 788, + 404, + 75, + 587, + 955, + 593, + 640, + 828, + 977, + 428, + 189, + 421, + 587, + 31, + 41, + 718, + 490, + 535, + 330, + 589, + 256, + 762, + 629, + 586, + 916, + 745, + 353, + 114, + 385, + 517, + 1, + 279, + 673, + 638, + 516, + 273, + 953, + 822, + 323, + 973, + 946, + 715, + 414, + 811, + 28, + 804, + 139, + 254, + 110, + 811, + 684, + 405, + 174, + 97, + 444, + 222, + 329, + 911, + 670, + 642, + 424, + 24, + 129, + 772, + 432, + 372, + 124, + 43, + 396, + 319, + 386, + 934, + 153, + 697, + 562, + 375, + 838, + 510, + 574, + 8, + 870, + 677, + 326, + 410, + 19, + 510, + 433, + 893, + 768, + 853, + 775, + 994, + 851, + 611, + 885, + 212, + 885, + 411, + 597, + 36, + 951, + 482, + 530, + 572, + 492, + 583, + 749, + 579, + 293, + 315, + 783, + 31, + 789, + 298, + 772, + 697, + 113, + 87, + 624, + 402, + 939, + 214, + 569, + 92, + 324, + 338, + 680, + 627, + 979, + 679, + 685, + 954, + 247, + 130, + 718, + 993, + 444, + 692, + 459, + 652, + 877, + 733, + 689, + 848, + 63, + 325, + 90, + 638, + 494, + 278, + 454, + 490, + 807, + 30, + 904, + 133, + 648, + 201, + 990, + 662, + 647, + 987, + 94, + 103, + 886, + 386, + 578, + 667, + 536, + 754, + 56, + 382, + 963, + 506, + 825, + 173, + 850, + 635, + 796, + 229, + 893, + 785, + 30, + 143, + 375, + 306, + 367, + 888, + 996, + 908, + 332, + 239, + 925, + 603, + 189, + 160, + 738, + 16, + 403, + 222, + 546, + 469, + 416, + 29, + 914, + 212, + 666, + 260, + 352, + 592, + 389, + 793, + 834, + 43, + 260, + 583, + 984, + 590, + 508, + 347, + 115, + 199, + 309, + 508, + 400, + 669, + 110, + 201, + 5, + 575, + 500, + 292, + 759, + 898, + 671, + 612, + 438, + 33, + 561, + 560, + 205, + 719, + 987, + 263, + 313, + 144, + 189, + 429, + 366, + 229, + 618, + 384, + 865, + 278, + 926, + 329, + 869, + 930, + 789, + 925, + 797, + 554, + 442, + 595, + 979, + 276, + 72, + 960, + 883, + 436, + 816, + 70, + 631, + 956, + 704, + 691, + 775, + 67, + 196, + 246, + 324, + 260, + 252, + 68, + 442, + 493, + 266, + 873, + 264, + 920, + 686, + 970, + 661, + 807, + 496, + 214, + 225, + 80, + 505, + 837, + 965, + 360, + 494, + 233, + 584, + 268, + 618, + 633, + 894, + 994, + 110, + 917, + 711, + 214, + 832, + 291, + 354, + 961, + 142, + 343, + 548, + 803, + 661, + 706, + 969, + 201, + 938, + 706, + 438, + 922, + 228, + 775, + 736, + 91, + 948, + 581, + 564, + 370, + 995, + 653, + 252, + 872, + 70, + 990, + 323, + 392, + 48, + 737, + 957, + 660, + 405, + 290, + 886, + 550, + 86, + 426, + 678, + 908, + 325, + 65, + 845, + 933, + 918, + 393, + 504, + 272, + 785, + 526, + 480, + 331, + 400, + 514, + 940, + 121, + 9, + 965, + 907, + 165, + 521, + 825, + 40, + 251, + 227, + 739, + 370, + 606, + 572, + 70, + 118, + 684, + 236, + 809, + 947, + 221, + 588, + 369, + 826, + 554, + 206, + 353, + 168, + 995, + 549, + 733, + 42, + 297, + 346, + 495, + 684, + 266, + 672, + 400, + 150, + 178, + 45, + 40, + 723, + 527, + 349, + 985, + 279, + 965, + 668, + 29, + 684, + 447, + 152, + 241, + 801, + 335, + 777, + 601, + 968, + 997, + 614, + 762, + 586, + 540, + 429, + 174, + 626, + 770, + 855, + 522, + 250, + 846, + 878, + 412, + 566, + 995, + 715, + 880, + 819, + 67, + 152, + 154, + 331, + 191, + 879, + 869, + 201, + 642, + 229, + 298, + 251, + 182, + 871, + 757, + 905, + 462, + 7, + 9, + 896, + 234, + 51, + 579, + 603, + 265, + 850, + 203, + 62, + 577, + 812, + 511, + 816, + 498, + 805, + 35, + 358, + 144, + 77, + 731, + 198, + 647, + 679, + 697, + 766, + 553, + 980, + 49, + 337, + 803, + 387, + 593, + 459, + 286, + 352, + 798, + 154, + 888, + 494, + 914, + 961, + 547, + 154, + 802, + 889, + 726, + 638, + 740, + 710, + 263, + 126, + 509, + 220, + 626, + 650, + 40, + 821, + 979, + 240, + 371, + 936, + 7, + 926, + 252, + 142, + 200, + 1, + 801, + 252, + 208, + 605, + 516, + 777, + 997, + 370, + 869, + 523, + 651, + 799, + 321, + 938, + 575, + 397, + 289, + 704, + 359, + 99, + 245, + 635, + 79, + 849, + 375, + 753, + 806, + 315, + 21, + 871, + 991, + 828, + 942, + 478, + 651, + 532, + 357, + 482, + 76, + 536, + 603, + 8, + 941, + 541, + 639, + 924, + 709, + 648, + 169, + 84, + 810, + 836, + 724, + 997, + 346, + 945, + 961, + 296, + 708, + 790, + 640, + 0, + 829, + 692, + 178, + 258, + 727, + 958, + 490, + 169, + 612, + 232, + 33, + 526, + 776, + 947, + 161, + 697, + 20, + 930, + 57, + 630, + 359, + 716, + 247, + 214, + 839, + 662, + 141, + 401, + 157, + 436, + 98, + 173, + 390, + 620, + 608, + 14, + 518, + 880, + 749, + 218, + 704, + 902, + 131, + 663, + 288, + 797, + 171, + 316, + 89, + 806, + 367, + 513, + 666, + 917, + 660, + 891, + 835, + 610, + 822, + 88, + 765, + 760, + 69, + 579, + 16, + 202, + 470, + 973, + 542, + 21, + 853, + 905, + 108, + 62, + 285, + 313, + 337, + 488, + 546, + 482, + 575, + 385, + 997, + 73, + 919, + 939, + 503, + 888, + 345, + 666, + 425, + 722, + 864, + 831, + 432, + 542, + 196, + 536, + 582, + 275, + 489, + 793, + 835, + 457, + 645, + 275, + 499, + 7, + 759, + 959, + 400, + 983, + 387, + 768, + 928, + 858, + 938, + 938, + 258, + 457, + 166, + 547, + 954, + 505, + 483, + 868, + 556, + 994, + 752, + 163, + 301, + 340, + 445, + 641, + 436, + 439, + 935, + 91, + 736, + 277, + 895, + 935, + 139, + 582, + 208, + 309, + 468, + 784, + 847, + 991, + 571, + 561, + 573, + 143, + 181, + 99, + 232, + 691, + 567, + 634, + 352, + 775, + 39, + 173, + 877, + 688, + 845, + 102, + 565, + 760, + 585, + 920, + 979, + 563, + 839, + 324, + 987, + 541, + 557, + 904, + 658, + 830, + 141, + 77, + 955, + 19, + 357, + 939, + 324, + 793, + 604, + 731, + 535, + 848, + 527, + 392, + 804, + 771, + 202, + 955, + 996, + 904, + 290, + 762, + 368, + 552, + 30, + 277, + 784, + 204, + 446, + 829, + 367, + 857, + 180, + 880, + 148, + 946, + 447, + 309, + 315, + 858, + 231, + 664, + 490, + 946, + 242, + 443, + 448, + 309, + 869, + 650, + 431, + 141, + 990, + 745, + 850, + 593, + 62, + 580, + 690, + 158, + 28, + 98, + 371, + 567, + 309, + 647, + 651, + 602, + 647, + 949, + 938, + 848, + 612, + 239, + 812, + 521, + 37, + 121, + 756, + 674, + 948, + 735, + 779, + 668, + 515, + 320, + 142, + 154, + 266, + 582, + 941, + 887, + 171, + 277, + 392, + 489, + 603, + 654, + 492, + 670, + 313, + 768, + 51, + 545, + 424, + 497, + 834, + 457, + 577, + 798, + 243, + 695, + 722, + 429, + 691, + 209, + 363, + 179, + 302, + 152, + 647, + 743, + 158, + 234, + 127, + 993, + 971, + 477, + 26, + 345, + 84, + 737, + 585, + 496, + 220, + 465, + 126, + 125, + 991, + 870, + 645, + 502, + 531, + 63, + 347, + 616, + 580, + 96, + 315, + 286, + 264, + 230, + 432, + 274, + 537, + 733, + 708, + 931, + 224, + 871, + 886, + 843, + 727, + 249, + 306, + 691, + 887, + 763, + 899, + 717, + 480, + 411, + 124, + 990, + 895, + 767, + 252, + 398, + 713, + 893, + 935, + 773, + 998, + 625, + 849, + 380, + 761, + 627, + 125, + 541, + 108, + 177, + 508, + 824, + 640, + 320, + 809, + 788, + 513, + 115, + 65, + 270, + 584, + 422, + 17, + 840, + 587, + 778, + 703, + 433, + 399, + 92, + 570, + 325, + 22, + 452, + 950, + 105, + 459, + 671, + 7, + 357, + 713, + 106, + 871, + 94, + 404, + 948, + 530, + 631, + 679, + 806, + 774, + 371, + 124, + 529, + 513, + 26, + 859, + 172, + 331, + 566, + 434, + 1, + 970, + 56, + 18, + 411, + 123, + 316, + 194, + 574, + 190, + 302, + 548, + 643, + 635, + 871, + 630, + 207, + 193, + 984, + 963, + 623, + 742, + 257, + 336, + 153, + 792, + 967, + 235, + 506, + 401, + 408, + 45, + 648, + 153, + 364, + 320, + 619, + 949, + 354, + 243, + 437, + 646, + 675, + 74, + 658, + 781, + 24, + 282, + 902, + 530, + 403, + 499, + 962, + 787, + 980, + 815, + 163, + 921, + 355, + 375, + 103, + 223, + 556, + 860, + 636, + 420, + 212, + 690, + 559, + 39, + 222, + 201, + 70, + 282, + 83, + 53, + 83, + 520, + 716, + 286, + 149, + 456, + 277, + 130, + 500, + 379, + 495, + 485, + 729, + 922, + 762, + 59, + 880, + 432, + 6, + 500, + 19, + 982, + 612, + 22, + 812, + 278, + 222, + 897, + 854, + 360, + 719, + 923, + 264, + 120, + 760, + 427, + 520, + 304, + 800, + 411, + 720, + 729, + 399, + 207, + 336, + 917, + 368, + 763, + 560, + 568, + 609, + 361, + 359, + 253, + 672, + 742, + 141, + 397, + 292, + 262, + 881, + 258, + 564, + 566, + 72, + 633, + 920, + 904, + 419, + 990, + 10, + 812, + 547, + 545, + 232, + 129, + 284, + 975, + 178, + 483, + 75, + 780, + 562, + 910, + 277, + 107, + 836, + 912, + 638, + 896, + 204, + 861, + 507, + 604, + 103, + 868, + 644, + 496, + 215, + 215, + 553, + 645, + 398, + 752, + 352, + 984, + 6, + 846, + 49, + 811, + 354, + 263, + 286, + 518, + 269, + 639, + 74, + 637, + 917, + 15, + 244, + 539, + 595, + 545, + 856, + 68, + 354, + 968, + 10, + 256, + 106, + 124, + 864, + 595, + 936, + 194, + 956, + 201, + 612, + 603, + 546, + 703, + 582, + 139, + 436, + 716, + 605, + 65, + 832, + 103, + 742, + 511, + 26, + 122, + 309, + 599, + 251, + 324, + 507, + 125, + 294, + 877, + 45, + 956, + 27, + 330, + 36, + 80, + 298, + 272, + 438, + 243, + 437, + 741, + 121, + 507, + 674, + 194, + 263, + 440, + 772, + 93, + 3, + 139, + 173, + 594, + 174, + 770, + 954, + 393, + 549, + 33, + 435, + 836, + 75, + 842, + 469, + 887, + 919, + 901, + 326, + 898, + 346, + 314, + 389, + 818, + 663, + 371, + 843, + 363, + 959, + 215, + 802, + 218, + 776, + 153, + 648, + 150, + 257, + 31, + 711, + 335, + 516, + 582, + 317, + 999, + 393, + 435, + 371, + 926, + 507, + 933, + 925, + 825, + 554, + 870, + 845, + 194, + 588, + 423, + 819, + 698, + 312, + 107, + 541, + 443, + 833, + 20, + 79, + 147, + 331, + 986, + 784, + 130, + 261, + 714, + 537, + 500, + 363, + 259, + 122, + 506, + 550, + 204, + 466, + 763, + 650, + 360, + 826, + 385, + 189, + 836, + 807, + 862, + 943, + 431, + 547, + 300, + 682, + 336, + 71, + 467, + 871, + 6, + 207, + 214, + 482, + 128, + 42, + 151, + 788, + 597, + 644, + 217, + 507, + 653, + 330, + 660, + 696, + 287, + 513, + 506, + 124, + 348, + 195, + 344, + 480, + 112, + 839, + 497, + 751, + 689, + 579, + 820, + 490, + 903, + 809, + 790, + 409, + 684, + 708, + 538, + 177, + 77, + 702, + 997, + 846, + 958, + 767, + 174, + 206, + 236, + 340, + 66, + 495, + 364, + 833, + 710, + 598, + 889, + 36, + 413, + 485, + 27, + 824, + 138, + 864, + 146, + 890, + 855, + 133, + 57, + 788, + 755, + 597, + 256, + 76, + 75, + 795, + 970, + 384, + 463, + 528, + 142, + 232, + 973, + 961, + 696, + 231, + 251, + 918, + 383, + 264, + 229, + 103, + 610, + 505, + 311, + 725, + 203, + 414, + 53, + 258, + 973, + 293, + 254, + 782, + 26, + 490, + 190, + 927, + 341, + 479, + 858, + 804, + 463, + 457, + 47, + 718, + 205, + 521, + 107, + 171, + 414, + 845, + 941, + 865, + 778, + 315, + 513, + 236, + 669, + 681, + 187, + 964, + 875, + 548, + 869, + 157, + 782, + 876, + 820, + 436, + 595, + 304, + 452, + 667, + 827, + 803, + 227, + 466, + 253, + 874, + 43, + 987, + 416, + 64, + 529, + 943, + 471, + 753, + 259, + 81, + 693, + 231, + 159, + 143, + 399, + 492, + 510, + 257, + 825, + 557, + 263, + 536, + 200, + 71, + 744, + 132, + 231, + 842, + 159, + 49, + 302, + 806, + 870, + 999, + 580, + 941, + 437, + 261, + 861, + 423, + 929, + 994, + 534, + 396, + 315, + 783, + 765, + 930, + 644, + 756, + 462, + 195, + 564, + 22, + 384, + 521, + 730, + 505, + 63, + 457, + 709, + 976, + 314, + 282, + 864, + 118, + 724, + 440, + 316, + 776, + 848, + 506, + 48, + 233, + 789, + 380, + 580, + 889, + 81, + 697, + 763, + 59, + 234, + 408, + 647, + 306, + 431, + 170, + 942, + 7, + 854, + 406, + 217, + 257, + 654, + 945, + 846, + 874, + 436, + 621, + 787, + 538, + 556, + 245, + 891, + 675, + 141, + 746, + 646, + 56, + 919, + 717, + 816, + 234, + 712, + 458, + 339, + 680, + 705, + 485, + 616, + 610, + 208, + 251, + 273, + 242, + 151, + 560, + 362, + 520, + 417, + 760, + 758, + 89, + 229, + 964, + 150, + 683, + 851, + 620, + 180, + 304, + 339, + 923, + 78, + 12, + 253, + 307, + 854, + 692, + 339, + 854, + 773, + 925, + 938, + 926, + 680, + 358, + 592, + 522, + 3, + 916, + 431, + 61, + 649, + 448, + 463, + 508, + 758, + 646, + 122, + 644, + 508, + 85, + 945, + 934, + 473, + 86, + 380, + 856, + 26, + 642, + 831, + 889, + 592, + 669, + 896, + 665, + 897, + 497, + 740, + 987, + 530, + 217, + 945, + 800, + 104, + 267, + 558, + 688, + 806, + 944, + 79, + 119, + 416, + 715, + 389, + 267, + 333, + 579, + 882, + 278, + 972, + 767, + 890, + 412, + 110, + 525, + 605, + 273, + 857, + 312, + 841, + 312, + 76, + 596, + 956, + 484, + 30, + 230, + 319, + 789, + 586, + 44, + 341, + 434, + 565, + 238, + 907, + 581, + 719, + 944, + 19, + 447, + 599, + 966, + 776, + 472, + 393, + 179, + 350, + 59, + 291, + 317, + 585, + 868, + 750, + 464, + 35, + 79, + 888, + 245, + 972, + 150, + 190, + 511, + 785, + 79, + 726, + 51, + 655, + 456, + 474, + 441, + 257, + 664, + 257, + 683, + 70, + 763, + 743, + 208, + 190, + 857, + 693, + 574, + 626, + 411, + 484, + 434, + 507, + 779, + 306, + 549, + 778, + 512, + 343, + 549, + 679, + 259, + 793, + 492, + 966, + 281, + 787, + 858, + 419, + 580, + 588, + 626, + 166, + 360, + 780, + 747, + 249, + 856, + 305, + 861, + 383, + 938, + 520, + 78, + 311, + 334, + 592, + 8, + 629, + 606, + 623, + 217, + 466, + 378, + 856, + 551, + 458, + 243, + 484, + 294, + 587, + 953, + 749, + 287, + 733, + 796, + 498, + 534, + 989, + 379, + 804, + 560, + 971, + 333, + 384, + 367, + 292, + 898, + 277, + 508, + 58, + 636, + 37, + 312, + 742, + 879, + 536, + 239, + 240, + 730, + 3, + 593, + 301, + 66, + 144, + 62, + 248, + 634, + 863, + 14, + 579, + 120, + 250, + 322, + 964, + 447, + 727, + 322, + 765, + 268, + 206, + 364, + 515, + 471, + 858, + 438, + 840, + 968, + 13, + 264, + 388, + 75, + 163, + 137, + 999, + 866, + 153, + 356, + 193, + 854, + 718, + 606, + 730, + 162, + 431, + 375, + 917, + 548, + 825, + 99, + 271, + 0, + 303, + 228, + 894, + 370, + 644, + 38, + 532, + 512, + 546, + 303, + 923, + 170, + 489, + 40, + 82, + 479, + 971, + 452, + 637, + 557, + 940, + 132, + 908, + 268, + 774, + 932, + 786, + 976, + 491, + 710, + 197, + 554, + 532, + 265, + 909, + 18, + 758, + 213, + 45, + 698, + 180, + 990, + 471, + 610, + 575, + 659, + 412, + 595, + 275, + 498, + 713, + 306, + 259, + 1, + 253, + 316, + 357, + 155, + 55, + 520, + 687, + 350, + 644, + 974, + 945, + 277, + 654, + 850, + 412, + 847, + 384, + 820, + 512, + 979, + 21, + 823, + 299, + 93, + 793, + 204, + 925, + 130, + 103, + 314, + 105, + 564, + 762, + 524, + 478, + 178, + 807, + 56, + 916, + 711, + 511, + 111, + 865, + 110, + 195, + 982, + 171, + 631, + 960, + 640, + 584, + 600, + 770, + 669, + 649, + 51, + 212, + 828, + 973, + 448, + 101, + 856, + 801, + 679, + 694, + 242, + 334, + 620, + 160, + 667, + 891, + 791, + 659, + 107, + 865, + 126, + 882, + 675, + 726, + 234, + 346, + 875, + 88, + 115, + 592, + 729, + 299, + 177, + 210, + 456, + 766, + 928, + 837, + 417, + 856, + 631, + 142, + 640, + 848, + 805, + 989, + 509, + 106, + 440, + 276, + 581, + 117, + 187, + 565, + 620, + 433, + 475, + 873, + 626, + 342, + 455, + 373, + 767, + 855, + 866, + 942, + 108, + 117, + 799, + 85, + 936, + 665, + 975, + 750, + 35, + 769, + 889, + 610, + 210, + 220, + 359, + 981, + 728, + 649, + 0, + 826, + 950, + 120, + 648, + 58, + 383, + 436, + 737, + 11, + 714, + 424, + 251, + 301, + 204, + 287, + 183, + 472, + 265, + 120, + 780, + 369, + 695, + 758, + 740, + 107, + 831, + 93, + 535, + 306, + 777, + 976, + 562, + 59, + 956, + 304, + 83, + 576, + 399, + 999, + 899, + 824, + 350, + 635, + 896, + 802, + 332, + 421, + 878, + 433, + 193, + 353, + 802, + 683, + 456, + 88, + 211, + 132, + 432, + 354, + 421, + 616, + 53, + 231, + 915, + 510, + 106, + 28, + 32, + 600, + 461, + 131, + 594, + 678, + 744, + 674, + 620, + 290, + 535, + 534, + 543, + 62, + 971, + 905, + 180, + 10, + 234, + 166, + 272, + 73, + 128, + 437, + 613, + 291, + 638, + 610, + 225, + 630, + 309, + 112, + 868, + 557, + 439, + 355, + 555, + 579, + 443, + 843, + 20, + 464, + 987, + 284, + 302, + 450, + 355, + 83, + 407, + 711, + 752, + 187, + 249, + 807, + 883, + 924, + 858, + 110, + 409, + 189, + 998, + 439, + 120, + 321, + 875, + 140, + 640, + 285, + 561, + 873, + 371, + 73, + 4, + 169, + 771, + 413, + 447, + 985, + 206, + 635, + 943, + 960, + 240, + 554, + 209, + 576, + 254, + 163, + 977, + 846, + 610, + 596, + 920, + 524, + 608, + 402, + 249, + 624, + 180, + 875, + 240, + 670, + 421, + 1, + 911, + 505, + 474, + 979, + 623, + 678, + 952, + 909, + 751, + 241, + 269, + 968, + 396, + 641, + 516, + 965, + 406, + 54, + 853, + 346, + 650, + 787, + 400, + 175, + 929, + 662, + 870, + 170, + 468, + 173, + 620, + 318, + 170, + 995, + 525, + 138, + 520, + 151, + 851, + 30, + 596, + 605, + 802, + 449, + 174, + 518, + 633, + 293, + 652, + 779, + 606, + 444, + 472, + 359, + 204, + 308, + 104, + 274, + 707, + 638, + 193, + 577, + 125, + 28, + 537, + 987, + 521, + 80, + 56, + 111, + 589, + 81, + 794, + 377, + 36, + 680, + 476, + 227, + 778, + 138, + 24, + 752, + 160, + 590, + 855, + 396, + 289, + 142, + 785, + 551, + 696, + 514, + 268, + 536, + 547, + 207, + 943, + 166, + 0, + 959, + 114, + 322, + 906, + 322, + 892, + 960, + 152, + 219, + 944, + 540, + 874, + 965, + 269, + 858, + 681, + 764, + 673, + 30, + 954, + 88, + 521, + 729, + 159, + 275, + 56, + 125, + 755, + 556, + 505, + 72, + 919, + 180, + 714, + 476, + 557, + 286, + 639, + 983, + 152, + 572, + 584, + 774, + 510, + 716, + 601, + 148, + 732, + 601, + 940, + 969, + 20, + 190, + 364, + 622, + 685, + 61, + 344, + 196, + 7, + 990, + 899, + 252, + 754, + 435, + 284, + 201, + 722, + 552, + 343, + 657, + 969, + 888, + 215, + 691, + 409, + 26, + 814, + 955, + 756, + 555, + 490, + 721, + 618, + 204, + 30, + 599, + 134, + 692, + 978, + 825, + 270, + 841, + 504, + 774, + 525, + 384, + 45, + 973, + 630, + 292, + 407, + 67, + 655, + 51, + 321, + 712, + 920, + 987, + 848, + 722, + 54, + 844, + 881, + 2, + 745, + 543, + 18, + 346, + 886, + 284, + 553, + 327, + 745, + 802, + 253, + 852, + 636, + 390, + 455, + 868, + 740, + 663, + 964, + 729, + 838, + 160, + 466, + 658, + 934, + 788, + 92, + 286, + 175, + 248, + 540, + 880, + 948, + 738, + 221, + 979, + 785, + 992, + 482, + 300, + 55, + 307, + 541, + 695, + 226, + 659, + 648, + 922, + 441, + 203, + 794, + 22, + 970, + 164, + 46, + 259, + 951, + 704, + 886, + 299, + 673, + 173, + 240, + 807, + 719, + 658, + 194, + 357, + 971, + 821, + 711, + 707, + 225, + 482, + 734, + 77, + 917, + 665, + 867, + 755, + 544, + 326, + 524, + 598, + 78, + 244, + 906, + 617, + 928, + 395, + 658, + 732, + 601, + 421, + 359, + 459, + 727, + 409, + 806, + 285, + 943, + 207, + 630, + 752, + 85, + 819, + 81, + 714, + 599, + 44, + 892, + 139, + 813, + 684, + 175, + 718, + 720, + 697, + 401, + 310, + 84, + 666, + 259, + 357, + 939, + 246, + 527, + 856, + 455, + 533, + 717, + 790, + 923, + 962, + 105, + 447, + 598, + 8, + 941, + 409, + 510, + 130, + 823, + 606, + 773, + 511, + 574, + 98, + 731, + 402, + 862, + 752, + 623, + 991, + 46, + 307, + 347, + 826, + 698, + 658, + 35, + 642, + 770, + 293, + 385, + 50, + 470, + 908, + 177, + 919, + 460, + 783, + 812, + 885, + 144, + 408, + 659, + 741, + 639, + 741, + 234, + 361, + 975, + 361, + 934, + 345, + 46, + 370, + 804, + 357, + 22, + 797, + 24, + 698, + 274, + 669, + 711, + 610, + 104, + 699, + 121, + 724, + 99, + 296, + 870, + 786, + 907, + 517, + 300, + 369, + 115, + 987, + 98, + 420, + 792, + 167, + 589, + 81, + 929, + 901, + 444, + 109, + 382, + 693, + 593, + 875, + 545, + 683, + 487, + 631, + 35, + 664, + 35, + 465, + 381, + 502, + 512, + 213, + 325, + 921, + 435, + 368, + 265, + 897, + 888, + 773, + 659, + 636, + 822, + 940, + 704, + 937, + 990, + 380, + 22, + 806, + 443, + 272, + 226, + 75, + 390, + 701, + 604, + 103, + 834, + 836, + 128, + 776, + 390, + 490, + 761, + 481, + 372, + 204, + 99, + 91, + 22, + 808, + 253, + 230, + 576, + 111, + 530, + 569, + 205, + 79, + 723, + 69, + 129, + 157, + 690, + 663, + 960, + 928, + 549, + 861, + 858, + 688, + 269, + 88, + 740, + 156, + 907, + 39, + 916, + 907, + 334, + 924, + 489, + 523, + 243, + 832, + 196, + 238, + 353, + 1, + 7, + 314, + 127, + 188, + 96, + 15, + 805, + 54, + 9, + 827, + 404, + 908, + 152, + 993, + 739, + 18, + 830, + 225, + 119, + 544, + 559, + 312, + 438, + 641, + 301, + 560, + 392, + 365, + 576, + 955, + 898, + 503, + 118, + 601, + 848, + 464, + 83, + 817, + 190, + 930, + 333, + 675, + 660, + 97, + 975, + 412, + 292, + 419, + 456, + 795, + 937, + 793, + 775, + 168, + 22, + 285, + 446, + 516, + 479, + 419, + 80, + 724, + 440, + 812, + 799, + 215, + 257, + 254, + 998, + 103, + 914, + 559, + 536, + 588, + 833, + 464, + 188, + 548, + 869, + 359, + 478, + 711, + 413, + 236, + 826, + 534, + 811, + 997, + 919, + 179, + 790, + 869, + 958, + 428, + 792, + 503, + 118, + 329, + 350, + 240, + 390, + 989, + 365, + 170, + 270, + 362, + 823, + 277, + 978, + 293, + 777, + 833, + 515, + 336, + 976, + 174, + 532, + 206, + 600, + 236, + 270, + 737, + 513, + 511, + 672, + 679, + 854, + 554, + 295, + 755, + 523, + 932, + 750, + 520, + 450, + 535, + 586, + 41, + 2, + 357, + 349, + 195, + 5, + 421, + 165, + 148, + 341, + 548, + 200, + 620, + 554, + 759, + 518, + 145, + 722, + 932, + 586, + 186, + 189, + 713, + 830, + 193, + 436, + 92, + 883, + 115, + 46, + 257, + 114, + 244, + 303, + 658, + 66, + 395, + 469, + 697, + 430, + 317, + 184, + 224, + 362, + 429, + 493, + 506, + 218, + 593, + 279, + 450, + 567, + 823, + 411, + 889, + 871, + 439, + 366, + 693, + 160, + 602, + 813, + 85, + 824, + 224, + 144, + 721, + 540, + 880, + 444, + 222, + 843, + 704, + 285, + 480, + 71, + 556, + 404, + 959, + 31, + 235, + 826, + 228, + 372, + 477, + 993, + 269, + 254, + 432, + 643, + 380, + 81, + 642, + 794, + 462, + 386, + 625, + 787, + 623, + 528, + 718, + 472, + 82, + 225, + 488, + 488, + 382, + 114, + 741, + 356, + 237, + 434, + 915, + 593, + 334, + 875, + 525, + 846, + 418, + 726, + 633, + 9, + 228, + 131, + 198, + 922, + 681, + 218, + 435, + 803, + 310, + 641, + 258, + 90, + 521, + 538, + 971, + 301, + 904, + 31, + 805, + 745, + 702, + 285, + 511, + 591, + 404, + 739, + 157, + 12, + 212, + 69, + 478, + 627, + 720, + 177, + 290, + 417, + 585, + 965, + 881, + 508, + 92, + 443, + 655, + 217, + 758, + 203, + 491, + 497, + 753, + 347, + 582, + 15, + 142, + 301, + 481, + 728, + 242, + 325, + 272, + 127, + 694, + 174, + 851, + 309, + 486, + 520, + 498, + 794, + 155, + 671, + 872, + 698, + 579, + 771, + 665, + 591, + 806, + 984, + 37, + 886, + 580, + 305, + 103, + 585, + 234, + 918, + 62, + 857, + 548, + 295, + 618, + 901, + 12, + 20, + 59, + 291, + 376, + 299, + 339, + 10, + 586, + 540, + 972, + 682, + 473, + 340, + 820, + 752, + 332, + 93, + 973, + 434, + 39, + 526, + 841, + 955, + 270, + 116, + 778, + 140, + 878, + 509, + 760, + 216, + 851, + 836, + 475, + 33, + 884, + 382, + 264, + 324, + 787, + 640, + 793, + 686, + 280, + 115, + 461, + 258, + 5, + 461, + 527, + 672, + 196, + 813, + 585, + 387, + 413, + 339, + 113, + 767, + 564, + 10, + 332, + 500, + 311, + 282, + 143, + 108, + 29, + 966, + 13, + 837, + 241, + 431, + 51, + 564, + 414, + 835, + 855, + 71, + 885, + 990, + 86, + 340, + 225, + 179, + 12, + 795, + 628, + 615, + 167, + 756, + 274, + 154, + 484, + 607, + 155, + 522, + 699, + 407, + 582, + 710, + 535, + 153, + 417, + 349, + 37, + 743, + 966, + 840, + 230, + 83, + 759, + 610, + 31, + 962, + 561, + 19, + 702, + 56, + 838, + 235, + 47, + 393, + 700, + 873, + 548, + 419, + 508, + 320, + 91, + 70, + 693, + 587, + 889, + 716, + 7, + 213, + 628, + 603, + 411, + 351, + 79, + 220, + 823, + 919, + 430, + 423, + 336, + 265, + 161, + 357, + 184, + 821, + 598, + 529, + 663, + 197, + 655, + 620, + 749, + 488, + 130, + 45, + 861, + 912, + 383, + 273, + 357, + 285, + 244, + 860, + 867, + 156, + 540, + 428, + 250, + 383, + 327, + 125, + 170, + 226, + 163, + 295, + 901, + 703, + 992, + 625, + 805, + 143, + 416, + 488, + 83, + 838, + 901, + 832, + 722, + 33, + 565, + 957, + 386, + 255, + 529, + 22, + 385, + 641, + 3, + 975, + 43, + 360, + 374, + 26, + 50, + 513, + 623, + 498, + 962, + 47, + 824, + 955, + 947, + 877, + 718, + 305, + 433, + 838, + 16, + 971, + 56, + 315, + 40, + 251, + 32, + 776, + 910, + 502, + 872, + 404, + 24, + 266, + 655, + 444, + 38, + 433, + 166, + 251, + 737, + 585, + 802, + 879, + 316, + 909, + 85, + 530, + 162, + 819, + 420, + 995, + 655, + 546, + 83, + 666, + 491, + 224, + 436, + 981, + 473, + 206, + 574, + 977, + 573, + 905, + 370, + 928, + 524, + 974, + 177, + 667, + 662, + 121, + 514, + 916, + 830, + 801, + 455, + 43, + 986, + 364, + 479, + 667, + 157, + 546, + 927, + 120, + 882, + 184, + 769, + 480, + 892, + 324, + 822, + 947, + 608, + 704, + 503, + 888, + 28, + 741, + 735, + 189, + 673, + 549, + 13, + 594, + 331, + 965, + 430, + 323, + 625, + 845, + 487, + 704, + 232, + 774, + 239, + 323, + 458, + 415, + 843, + 822, + 500, + 699, + 940, + 198, + 205, + 274, + 723, + 728, + 817, + 307, + 500, + 942, + 294, + 475, + 840, + 245, + 863, + 692, + 884, + 15, + 43, + 589, + 639, + 584, + 66, + 194, + 473, + 487, + 382, + 984, + 855, + 19, + 764, + 751, + 420, + 783, + 774, + 692, + 537, + 467, + 185, + 506, + 348, + 617, + 961, + 109, + 118, + 833, + 725, + 706, + 47, + 641, + 69, + 382, + 892, + 613, + 168, + 546, + 72, + 287, + 658, + 280, + 961, + 11, + 786, + 468, + 65, + 25, + 145, + 746, + 846, + 911, + 574, + 392, + 779, + 746, + 711, + 935, + 796, + 482, + 506, + 772, + 873, + 712, + 546, + 93, + 546, + 28, + 757, + 858, + 313, + 663, + 914, + 858, + 508, + 945, + 912, + 223, + 945, + 200, + 313, + 367, + 309, + 487, + 637, + 824, + 869, + 534, + 699, + 79, + 510, + 860, + 34, + 420, + 255, + 493, + 790, + 310, + 444, + 113, + 719, + 695, + 358, + 148, + 947, + 483, + 821, + 59, + 835, + 434, + 903, + 41, + 634, + 592, + 594, + 150, + 410, + 598, + 14, + 961, + 97, + 942, + 79, + 466, + 17, + 112, + 830, + 751, + 454, + 84, + 374, + 264, + 624, + 963, + 372, + 81, + 536, + 775, + 159, + 372, + 174, + 707, + 399, + 984, + 57, + 648, + 923, + 258, + 417, + 86, + 978, + 982, + 414, + 147, + 403, + 610, + 251, + 571, + 656, + 151, + 156, + 812, + 621, + 669, + 21, + 148, + 31, + 74, + 77, + 49, + 175, + 263, + 527, + 797, + 797, + 775, + 553, + 981, + 898, + 725, + 357, + 116, + 678, + 297, + 357, + 496, + 159, + 750, + 979, + 145, + 331, + 691, + 711, + 921, + 829, + 284, + 217, + 581, + 203, + 124, + 670, + 62, + 544, + 289, + 240, + 308, + 333, + 829, + 758, + 48, + 339, + 468, + 795, + 844, + 212, + 623, + 954, + 946, + 951, + 531, + 119, + 806, + 153, + 382, + 632, + 472, + 665, + 241, + 794, + 786, + 436, + 323, + 840, + 594, + 95, + 175, + 134, + 796, + 940, + 747, + 997, + 360, + 755, + 467, + 711, + 275, + 449, + 291, + 217, + 677, + 446, + 422, + 225, + 302, + 8, + 957, + 836, + 901, + 37, + 919, + 426, + 623, + 94, + 105, + 654, + 752, + 464, + 323, + 877, + 954, + 228, + 375, + 752, + 743, + 349, + 350, + 181, + 532, + 97, + 777, + 935, + 148, + 433, + 153, + 973, + 525, + 131, + 947, + 752, + 692, + 927, + 84, + 270, + 152, + 62, + 676, + 772, + 301, + 542, + 874, + 841, + 976, + 442, + 540, + 397, + 922, + 430, + 729, + 328, + 779, + 624, + 430, + 783, + 852, + 691, + 657, + 553, + 216, + 941, + 965, + 248, + 656, + 952, + 514, + 250, + 890, + 502, + 392, + 951, + 357, + 453, + 744, + 557, + 940, + 738, + 207, + 960, + 612, + 410, + 688, + 517, + 612, + 723, + 773, + 269, + 176, + 305, + 210, + 455, + 178, + 764, + 414, + 918, + 958, + 727, + 54, + 74, + 191, + 371, + 376, + 770, + 275, + 82, + 913, + 527, + 249, + 800, + 675, + 387, + 810, + 388, + 503, + 240, + 491, + 28, + 491, + 110, + 133, + 734, + 720, + 476, + 943, + 315, + 810, + 672, + 761, + 421, + 269, + 449, + 677, + 98, + 912, + 873, + 36, + 313, + 585, + 401, + 35, + 248, + 301, + 668, + 136, + 88, + 514, + 765, + 68, + 160, + 267, + 325, + 663, + 511, + 927, + 524, + 243, + 22, + 126, + 193, + 846, + 233, + 289, + 676, + 783, + 957, + 845, + 673, + 692, + 285, + 763, + 575, + 742, + 791, + 744, + 630, + 650, + 435, + 748, + 128, + 612, + 892, + 729, + 230, + 818, + 271, + 634, + 875, + 930, + 576, + 333, + 589, + 849, + 116, + 143, + 383, + 705, + 321, + 218, + 620, + 142, + 602, + 477, + 31, + 550, + 407, + 552, + 766, + 851, + 17, + 123, + 828, + 678, + 986, + 66, + 629, + 393, + 595, + 319, + 404, + 352, + 95, + 140, + 329, + 357, + 197, + 571, + 46, + 8, + 251, + 628, + 0, + 327, + 965, + 938, + 187, + 95, + 925, + 514, + 566, + 95, + 301, + 153, + 166, + 526, + 648, + 41, + 663, + 145, + 534, + 712, + 452, + 770, + 326, + 518, + 767, + 743, + 726, + 560, + 301, + 198, + 253, + 702, + 177, + 619, + 698, + 645, + 696, + 622, + 686, + 401, + 644, + 124, + 276, + 707, + 746, + 136, + 48, + 275, + 263, + 285, + 301, + 59, + 367, + 802, + 225, + 719, + 334, + 91, + 899, + 836, + 39, + 801, + 797, + 52, + 769, + 941, + 404, + 667, + 842, + 726, + 652, + 538, + 68, + 780, + 305, + 694, + 212, + 208, + 576, + 35, + 505, + 26, + 939, + 402, + 977, + 342, + 4, + 436, + 287, + 861, + 465, + 898, + 593, + 691, + 341, + 595, + 526, + 722, + 464, + 273, + 301, + 51, + 148, + 888, + 16, + 548, + 760, + 252, + 855, + 690, + 754, + 886, + 625, + 404, + 861, + 546, + 558, + 201, + 715, + 800, + 24, + 464, + 763, + 181, + 111, + 42, + 899, + 398, + 995, + 166, + 769, + 737, + 196, + 1, + 99, + 136, + 62, + 335, + 351, + 346, + 289, + 899, + 124, + 607, + 468, + 686, + 775, + 991, + 561, + 335, + 250, + 880, + 252, + 56, + 390, + 363, + 965, + 233, + 98, + 954, + 669, + 596, + 836, + 912, + 645, + 516, + 891, + 340, + 529, + 722, + 391, + 580, + 212, + 501, + 961, + 154, + 117, + 877, + 956, + 245, + 543, + 749, + 229, + 959, + 415, + 3, + 886, + 430, + 294, + 501, + 957, + 218, + 686, + 825, + 508, + 746, + 186, + 624, + 450, + 123, + 310, + 161, + 775, + 581, + 541, + 630, + 788, + 652, + 849, + 101, + 81, + 872, + 316, + 621, + 8, + 17, + 934, + 555, + 326, + 252, + 104, + 720, + 706, + 130, + 364, + 56, + 558, + 83, + 928, + 538, + 227, + 366, + 463, + 527, + 769, + 19, + 815, + 801, + 899, + 72, + 970, + 25, + 993, + 340, + 724, + 765, + 167, + 347, + 803, + 148, + 363, + 967, + 325, + 927, + 588, + 791, + 579, + 647, + 245, + 767, + 522, + 989, + 49, + 619, + 794, + 385, + 865, + 665, + 136, + 426, + 849, + 354, + 982, + 870, + 328, + 181, + 922, + 304, + 822, + 665, + 956, + 324, + 168, + 412, + 785, + 919, + 486, + 340, + 677, + 751, + 646, + 857, + 629, + 108, + 650, + 366, + 931, + 195, + 684, + 498, + 266, + 669, + 73, + 103, + 512, + 456, + 187, + 190, + 356, + 146, + 361, + 597, + 277, + 261, + 993, + 479, + 850, + 883, + 950, + 622, + 192, + 351, + 293, + 375, + 86, + 141, + 824, + 714, + 492, + 48, + 589, + 564, + 266, + 359, + 425, + 75, + 797, + 538, + 550, + 885, + 404, + 863, + 468, + 301, + 321, + 475, + 876, + 916, + 666, + 927, + 31, + 256, + 839, + 177, + 61, + 875, + 23, + 348, + 257, + 939, + 931, + 533, + 473, + 865, + 108, + 130, + 772, + 296, + 768, + 721, + 908, + 108, + 727, + 659, + 811, + 821, + 971, + 652, + 546, + 727, + 678, + 767, + 229, + 606, + 503, + 298, + 186, + 539, + 4, + 203, + 752, + 630, + 179, + 182, + 476, + 366, + 651, + 924, + 38, + 925, + 37, + 177, + 658, + 489, + 816, + 322, + 963, + 928, + 818, + 169, + 602, + 403, + 506, + 127, + 844, + 749, + 674, + 845, + 529, + 865, + 635, + 791, + 776, + 334, + 136, + 342, + 593, + 512, + 660, + 640, + 787, + 139, + 544, + 181, + 43, + 46, + 413, + 337, + 854, + 986, + 815, + 121, + 877, + 294, + 218, + 4, + 136, + 225, + 766, + 992, + 910, + 530, + 646, + 213, + 695, + 271, + 967, + 986, + 628, + 777, + 180, + 866, + 599, + 664, + 46, + 994, + 396, + 56, + 256, + 739, + 481, + 608, + 360, + 134, + 970, + 282, + 898, + 417, + 948, + 956, + 230, + 884, + 748, + 74, + 938, + 224, + 920, + 974, + 475, + 405, + 442, + 630, + 596, + 118, + 398, + 439, + 969, + 188, + 169, + 251, + 630, + 835, + 480, + 557, + 904, + 461, + 371, + 885, + 197, + 305, + 678, + 12, + 663, + 960, + 311, + 877, + 747, + 20, + 271, + 622, + 48, + 621, + 135, + 59, + 179, + 377, + 684, + 861, + 760, + 38, + 780, + 91, + 18, + 23, + 432, + 37, + 443, + 450, + 508, + 193, + 960, + 986, + 761, + 605, + 788, + 86, + 436, + 23, + 581, + 605, + 128, + 84, + 979, + 732, + 230, + 787, + 836, + 261, + 677, + 117, + 292, + 477, + 388, + 20, + 962, + 707, + 979, + 933, + 662, + 112, + 234, + 771, + 167, + 31, + 673, + 42, + 705, + 675, + 151, + 452, + 875, + 655, + 399, + 59, + 702, + 502, + 444, + 892, + 290, + 856, + 53, + 260, + 19, + 221, + 987, + 330, + 80, + 665, + 551, + 377, + 540, + 188, + 920, + 680, + 133, + 77, + 466, + 439, + 258, + 570, + 659, + 56, + 10, + 615, + 504, + 336, + 655, + 720, + 156, + 289, + 354, + 637, + 184, + 853, + 944, + 177, + 973, + 177, + 537, + 934, + 78, + 267, + 209, + 898, + 115, + 986, + 920, + 926, + 393, + 217, + 204, + 312, + 989, + 655, + 214, + 47, + 231, + 278, + 866, + 734, + 707, + 605, + 208, + 232, + 506, + 116, + 383, + 662, + 151, + 92, + 785, + 431, + 614, + 585, + 682, + 781, + 343, + 590, + 458, + 232, + 360, + 187, + 18, + 769, + 704, + 620, + 67, + 109, + 88, + 353, + 401, + 228, + 508, + 406, + 255, + 989, + 151, + 702, + 277, + 376, + 381, + 409, + 932, + 31, + 761, + 783, + 233, + 154, + 871, + 55, + 648, + 5, + 12, + 465, + 96, + 904, + 169, + 325, + 428, + 572, + 47, + 78, + 258, + 525, + 276, + 502, + 972, + 488, + 763, + 798, + 973, + 186, + 490, + 362, + 205, + 154, + 245, + 784, + 493, + 76, + 975, + 459, + 598, + 227, + 161, + 752, + 243, + 858, + 931, + 996, + 543, + 488, + 560, + 240, + 49, + 318, + 374, + 914, + 52, + 693, + 762, + 329, + 691, + 193, + 122, + 925, + 577, + 748, + 236, + 8, + 591, + 640, + 61, + 77, + 295, + 117, + 323, + 732, + 493, + 811, + 67, + 694, + 158, + 589, + 247, + 115, + 184, + 682, + 927, + 918, + 353, + 217, + 904, + 834, + 107, + 728, + 683, + 908, + 596, + 721, + 44, + 412, + 780, + 882, + 682, + 497, + 832, + 559, + 126, + 303, + 100, + 214, + 829, + 344, + 654, + 679, + 336, + 148, + 213, + 982, + 859, + 558, + 855, + 999, + 698, + 38, + 490, + 340, + 846, + 852, + 26, + 942, + 575, + 383, + 1, + 198, + 836, + 570, + 893, + 950, + 7, + 527, + 628, + 753, + 660, + 180, + 354, + 819, + 775, + 271, + 187, + 374, + 532, + 374, + 900 +}; +const int idx[10004] = { + 13, + 111, + 124, + 218, + 316, + 502, + 34, + 119, + 167, + 180, + 186, + 346, + 511, + 543, + 755, + 788, + 833, + 929, + 46, + 109, + 154, + 220, + 248, + 448, + 509, + 517, + 530, + 557, + 639, + 643, + 720, + 137, + 189, + 424, + 480, + 570, + 642, + 849, + 896, + 968, + 117, + 136, + 208, + 248, + 347, + 410, + 433, + 515, + 747, + 144, + 148, + 375, + 405, + 444, + 532, + 788, + 808, + 987, + 110, + 112, + 403, + 415, + 596, + 612, + 669, + 794, + 851, + 80, + 285, + 288, + 433, + 500, + 628, + 982, + 999, + 57, + 237, + 252, + 304, + 469, + 600, + 609, + 621, + 741, + 798, + 251, + 322, + 369, + 374, + 376, + 507, + 623, + 666, + 669, + 677, + 707, + 823, + 919, + 63, + 187, + 266, + 360, + 396, + 439, + 459, + 526, + 623, + 804, + 857, + 881, + 948, + 160, + 165, + 226, + 446, + 538, + 585, + 624, + 866, + 975, + 979, + 18, + 54, + 151, + 180, + 230, + 298, + 480, + 678, + 688, + 696, + 742, + 757, + 889, + 979, + 100, + 245, + 513, + 925, + 162, + 413, + 427, + 588, + 645, + 807, + 853, + 194, + 313, + 339, + 466, + 539, + 581, + 732, + 791, + 832, + 927, + 954, + 962, + 966, + 42, + 45, + 138, + 141, + 239, + 338, + 584, + 696, + 912, + 929, + 269, + 352, + 443, + 463, + 896, + 962, + 60, + 92, + 273, + 568, + 591, + 851, + 38, + 77, + 281, + 362, + 544, + 614, + 651, + 836, + 871, + 873, + 45, + 61, + 140, + 153, + 234, + 439, + 472, + 509, + 588, + 675, + 760, + 777, + 178, + 198, + 248, + 517, + 566, + 679, + 700, + 289, + 455, + 602, + 695, + 711, + 853, + 923, + 179, + 199, + 214, + 280, + 343, + 405, + 435, + 504, + 898, + 910, + 939, + 130, + 219, + 296, + 445, + 508, + 634, + 763, + 918, + 922, + 978, + 87, + 285, + 614, + 667, + 679, + 739, + 834, + 192, + 347, + 549, + 557, + 724, + 764, + 928, + 929, + 976, + 17, + 283, + 413, + 429, + 612, + 683, + 707, + 725, + 743, + 833, + 856, + 165, + 267, + 304, + 361, + 397, + 410, + 570, + 683, + 766, + 788, + 849, + 882, + 885, + 30, + 58, + 221, + 254, + 453, + 457, + 470, + 674, + 687, + 745, + 809, + 819, + 55, + 121, + 231, + 538, + 604, + 718, + 768, + 960, + 71, + 77, + 104, + 186, + 205, + 234, + 456, + 467, + 579, + 682, + 733, + 767, + 947, + 66, + 86, + 157, + 290, + 422, + 441, + 473, + 560, + 607, + 640, + 682, + 888, + 37, + 296, + 439, + 629, + 642, + 733, + 824, + 917, + 969, + 4, + 25, + 580, + 622, + 636, + 666, + 672, + 732, + 802, + 921, + 943, + 130, + 194, + 245, + 273, + 323, + 344, + 603, + 740, + 795, + 974, + 189, + 422, + 445, + 446, + 831, + 905, + 912, + 36, + 60, + 218, + 428, + 455, + 627, + 743, + 796, + 801, + 903, + 136, + 152, + 166, + 352, + 364, + 369, + 382, + 466, + 521, + 577, + 665, + 746, + 910, + 294, + 345, + 445, + 645, + 686, + 718, + 757, + 762, + 796, + 817, + 832, + 836, + 997, + 127, + 258, + 259, + 449, + 541, + 643, + 665, + 756, + 817, + 854, + 870, + 89, + 134, + 188, + 362, + 408, + 531, + 566, + 816, + 127, + 170, + 302, + 336, + 426, + 434, + 601, + 708, + 774, + 780, + 900, + 935, + 377, + 469, + 618, + 650, + 790, + 809, + 78, + 253, + 340, + 382, + 586, + 673, + 684, + 282, + 354, + 363, + 398, + 636, + 655, + 729, + 885, + 911, + 10, + 175, + 195, + 229, + 273, + 339, + 380, + 531, + 660, + 681, + 794, + 800, + 236, + 416, + 646, + 679, + 685, + 885, + 7, + 116, + 299, + 481, + 702, + 747, + 922, + 64, + 153, + 374, + 391, + 532, + 558, + 602, + 655, + 662, + 804, + 847, + 867, + 998, + 45, + 66, + 97, + 106, + 236, + 240, + 247, + 453, + 641, + 646, + 711, + 712, + 715, + 855, + 906, + 923, + 37, + 65, + 122, + 331, + 578, + 589, + 610, + 139, + 293, + 354, + 395, + 430, + 486, + 589, + 614, + 661, + 699, + 846, + 910, + 18, + 53, + 78, + 234, + 296, + 690, + 828, + 923, + 87, + 115, + 156, + 161, + 173, + 201, + 400, + 474, + 501, + 526, + 782, + 861, + 63, + 271, + 427, + 552, + 590, + 657, + 920, + 41, + 194, + 281, + 571, + 640, + 681, + 696, + 301, + 306, + 514, + 553, + 560, + 641, + 683, + 762, + 812, + 818, + 876, + 904, + 932, + 978, + 38, + 62, + 98, + 103, + 370, + 390, + 531, + 559, + 693, + 813, + 924, + 943, + 955, + 973, + 13, + 40, + 62, + 75, + 396, + 419, + 615, + 773, + 968, + 989, + 150, + 183, + 241, + 261, + 407, + 476, + 492, + 524, + 541, + 863, + 994, + 156, + 195, + 197, + 278, + 457, + 467, + 610, + 621, + 956, + 49, + 343, + 454, + 477, + 572, + 600, + 700, + 759, + 804, + 923, + 92, + 194, + 455, + 842, + 968, + 160, + 211, + 461, + 463, + 467, + 622, + 854, + 972, + 333, + 469, + 563, + 571, + 639, + 838, + 977, + 18, + 105, + 133, + 258, + 572, + 720, + 804, + 851, + 930, + 19, + 139, + 158, + 301, + 354, + 407, + 589, + 726, + 846, + 904, + 26, + 54, + 155, + 212, + 216, + 418, + 534, + 647, + 792, + 862, + 889, + 101, + 216, + 228, + 396, + 470, + 473, + 592, + 706, + 799, + 913, + 922, + 98, + 324, + 524, + 672, + 685, + 856, + 213, + 224, + 228, + 300, + 395, + 604, + 631, + 651, + 835, + 944, + 289, + 574, + 613, + 657, + 671, + 748, + 763, + 768, + 815, + 843, + 908, + 74, + 79, + 203, + 218, + 245, + 249, + 390, + 548, + 616, + 804, + 986, + 49, + 196, + 585, + 591, + 608, + 728, + 750, + 810, + 836, + 920, + 980, + 38, + 41, + 93, + 94, + 320, + 360, + 502, + 555, + 729, + 742, + 814, + 984, + 89, + 131, + 499, + 677, + 825, + 846, + 919, + 966, + 17, + 37, + 121, + 168, + 560, + 585, + 691, + 788, + 892, + 925, + 951, + 995, + 13, + 69, + 124, + 229, + 308, + 554, + 643, + 668, + 717, + 747, + 813, + 814, + 864, + 298, + 327, + 386, + 425, + 586, + 600, + 725, + 730, + 832, + 12, + 38, + 94, + 150, + 175, + 501, + 538, + 552, + 571, + 606, + 624, + 650, + 686, + 728, + 157, + 605, + 630, + 713, + 784, + 850, + 954, + 181, + 234, + 610, + 612, + 661, + 663, + 677, + 688, + 726, + 809, + 818, + 67, + 77, + 164, + 193, + 214, + 345, + 352, + 551, + 696, + 919, + 994, + 12, + 311, + 404, + 454, + 473, + 521, + 581, + 651, + 677, + 717, + 850, + 873, + 880, + 892, + 945, + 54, + 138, + 210, + 219, + 248, + 413, + 480, + 491, + 639, + 652, + 773, + 807, + 824, + 962, + 79, + 211, + 499, + 560, + 561, + 759, + 774, + 800, + 865, + 35, + 146, + 619, + 746, + 754, + 81, + 237, + 258, + 388, + 477, + 658, + 704, + 712, + 781, + 109, + 720, + 758, + 98, + 209, + 252, + 311, + 410, + 532, + 611, + 656, + 722, + 772, + 822, + 828, + 912, + 980, + 95, + 107, + 167, + 287, + 289, + 303, + 441, + 446, + 580, + 600, + 630, + 632, + 658, + 682, + 847, + 92, + 137, + 177, + 238, + 262, + 324, + 438, + 479, + 534, + 539, + 689, + 846, + 956, + 962, + 200, + 496, + 521, + 656, + 714, + 785, + 814, + 857, + 184, + 204, + 455, + 702, + 754, + 803, + 887, + 928, + 993, + 42, + 51, + 189, + 204, + 358, + 572, + 601, + 665, + 867, + 71, + 108, + 208, + 243, + 263, + 314, + 359, + 418, + 482, + 556, + 680, + 945, + 958, + 964, + 97, + 200, + 202, + 223, + 230, + 428, + 447, + 537, + 574, + 635, + 663, + 728, + 737, + 858, + 861, + 930, + 71, + 84, + 85, + 196, + 199, + 242, + 513, + 761, + 48, + 98, + 127, + 194, + 233, + 283, + 334, + 420, + 627, + 632, + 931, + 34, + 82, + 176, + 197, + 217, + 235, + 237, + 358, + 462, + 947, + 10, + 178, + 265, + 350, + 396, + 468, + 539, + 586, + 612, + 628, + 644, + 791, + 40, + 234, + 292, + 299, + 375, + 396, + 410, + 429, + 728, + 36, + 360, + 475, + 562, + 962, + 5, + 60, + 169, + 509, + 558, + 594, + 613, + 648, + 654, + 726, + 769, + 773, + 777, + 40, + 49, + 403, + 446, + 524, + 548, + 730, + 774, + 938, + 978, + 997, + 221, + 248, + 407, + 447, + 585, + 756, + 824, + 894, + 972, + 121, + 189, + 364, + 537, + 563, + 179, + 328, + 344, + 692, + 711, + 750, + 760, + 780, + 810, + 929, + 942, + 106, + 336, + 551, + 616, + 640, + 654, + 726, + 890, + 74, + 200, + 233, + 254, + 382, + 396, + 895, + 971, + 283, + 614, + 898, + 87, + 122, + 172, + 255, + 324, + 383, + 498, + 525, + 699, + 817, + 825, + 3, + 41, + 104, + 280, + 399, + 617, + 641, + 769, + 789, + 817, + 891, + 937, + 143, + 175, + 185, + 217, + 222, + 362, + 391, + 465, + 515, + 544, + 818, + 868, + 35, + 44, + 122, + 235, + 345, + 415, + 479, + 569, + 575, + 740, + 765, + 867, + 967, + 78, + 107, + 265, + 358, + 524, + 646, + 716, + 720, + 840, + 76, + 77, + 353, + 406, + 533, + 648, + 726, + 733, + 906, + 979, + 65, + 133, + 182, + 187, + 191, + 424, + 430, + 520, + 674, + 776, + 945, + 975, + 18, + 242, + 393, + 458, + 468, + 530, + 599, + 717, + 933, + 278, + 297, + 465, + 476, + 579, + 591, + 633, + 643, + 937, + 271, + 481, + 618, + 890, + 5, + 126, + 171, + 192, + 209, + 259, + 367, + 840, + 861, + 6, + 26, + 47, + 90, + 225, + 239, + 385, + 577, + 782, + 795, + 797, + 893, + 76, + 82, + 309, + 348, + 450, + 583, + 677, + 696, + 752, + 785, + 800, + 991, + 2, + 191, + 211, + 279, + 280, + 556, + 591, + 774, + 785, + 822, + 913, + 34, + 117, + 159, + 204, + 266, + 418, + 547, + 565, + 962, + 992, + 33, + 72, + 140, + 141, + 157, + 254, + 513, + 558, + 643, + 695, + 779, + 791, + 882, + 978, + 13, + 53, + 65, + 479, + 513, + 674, + 687, + 711, + 785, + 811, + 830, + 4, + 5, + 9, + 34, + 77, + 137, + 265, + 270, + 542, + 552, + 622, + 632, + 634, + 647, + 783, + 895, + 951, + 995, + 89, + 113, + 174, + 225, + 231, + 258, + 294, + 347, + 383, + 414, + 444, + 463, + 467, + 493, + 535, + 612, + 688, + 107, + 111, + 213, + 238, + 494, + 555, + 572, + 676, + 40, + 50, + 59, + 119, + 291, + 365, + 416, + 565, + 607, + 613, + 631, + 902, + 908, + 998, + 63, + 495, + 534, + 581, + 601, + 694, + 719, + 731, + 790, + 969, + 176, + 262, + 481, + 545, + 694, + 737, + 853, + 202, + 267, + 269, + 302, + 466, + 727, + 786, + 816, + 858, + 923, + 14, + 241, + 387, + 416, + 468, + 501, + 513, + 599, + 48, + 157, + 318, + 426, + 589, + 632, + 871, + 882, + 87, + 444, + 486, + 558, + 618, + 773, + 794, + 73, + 116, + 199, + 229, + 233, + 255, + 360, + 400, + 425, + 468, + 474, + 540, + 589, + 786, + 834, + 868, + 888, + 85, + 112, + 162, + 185, + 316, + 331, + 346, + 410, + 611, + 729, + 798, + 863, + 234, + 591, + 637, + 933, + 8, + 12, + 32, + 43, + 101, + 339, + 436, + 708, + 88, + 111, + 115, + 790, + 841, + 935, + 976, + 12, + 175, + 245, + 447, + 449, + 548, + 581, + 652, + 743, + 763, + 773, + 776, + 828, + 951, + 58, + 62, + 68, + 277, + 297, + 401, + 418, + 460, + 482, + 561, + 656, + 734, + 812, + 818, + 837, + 861, + 118, + 192, + 254, + 267, + 270, + 276, + 347, + 463, + 509, + 514, + 714, + 717, + 788, + 905, + 924, + 100, + 256, + 334, + 335, + 465, + 627, + 803, + 815, + 884, + 996, + 15, + 140, + 172, + 197, + 227, + 300, + 310, + 466, + 530, + 560, + 567, + 784, + 860, + 15, + 108, + 132, + 188, + 310, + 621, + 838, + 839, + 988, + 8, + 130, + 289, + 462, + 472, + 549, + 557, + 561, + 643, + 753, + 755, + 841, + 955, + 40, + 325, + 334, + 371, + 375, + 417, + 573, + 872, + 921, + 989, + 25, + 94, + 138, + 217, + 312, + 370, + 528, + 585, + 603, + 630, + 729, + 803, + 810, + 73, + 424, + 570, + 624, + 630, + 642, + 671, + 697, + 873, + 935, + 987, + 94, + 174, + 318, + 415, + 507, + 516, + 676, + 779, + 821, + 941, + 973, + 73, + 78, + 97, + 148, + 237, + 269, + 293, + 304, + 483, + 575, + 591, + 916, + 64, + 228, + 238, + 269, + 287, + 400, + 633, + 749, + 114, + 173, + 311, + 400, + 454, + 634, + 644, + 726, + 731, + 860, + 921, + 224, + 262, + 367, + 401, + 504, + 589, + 630, + 727, + 848, + 161, + 392, + 401, + 410, + 530, + 548, + 787, + 894, + 989, + 121, + 372, + 437, + 676, + 929, + 976, + 980, + 111, + 365, + 706, + 954, + 82, + 379, + 563, + 728, + 949, + 124, + 227, + 540, + 671, + 767, + 861, + 484, + 678, + 840, + 864, + 916, + 304, + 348, + 502, + 599, + 617, + 657, + 82, + 149, + 163, + 216, + 229, + 449, + 612, + 620, + 636, + 673, + 679, + 756, + 802, + 859, + 953, + 142, + 176, + 215, + 273, + 335, + 415, + 586, + 658, + 682, + 764, + 865, + 896, + 923, + 76, + 283, + 284, + 464, + 481, + 588, + 625, + 742, + 790, + 947, + 119, + 186, + 309, + 320, + 404, + 407, + 440, + 496, + 692, + 853, + 884, + 901, + 980, + 990, + 345, + 493, + 503, + 691, + 738, + 743, + 890, + 929, + 993, + 998, + 45, + 272, + 313, + 350, + 384, + 452, + 499, + 569, + 248, + 346, + 515, + 676, + 751, + 755, + 775, + 778, + 17, + 491, + 522, + 538, + 622, + 672, + 919, + 961, + 54, + 126, + 207, + 301, + 375, + 447, + 500, + 599, + 651, + 683, + 890, + 947, + 93, + 317, + 482, + 656, + 774, + 865, + 904, + 96, + 224, + 260, + 313, + 340, + 372, + 410, + 437, + 452, + 511, + 512, + 718, + 911, + 77, + 100, + 176, + 232, + 418, + 661, + 689, + 805, + 956, + 51, + 262, + 280, + 352, + 380, + 413, + 461, + 538, + 616, + 769, + 783, + 821, + 855, + 946, + 956, + 73, + 169, + 238, + 246, + 319, + 391, + 392, + 669, + 769, + 770, + 786, + 946, + 415, + 453, + 590, + 628, + 630, + 684, + 852, + 52, + 258, + 318, + 322, + 535, + 545, + 561, + 610, + 621, + 662, + 687, + 839, + 87, + 98, + 181, + 269, + 454, + 666, + 667, + 684, + 891, + 142, + 270, + 300, + 396, + 398, + 443, + 652, + 677, + 821, + 0, + 77, + 85, + 163, + 180, + 281, + 470, + 491, + 665, + 694, + 760, + 899, + 992, + 32, + 51, + 73, + 75, + 157, + 216, + 224, + 301, + 376, + 433, + 536, + 612, + 703, + 11, + 228, + 456, + 471, + 543, + 627, + 650, + 873, + 898, + 144, + 258, + 597, + 796, + 36, + 394, + 486, + 492, + 497, + 681, + 710, + 963, + 522, + 582, + 709, + 769, + 775, + 987, + 80, + 129, + 156, + 281, + 339, + 346, + 402, + 777, + 789, + 812, + 822, + 859, + 108, + 127, + 207, + 293, + 337, + 385, + 415, + 479, + 509, + 539, + 746, + 785, + 929, + 934, + 943, + 27, + 52, + 55, + 67, + 124, + 298, + 381, + 625, + 690, + 741, + 975, + 26, + 112, + 127, + 152, + 225, + 513, + 534, + 672, + 734, + 766, + 968, + 26, + 87, + 123, + 198, + 266, + 279, + 410, + 445, + 612, + 791, + 807, + 946, + 996, + 287, + 417, + 458, + 515, + 562, + 576, + 725, + 750, + 779, + 92, + 136, + 168, + 174, + 213, + 300, + 392, + 541, + 602, + 618, + 729, + 761, + 960, + 2, + 340, + 378, + 414, + 441, + 575, + 632, + 731, + 791, + 870, + 875, + 2, + 176, + 241, + 307, + 436, + 707, + 912, + 929, + 962, + 232, + 300, + 389, + 397, + 400, + 483, + 547, + 628, + 766, + 781, + 783, + 833, + 981, + 193, + 200, + 224, + 681, + 739, + 750, + 25, + 404, + 409, + 420, + 511, + 621, + 623, + 857, + 909, + 144, + 179, + 221, + 223, + 400, + 413, + 483, + 507, + 516, + 609, + 806, + 869, + 995, + 1, + 194, + 270, + 433, + 450, + 549, + 591, + 794, + 872, + 106, + 125, + 136, + 207, + 239, + 432, + 529, + 588, + 634, + 869, + 936, + 61, + 70, + 156, + 171, + 172, + 272, + 582, + 594, + 943, + 310, + 445, + 589, + 752, + 769, + 775, + 778, + 901, + 76, + 130, + 151, + 165, + 236, + 473, + 503, + 558, + 794, + 804, + 945, + 953, + 971, + 2, + 4, + 44, + 150, + 167, + 190, + 209, + 658, + 747, + 934, + 75, + 156, + 315, + 528, + 697, + 760, + 156, + 165, + 232, + 644, + 680, + 686, + 771, + 846, + 100, + 197, + 377, + 497, + 658, + 674, + 685, + 716, + 759, + 890, + 1, + 18, + 104, + 318, + 462, + 643, + 793, + 930, + 999, + 104, + 112, + 141, + 231, + 255, + 414, + 419, + 651, + 754, + 900, + 914, + 965, + 969, + 43, + 275, + 386, + 410, + 419, + 480, + 607, + 649, + 688, + 763, + 850, + 149, + 184, + 326, + 434, + 485, + 599, + 618, + 786, + 915, + 54, + 113, + 195, + 358, + 383, + 489, + 564, + 788, + 840, + 887, + 219, + 232, + 351, + 373, + 691, + 777, + 42, + 58, + 124, + 272, + 297, + 571, + 583, + 590, + 618, + 734, + 867, + 60, + 90, + 174, + 217, + 339, + 423, + 531, + 640, + 707, + 767, + 798, + 896, + 981, + 208, + 304, + 402, + 657, + 959, + 197, + 242, + 348, + 373, + 409, + 449, + 489, + 529, + 545, + 577, + 812, + 844, + 853, + 956, + 114, + 128, + 137, + 254, + 386, + 401, + 424, + 425, + 470, + 509, + 735, + 835, + 872, + 899, + 29, + 49, + 189, + 201, + 495, + 517, + 598, + 669, + 712, + 734, + 794, + 903, + 32, + 34, + 191, + 411, + 499, + 542, + 581, + 593, + 748, + 823, + 878, + 99, + 169, + 439, + 522, + 729, + 879, + 31, + 97, + 195, + 273, + 314, + 496, + 498, + 863, + 55, + 75, + 100, + 153, + 198, + 404, + 459, + 664, + 800, + 877, + 919, + 999, + 97, + 252, + 330, + 477, + 572, + 663, + 687, + 707, + 726, + 778, + 822, + 905, + 909, + 62, + 285, + 353, + 384, + 564, + 578, + 626, + 669, + 34, + 82, + 303, + 585, + 614, + 682, + 816, + 896, + 917, + 971, + 198, + 200, + 255, + 508, + 524, + 640, + 789, + 840, + 855, + 125, + 177, + 277, + 332, + 491, + 513, + 514, + 526, + 619, + 626, + 651, + 730, + 735, + 795, + 999, + 91, + 141, + 279, + 457, + 617, + 717, + 24, + 26, + 255, + 270, + 314, + 333, + 425, + 493, + 518, + 626, + 900, + 943, + 161, + 381, + 386, + 412, + 688, + 795, + 970, + 999, + 51, + 77, + 123, + 193, + 225, + 227, + 340, + 757, + 826, + 901, + 927, + 938, + 972, + 180, + 304, + 358, + 508, + 531, + 997, + 46, + 99, + 182, + 354, + 653, + 661, + 749, + 765, + 766, + 911, + 50, + 320, + 365, + 604, + 720, + 812, + 60, + 91, + 196, + 249, + 492, + 525, + 671, + 681, + 724, + 801, + 813, + 936, + 34, + 221, + 318, + 353, + 490, + 557, + 584, + 640, + 801, + 152, + 253, + 264, + 314, + 567, + 587, + 888, + 898, + 238, + 263, + 269, + 386, + 446, + 578, + 613, + 632, + 853, + 893, + 193, + 311, + 391, + 604, + 638, + 780, + 786, + 890, + 909, + 931, + 25, + 152, + 201, + 221, + 222, + 345, + 358, + 442, + 578, + 622, + 640, + 711, + 748, + 979, + 474, + 479, + 541, + 963, + 193, + 202, + 264, + 365, + 512, + 648, + 992, + 60, + 135, + 327, + 330, + 355, + 400, + 434, + 556, + 561, + 691, + 760, + 810, + 848, + 3, + 25, + 372, + 421, + 555, + 618, + 678, + 723, + 790, + 850, + 876, + 947, + 47, + 179, + 253, + 284, + 588, + 608, + 615, + 688, + 732, + 746, + 753, + 923, + 997, + 70, + 197, + 212, + 281, + 360, + 588, + 897, + 994, + 140, + 146, + 209, + 212, + 321, + 427, + 581, + 736, + 744, + 755, + 848, + 913, + 15, + 183, + 733, + 792, + 804, + 848, + 854, + 6, + 13, + 42, + 187, + 211, + 465, + 567, + 741, + 755, + 858, + 955, + 36, + 56, + 131, + 213, + 352, + 377, + 393, + 405, + 520, + 543, + 729, + 826, + 865, + 42, + 66, + 80, + 116, + 322, + 463, + 768, + 866, + 981, + 105, + 252, + 513, + 613, + 652, + 788, + 199, + 245, + 609, + 673, + 703, + 770, + 863, + 868, + 34, + 432, + 522, + 571, + 641, + 649, + 804, + 842, + 934, + 24, + 25, + 88, + 322, + 369, + 423, + 598, + 632, + 675, + 711, + 969, + 161, + 274, + 320, + 377, + 434, + 705, + 749, + 753, + 850, + 881, + 134, + 158, + 235, + 245, + 346, + 383, + 422, + 425, + 594, + 598, + 735, + 750, + 876, + 988, + 144, + 183, + 191, + 344, + 460, + 522, + 527, + 529, + 537, + 619, + 711, + 812, + 852, + 901, + 979, + 100, + 143, + 653, + 755, + 759, + 816, + 23, + 161, + 188, + 223, + 266, + 326, + 726, + 750, + 802, + 898, + 998, + 27, + 178, + 242, + 269, + 604, + 870, + 990, + 137, + 350, + 424, + 447, + 553, + 559, + 580, + 624, + 677, + 690, + 751, + 894, + 922, + 995, + 41, + 147, + 178, + 272, + 357, + 361, + 415, + 782, + 891, + 124, + 149, + 194, + 473, + 542, + 687, + 758, + 776, + 852, + 935, + 33, + 63, + 420, + 25, + 54, + 134, + 169, + 216, + 217, + 315, + 367, + 378, + 452, + 535, + 549, + 598, + 624, + 683, + 731, + 882, + 893, + 203, + 277, + 470, + 676, + 686, + 688, + 711, + 805, + 880, + 943, + 74, + 139, + 158, + 190, + 216, + 295, + 380, + 431, + 436, + 445, + 514, + 683, + 713, + 807, + 809, + 820, + 845, + 897, + 991, + 46, + 227, + 290, + 462, + 672, + 901, + 10, + 76, + 108, + 110, + 111, + 160, + 168, + 257, + 453, + 533, + 739, + 746, + 764, + 846, + 946, + 999, + 36, + 136, + 311, + 392, + 724, + 908, + 30, + 450, + 495, + 648, + 672, + 726, + 878, + 881, + 984, + 80, + 208, + 329, + 502, + 511, + 515, + 553, + 560, + 694, + 824, + 938, + 70, + 110, + 144, + 183, + 309, + 332, + 337, + 342, + 398, + 591, + 635, + 811, + 842, + 192, + 339, + 449, + 504, + 570, + 594, + 644, + 666, + 692, + 779, + 847, + 32, + 138, + 155, + 279, + 296, + 409, + 427, + 524, + 605, + 837, + 919, + 993, + 38, + 72, + 139, + 173, + 279, + 281, + 285, + 306, + 375, + 390, + 426, + 734, + 909, + 958, + 17, + 61, + 451, + 523, + 573, + 622, + 935, + 16, + 74, + 97, + 139, + 149, + 193, + 268, + 353, + 433, + 475, + 481, + 508, + 752, + 881, + 919, + 9, + 93, + 292, + 406, + 543, + 573, + 610, + 612, + 642, + 855, + 326, + 327, + 428, + 430, + 677, + 781, + 796, + 906, + 918, + 93, + 191, + 206, + 467, + 654, + 704, + 707, + 709, + 813, + 908, + 87, + 212, + 252, + 315, + 586, + 755, + 777, + 801, + 809, + 838, + 982, + 479, + 491, + 499, + 681, + 887, + 996, + 37, + 378, + 408, + 456, + 460, + 493, + 568, + 601, + 616, + 684, + 820, + 866, + 915, + 153, + 186, + 593, + 781, + 878, + 48, + 262, + 320, + 361, + 599, + 696, + 698, + 871, + 17, + 104, + 128, + 142, + 216, + 347, + 468, + 583, + 656, + 737, + 752, + 759, + 767, + 848, + 860, + 885, + 105, + 151, + 173, + 198, + 412, + 467, + 701, + 709, + 967, + 65, + 165, + 315, + 431, + 523, + 562, + 633, + 694, + 780, + 782, + 795, + 943, + 991, + 28, + 125, + 223, + 283, + 384, + 460, + 586, + 589, + 600, + 743, + 754, + 846, + 907, + 983, + 12, + 26, + 94, + 190, + 256, + 282, + 380, + 385, + 450, + 570, + 582, + 669, + 672, + 751, + 804, + 892, + 26, + 167, + 259, + 337, + 409, + 425, + 121, + 133, + 305, + 332, + 408, + 432, + 531, + 582, + 598, + 680, + 716, + 778, + 790, + 907, + 942, + 224, + 240, + 394, + 449, + 489, + 503, + 575, + 594, + 618, + 653, + 711, + 736, + 744, + 821, + 961, + 536, + 603, + 781, + 866, + 901, + 911, + 916, + 970, + 42, + 110, + 186, + 276, + 396, + 565, + 573, + 677, + 738, + 918, + 956, + 965, + 978, + 160, + 191, + 338, + 502, + 572, + 721, + 731, + 45, + 209, + 224, + 226, + 623, + 718, + 721, + 725, + 840, + 953, + 977, + 24, + 77, + 117, + 290, + 941, + 945, + 84, + 200, + 254, + 374, + 591, + 635, + 652, + 765, + 826, + 949, + 104, + 257, + 715, + 162, + 456, + 479, + 892, + 34, + 110, + 142, + 645, + 664, + 840, + 950, + 139, + 313, + 453, + 615, + 792, + 798, + 47, + 133, + 170, + 350, + 605, + 757, + 922, + 940, + 45, + 204, + 274, + 369, + 411, + 809, + 888, + 903, + 969, + 151, + 318, + 354, + 375, + 629, + 758, + 881, + 917, + 972, + 185, + 238, + 397, + 405, + 422, + 450, + 500, + 532, + 625, + 677, + 708, + 755, + 780, + 824, + 845, + 931, + 963, + 975, + 18, + 245, + 447, + 519, + 700, + 21, + 49, + 130, + 133, + 185, + 191, + 388, + 654, + 760, + 812, + 817, + 858, + 906, + 982, + 997, + 209, + 508, + 611, + 691, + 725, + 79, + 232, + 320, + 367, + 481, + 559, + 649, + 656, + 830, + 960, + 40, + 288, + 542, + 644, + 646, + 749, + 827, + 894, + 929, + 956, + 73, + 87, + 215, + 261, + 377, + 517, + 822, + 906, + 997, + 56, + 267, + 276, + 375, + 415, + 528, + 660, + 670, + 892, + 959, + 998, + 999, + 146, + 329, + 331, + 332, + 400, + 510, + 623, + 653, + 822, + 18, + 375, + 394, + 477, + 482, + 596, + 665, + 724, + 847, + 872, + 935, + 40, + 136, + 320, + 332, + 408, + 767, + 975, + 24, + 49, + 156, + 246, + 378, + 578, + 627, + 916, + 965, + 998, + 123, + 285, + 305, + 438, + 476, + 538, + 554, + 773, + 804, + 968, + 4, + 181, + 240, + 411, + 715, + 797, + 802, + 896, + 904, + 985, + 68, + 118, + 185, + 326, + 645, + 690, + 736, + 744, + 961, + 3, + 404, + 437, + 572, + 812, + 902, + 917, + 921, + 180, + 291, + 327, + 328, + 389, + 407, + 408, + 530, + 650, + 727, + 996, + 230, + 313, + 506, + 579, + 593, + 610, + 814, + 832, + 840, + 876, + 951, + 251, + 327, + 353, + 581, + 588, + 711, + 837, + 2, + 60, + 165, + 275, + 291, + 320, + 735, + 796, + 63, + 78, + 165, + 318, + 433, + 439, + 456, + 466, + 529, + 765, + 144, + 221, + 259, + 686, + 793, + 7, + 242, + 265, + 433, + 474, + 664, + 840, + 954, + 95, + 161, + 165, + 209, + 396, + 820, + 947, + 36, + 198, + 262, + 342, + 449, + 482, + 621, + 742, + 756, + 822, + 972, + 145, + 339, + 342, + 479, + 523, + 811, + 916, + 199, + 318, + 323, + 363, + 491, + 496, + 562, + 570, + 612, + 719, + 739, + 836, + 168, + 216, + 252, + 319, + 760, + 841, + 845, + 955, + 144, + 354, + 442, + 443, + 662, + 752, + 936, + 77, + 185, + 315, + 473, + 512, + 596, + 612, + 634, + 900, + 936, + 974, + 166, + 189, + 428, + 498, + 755, + 922, + 23, + 100, + 204, + 534, + 719, + 738, + 854, + 44, + 120, + 273, + 407, + 988, + 50, + 386, + 460, + 472, + 513, + 552, + 811, + 912, + 981, + 995, + 24, + 113, + 129, + 302, + 442, + 512, + 685, + 726, + 966, + 161, + 413, + 491, + 498, + 499, + 543, + 688, + 690, + 809, + 843, + 888, + 564, + 624, + 756, + 815, + 832, + 866, + 932, + 1, + 13, + 26, + 39, + 87, + 176, + 279, + 284, + 317, + 344, + 397, + 442, + 507, + 591, + 663, + 691, + 800, + 803, + 865, + 925, + 987, + 995, + 996, + 315, + 541, + 557, + 664, + 679, + 754, + 808, + 851, + 918, + 0, + 117, + 131, + 262, + 442, + 627, + 702, + 799, + 945, + 281, + 313, + 314, + 384, + 427, + 558, + 669, + 706, + 720, + 721, + 766, + 786, + 840, + 842, + 923, + 58, + 119, + 317, + 411, + 415, + 416, + 680, + 997, + 84, + 442, + 487, + 689, + 811, + 833, + 940, + 22, + 431, + 515, + 598, + 605, + 738, + 876, + 919, + 960, + 980, + 3, + 38, + 130, + 716, + 854, + 885, + 51, + 93, + 141, + 153, + 195, + 258, + 329, + 390, + 497, + 508, + 680, + 863, + 169, + 211, + 335, + 423, + 442, + 479, + 864, + 169, + 239, + 534, + 605, + 708, + 743, + 772, + 814, + 832, + 54, + 110, + 167, + 171, + 290, + 370, + 433, + 652, + 661, + 677, + 710, + 726, + 829, + 902, + 915, + 44, + 88, + 104, + 214, + 313, + 346, + 487, + 555, + 582, + 660, + 674, + 713, + 721, + 762, + 785, + 797, + 986, + 998, + 50, + 143, + 158, + 281, + 488, + 566, + 579, + 584, + 596, + 846, + 876, + 42, + 64, + 71, + 73, + 105, + 170, + 171, + 210, + 276, + 531, + 577, + 699, + 879, + 889, + 925, + 932, + 442, + 447, + 462, + 504, + 530, + 687, + 714, + 838, + 120, + 171, + 280, + 358, + 644, + 735, + 765, + 964, + 988, + 993, + 80, + 352, + 740, + 813, + 999, + 133, + 155, + 192, + 196, + 442, + 456, + 504, + 519, + 530, + 606, + 777, + 916, + 985, + 24, + 42, + 351, + 407, + 504, + 516, + 682, + 879, + 67, + 69, + 145, + 152, + 492, + 515, + 562, + 575, + 658, + 668, + 700, + 722, + 811, + 956, + 18, + 126, + 283, + 289, + 297, + 307, + 337, + 368, + 519, + 615, + 789, + 838, + 876, + 970, + 38, + 137, + 307, + 378, + 436, + 437, + 453, + 520, + 793, + 844, + 893, + 168, + 179, + 230, + 327, + 487, + 662, + 727, + 126, + 320, + 584, + 707, + 864, + 895, + 295, + 309, + 781, + 823, + 988, + 18, + 42, + 151, + 163, + 259, + 324, + 349, + 416, + 521, + 659, + 689, + 912, + 24, + 87, + 201, + 319, + 406, + 434, + 488, + 554, + 576, + 624, + 714, + 851, + 995, + 49, + 142, + 236, + 300, + 416, + 497, + 586, + 708, + 777, + 962, + 969, + 217, + 235, + 279, + 316, + 430, + 491, + 630, + 842, + 907, + 124, + 143, + 180, + 455, + 672, + 695, + 891, + 971, + 90, + 173, + 363, + 410, + 446, + 480, + 528, + 631, + 690, + 777, + 792, + 143, + 187, + 261, + 268, + 292, + 410, + 524, + 557, + 618, + 643, + 656, + 680, + 807, + 812, + 824, + 900, + 2, + 5, + 117, + 216, + 329, + 355, + 400, + 493, + 606, + 631, + 850, + 875, + 947, + 93, + 134, + 172, + 427, + 477, + 508, + 540, + 585, + 878, + 123, + 302, + 594, + 678, + 697, + 747, + 824, + 868, + 965, + 14, + 21, + 178, + 180, + 227, + 281, + 379, + 412, + 417, + 450, + 456, + 465, + 589, + 596, + 736, + 760, + 844, + 13, + 81, + 177, + 276, + 327, + 359, + 623, + 674, + 676, + 3, + 6, + 34, + 144, + 150, + 202, + 219, + 376, + 429, + 539, + 648, + 663, + 885, + 944, + 997, + 31, + 259, + 263, + 291, + 646, + 783, + 820, + 836, + 903, + 929, + 83, + 145, + 193, + 372, + 392, + 422, + 564, + 734, + 740, + 846, + 868, + 945, + 185, + 277, + 325, + 394, + 499, + 649, + 656, + 748, + 841, + 922, + 958, + 19, + 43, + 51, + 96, + 291, + 397, + 680, + 729, + 913, + 943, + 978, + 151, + 179, + 234, + 248, + 358, + 692, + 704, + 778, + 809, + 847, + 850, + 873, + 969, + 242, + 327, + 340, + 552, + 736, + 742, + 837, + 959, + 179, + 216, + 355, + 356, + 443, + 447, + 512, + 515, + 529, + 634, + 786, + 47, + 142, + 203, + 223, + 606, + 623, + 815, + 24, + 37, + 67, + 199, + 272, + 349, + 380, + 512, + 574, + 586, + 743, + 847, + 890, + 897, + 25, + 107, + 347, + 474, + 476, + 621, + 642, + 734, + 755, + 142, + 211, + 273, + 526, + 528, + 602, + 632, + 761, + 765, + 776, + 847, + 112, + 118, + 140, + 153, + 229, + 313, + 448, + 469, + 619, + 627, + 637, + 672, + 751, + 900, + 906, + 297, + 411, + 464, + 497, + 691, + 740, + 886, + 14, + 109, + 125, + 187, + 194, + 241, + 263, + 379, + 552, + 615, + 657, + 670, + 750, + 47, + 133, + 386, + 482, + 517, + 641, + 696, + 734, + 951, + 1, + 101, + 103, + 134, + 205, + 526, + 533, + 538, + 559, + 594, + 680, + 835, + 4, + 224, + 526, + 600, + 769, + 885, + 991, + 2, + 292, + 326, + 380, + 393, + 539, + 798, + 907, + 465, + 641, + 727, + 763, + 794, + 854, + 44, + 92, + 235, + 381, + 420, + 430, + 461, + 538, + 555, + 725, + 756, + 849, + 177, + 180, + 337, + 353, + 540, + 571, + 588, + 706, + 734, + 753, + 776, + 786, + 982, + 999, + 10, + 159, + 258, + 428, + 449, + 505, + 588, + 888, + 998, + 55, + 79, + 95, + 211, + 226, + 432, + 435, + 560, + 563, + 613, + 694, + 806, + 968, + 90, + 165, + 207, + 422, + 439, + 489, + 674, + 693, + 985, + 8, + 111, + 336, + 474, + 489, + 554, + 715, + 742, + 772, + 889, + 906, + 918, + 102, + 197, + 236, + 294, + 345, + 562, + 568, + 697, + 850, + 950, + 113, + 151, + 204, + 226, + 235, + 267, + 302, + 380, + 407, + 499, + 813, + 916, + 956, + 200, + 275, + 403, + 546, + 607, + 697, + 734, + 187, + 211, + 255, + 329, + 359, + 421, + 495, + 555, + 581, + 696, + 961, + 973, + 231, + 318, + 359, + 388, + 422, + 643, + 707, + 932, + 940, + 949, + 3, + 65, + 128, + 134, + 172, + 231, + 349, + 728, + 749, + 757, + 772, + 891, + 150, + 185, + 551, + 599, + 617, + 709, + 816, + 170, + 339, + 406, + 487, + 800, + 887, + 71, + 196, + 209, + 449, + 497, + 517, + 518, + 529, + 629, + 661, + 715, + 869, + 20, + 37, + 96, + 99, + 214, + 273, + 400, + 555, + 917, + 31, + 227, + 228, + 246, + 353, + 379, + 507, + 534, + 590, + 620, + 680, + 734, + 830, + 876, + 955, + 996, + 5, + 361, + 364, + 559, + 699, + 882, + 920, + 11, + 114, + 119, + 154, + 161, + 319, + 467, + 533, + 570, + 787, + 827, + 995, + 23, + 171, + 240, + 254, + 268, + 287, + 455, + 580, + 672, + 726, + 977, + 982, + 203, + 239, + 298, + 407, + 579, + 594, + 610, + 624, + 672, + 756, + 161, + 228, + 437, + 465, + 552, + 861, + 879, + 968, + 987, + 989, + 59, + 79, + 143, + 149, + 166, + 271, + 300, + 411, + 641, + 677, + 757, + 868, + 918, + 994, + 0, + 321, + 340, + 346, + 548, + 788, + 821, + 953, + 59, + 120, + 230, + 344, + 726, + 823, + 850, + 83, + 121, + 201, + 345, + 355, + 369, + 398, + 422, + 507, + 527, + 554, + 599, + 712, + 735, + 874, + 900, + 28, + 40, + 149, + 243, + 344, + 494, + 759, + 902, + 979, + 9, + 168, + 493, + 610, + 655, + 747, + 806, + 975, + 8, + 29, + 56, + 150, + 177, + 207, + 268, + 364, + 368, + 458, + 473, + 719, + 796, + 862, + 865, + 45, + 52, + 115, + 198, + 285, + 377, + 396, + 548, + 682, + 705, + 807, + 833, + 957, + 36, + 149, + 150, + 278, + 440, + 451, + 558, + 575, + 625, + 630, + 689, + 932, + 953, + 985, + 16, + 106, + 338, + 342, + 667, + 675, + 723, + 745, + 973, + 86, + 175, + 207, + 262, + 385, + 496, + 774, + 33, + 222, + 265, + 295, + 297, + 410, + 412, + 500, + 526, + 595, + 813, + 899, + 87, + 155, + 168, + 505, + 612, + 650, + 753, + 819, + 830, + 103, + 147, + 237, + 278, + 438, + 480, + 490, + 648, + 671, + 748, + 822, + 183, + 246, + 400, + 541, + 582, + 614, + 622, + 745, + 807, + 80, + 137, + 430, + 461, + 541, + 724, + 6, + 142, + 168, + 183, + 196, + 313, + 484, + 594, + 635, + 716, + 803, + 825, + 861, + 972, + 981, + 83, + 164, + 202, + 232, + 270, + 311, + 404, + 431, + 688, + 729, + 867, + 903, + 925, + 69, + 283, + 295, + 363, + 410, + 434, + 457, + 481, + 574, + 578, + 587, + 600, + 664, + 803, + 858, + 76, + 205, + 334, + 441, + 553, + 590, + 944, + 69, + 272, + 486, + 513, + 604, + 749, + 842, + 852, + 954, + 17, + 86, + 115, + 203, + 343, + 355, + 467, + 478, + 629, + 646, + 748, + 811, + 900, + 13, + 25, + 120, + 353, + 608, + 612, + 747, + 766, + 856, + 109, + 234, + 265, + 279, + 325, + 379, + 418, + 464, + 550, + 552, + 571, + 344, + 448, + 517, + 682, + 895, + 173, + 242, + 281, + 314, + 350, + 502, + 518, + 552, + 745, + 19, + 70, + 75, + 80, + 695, + 697, + 793, + 877, + 85, + 189, + 248, + 300, + 417, + 433, + 507, + 936, + 947, + 8, + 351, + 368, + 400, + 450, + 470, + 474, + 501, + 518, + 524, + 558, + 616, + 666, + 712, + 953, + 172, + 398, + 644, + 680, + 785, + 71, + 116, + 288, + 314, + 327, + 488, + 724, + 770, + 858, + 934, + 958, + 67, + 115, + 279, + 654, + 689, + 707, + 752, + 888, + 966, + 208, + 544, + 679, + 719, + 789, + 831, + 49, + 263, + 420, + 433, + 502, + 602, + 651, + 678, + 730, + 756, + 762, + 900, + 100, + 113, + 177, + 198, + 509, + 516, + 596, + 645, + 783, + 939, + 987, + 335, + 429, + 437, + 543, + 566, + 695, + 707, + 747, + 868, + 921, + 0, + 84, + 203, + 215, + 477, + 523, + 526, + 612, + 627, + 766, + 778, + 809, + 126, + 203, + 373, + 590, + 640, + 863, + 871, + 937, + 201, + 221, + 729, + 746, + 772, + 924, + 937, + 964, + 78, + 339, + 406, + 424, + 475, + 679, + 869, + 938, + 64, + 147, + 163, + 171, + 293, + 381, + 390, + 511, + 989, + 63, + 85, + 208, + 335, + 441, + 510, + 566, + 586, + 909, + 935, + 970, + 50, + 100, + 351, + 354, + 397, + 442, + 448, + 580, + 657, + 789, + 836, + 293, + 311, + 456, + 795, + 796, + 799, + 909, + 972, + 984, + 28, + 132, + 226, + 361, + 473, + 493, + 586, + 611, + 676, + 693, + 939, + 948, + 150, + 185, + 269, + 362, + 648, + 650, + 870, + 307, + 330, + 438, + 756, + 852, + 99, + 223, + 285, + 371, + 767, + 912, + 966, + 1, + 3, + 111, + 583, + 733, + 841, + 959, + 977, + 115, + 263, + 283, + 498, + 517, + 534, + 604, + 656, + 661, + 769, + 876, + 974, + 59, + 123, + 291, + 343, + 473, + 565, + 634, + 834, + 898, + 923, + 962, + 75, + 85, + 92, + 125, + 305, + 827, + 836, + 901, + 936, + 28, + 124, + 316, + 541, + 636, + 694, + 929, + 960, + 37, + 69, + 169, + 442, + 491, + 588, + 619, + 643, + 740, + 794, + 939, + 941, + 10, + 43, + 248, + 450, + 812, + 907, + 984, + 271, + 307, + 316, + 533, + 702, + 733, + 752, + 850, + 892, + 919, + 971, + 97, + 132, + 154, + 461, + 633, + 741, + 905, + 940, + 74, + 115, + 118, + 251, + 297, + 344, + 405, + 623, + 655, + 658, + 775, + 801, + 903, + 965, + 53, + 309, + 392, + 643, + 696, + 752, + 764, + 867, + 981, + 64, + 228, + 236, + 301, + 498, + 512, + 536, + 568, + 685, + 865, + 925, + 29, + 371, + 372, + 626, + 760, + 765, + 773, + 813, + 980, + 109, + 177, + 211, + 322, + 370, + 415, + 425, + 514, + 647, + 672, + 767, + 945, + 613, + 720, + 863, + 870, + 886, + 924, + 144, + 233, + 483, + 504, + 811, + 872, + 908, + 921, + 61, + 160, + 350, + 376, + 424, + 602, + 632, + 675, + 682, + 861, + 959, + 380, + 389, + 848, + 7, + 13, + 458, + 629, + 103, + 193, + 231, + 533, + 590, + 598, + 661, + 741, + 880, + 243, + 400, + 505, + 601, + 689, + 965, + 15, + 136, + 200, + 230, + 322, + 419, + 792, + 890, + 3, + 71, + 174, + 189, + 336, + 363, + 371, + 403, + 534, + 743, + 792, + 799, + 867, + 909, + 951, + 57, + 198, + 202, + 334, + 471, + 542, + 709, + 19, + 104, + 156, + 246, + 421, + 450, + 593, + 721, + 866, + 972, + 43, + 185, + 199, + 243, + 255, + 293, + 343, + 395, + 413, + 608, + 749, + 759, + 819, + 160, + 261, + 357, + 728, + 734, + 788, + 849, + 859, + 884, + 915, + 129, + 394, + 592, + 803, + 974, + 57, + 79, + 246, + 528, + 698, + 740, + 909, + 968, + 90, + 204, + 337, + 699, + 926, + 125, + 181, + 251, + 333, + 335, + 439, + 737, + 778, + 905, + 922, + 1, + 22, + 64, + 80, + 304, + 45, + 63, + 99, + 144, + 222, + 274, + 384, + 406, + 447, + 643, + 774, + 784, + 918, + 58, + 110, + 156, + 294, + 436, + 531, + 654, + 742, + 769, + 948, + 153, + 171, + 177, + 389, + 647, + 722, + 781, + 825, + 829, + 854, + 33, + 150, + 194, + 237, + 313, + 314, + 386, + 502, + 645, + 705, + 791, + 833, + 845, + 882, + 916, + 136, + 222, + 275, + 381, + 471, + 859, + 901, + 902, + 917, + 992, + 118, + 319, + 494, + 512, + 812, + 897, + 960, + 35, + 252, + 489, + 565, + 573, + 605, + 684, + 847, + 22, + 396, + 541, + 560, + 589, + 618, + 685, + 771, + 793, + 968, + 53, + 102, + 130, + 434, + 506, + 738, + 759, + 867, + 884, + 886, + 894, + 956, + 95, + 100, + 117, + 215, + 360, + 399, + 416, + 421, + 612, + 692, + 697, + 707, + 815, + 852, + 875, + 892, + 936, + 346, + 380, + 563, + 691, + 718, + 115, + 192, + 309, + 603, + 881, + 888, + 927, + 983, + 182, + 206, + 222, + 295, + 355, + 446, + 672, + 710, + 751, + 85, + 127, + 144, + 267, + 306, + 339, + 372, + 393, + 688, + 739, + 821, + 886, + 894, + 915, + 952, + 169, + 179, + 233, + 316, + 654, + 864, + 988, + 98, + 102, + 153, + 188, + 205, + 245, + 290, + 333, + 901, + 922, + 986, + 988, + 996, + 93, + 390, + 438, + 445, + 539, + 614, + 713, + 800, + 856, + 962, + 101, + 145, + 245, + 546, + 560, + 581, + 598, + 937, + 54, + 148, + 181, + 302, + 592, + 670, + 761, + 287, + 324, + 365, + 464, + 471, + 473, + 487, + 598, + 667, + 741, + 0, + 95, + 183, + 420, + 469, + 648, + 686, + 890, + 902, + 20, + 207, + 397, + 410, + 481, + 545, + 579, + 635, + 689, + 755, + 791, + 850, + 856, + 857, + 998, + 15, + 332, + 481, + 577, + 603, + 635, + 948, + 58, + 135, + 208, + 370, + 469, + 848, + 942, + 946, + 31, + 149, + 153, + 164, + 174, + 329, + 444, + 534, + 548, + 615, + 110, + 137, + 177, + 287, + 699, + 705, + 848, + 197, + 204, + 236, + 382, + 543, + 874, + 984, + 49, + 78, + 163, + 185, + 316, + 355, + 365, + 577, + 667, + 673, + 720, + 722, + 785, + 942, + 10, + 117, + 182, + 218, + 305, + 398, + 471, + 676, + 807, + 839, + 944, + 173, + 182, + 184, + 302, + 340, + 426, + 609, + 693, + 735, + 762, + 873, + 947, + 24, + 85, + 290, + 299, + 499, + 551, + 609, + 648, + 660, + 685, + 11, + 62, + 109, + 185, + 345, + 797, + 843, + 264, + 776, + 824, + 845, + 958, + 49, + 58, + 170, + 367, + 451, + 469, + 654, + 794, + 842, + 877, + 897, + 950, + 4, + 57, + 58, + 61, + 260, + 334, + 494, + 540, + 561, + 636, + 659, + 950, + 68, + 96, + 146, + 167, + 270, + 293, + 401, + 623, + 625, + 668, + 690, + 934, + 946, + 218, + 280, + 309, + 389, + 447, + 492, + 641, + 730, + 786, + 843, + 871, + 970, + 973, + 14, + 93, + 284, + 404, + 666, + 713, + 835, + 183, + 214, + 292, + 563, + 739, + 823, + 876, + 6, + 84, + 543, + 556, + 579, + 855, + 35, + 227, + 327, + 380, + 439, + 712, + 769, + 776, + 46, + 176, + 178, + 192, + 239, + 555, + 703, + 744, + 751, + 813, + 939, + 30, + 89, + 141, + 260, + 268, + 348, + 367, + 374, + 730, + 742, + 766, + 769, + 832, + 99, + 150, + 199, + 229, + 286, + 292, + 344, + 464, + 524, + 558, + 565, + 629, + 716, + 766, + 818, + 867, + 876, + 877, + 881, + 131, + 208, + 312, + 472, + 524, + 565, + 638, + 645, + 655, + 663, + 665, + 713, + 752, + 877, + 958, + 963, + 985, + 993, + 23, + 160, + 240, + 594, + 602, + 663, + 876, + 945, + 961, + 53, + 82, + 159, + 217, + 219, + 270, + 549, + 598, + 742, + 846, + 885, + 628, + 878, + 121, + 210, + 273, + 554, + 555, + 759, + 911, + 913, + 28, + 233, + 269, + 347, + 489, + 592, + 859, + 934, + 952, + 6, + 60, + 79, + 123, + 256, + 279, + 455, + 557, + 727, + 123, + 750, + 906, + 971, + 7, + 26, + 96, + 209, + 464, + 477, + 662, + 693, + 963, + 201, + 427, + 474, + 663, + 728, + 917, + 81, + 102, + 488, + 644, + 802, + 834, + 929, + 987, + 273, + 283, + 459, + 531, + 736, + 918, + 960, + 112, + 182, + 187, + 193, + 311, + 360, + 400, + 517, + 668, + 885, + 888, + 70, + 89, + 130, + 190, + 248, + 262, + 334, + 447, + 451, + 493, + 513, + 531, + 548, + 721, + 891, + 918, + 925, + 968, + 102, + 249, + 396, + 397, + 405, + 473, + 532, + 761, + 869, + 127, + 211, + 234, + 375, + 377, + 513, + 517, + 523, + 526, + 712, + 772, + 848, + 890, + 172, + 264, + 385, + 445, + 461, + 474, + 485, + 537, + 608, + 687, + 735, + 11, + 220, + 328, + 381, + 488, + 690, + 790, + 910, + 969, + 994, + 191, + 284, + 472, + 565, + 584, + 660, + 706, + 715, + 739, + 75, + 78, + 81, + 260, + 372, + 741, + 898, + 910, + 967, + 972, + 108, + 410, + 463, + 923, + 936, + 947, + 961, + 110, + 111, + 160, + 191, + 239, + 735, + 963, + 77, + 267, + 275, + 330, + 357, + 620, + 664, + 699, + 837, + 842, + 42, + 45, + 375, + 384, + 468, + 516, + 521, + 552, + 564, + 700, + 943, + 981, + 36, + 272, + 288, + 442, + 506, + 507, + 533, + 708, + 748, + 834, + 950, + 261, + 275, + 24, + 97, + 124, + 311, + 398, + 504, + 558, + 581, + 653, + 799, + 930, + 988, + 63, + 164, + 260, + 305, + 348, + 372, + 456, + 468, + 667, + 794, + 934, + 956, + 210, + 478, + 533, + 927, + 14, + 89, + 163, + 207, + 356, + 626, + 628, + 658, + 696, + 725, + 731, + 764, + 43, + 58, + 449, + 639, + 894, + 138, + 163, + 290, + 344, + 345, + 386, + 432, + 466, + 614, + 767, + 800, + 831, + 7, + 292, + 314, + 322, + 327, + 518, + 549, + 760, + 981, + 122, + 246, + 297, + 461, + 489, + 502, + 581, + 630, + 746, + 769, + 904, + 0, + 27, + 157, + 259, + 337, + 434, + 504, + 541, + 573, + 781, + 794, + 842, + 928, + 986, + 184, + 244, + 372, + 423, + 482, + 503, + 626, + 644, + 785, + 890, + 47, + 242, + 509, + 671, + 675, + 765, + 884, + 982, + 81, + 84, + 147, + 314, + 456, + 483, + 603, + 670, + 691, + 896, + 928, + 18, + 21, + 75, + 114, + 284, + 513, + 574, + 621, + 630, + 753, + 765, + 896, + 331, + 344, + 358, + 409, + 499, + 678, + 679, + 953, + 90, + 123, + 139, + 150, + 161, + 228, + 296, + 534, + 658, + 707, + 715, + 743, + 757, + 945, + 962, + 993, + 92, + 133, + 147, + 201, + 297, + 363, + 517, + 7, + 80, + 147, + 183, + 328, + 348, + 351, + 594, + 691, + 723, + 735, + 18, + 145, + 216, + 231, + 305, + 364, + 380, + 447, + 589, + 629, + 648, + 727, + 729, + 109, + 132, + 161, + 195, + 408, + 443, + 527, + 748, + 770, + 821, + 928, + 962, + 119, + 298, + 395, + 556, + 728, + 898, + 945, + 10, + 129, + 451, + 490, + 606, + 620, + 662, + 698, + 782, + 813, + 816, + 952, + 69, + 175, + 203, + 306, + 399, + 405, + 707, + 710, + 12, + 107, + 284, + 285, + 448, + 584, + 689, + 818, + 990, + 11, + 105, + 114, + 271, + 305, + 561, + 572, + 626, + 669, + 710, + 72, + 224, + 233, + 276, + 445, + 476, + 613, + 615, + 879, + 244, + 268, + 502, + 512, + 520, + 600, + 671, + 694, + 887, + 987, + 81, + 87, + 378, + 384, + 397, + 423, + 427, + 626, + 630, + 693, + 699, + 726, + 887, + 929, + 967, + 31, + 71, + 326, + 345, + 350, + 422, + 515, + 531, + 630, + 761, + 26, + 33, + 461, + 601, + 627, + 716, + 743, + 975, + 81, + 399, + 489, + 609, + 733, + 741, + 787, + 806, + 874, + 903, + 932, + 988, + 81, + 367, + 406, + 492, + 550, + 561, + 599, + 635, + 756, + 838, + 944, + 958, + 39, + 75, + 102, + 259, + 345, + 376, + 499, + 519, + 548, + 763, + 788, + 857, + 899, + 947, + 948, + 970, + 975, + 26, + 244, + 367, + 408, + 410, + 415, + 669, + 849, + 904, + 912, + 913, + 932, + 84, + 89, + 233, + 297, + 433, + 599, + 818, + 869, + 957, + 194, + 373, + 632, + 651, + 718, + 728, + 827, + 997, + 15, + 45, + 173, + 175, + 229, + 339, + 690, + 714, + 758, + 764, + 824, + 837, + 961, + 211, + 223, + 606, + 623, + 648, + 674, + 684, + 819, + 919, + 207, + 258, + 277, + 280, + 285, + 424, + 429, + 670, + 855, + 867, + 872, + 966, + 0, + 21, + 346, + 560, + 652, + 791, + 911, + 327, + 376, + 387, + 460, + 491, + 496, + 662, + 667, + 745, + 754, + 767, + 974, + 2, + 209, + 210, + 598, + 883, + 930, + 952, + 7, + 90, + 267, + 342, + 368, + 486, + 628, + 698, + 915, + 935, + 2, + 12, + 86, + 209, + 243, + 383, + 449, + 604, + 841, + 967, + 976, + 27, + 31, + 47, + 117, + 424, + 536, + 714, + 745, + 891, + 899, + 950, + 85, + 152, + 210, + 270, + 389, + 551, + 86, + 140, + 202, + 432, + 625, + 885, + 908, + 928, + 43, + 81, + 110, + 227, + 278, + 589, + 613, + 729, + 732, + 743, + 747, + 762, + 784, + 864, + 980, + 57, + 132, + 309, + 313, + 349, + 366, + 494, + 563, + 564, + 604, + 640, + 800, + 935, + 6, + 77, + 201, + 726, + 745, + 772, + 833, + 990, + 33, + 45, + 178, + 335, + 393, + 410, + 498, + 534, + 603, + 626, + 672, + 685, + 740, + 930, + 995, + 118, + 142, + 306, + 373, + 446, + 480, + 802, + 930, + 998, + 184, + 273, + 401, + 444, + 483, + 484, + 526, + 611, + 641, + 666, + 681, + 786, + 899, + 919, + 942, + 31, + 50, + 66, + 68, + 86, + 140, + 229, + 349, + 445, + 588, + 665, + 682, + 686, + 783, + 798, + 900, + 926, + 976, + 261, + 727, + 811, + 125, + 144, + 256, + 377, + 644, + 660, + 752, + 843, + 981, + 982, + 997, + 998, + 296, + 382, + 477, + 479, + 548, + 583, + 676, + 767, + 791, + 25, + 446, + 546, + 585, + 654, + 727, + 804, + 969, + 7, + 53, + 203, + 220, + 247, + 450, + 487, + 503, + 578, + 638, + 657, + 730, + 753, + 792, + 998, + 4, + 87, + 316, + 379, + 840, + 891, + 896, + 902, + 906, + 150, + 361, + 490, + 517, + 533, + 693, + 696, + 791, + 805, + 868, + 944, + 962, + 128, + 154, + 165, + 374, + 573, + 636, + 796, + 44, + 78, + 249, + 341, + 392, + 538, + 569, + 746, + 752, + 858, + 59, + 106, + 357, + 471, + 570, + 680, + 850, + 968, + 984, + 166, + 184, + 216, + 263, + 306, + 660, + 745, + 807, + 207, + 236, + 295, + 302, + 444, + 536, + 603, + 618, + 632, + 938, + 198, + 212, + 293, + 357, + 381, + 384, + 406, + 564, + 763, + 813, + 908, + 922, + 936, + 958, + 54, + 119, + 458, + 459, + 586, + 764, + 810, + 869, + 897, + 168, + 200, + 232, + 274, + 312, + 423, + 434, + 497, + 549, + 618, + 628, + 829, + 842, + 896, + 961, + 105, + 226, + 276, + 292, + 592, + 727, + 818, + 106, + 426, + 459, + 529, + 543, + 544, + 569, + 572, + 600, + 601, + 629, + 641, + 700, + 766, + 793, + 24, + 87, + 89, + 173, + 312, + 617, + 680, + 921, + 960, + 991, + 234, + 289, + 308, + 321, + 364, + 865, + 14, + 76, + 98, + 425, + 656, + 965, + 289, + 435, + 497, + 630, + 695, + 907, + 977, + 41, + 95, + 276, + 584, + 700, + 822, + 829, + 29, + 129, + 183, + 244, + 247, + 258, + 276, + 303, + 337, + 374, + 413, + 424, + 431, + 434, + 507, + 675, + 713, + 827, + 855, + 49, + 81, + 99, + 133, + 163, + 213, + 219, + 425, + 747, + 810, + 997, + 95, + 271, + 454, + 553, + 775, + 796, + 974, + 984, + 439, + 468, + 662, + 799, + 897, + 907, + 936, + 92, + 101, + 119, + 146, + 780, + 915, + 65, + 292, + 373, + 408, + 465, + 564, + 752, + 756, + 818, + 863, + 960, + 124, + 128, + 414, + 811, + 843, + 890, + 134, + 211, + 218, + 271, + 288, + 353, + 612, + 765, + 772, + 825, + 853, + 859, + 910, + 60, + 68, + 327, + 452, + 638, + 642, + 675, + 682, + 692, + 710, + 722, + 732, + 807, + 42, + 93, + 220, + 272, + 284, + 306, + 472, + 635, + 714, + 718, + 61, + 67, + 110, + 362, + 397, + 471, + 667, + 965, + 98, + 180, + 259, + 387, + 400, + 433, + 592, + 725, + 811, + 884, + 975, + 181, + 383, + 497, + 584, + 595, + 634, + 883, + 957, + 386, + 387, + 419, + 538, + 604, + 681, + 780, + 834, + 981, + 113, + 146, + 166, + 224, + 228, + 237, + 249, + 341, + 516, + 569, + 593, + 744, + 819, + 891, + 984, + 23, + 74, + 323, + 540, + 592, + 681, + 733, + 739, + 853, + 19, + 176, + 191, + 580, + 581, + 823, + 930, + 8, + 35, + 97, + 238, + 240, + 264, + 575, + 620, + 649, + 668, + 686, + 713, + 775, + 784, + 900, + 992, + 185, + 448, + 498, + 697, + 709, + 783, + 278, + 279, + 325, + 554, + 667, + 672, + 894, + 925, + 43, + 89, + 172, + 524, + 526, + 735, + 748, + 772, + 778, + 268, + 435, + 528, + 561, + 604, + 708, + 79, + 334, + 401, + 650, + 838, + 841, + 898, + 82, + 112, + 196, + 217, + 229, + 441, + 644, + 101, + 116, + 139, + 398, + 399, + 424, + 493, + 600, + 644, + 659, + 785, + 966, + 983, + 5, + 284, + 315, + 495, + 563, + 566, + 624, + 802, + 986, + 129, + 169, + 325, + 440, + 448, + 706, + 752, + 845, + 863, + 114, + 153, + 277, + 287, + 535, + 588, + 602, + 609, + 736, + 769, + 185, + 272, + 304, + 332, + 569, + 743, + 811, + 54, + 72, + 218, + 292, + 379, + 556, + 638, + 825, + 8, + 60, + 87, + 391, + 421, + 568, + 602, + 644, + 667, + 764, + 797, + 809, + 872, + 900, + 950, + 952, + 178, + 247, + 251, + 412, + 811, + 823, + 897, + 929, + 115, + 129, + 212, + 341, + 352, + 578, + 754, + 920, + 925, + 160, + 429, + 511, + 522, + 709, + 838, + 942, + 12, + 123, + 206, + 214, + 253, + 255, + 264, + 458, + 641, + 679, + 848, + 238, + 309, + 380, + 491, + 565, + 619, + 697, + 750, + 835, + 936, + 957, + 962, + 345, + 380, + 463, + 486, + 547, + 653, + 763, + 787, + 859, + 861, + 940, + 950, + 984, + 164, + 281, + 297, + 344, + 510, + 570, + 580, + 657, + 936, + 984, + 66, + 210, + 590, + 877, + 72, + 85, + 106, + 143, + 148, + 385, + 557, + 627, + 631, + 653, + 724, + 742, + 745, + 800, + 829, + 58, + 179, + 352, + 528, + 658, + 696, + 761, + 763, + 864, + 28, + 34, + 164, + 235, + 712, + 742, + 802, + 919, + 943, + 962, + 64, + 143, + 312, + 336, + 338, + 371, + 381, + 519, + 690, + 811, + 868, + 65, + 374, + 403, + 440, + 508, + 525, + 884, + 26, + 112, + 144, + 218, + 228, + 234, + 254, + 281, + 315, + 455, + 493, + 505, + 598, + 677, + 707, + 948, + 20, + 160, + 165, + 186, + 290, + 353, + 787, + 806, + 904, + 917, + 10, + 67, + 246, + 290, + 560, + 620, + 711, + 724, + 8, + 375, + 410, + 481, + 515, + 663, + 743, + 747, + 967, + 179, + 252, + 256, + 324, + 877, + 885, + 971, + 90, + 306, + 330, + 445, + 728, + 806, + 888, + 287, + 348, + 412, + 500, + 631, + 687, + 726, + 728, + 85, + 238, + 273, + 403, + 532, + 654, + 879, + 23, + 102, + 434, + 437, + 849, + 856, + 17, + 265, + 383, + 547, + 599, + 858, + 995, + 285, + 320, + 553, + 737, + 787, + 894, + 5, + 17, + 89, + 190, + 327, + 418, + 525, + 543, + 587, + 678, + 730, + 835, + 928, + 947, + 13, + 74, + 134, + 303, + 421, + 436, + 475, + 701, + 929, + 156, + 347, + 498, + 698, + 870, + 909, + 4, + 15, + 45, + 73, + 229, + 268, + 345, + 357, + 459, + 500, + 513, + 544, + 620, + 624, + 702, + 959, + 29, + 71, + 163, + 196, + 197, + 416, + 756, + 851, + 890, + 921, + 926, + 65, + 443, + 507, + 514, + 531, + 581, + 649, + 674, + 855, + 861, + 865, + 957, + 35, + 94, + 113, + 505, + 660, + 821, + 208, + 229, + 246, + 324, + 327, + 446, + 470, + 494, + 518, + 526, + 600, + 659, + 886, + 897, + 103, + 402, + 403, + 460, + 541, + 709, + 815, + 816, + 973, + 128, + 236, + 378, + 398, + 561, + 602, + 609, + 659, + 677, + 688, + 741, + 815, + 59, + 82, + 122, + 162, + 233, + 265, + 335, + 407, + 452, + 489, + 495, + 542, + 642, + 696, + 825, + 902, + 262, + 524, + 738, + 166, + 389, + 408, + 564, + 603, + 639, + 942, + 16, + 51, + 87, + 211, + 336, + 371, + 404, + 449, + 538, + 560, + 594, + 612, + 849, + 953, + 23, + 64, + 432, + 559, + 802, + 813, + 874, + 919, + 89, + 341, + 355, + 383, + 509, + 650, + 778, + 972, + 998, + 13, + 208, + 407, + 419, + 465, + 582, + 595, + 825, + 909, + 83, + 110, + 184, + 240, + 362, + 559, + 684, + 815, + 840, + 881, + 269, + 670, + 675, + 680, + 793, + 794, + 804, + 805, + 807, + 830, + 2, + 20, + 491, + 581, + 676, + 9, + 231, + 243, + 294, + 464, + 513, + 544, + 703, + 763, + 813, + 862, + 880, + 943, + 114, + 115, + 131, + 145, + 191, + 357, + 380, + 391, + 394, + 399, + 548, + 651, + 654, + 805, + 82, + 152, + 163, + 241, + 250, + 331, + 430, + 467, + 474, + 536, + 598, + 634, + 722, + 778, + 857, + 951, + 954, + 104, + 131, + 190, + 354, + 475, + 511, + 574, + 656, + 778, + 801, + 902, + 100, + 296, + 462, + 928, + 9, + 231, + 239, + 263, + 311, + 485, + 614, + 713, + 139, + 238, + 307, + 343, + 349, + 395, + 499, + 678, + 821, + 912, + 166, + 181, + 312, + 491, + 520, + 710, + 752, + 871, + 108, + 306, + 511, + 652, + 679, + 777, + 799, + 19, + 23, + 80, + 92, + 261, + 466, + 558, + 606, + 781, + 844, + 941, + 11, + 89, + 94, + 178, + 257, + 381, + 398, + 586, + 610, + 646, + 817, + 903, + 952, + 988, + 107, + 176, + 296, + 332, + 430, + 434, + 531, + 669, + 807, + 888, + 997, + 124, + 246, + 537, + 650, + 786, + 979, + 194, + 535, + 548, + 560, + 566, + 711, + 760, + 930, + 947, + 143, + 151, + 395, + 872, + 981, + 95, + 107, + 380, + 475, + 552, + 597, + 757, + 804, + 810, + 914, + 96, + 210, + 329, + 445, + 516, + 575, + 609, + 690, + 860, + 913, + 963, + 134, + 197, + 307, + 313, + 414, + 465, + 560, + 639, + 780, + 854, + 946, + 103, + 353, + 413, + 532, + 657, + 689, + 904, + 958, + 990, + 43, + 131, + 142, + 217, + 236, + 406, + 597, + 859, + 61, + 153, + 437, + 468, + 586, + 635, + 670, + 701, + 117, + 138, + 237, + 305, + 358, + 528, + 605, + 613, + 628, + 759, + 771, + 836, + 896, + 968, + 988, + 34, + 82, + 347, + 448, + 461, + 575, + 761, + 910, + 977, + 50, + 103, + 173, + 185, + 287, + 308, + 406, + 462, + 671, + 767, + 789, + 890, + 905, + 548, + 562, + 606, + 653, + 692, + 846, + 114, + 170, + 477, + 549, + 607, + 696, + 945, + 130, + 172, + 175, + 319, + 443, + 480, + 869, + 44, + 65, + 111, + 324, + 413, + 474, + 610, + 627, + 642, + 685, + 807, + 824, + 265, + 465, + 558, + 564, + 614, + 628, + 833, + 916, + 942, + 26, + 70, + 136, + 208, + 492, + 641, + 803, + 912, + 914, + 74, + 168, + 198, + 368, + 376, + 558, + 737, + 783, + 816, + 845, + 959, + 126, + 246, + 406, + 444, + 449, + 517, + 579, + 665, + 772, + 789, + 906, + 988, + 189, + 235, + 374, + 387, + 446, + 456, + 554, + 643, + 685, + 826, + 848, + 893, + 944, + 972, + 21, + 134, + 141, + 304, + 360, + 385, + 409, + 498, + 523, + 659, + 8, + 111, + 156, + 256, + 276, + 342, + 449, + 480, + 543, + 686, + 691, + 863, + 205, + 281, + 302, + 375, + 439, + 492, + 605, + 675, + 707, + 741, + 933, + 966, + 971, + 42, + 381, + 569, + 899, + 902, + 980, + 217, + 321, + 374, + 416, + 482, + 560, + 563, + 626, + 677, + 690, + 780, + 788, + 963, + 57, + 58, + 61, + 77, + 110, + 255, + 326, + 389, + 466, + 476, + 557, + 744, + 791, + 846, + 861, + 967, + 980, + 31, + 99, + 213, + 234, + 282, + 362, + 396, + 702, + 861, + 51, + 102, + 209, + 308, + 335, + 408, + 418, + 511, + 567, + 726, + 758, + 899, + 927, + 940, + 992, + 69, + 132, + 185, + 261, + 358, + 396, + 684, + 872, + 986, + 116, + 149, + 204, + 691, + 814, + 892, + 895, + 914, + 916, + 154, + 224, + 243, + 253, + 282, + 368, + 579, + 654, + 661, + 703, + 735, + 868, + 930, + 29, + 164, + 253, + 277, + 290, + 340, + 626, + 765, + 852, + 173, + 203, + 225, + 282, + 415, + 587, + 595, + 643, + 858, + 874, + 83, + 238, + 314, + 462, + 803, + 822, + 960, + 83, + 362, + 467, + 497, + 666, + 748, + 814, + 76, + 210, + 256, + 374, + 538, + 759, + 833, + 881, + 8, + 57, + 74, + 92, + 117, + 142, + 383, + 649, + 738, + 815, + 821, + 836, + 919, + 13, + 18, + 218, + 342, + 474, + 664, + 723, + 827, + 866, + 147, + 153, + 240, + 404, + 557, + 567, + 591, + 656, + 721, + 757, + 822, + 12, + 98, + 205, + 241, + 376, + 394, + 487, + 494, + 823, + 919, + 74, + 272, + 285, + 362, + 575, + 598, + 873, + 880, + 894, + 119, + 221, + 227, + 291, + 338, + 447, + 507, + 541, + 559, + 620, + 721, + 752, + 802, + 819, + 835, + 843, + 849, + 90, + 130, + 258, + 417, + 481, + 576, + 611, + 826, + 859, + 893, + 950, + 321, + 476, + 528, + 664, + 679, + 752, + 789, + 940, + 951, + 51, + 97, + 144, + 274, + 341, + 384, + 466, + 627, + 642, + 682, + 753, + 766, + 140, + 301, + 310, + 340, + 480, + 669, + 793, + 885, + 887, + 917, + 83, + 115, + 188, + 269, + 272, + 418, + 534, + 546, + 746, + 810, + 869, + 109, + 126, + 185, + 245, + 345, + 750, + 759, + 815, + 854, + 492, + 514, + 609, + 647, + 706, + 726, + 760, + 106, + 176, + 289, + 544, + 753, + 861, + 901, + 47, + 145, + 234, + 253, + 308, + 466, + 467, + 826, + 38, + 89, + 147, + 210, + 254, + 270, + 283, + 453, + 607, + 727, + 828, + 874, + 912, + 915, + 921, + 17, + 201, + 303, + 338, + 815, + 880, + 984, + 100, + 296, + 475, + 490, + 567, + 963, + 979, + 72, + 110, + 120, + 308, + 451, + 622, + 670, + 695, + 696, + 720, + 912, + 981, + 23, + 239, + 255, + 344, + 397, + 847, + 950, + 45, + 141, + 311, + 607, + 626, + 877, + 58, + 87, + 106, + 132, + 210, + 232, + 265, + 373, + 447, + 476, + 621, + 887, + 959, + 134, + 135, + 187, + 189, + 345, + 346, + 411, + 603, + 626, + 901, + 21, + 158, + 177, + 263, + 344, + 408, + 458, + 851, + 855, + 856, + 942, + 971, + 978, + 6, + 23, + 129, + 235, + 368, + 400, + 617, + 962, + 311, + 445, + 457, + 530, + 540, + 650, + 722, + 18, + 118, + 176, + 177, + 337, + 350, + 510, + 771, + 787, + 804, + 839, + 193, + 229, + 261, + 434, + 523, + 528, + 553, + 559, + 660, + 673, + 197, + 400, + 436, + 481, + 556, + 566, + 569, + 627, + 642, + 662, + 866, + 101, + 247, + 354, + 423, + 611, + 669, + 714, + 923, + 323, + 447, + 531, + 561, + 668, + 674, + 700, + 816, + 921, + 27, + 243, + 270, + 324, + 341, + 380, + 546, + 594, + 730, + 877, + 889, + 367, + 683, + 847, + 889, + 897, + 166, + 535, + 574, + 680, + 819, + 949, + 185, + 261, + 266, + 637, + 639, + 669, + 836, + 963, + 990, + 72, + 233, + 450, + 675, + 815, + 826, + 996, + 93, + 129, + 278, + 355, + 405, + 422, + 430, + 550, + 585, + 727, + 783, + 795, + 882, + 51, + 79, + 303, + 308, + 311, + 354, + 449, + 469, + 530, + 553, + 572, + 731, + 757, + 900, + 933, + 255, + 359, + 382, + 405, + 426, + 453, + 680, + 727, + 757, + 195, + 287, + 342, + 445, + 687, + 693, + 824, + 875, + 955, + 986, + 29, + 61, + 154, + 200, + 236, + 287, + 359, + 497, + 568, + 761, + 843, + 965, + 140, + 217, + 301, + 459, + 518, + 647, + 698, + 870, + 880, + 24, + 60, + 158, + 202, + 223, + 333, + 477, + 746, + 749, + 826, + 930, + 265, + 431, + 539, + 588, + 610, + 620, + 900, + 901, + 929, + 13, + 117, + 140, + 170, + 287, + 390, + 438, + 580, + 611, + 659, + 806, + 916, + 930, + 940, + 159, + 296, + 467, + 534, + 639, + 679, + 706, + 878, + 989, + 147, + 533, + 545, + 685, + 741, + 846, + 2, + 34, + 251, + 331, + 424, + 440, + 647, + 694, + 733, + 808, + 866, + 929, + 423, + 571, + 667, + 692, + 996, + 74, + 347, + 424, + 565, + 581, + 618, + 638, + 658, + 681, + 833, + 919, + 936, + 965, + 128, + 307, + 357, + 367, + 412, + 468, + 523, + 571, + 616, + 667, + 683, + 57, + 137, + 197, + 337, + 398, + 606, + 781, + 840, + 850, + 864, + 880, + 948, + 115, + 177, + 229, + 265, + 293, + 303, + 479, + 659, + 667, + 813, + 844, + 953, + 22, + 95, + 274, + 308, + 423, + 485, + 608, + 632, + 688, + 820, + 875, + 945, + 952, + 71, + 234, + 248, + 250, + 497, + 951, + 141, + 170, + 236, + 265, + 394, + 471, + 567, + 703, + 854, + 896, + 897, + 37, + 164, + 271, + 395, + 524, + 793, + 943, + 5, + 109, + 156, + 183, + 293, + 349, + 383, + 533, + 679, + 743, + 114, + 138, + 236, + 316, + 334, + 352, + 489, + 569, + 699, + 755, + 904, + 993, + 314, + 489, + 568, + 658, + 736, + 748, + 848, + 156, + 160, + 252, + 472, + 531, + 613, + 687, + 701, + 740, + 767, + 780, + 841, + 882, + 975, + 990, + 47, + 195, + 363, + 506, + 654, + 767, + 792, + 802, + 150, + 204, + 319, + 379, + 455, + 574, + 843, + 869, + 84, + 116, + 190, + 191, + 193, + 268, + 366, + 409, + 579, + 628, + 767, + 794, + 801, + 823, + 887, + 107, + 176, + 361, + 465, + 467, + 647, + 666, + 700, + 708, + 720, + 754, + 784, + 932, + 959, + 66, + 167, + 196, + 213, + 261, + 319, + 330, + 398, + 416, + 534, + 598, + 677, + 787, + 800, + 910, + 961, + 999, + 404, + 411, + 452, + 536, + 786, + 886, + 940, + 84, + 116, + 236, + 334, + 374, + 433, + 701, + 870, + 73, + 184, + 341, + 367, + 412, + 423, + 673, + 678, + 981, + 258, + 269, + 313, + 360, + 423, + 561, + 602, + 854, + 985, + 112, + 227, + 253, + 256, + 326, + 327, + 517, + 624, + 736, + 891, + 38, + 79, + 361, + 369, + 581, + 583, + 700, + 43, + 100, + 329, + 391, + 722, + 926, + 967, + 972, + 82, + 224, + 254, + 366, + 389, + 755, + 756, + 820, + 942, + 54, + 393, + 405, + 464, + 596, + 663, + 864, + 966, + 108, + 297, + 305, + 368, + 832, + 878, + 903, + 918, + 995, + 324, + 797, + 823, + 871, + 298, + 535, + 642, + 720, + 803, + 910, + 961, + 33, + 319, + 442, + 492, + 568, + 803, + 8, + 84, + 197, + 359, + 435, + 791, + 922, + 949, + 969, + 984, + 210, + 220, + 380, + 904, + 949, + 977, + 984, + 22, + 68, + 83, + 190, + 333, + 468, + 648, + 683, + 783, + 807, + 856, + 959, + 54, + 95, + 180, + 213, + 353, + 417, + 721, + 744, + 888, + 331, + 388, + 441, + 951, + 5, + 86, + 132, + 167, + 224, + 366, + 553, + 655, + 812, + 815, + 989, + 33, + 34, + 183, + 239, + 270, + 529, + 811, + 105, + 117, + 126, + 220, + 280, + 315, + 353, + 201, + 294, + 364, + 511, + 521, + 532, + 557, + 744, + 756, + 846, + 173, + 199, + 436, + 511, + 712, + 725, + 27, + 244, + 262, + 274, + 347, + 404, + 486, + 623, + 857, + 858, + 34, + 126, + 217, + 618, + 674, + 813, + 818, + 830, + 876, + 885, + 63, + 134, + 200, + 269, + 427, + 448, + 486, + 646, + 774, + 778, + 928, + 162, + 229, + 251, + 273, + 277, + 281, + 372, + 448, + 563, + 606, + 641, + 845, + 997, + 81, + 93, + 153, + 516, + 592, + 603, + 641, + 706, + 929, + 945, + 17, + 25, + 109, + 140, + 440, + 524, + 803, + 309, + 494, + 513, + 542, + 778, + 809, + 93, + 161, + 360, + 405, + 507, + 556, + 559, + 734, + 881, + 986, + 53, + 238, + 271, + 320, + 367, + 600, + 768, + 940, + 315, + 351, + 521, + 530, + 548, + 549, + 628, + 881, + 909, + 917, + 246, + 296, + 318, + 324, + 339, + 359, + 393, + 511, + 557, + 690, + 696, + 764, + 777, + 810, + 954, + 73, + 337, + 473, + 526, + 601, + 620, + 668, + 689, + 698, + 768, + 782, + 859, + 930, + 937, + 942, + 954, + 162, + 279, + 410, + 454, + 958, + 29, + 36, + 77, + 109, + 139, + 185, + 224, + 270, + 512, + 601, + 657, + 664, + 669, + 683, + 695, + 734, + 947, + 146, + 193, + 464, + 491, + 767, + 771, + 818, + 911, + 947, + 981, + 56, + 102, + 291, + 434, + 527, + 601, + 613, + 646, + 731, + 777, + 3, + 90, + 179, + 196, + 270, + 380, + 458, + 638, + 680, + 854, + 883, + 956, + 72, + 104, + 272, + 518, + 755, + 33, + 387, + 450, + 519, + 528, + 576, + 607, + 637, + 786, + 228, + 298, + 355, + 377, + 414, + 560, + 847, + 853, + 927, + 47, + 191, + 304, + 328, + 371, + 424, + 441, + 555, + 658, + 837, + 902, + 132, + 215, + 252, + 278, + 293, + 339, + 390, + 729, + 754, + 855, + 896, + 11, + 115, + 159, + 173, + 351, + 407, + 412, + 438, + 996, + 87, + 104, + 164, + 212, + 213, + 329, + 419, + 668, + 683, + 847, + 940, + 134, + 245, + 296, + 306, + 346, + 369, + 382, + 417, + 495, + 555, + 578, + 662, + 712, + 844, + 850, + 885, + 988, + 58, + 212, + 347, + 886, + 925, + 60, + 132, + 301, + 377, + 933, + 26, + 38, + 49, + 94, + 176, + 206, + 344, + 416, + 686, + 719, + 734, + 837, + 32, + 160, + 194, + 481, + 567, + 653, + 711, + 813, + 871, + 946, + 980, + 48, + 53, + 124, + 170, + 281, + 370, + 414, + 501, + 938, + 943, + 951, + 115, + 386, + 540, + 583, + 678, + 729, + 901, + 28, + 105, + 153, + 177, + 178, + 443, + 494, + 496, + 591, + 609, + 628, + 683, + 22, + 144, + 185, + 234, + 306, + 323, + 704, + 830, + 838, + 923, + 940, + 29, + 75, + 140, + 393, + 625, + 760, + 916, + 919, + 15, + 109, + 266, + 846, + 107, + 129, + 278, + 279, + 323, + 438, + 461, + 543, + 567, + 648, + 713, + 866, + 908, + 277, + 320, + 390, + 421, + 549, + 564, + 620, + 885, + 935, + 58, + 322, + 330, + 432, + 435, + 517, + 578, + 704, + 941, + 952, + 89, + 172, + 420, + 511, + 542, + 607, + 654, + 921, + 103, + 240, + 287, + 289, + 302, + 324, + 399, + 415, + 657, + 680, + 764, + 781, + 799, + 824, + 835, + 911, + 36, + 148, + 156, + 170, + 241, + 478, + 600, + 672, + 685, + 764, + 936, + 979, + 106, + 285, + 492, + 493, + 834, + 839, + 873, + 948, + 956, + 35, + 50, + 122, + 176, + 261, + 597, + 621, + 628, + 654, + 935, + 190, + 244, + 301, + 337, + 473, + 646, + 886, + 76, + 193, + 213, + 313, + 331, + 356, + 408, + 449, + 511, + 848, + 853, + 876, + 19, + 109, + 168, + 262, + 269, + 320, + 467, + 642, + 650, + 687, + 703, + 921, + 936, + 973, + 43, + 68, + 305, + 395, + 433, + 534, + 746, + 812, + 815, + 986, + 998, + 165, + 240, + 323, + 346, + 459, + 468, + 474, + 650, + 834, + 919, + 991, + 993, + 36, + 40, + 46, + 195, + 331, + 346, + 844, + 852, + 7, + 216, + 248, + 548, + 637, + 733, + 788, + 810, + 909, + 151, + 205, + 248, + 297, + 381, + 501, + 589, + 601, + 610, + 693, + 851, + 211, + 379, + 508, + 770, + 955, + 17, + 216, + 372, + 471, + 804, + 838, + 934, + 977, + 16, + 119, + 332, + 338, + 478, + 628, + 803, + 911, + 8, + 132, + 144, + 169, + 192, + 713, + 748, + 808, + 824, + 13, + 19, + 31, + 78, + 94, + 513, + 561, + 587, + 825, + 953, + 248, + 254, + 470, + 520, + 594, + 634, + 636, + 647, + 830, + 862, + 869, + 17, + 37, + 62, + 138, + 270, + 337, + 449, + 474, + 540, + 566, + 583, + 721, + 929, + 935, + 954, + 221, + 273, + 315, + 397, + 447, + 641, + 725, + 830, + 885, + 928, + 7, + 175, + 188, + 464, + 482, + 493, + 519, + 612, + 615, + 666, + 758, + 807, + 915, + 70, + 133, + 350, + 438, + 479, + 522, + 564, + 893, + 120, + 273, + 384, + 424, + 446, + 447, + 467, + 585, + 633, + 792, + 948, + 997, + 7, + 51, + 151, + 197, + 232, + 348, + 581, + 596, + 628, + 833, + 890, + 32, + 96, + 265, + 272, + 387, + 691, + 694, + 17, + 322, + 369, + 457, + 499, + 611, + 735, + 813, + 885, + 72, + 84, + 130, + 210, + 228, + 334, + 349, + 396, + 443, + 483, + 498, + 508, + 509, + 762, + 105, + 127, + 157, + 198, + 206, + 286, + 298, + 371, + 380, + 516, + 698, + 738, + 837, + 840, + 946, + 982, + 359, + 436, + 687, + 802, + 805, + 950, + 112, + 113, + 141, + 282, + 290, + 524, + 527, + 624, + 642, + 762, + 840, + 858, + 997, + 30, + 257, + 465, + 573, + 605, + 661, + 752, + 783, + 795, + 880, + 907, + 8, + 101, + 145, + 253, + 375, + 459, + 556, + 559, + 584, + 748, + 999, + 50, + 180, + 388, + 638, + 902, + 122, + 192, + 405, + 468, + 486, + 562, + 604, + 841, + 844, + 134, + 197, + 381, + 382, + 414, + 430, + 431, + 655, + 666, + 807, + 958, + 81, + 210, + 496, + 538, + 724, + 903, + 947, + 51, + 118, + 243, + 326, + 537, + 597, + 836, + 966, + 11, + 139, + 147, + 204, + 214, + 269, + 288, + 290, + 304, + 307, + 334, + 451, + 575, + 600, + 661, + 775, + 800, + 969, + 986, + 64, + 206, + 269, + 403, + 461, + 508, + 548, + 581, + 596, + 692, + 777, + 124, + 232, + 312, + 322, + 447, + 498, + 526, + 543, + 656, + 670, + 712, + 751, + 907, + 923, + 71, + 94, + 114, + 148, + 201, + 249, + 293, + 296, + 331, + 336, + 505, + 607, + 768, + 933, + 217, + 260, + 296, + 302, + 311, + 581, + 625, + 655, + 781, + 892, + 926, + 23, + 43, + 100, + 156, + 273, + 337, + 572, + 673, + 741, + 980, + 52, + 156, + 164, + 336, + 373, + 400, + 470, + 951, + 20, + 30, + 73, + 179, + 351, + 566, + 636, + 872, + 883, + 944, + 11, + 62, + 460, + 482, + 486, + 495, + 512, + 651, + 868, + 917, + 997, + 16, + 74, + 417, + 496, + 590, + 639, + 692, + 778, + 781, + 855, + 928, + 930, + 259, + 275, + 477, + 637, + 748, + 807, + 957, + 999, + 38, + 184, + 260, + 266, + 268, + 323, + 391, + 598, + 628, + 881, + 947, + 54, + 62, + 219, + 270, + 471, + 473, + 491, + 673, + 859, + 892, + 947, + 72, + 218, + 309, + 331, + 372, + 573, + 741, + 822, + 825, + 966, + 48, + 200, + 205, + 237, + 261, + 265, + 338, + 353, + 666, + 928, + 967, + 53, + 74, + 259, + 284, + 507, + 615, + 886, + 905, + 955, + 10, + 21, + 44, + 406, + 460, + 684, + 782, + 816, + 826, + 907, + 34, + 189, + 260, + 332, + 356, + 444, + 460, + 758, + 781, + 838, + 842, + 905, + 967, + 6, + 7, + 169, + 220, + 295, + 384, + 399, + 442, + 739, + 922, + 969, + 286, + 300, + 401, + 460, + 503, + 659, + 686, + 727, + 749, + 785, + 974, + 993, + 998, + 183, + 210, + 328, + 450, + 453, + 480, + 496, + 517, + 525, + 549, + 635, + 716, + 732, + 748, + 749, + 832, + 959, + 95, + 107, + 121, + 258, + 326, + 416, + 588, + 654, + 753, + 831, + 34, + 83, + 101, + 181, + 224, + 552, + 623, + 671, + 866, + 983, + 997, + 104, + 129, + 143, + 198, + 213, + 420, + 438, + 612, + 674, + 910, + 943, + 210, + 212, + 218, + 321, + 330, + 455, + 692, + 794, + 839, + 960, + 965, + 17, + 101, + 124, + 395, + 476, + 513, + 514, + 566, + 692, + 846, + 856, + 859, + 862, + 908, + 920, + 947, + 958, + 8, + 200, + 373, + 462, + 556, + 739, + 796, + 932, + 951, + 958, + 44, + 56, + 186, + 262, + 310, + 355, + 380, + 470, + 593, + 714, + 906, + 964, + 989, + 65, + 114, + 195, + 306, + 307, + 355, + 403, + 469, + 513, + 654, + 685, + 800, + 812, + 816, + 825, + 843, + 925, + 3, + 328, + 425, + 486, + 730, + 773, + 789, + 824, + 943, + 966, + 967, + 981, + 984, + 83, + 156, + 311, + 439, + 545, + 565, + 650, + 682, + 769, + 299, + 341, + 409, + 782, + 943, + 5, + 52, + 57, + 123, + 146, + 175, + 409, + 443, + 532, + 989, + 120, + 158, + 430, + 436, + 449, + 640, + 659, + 734, + 749, + 834, + 882, + 911, + 952, + 22, + 226, + 442, + 591, + 879, + 51, + 69, + 86, + 97, + 178, + 263, + 316, + 425, + 534, + 554, + 565, + 888, + 988, + 991, + 24, + 352, + 511, + 522, + 555, + 570, + 603, + 696, + 887, + 960, + 39, + 133, + 260, + 401, + 465, + 526, + 609, + 732, + 131, + 206, + 305, + 669, + 809, + 877, + 986, + 439, + 520, + 567, + 588, + 617, + 712, + 891, + 998, + 274, + 358, + 425, + 495, + 715, + 872, + 918, + 923, + 951, + 980, + 983, + 119, + 123, + 316, + 324, + 349, + 644, + 705, + 718, + 769, + 781, + 795, + 884, + 110, + 133, + 140, + 152, + 157, + 495, + 569, + 608, + 629, + 803, + 827, + 909, + 942, + 9, + 230, + 268, + 423, + 626, + 707, + 724, + 748, + 828, + 996, + 274, + 308, + 436, + 722, + 879, + 213, + 259, + 324, + 329, + 377, + 534, + 588, + 827, + 896, + 149, + 261, + 591, + 597, + 785, + 813, + 883, + 920, + 996, + 10, + 64, + 237, + 417, + 535, + 686, + 709, + 717, + 744, + 41, + 67, + 260, + 370, + 405, + 407, + 520, + 632, + 893, + 955, + 127, + 250, + 336, + 354, + 388, + 474, + 591, + 703, + 805, + 811, + 833, + 871, + 881, + 991, + 994, + 17, + 91, + 113, + 122, + 300, + 301, + 463, + 716, + 741, + 776, + 784, + 906, + 994, + 33, + 57, + 206, + 448, + 520, + 612, + 769, + 834, + 282, + 393, + 441, + 461, + 503, + 796, + 72, + 206, + 304, + 381, + 565, + 723, + 114, + 121, + 130, + 259, + 346, + 386, + 432, + 538, + 575, + 595, + 855, + 945 +}; +const double x[1000] = { + 602, + 730, + 528, + 886, + 890, + 755, + 124, + 435, + 24, + 245, + 112, + 144, + 171, + 746, + 547, + 172, + 905, + 97, + 70, + 133, + 117, + 951, + 783, + 271, + 174, + 263, + 769, + 889, + 920, + 698, + 644, + 138, + 34, + 866, + 831, + 249, + 611, + 672, + 502, + 450, + 225, + 557, + 793, + 244, + 336, + 942, + 604, + 135, + 507, + 328, + 36, + 299, + 769, + 323, + 957, + 171, + 455, + 627, + 701, + 624, + 383, + 354, + 675, + 971, + 562, + 945, + 354, + 90, + 495, + 269, + 684, + 468, + 832, + 38, + 189, + 103, + 509, + 754, + 85, + 70, + 727, + 897, + 441, + 745, + 443, + 561, + 23, + 796, + 104, + 178, + 388, + 178, + 663, + 652, + 533, + 738, + 423, + 500, + 390, + 567, + 834, + 806, + 97, + 517, + 352, + 636, + 158, + 839, + 822, + 68, + 707, + 838, + 778, + 15, + 201, + 364, + 397, + 166, + 372, + 39, + 525, + 360, + 596, + 664, + 606, + 182, + 684, + 147, + 941, + 695, + 815, + 721, + 377, + 215, + 386, + 265, + 598, + 890, + 241, + 302, + 423, + 623, + 610, + 26, + 311, + 887, + 496, + 968, + 549, + 581, + 421, + 638, + 154, + 471, + 768, + 953, + 7, + 906, + 894, + 155, + 687, + 813, + 376, + 463, + 815, + 436, + 817, + 5, + 366, + 412, + 435, + 825, + 437, + 614, + 437, + 14, + 492, + 117, + 610, + 0, + 837, + 665, + 464, + 847, + 513, + 606, + 532, + 503, + 566, + 270, + 559, + 509, + 634, + 339, + 535, + 708, + 663, + 1, + 837, + 508, + 499, + 216, + 758, + 36, + 242, + 351, + 432, + 439, + 562, + 307, + 643, + 498, + 659, + 16, + 265, + 653, + 105, + 527, + 595, + 448, + 832, + 381, + 714, + 533, + 178, + 644, + 455, + 667, + 7, + 378, + 639, + 19, + 50, + 415, + 591, + 827, + 956, + 69, + 712, + 767, + 368, + 552, + 230, + 288, + 146, + 676, + 651, + 333, + 284, + 782, + 283, + 774, + 791, + 451, + 795, + 991, + 618, + 620, + 547, + 769, + 226, + 563, + 117, + 524, + 287, + 615, + 322, + 41, + 582, + 156, + 664, + 261, + 368, + 702, + 25, + 439, + 382, + 123, + 682, + 970, + 511, + 928, + 870, + 453, + 865, + 724, + 255, + 504, + 567, + 105, + 465, + 146, + 349, + 616, + 419, + 389, + 629, + 964, + 482, + 483, + 252, + 183, + 300, + 578, + 255, + 825, + 702, + 650, + 468, + 808, + 939, + 360, + 830, + 281, + 969, + 139, + 488, + 603, + 449, + 731, + 941, + 172, + 643, + 569, + 90, + 966, + 468, + 818, + 249, + 649, + 661, + 661, + 955, + 52, + 17, + 364, + 472, + 854, + 154, + 543, + 110, + 327, + 905, + 715, + 940, + 612, + 248, + 634, + 690, + 326, + 622, + 52, + 935, + 244, + 406, + 604, + 351, + 303, + 268, + 717, + 247, + 475, + 718, + 835, + 885, + 534, + 842, + 942, + 929, + 713, + 786, + 72, + 122, + 443, + 64, + 512, + 38, + 189, + 552, + 935, + 778, + 832, + 569, + 144, + 810, + 634, + 399, + 261, + 918, + 728, + 648, + 340, + 730, + 358, + 496, + 928, + 344, + 929, + 572, + 876, + 667, + 933, + 584, + 122, + 739, + 978, + 37, + 250, + 192, + 113, + 763, + 214, + 852, + 365, + 638, + 570, + 82, + 861, + 448, + 649, + 813, + 950, + 843, + 154, + 527, + 12, + 953, + 153, + 311, + 177, + 490, + 754, + 973, + 511, + 777, + 649, + 605, + 311, + 539, + 133, + 245, + 940, + 717, + 851, + 189, + 905, + 410, + 214, + 170, + 983, + 998, + 404, + 599, + 843, + 41, + 955, + 505, + 916, + 947, + 851, + 397, + 194, + 288, + 781, + 897, + 546, + 305, + 113, + 356, + 454, + 679, + 774, + 314, + 897, + 452, + 169, + 391, + 344, + 880, + 840, + 327, + 404, + 29, + 353, + 688, + 196, + 135, + 860, + 878, + 288, + 523, + 335, + 1, + 680, + 923, + 480, + 108, + 10, + 188, + 165, + 500, + 331, + 668, + 279, + 939, + 797, + 203, + 925, + 768, + 310, + 453, + 213, + 909, + 769, + 136, + 93, + 501, + 926, + 249, + 888, + 591, + 628, + 317, + 668, + 364, + 375, + 951, + 432, + 217, + 765, + 469, + 458, + 25, + 330, + 279, + 734, + 995, + 187, + 150, + 739, + 179, + 551, + 844, + 920, + 871, + 906, + 397, + 540, + 376, + 123, + 233, + 19, + 227, + 109, + 158, + 20, + 11, + 899, + 462, + 655, + 837, + 756, + 930, + 580, + 304, + 655, + 419, + 695, + 319, + 496, + 856, + 575, + 700, + 223, + 793, + 462, + 666, + 274, + 967, + 650, + 287, + 521, + 69, + 898, + 684, + 759, + 31, + 373, + 515, + 56, + 966, + 971, + 836, + 950, + 94, + 647, + 948, + 766, + 988, + 556, + 458, + 415, + 46, + 741, + 519, + 186, + 393, + 409, + 658, + 349, + 833, + 339, + 61, + 250, + 49, + 63, + 503, + 21, + 951, + 809, + 391, + 242, + 739, + 823, + 9, + 548, + 876, + 431, + 920, + 451, + 967, + 291, + 529, + 37, + 133, + 656, + 240, + 981, + 223, + 167, + 458, + 624, + 473, + 570, + 942, + 260, + 808, + 16, + 792, + 699, + 537, + 84, + 906, + 429, + 728, + 320, + 785, + 301, + 9, + 679, + 882, + 98, + 431, + 223, + 920, + 173, + 895, + 605, + 68, + 698, + 696, + 987, + 855, + 191, + 657, + 533, + 478, + 321, + 846, + 921, + 490, + 278, + 145, + 500, + 274, + 974, + 505, + 33, + 936, + 691, + 922, + 140, + 846, + 951, + 745, + 893, + 803, + 316, + 689, + 960, + 509, + 518, + 911, + 121, + 12, + 477, + 702, + 94, + 521, + 751, + 840, + 492, + 666, + 922, + 714, + 43, + 683, + 871, + 531, + 774, + 137, + 914, + 745, + 722, + 78, + 398, + 384, + 536, + 365, + 245, + 807, + 925, + 201, + 917, + 368, + 214, + 246, + 143, + 388, + 937, + 483, + 480, + 793, + 415, + 835, + 554, + 514, + 838, + 655, + 837, + 481, + 483, + 777, + 447, + 963, + 596, + 248, + 819, + 696, + 540, + 163, + 333, + 589, + 863, + 603, + 835, + 952, + 253, + 329, + 552, + 207, + 684, + 593, + 618, + 742, + 53, + 90, + 27, + 955, + 217, + 955, + 20, + 520, + 221, + 316, + 45, + 948, + 552, + 110, + 594, + 774, + 517, + 880, + 32, + 575, + 852, + 463, + 685, + 10, + 58, + 945, + 572, + 875, + 633, + 942, + 880, + 426, + 283, + 491, + 848, + 491, + 280, + 412, + 1, + 819, + 199, + 190, + 577, + 488, + 936, + 678, + 79, + 317, + 408, + 689, + 353, + 889, + 294, + 561, + 501, + 411, + 554, + 321, + 193, + 748, + 309, + 110, + 454, + 33, + 28, + 193, + 166, + 804, + 710, + 581, + 70, + 726, + 805, + 673, + 751, + 147, + 793, + 395, + 151, + 129, + 143, + 610, + 700, + 590, + 577, + 814, + 104, + 990, + 56, + 254, + 816, + 278, + 108, + 765, + 31, + 208, + 804, + 730, + 960, + 323, + 152, + 202, + 449, + 238, + 907, + 532, + 618, + 377, + 295, + 625, + 252, + 383, + 345, + 46, + 934, + 908, + 851, + 304, + 235, + 623, + 808, + 363, + 80, + 373, + 858, + 839, + 385, + 426, + 727, + 615, + 675, + 860, + 602, + 623, + 780, + 246, + 22, + 681, + 623, + 293, + 421, + 908, + 419, + 811, + 631, + 155, + 139, + 861, + 262, + 789, + 344, + 507, + 14, + 445, + 995, + 316, + 74, + 32, + 239, + 932, + 586, + 167, + 578, + 555, + 8, + 720, + 804, + 18, + 185, + 637, + 185, + 21, + 121, + 993, + 457, + 0, + 911, + 330, + 214, + 343, + 600, + 720, + 645, + 542, + 991, + 704, + 261, + 481, + 242, + 949, + 909, + 745, + 799, + 644, + 858, + 132, + 886, + 194, + 886, + 695, + 912, + 980, + 956, + 51, + 885, + 410, + 88, + 578, + 636, + 698, + 636, + 532, + 579, + 389, + 124, + 386, + 54, + 616, + 203, + 838, + 732, + 152, + 775, + 749, + 373 +}; +const int ptr[1001] = { + 0, + 6, + 18, + 31, + 40, + 49, + 58, + 67, + 75, + 85, + 98, + 111, + 121, + 135, + 139, + 146, + 159, + 169, + 175, + 181, + 191, + 203, + 210, + 217, + 228, + 238, + 245, + 254, + 265, + 278, + 290, + 298, + 311, + 323, + 332, + 343, + 353, + 360, + 370, + 383, + 396, + 407, + 415, + 427, + 433, + 440, + 449, + 461, + 467, + 474, + 487, + 503, + 510, + 522, + 530, + 542, + 549, + 556, + 570, + 584, + 594, + 605, + 614, + 624, + 629, + 637, + 644, + 653, + 663, + 674, + 685, + 691, + 701, + 712, + 723, + 734, + 746, + 754, + 766, + 779, + 788, + 802, + 809, + 820, + 831, + 846, + 860, + 869, + 874, + 883, + 886, + 900, + 915, + 929, + 937, + 946, + 955, + 969, + 985, + 993, + 1004, + 1014, + 1026, + 1035, + 1040, + 1053, + 1064, + 1073, + 1078, + 1089, + 1097, + 1105, + 1108, + 1119, + 1131, + 1143, + 1156, + 1165, + 1175, + 1187, + 1196, + 1205, + 1209, + 1218, + 1230, + 1242, + 1253, + 1263, + 1277, + 1288, + 1306, + 1323, + 1331, + 1345, + 1355, + 1362, + 1372, + 1380, + 1388, + 1395, + 1412, + 1424, + 1428, + 1436, + 1443, + 1457, + 1473, + 1488, + 1498, + 1511, + 1520, + 1533, + 1543, + 1556, + 1567, + 1578, + 1590, + 1598, + 1609, + 1618, + 1627, + 1634, + 1638, + 1643, + 1649, + 1654, + 1660, + 1675, + 1688, + 1698, + 1712, + 1722, + 1730, + 1738, + 1746, + 1758, + 1765, + 1778, + 1787, + 1802, + 1814, + 1821, + 1833, + 1842, + 1851, + 1864, + 1877, + 1886, + 1890, + 1898, + 1904, + 1916, + 1931, + 1942, + 1953, + 1966, + 1975, + 1988, + 1999, + 2008, + 2021, + 2027, + 2036, + 2049, + 2058, + 2069, + 2078, + 2086, + 2099, + 2109, + 2115, + 2123, + 2133, + 2142, + 2155, + 2166, + 2175, + 2185, + 2191, + 2202, + 2215, + 2220, + 2234, + 2248, + 2260, + 2271, + 2277, + 2285, + 2297, + 2310, + 2318, + 2328, + 2337, + 2352, + 2358, + 2370, + 2378, + 2391, + 2397, + 2407, + 2413, + 2425, + 2434, + 2442, + 2452, + 2462, + 2476, + 2480, + 2487, + 2500, + 2512, + 2525, + 2533, + 2545, + 2552, + 2563, + 2576, + 2585, + 2591, + 2599, + 2608, + 2619, + 2629, + 2643, + 2658, + 2664, + 2675, + 2682, + 2696, + 2705, + 2715, + 2718, + 2736, + 2746, + 2765, + 2771, + 2787, + 2793, + 2802, + 2813, + 2826, + 2837, + 2849, + 2863, + 2870, + 2885, + 2895, + 2904, + 2914, + 2925, + 2931, + 2944, + 2949, + 2957, + 2973, + 2982, + 2995, + 3009, + 3025, + 3031, + 3046, + 3061, + 3069, + 3082, + 3089, + 3100, + 3106, + 3116, + 3119, + 3123, + 3130, + 3136, + 3144, + 3153, + 3162, + 3180, + 3185, + 3200, + 3205, + 3215, + 3225, + 3234, + 3246, + 3255, + 3266, + 3273, + 3283, + 3293, + 3303, + 3312, + 3320, + 3331, + 3342, + 3349, + 3357, + 3367, + 3372, + 3380, + 3387, + 3398, + 3405, + 3417, + 3425, + 3432, + 3443, + 3449, + 3456, + 3461, + 3471, + 3480, + 3491, + 3498, + 3521, + 3530, + 3539, + 3554, + 3562, + 3569, + 3579, + 3585, + 3597, + 3604, + 3613, + 3628, + 3646, + 3657, + 3673, + 3681, + 3691, + 3696, + 3709, + 3717, + 3731, + 3745, + 3756, + 3763, + 3769, + 3774, + 3786, + 3799, + 3810, + 3819, + 3827, + 3838, + 3854, + 3867, + 3876, + 3885, + 3902, + 3911, + 3926, + 3936, + 3948, + 3959, + 3970, + 3983, + 3991, + 4002, + 4009, + 4023, + 4032, + 4043, + 4058, + 4065, + 4078, + 4087, + 4099, + 4106, + 4114, + 4120, + 4132, + 4146, + 4155, + 4168, + 4177, + 4189, + 4199, + 4212, + 4219, + 4231, + 4241, + 4253, + 4260, + 4266, + 4278, + 4287, + 4303, + 4310, + 4322, + 4334, + 4344, + 4354, + 4368, + 4376, + 4383, + 4399, + 4408, + 4416, + 4431, + 4444, + 4458, + 4467, + 4474, + 4486, + 4495, + 4506, + 4515, + 4521, + 4536, + 4549, + 4564, + 4571, + 4580, + 4593, + 4602, + 4613, + 4618, + 4627, + 4635, + 4644, + 4659, + 4664, + 4675, + 4684, + 4690, + 4702, + 4713, + 4723, + 4735, + 4743, + 4751, + 4759, + 4768, + 4779, + 4790, + 4799, + 4811, + 4818, + 4823, + 4830, + 4838, + 4850, + 4861, + 4870, + 4878, + 4890, + 4897, + 4908, + 4916, + 4930, + 4939, + 4950, + 4959, + 4971, + 4977, + 4985, + 4996, + 4999, + 5003, + 5012, + 5018, + 5026, + 5041, + 5048, + 5058, + 5071, + 5081, + 5086, + 5094, + 5099, + 5109, + 5114, + 5127, + 5137, + 5147, + 5162, + 5172, + 5179, + 5187, + 5197, + 5209, + 5226, + 5231, + 5239, + 5248, + 5263, + 5270, + 5283, + 5293, + 5301, + 5308, + 5318, + 5327, + 5342, + 5349, + 5357, + 5367, + 5374, + 5381, + 5395, + 5406, + 5418, + 5428, + 5435, + 5440, + 5452, + 5464, + 5477, + 5490, + 5497, + 5504, + 5510, + 5518, + 5529, + 5542, + 5561, + 5579, + 5588, + 5599, + 5601, + 5609, + 5618, + 5627, + 5631, + 5640, + 5646, + 5654, + 5661, + 5672, + 5690, + 5699, + 5712, + 5723, + 5733, + 5742, + 5752, + 5759, + 5766, + 5776, + 5788, + 5799, + 5801, + 5813, + 5825, + 5829, + 5841, + 5846, + 5858, + 5867, + 5878, + 5892, + 5902, + 5910, + 5921, + 5933, + 5941, + 5957, + 5964, + 5975, + 5988, + 6000, + 6007, + 6019, + 6027, + 6036, + 6046, + 6055, + 6065, + 6080, + 6090, + 6098, + 6110, + 6122, + 6139, + 6151, + 6160, + 6168, + 6181, + 6190, + 6202, + 6209, + 6221, + 6228, + 6238, + 6249, + 6260, + 6266, + 6274, + 6289, + 6302, + 6310, + 6325, + 6334, + 6349, + 6367, + 6370, + 6382, + 6391, + 6399, + 6414, + 6423, + 6435, + 6442, + 6452, + 6461, + 6469, + 6479, + 6493, + 6502, + 6517, + 6524, + 6539, + 6549, + 6555, + 6561, + 6568, + 6575, + 6594, + 6605, + 6613, + 6620, + 6626, + 6637, + 6643, + 6656, + 6669, + 6679, + 6687, + 6698, + 6706, + 6715, + 6730, + 6739, + 6746, + 6762, + 6768, + 6776, + 6785, + 6791, + 6798, + 6805, + 6818, + 6827, + 6836, + 6846, + 6853, + 6861, + 6877, + 6885, + 6894, + 6901, + 6912, + 6924, + 6937, + 6947, + 6951, + 6966, + 6975, + 6985, + 6996, + 7003, + 7019, + 7029, + 7037, + 7046, + 7053, + 7060, + 7068, + 7075, + 7081, + 7088, + 7094, + 7108, + 7117, + 7123, + 7139, + 7150, + 7162, + 7168, + 7182, + 7191, + 7203, + 7219, + 7222, + 7229, + 7243, + 7251, + 7260, + 7269, + 7279, + 7289, + 7294, + 7307, + 7321, + 7338, + 7349, + 7353, + 7361, + 7371, + 7379, + 7386, + 7397, + 7411, + 7422, + 7428, + 7437, + 7442, + 7452, + 7463, + 7474, + 7483, + 7491, + 7499, + 7514, + 7523, + 7536, + 7542, + 7549, + 7556, + 7568, + 7577, + 7586, + 7597, + 7609, + 7623, + 7633, + 7645, + 7658, + 7664, + 7677, + 7694, + 7703, + 7718, + 7727, + 7736, + 7749, + 7758, + 7768, + 7775, + 7782, + 7790, + 7803, + 7812, + 7823, + 7833, + 7842, + 7859, + 7870, + 7879, + 7891, + 7901, + 7912, + 7921, + 7928, + 7935, + 7943, + 7958, + 7965, + 7972, + 7984, + 7991, + 7997, + 8010, + 8020, + 8033, + 8041, + 8048, + 8059, + 8069, + 8080, + 8088, + 8097, + 8108, + 8113, + 8119, + 8128, + 8135, + 8148, + 8163, + 8172, + 8182, + 8194, + 8203, + 8214, + 8223, + 8237, + 8246, + 8252, + 8264, + 8269, + 8282, + 8293, + 8305, + 8317, + 8330, + 8336, + 8347, + 8354, + 8364, + 8376, + 8383, + 8398, + 8406, + 8414, + 8429, + 8443, + 8460, + 8467, + 8475, + 8484, + 8493, + 8503, + 8510, + 8518, + 8527, + 8535, + 8544, + 8548, + 8555, + 8561, + 8571, + 8578, + 8590, + 8599, + 8603, + 8614, + 8621, + 8628, + 8638, + 8644, + 8654, + 8664, + 8675, + 8688, + 8698, + 8705, + 8711, + 8721, + 8729, + 8739, + 8754, + 8770, + 8775, + 8792, + 8802, + 8812, + 8824, + 8829, + 8838, + 8847, + 8858, + 8869, + 8878, + 8889, + 8906, + 8911, + 8916, + 8928, + 8939, + 8950, + 8957, + 8969, + 8980, + 8988, + 8992, + 9005, + 9014, + 9024, + 9032, + 9048, + 9060, + 9069, + 9079, + 9086, + 9098, + 9112, + 9123, + 9135, + 9143, + 9152, + 9163, + 9168, + 9176, + 9184, + 9193, + 9203, + 9214, + 9229, + 9239, + 9252, + 9260, + 9272, + 9283, + 9290, + 9299, + 9313, + 9329, + 9335, + 9348, + 9359, + 9370, + 9375, + 9384, + 9395, + 9402, + 9410, + 9429, + 9440, + 9454, + 9468, + 9479, + 9489, + 9497, + 9507, + 9518, + 9530, + 9538, + 9549, + 9560, + 9570, + 9581, + 9590, + 9600, + 9613, + 9624, + 9637, + 9654, + 9664, + 9675, + 9686, + 9697, + 9714, + 9724, + 9737, + 9754, + 9767, + 9776, + 9781, + 9791, + 9804, + 9809, + 9823, + 9833, + 9841, + 9848, + 9856, + 9867, + 9879, + 9892, + 9902, + 9907, + 9916, + 9925, + 9934, + 9944, + 9959, + 9972, + 9980, + 9986, + 9992, + 10004 +}; +const double verify_data[1000] = { + 1971101, + 3601995, + 3608374, + 3068439, + 2756891, + 1644445, + 2326970, + 3571797, + 2167311, + 3272467, + 5257490, + 2287052, + 5507394, + 1707471, + 1181529, + 2596954, + 2999820, + 1456597, + 1755714, + 2783599, + 2224880, + 953747, + 1863442, + 2375479, + 3838149, + 1472958, + 2613759, + 1412651, + 2454897, + 4139599, + 1540527, + 2373885, + 2371153, + 2496043, + 2946006, + 3041837, + 2102841, + 3413598, + 3937131, + 3428786, + 2323528, + 1657458, + 3358521, + 1821261, + 937257, + 2638848, + 3351703, + 2436591, + 1387045, + 3372777, + 4422352, + 2696491, + 2775768, + 1711500, + 2463910, + 1906176, + 2655972, + 2176802, + 4025605, + 1836921, + 2902963, + 1950818, + 2553243, + 2012524, + 2449182, + 1632320, + 2628093, + 1093587, + 3089207, + 3020390, + 1485696, + 1932818, + 3334949, + 1610563, + 2076427, + 3114683, + 1548840, + 3339439, + 3335032, + 1366398, + 1685659, + 1668385, + 2510712, + 2871270, + 3270369, + 4311377, + 1982006, + 1326681, + 1381634, + 398901, + 3333661, + 3352243, + 2878790, + 1577319, + 2415255, + 1191188, + 3219765, + 3467850, + 1940862, + 2056258, + 1786527, + 2278347, + 2077897, + 1457888, + 3707208, + 1405999, + 952210, + 1600564, + 2343319, + 1781556, + 2474389, + 522450, + 3674982, + 3619187, + 3211390, + 3586103, + 1475431, + 3546147, + 3698208, + 2049193, + 1979189, + 1111515, + 2790498, + 3439083, + 4279066, + 2774436, + 2077245, + 4390617, + 3149593, + 5326535, + 3848199, + 2772446, + 2682304, + 2277814, + 1222790, + 2067874, + 1982666, + 2371257, + 1270393, + 3228410, + 2598823, + 2428645, + 904561, + 2100006, + 2337148, + 3164102, + 3908197, + 1529402, + 3084375, + 1927419, + 3196639, + 2303890, + 4265937, + 2061281, + 2212135, + 2407656, + 1723976, + 2903704, + 3276733, + 1491735, + 1684162, + 1307018, + 1201185, + 636997, + 1186016, + 1774809, + 2607471, + 2619840, + 3493545, + 3226129, + 1737347, + 2380184, + 1201957, + 983240, + 2529069, + 2689857, + 3022018, + 2223714, + 3625235, + 3008732, + 2417998, + 4428750, + 2270952, + 2186948, + 4812008, + 2233927, + 3334976, + 1264519, + 1626345, + 1123879, + 3098605, + 4036407, + 3104973, + 2897790, + 3788865, + 2422217, + 3611590, + 1749696, + 2447434, + 2977777, + 1573650, + 2620107, + 2319242, + 2902283, + 1882200, + 1787017, + 2436605, + 3467551, + 2413830, + 187567, + 2242075, + 1754385, + 1836061, + 4245412, + 3751015, + 2715151, + 1557751, + 421948, + 2963355, + 2050843, + 1758567, + 2680768, + 4076059, + 4484640, + 3293151, + 1433126, + 1649435, + 4409656, + 2223098, + 2455979, + 1874200, + 2098066, + 4020158, + 1312572, + 2801068, + 3341899, + 3785087, + 1569098, + 2778159, + 1992179, + 2669866, + 1914494, + 1619868, + 2274333, + 1857912, + 3099797, + 809499, + 1679713, + 3531350, + 2599926, + 1970143, + 2920228, + 2883295, + 1394658, + 3554897, + 3534392, + 1625041, + 1492274, + 1451033, + 2248274, + 2910569, + 2341827, + 2768016, + 3567361, + 781606, + 2434644, + 1782504, + 4124675, + 3646132, + 2864945, + 512560, + 3618571, + 2223074, + 4315721, + 1195043, + 4737421, + 1748427, + 3474050, + 1798506, + 4916152, + 2411793, + 3382242, + 5132409, + 810557, + 4870878, + 1368859, + 2955757, + 1940419, + 3146202, + 880792, + 3448573, + 1017493, + 2481321, + 3652309, + 3475252, + 2845994, + 3182841, + 5898263, + 1771223, + 3346757, + 2512678, + 1778448, + 3432671, + 2814247, + 3403195, + 812303, + 2104162, + 85040, + 989115, + 1897384, + 1248980, + 2002961, + 1371732, + 2373820, + 5178478, + 1511192, + 5127654, + 1468260, + 2185303, + 2436412, + 2978141, + 2230665, + 1707852, + 2529167, + 1152196, + 3239187, + 2498749, + 2707774, + 1502699, + 1633289, + 2782744, + 4089832, + 1548833, + 1704769, + 2712629, + 992084, + 1369606, + 2480517, + 2846051, + 3100172, + 2371224, + 1173652, + 1837754, + 3822172, + 1417367, + 1538908, + 1146694, + 2528965, + 2800885, + 3461160, + 786155, + 6573509, + 3071638, + 1511640, + 3652853, + 1475533, + 1525596, + 2695806, + 1277883, + 3278333, + 2226936, + 2030339, + 3914645, + 4318373, + 2059669, + 3961569, + 1772074, + 3135802, + 1261862, + 4771438, + 1587528, + 2435428, + 2869031, + 2629400, + 1533986, + 1866116, + 1203541, + 2007311, + 4295134, + 3082652, + 2127515, + 3110833, + 2895900, + 4701588, + 2727753, + 2324739, + 2142817, + 4359375, + 2762710, + 2675084, + 2776056, + 2906201, + 2859945, + 1471060, + 3224362, + 2455374, + 2030195, + 909337, + 2716237, + 2230075, + 3070171, + 4476596, + 2646370, + 3421732, + 2163616, + 4043766, + 2111374, + 2016619, + 1318843, + 3586217, + 3000490, + 2914687, + 2728187, + 3496083, + 3137438, + 1555757, + 2975780, + 864871, + 3568793, + 3273559, + 4362169, + 1225951, + 1858409, + 1867854, + 2081582, + 4028493, + 1772236, + 2634979, + 3563733, + 1734270, + 2430471, + 3597625, + 1010411, + 1086456, + 3717761, + 3038402, + 1630224, + 4565438, + 3347069, + 2543316, + 3034145, + 1190307, + 3710367, + 2894919, + 4122408, + 1917891, + 1308296, + 1847812, + 2799933, + 5544619, + 990734, + 2302389, + 2828494, + 2767749, + 2734181, + 1584801, + 2096227, + 2132396, + 1605917, + 3953389, + 489065, + 3370917, + 1246610, + 1859633, + 3905768, + 2375583, + 2352791, + 3066605, + 3023804, + 1714567, + 1630198, + 3244096, + 3311209, + 2837076, + 1806523, + 3111912, + 924345, + 891749, + 1710635, + 2779972, + 2288984, + 2104226, + 2726511, + 2994247, + 4159385, + 927922, + 3372483, + 2093351, + 3228595, + 1549615, + 3203118, + 1566786, + 2046013, + 1122663, + 902592, + 2101848, + 633763, + 1382735, + 2235887, + 1595380, + 1684910, + 4534882, + 1927642, + 3881319, + 4091228, + 3489550, + 1186206, + 1089968, + 1673520, + 2908231, + 1060251, + 4422500, + 2814892, + 2014163, + 3954105, + 2685902, + 1427353, + 1040905, + 2481509, + 2984177, + 5050926, + 1266027, + 2158372, + 2317752, + 4020554, + 1226253, + 3034218, + 3335936, + 3282626, + 1782262, + 3007006, + 2399815, + 4116453, + 1101525, + 2175742, + 1919181, + 1935647, + 3021439, + 2975812, + 1409385, + 3435714, + 2843659, + 2535310, + 973352, + 4051148, + 3198667, + 3025227, + 3821291, + 2634495, + 1066026, + 1015860, + 2374721, + 1893315, + 2896157, + 5768610, + 4638503, + 1096525, + 2521763, + 201516, + 1885950, + 2456554, + 2395576, + 1805310, + 3539192, + 706652, + 3652867, + 1803915, + 2740108, + 4902727, + 2480670, + 4763486, + 2831231, + 2804267, + 2958655, + 1180330, + 1377988, + 1967048, + 3251495, + 3641699, + 2327118, + 518996, + 3627226, + 4512513, + 821503, + 4513458, + 1746977, + 3396668, + 2072470, + 3064446, + 4435618, + 2734309, + 2193304, + 4275484, + 3468741, + 2498396, + 3068739, + 1699359, + 2816909, + 2705770, + 2392503, + 1288021, + 2667346, + 1722567, + 2924017, + 3160472, + 1098169, + 3756129, + 5913618, + 3768712, + 2089078, + 2340072, + 2483109, + 4368798, + 2778403, + 1706517, + 2503001, + 2633764, + 2488649, + 3759253, + 1596753, + 1671868, + 1377167, + 2721074, + 2026518, + 3148597, + 1753515, + 2407030, + 3191030, + 3974792, + 1798541, + 4805468, + 2569249, + 4324091, + 3385093, + 745588, + 2231981, + 2000465, + 2339460, + 3327609, + 3719613, + 4276833, + 1018769, + 2495582, + 2942706, + 2035953, + 2227503, + 3631249, + 2988856, + 2784977, + 1822310, + 4621193, + 2352625, + 1249877, + 1540945, + 1241921, + 1994350, + 5628798, + 1620488, + 1897543, + 952310, + 1052254, + 3358187, + 2994928, + 2959189, + 2720309, + 2875425, + 2144130, + 4548462, + 2048162, + 1339841, + 4090958, + 1862715, + 1268274, + 4042390, + 1581631, + 2874452, + 1735445, + 1588799, + 1331885, + 2179684, + 5179645, + 1959366, + 2027198, + 2755029, + 2265692, + 2335785, + 4348426, + 1879924, + 2696539, + 1106357, + 2932568, + 2492358, + 3120132, + 3691105, + 1442767, + 4534420, + 2112951, + 2625910, + 3375099, + 1555111, + 4988419, + 1174798, + 1332818, + 1869705, + 1696774, + 1175511, + 1819161, + 1548388, + 1420761, + 1580164, + 943541, + 4405558, + 2240390, + 1501984, + 4062955, + 3082580, + 2967491, + 1152855, + 3788527, + 2868984, + 4078134, + 3701904, + 752170, + 1758523, + 3256074, + 2335111, + 2496969, + 2165110, + 2589055, + 1648006, + 966763, + 3719559, + 4883836, + 2489406, + 2900336, + 1003207, + 914713, + 2687415, + 2957174, + 991602, + 3005713, + 3016805, + 3646583, + 2002778, + 2188117, + 996416, + 3940661, + 3749144, + 1702093, + 1779575, + 2135189, + 1198463, + 1665170, + 1230802, + 3071243, + 1250575, + 1159769, + 2008716, + 2577482, + 1680782, + 2755046, + 2798673, + 2779172, + 4719731, + 2451896, + 2268516, + 3364116, + 2139930, + 4014502, + 5474835, + 2379560, + 3272928, + 2133308, + 2638465, + 3610736, + 2437161, + 2469816, + 1951246, + 1998282, + 2022421, + 2093450, + 2415039, + 4011191, + 2829334, + 2863331, + 4093600, + 2661113, + 2923200, + 2198013, + 2162835, + 2958211, + 1829311, + 750764, + 1125263, + 1293794, + 4883789, + 1165273, + 1322292, + 2045605, + 1796576, + 1587215, + 3595048, + 2442957, + 3675117, + 2022610, + 2207877, + 3164247, + 2539827, + 2289433, + 2050621, + 2033111, + 2996013, + 643859, + 1353849, + 2284477, + 1687120, + 2374034, + 3975861, + 3174103, + 3090405, + 3004853, + 1655110, + 2881453, + 3229992, + 3406893, + 1953384, + 2162162, + 3005248, + 1806960, + 2262637, + 2658934, + 3172203, + 2346601, + 2083857, + 1905139, + 2243485, + 1779413, + 2958736, + 2324181, + 1167937, + 2487352, + 2195558, + 2511598, + 3374057, + 3239559, + 3989322, + 2007874, + 1142953, + 1917363, + 1413284, + 2254989, + 2519517, + 2612721, + 1979898, + 1472130, + 4246577, + 678823, + 1032892, + 1956684, + 2963972, + 2501714, + 3206467, + 3867577, + 1866296, + 1852756, + 2674353, + 2068891, + 2485623, + 1691978, + 3224678, + 2235530, + 2642436, + 3528805, + 3154289, + 763332, + 2188687, + 2175236, + 3423181, + 2228774, + 4926897, + 4720293, + 1365097, + 4384144, + 1933318, + 1538742, + 3060760, + 891455, + 2247727, + 1481978, + 2009726, + 3389542, + 737932, + 4035426, + 4661761, + 1332633, + 913928, + 2479290, + 1992229, + 2961682, + 1641167, + 3217414, + 3225260, + 2595246, + 591918, + 5566353, + 2528672, + 2502651, + 1241588, + 2590376, + 3876970, + 1793155, + 1501528, + 1838442, + 2522918, + 2422260, + 3056321, + 2273838, + 2071241, + 1658722, + 2562266, + 1338349, + 1376886, + 2223907, + 1921712, + 2211260, + 1602704, + 5260200, + 2189077, + 3019251, + 2106858, + 3976347, + 2463524, + 1576729, + 491605, + 3168168, + 4672180, + 1922298, + 2396219, + 2857066, + 3012596, + 874988, + 2600192, + 2197450, + 1567978, + 1636166, + 4334187, + 2964752, + 4434709, + 2753079, + 2384760, + 1534463, + 2112708, + 2065799, + 1431116, + 3960134, + 2861238, + 2406750, + 2744852, + 2940188, + 3343790, + 2451949, + 2431427, + 2343771, + 4247520, + 2386347, + 5806313, + 2995484, + 3520605, + 1723394, + 2278390, + 4240678, + 1794433, + 3515379, + 4577968, + 2412014, + 1533701, + 733354, + 2879952, + 4102595, + 1847856, + 1920316, + 2281251, + 1136467, + 2032967, + 2387741, + 2059754, + 3098458, + 2813846, + 2264943, + 1328950, + 1544527, + 1143015, + 2417418, + 2816076, + 4485204, + 2576250, + 2144794, + 1827914, + 1906691, + 2348923 +}; diff --git a/benchmarks/spmv/spmv_gendata.scala b/benchmarks/spmv/spmv_gendata.scala new file mode 100644 index 0000000..f777445 --- /dev/null +++ b/benchmarks/spmv/spmv_gendata.scala @@ -0,0 +1,48 @@ +#!/usr/bin/env scala +!# + +val m = args(0).toInt +val n = args(1).toInt +val approx_nnz = args(2).toInt + +val pnnz = approx_nnz.toDouble/(m*n) +val idx = collection.mutable.ArrayBuffer[Int]() +val p = collection.mutable.ArrayBuffer(0) + +for (i <- 0 until m) { + for (j <- 0 until n) { + if (util.Random.nextDouble < pnnz) + idx += j + } + p += idx.length +} + +val nnz = idx.length +val v = Array.tabulate(n)(i => util.Random.nextInt(1000)) +val d = Array.tabulate(nnz)(i => util.Random.nextInt(1000)) + +def printVec(t: String, name: String, data: Seq[Int]) = { + println("const " + t + " " + name + "[" + data.length + "] = {") + println(" "+data.map(_.toString).reduceLeft(_+",\n "+_)) + println("};") +} + +def spmv(p: Seq[Int], d: Seq[Int], idx: Seq[Int], v: Seq[Int]) = { + val y = collection.mutable.ArrayBuffer[Int]() + for (i <- 0 until p.length-1) { + var yi = 0 + for (k <- p(i) until p(i+1)) + yi = yi + d(k)*v(idx(k)) + y += yi + } + y +} + +println("#define R " + m) +println("#define C " + n) +println("#define NNZ " + nnz) +printVec("double", "val", d) +printVec("int", "idx", idx) +printVec("double", "x", v) +printVec("int", "ptr", p) +printVec("double", "verify_data", spmv(p, d, idx, v)) diff --git a/benchmarks/spmv/spmv_main.c b/benchmarks/spmv/spmv_main.c new file mode 100644 index 0000000..11d9540 --- /dev/null +++ b/benchmarks/spmv/spmv_main.c @@ -0,0 +1,123 @@ +//************************************************************************** +// Double-precision general matrix multiplication benchmark +//-------------------------------------------------------------------------- + +//-------------------------------------------------------------------------- +// Macros + +// Set HOST_DEBUG to 1 if you are going to compile this for a host +// machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG +// to 0 if you are compiling with the smips-gcc toolchain. + +#ifndef HOST_DEBUG +#define HOST_DEBUG 0 +#endif + +// Set PREALLOCATE to 1 if you want to preallocate the benchmark +// function before starting stats. If you have instruction/data +// caches and you don't want to count the overhead of misses, then +// you will need to use preallocation. + +#ifndef PREALLOCATE +#define PREALLOCATE 0 +#endif + +// Set SET_STATS to 1 if you want to carve out the piece that actually +// does the computation. + +#ifndef SET_STATS +#define SET_STATS 0 +#endif + +//-------------------------------------------------------------------------- +// Input/Reference Data + +#include "dataset1.h" + +//-------------------------------------------------------------------------- +// Helper functions + +int verify( long n, const double test[], const double correct[] ) +{ + int i; + for ( i = 0; i < n; i++ ) { + if ( test[i] != correct[i] ) { + return 2; + } + } + return 1; +} + +#if HOST_DEBUG +#include <stdio.h> +#include <stdlib.h> +void printArray( char name[], long n, const double arr[] ) +{ + int i; + printf( " %10s :", name ); + for ( i = 0; i < n; i++ ) + printf( " %8.1f ", arr[i] ); + printf( "\n" ); +} +#endif + +void finishTest( int toHostValue ) +{ +#if HOST_DEBUG + if ( toHostValue == 1 ) + printf( "*** PASSED ***\n" ); + else + printf( "*** FAILED *** (tohost = %d)\n", toHostValue ); + exit(0); +#else + asm( "mtpcr %0, cr30" : : "r" (toHostValue) ); + while ( 1 ) { } +#endif +} + +void setStats( int enable ) +{ +#if ( !HOST_DEBUG && SET_STATS ) + asm( "mtpcr %0, cr10" : : "r" (enable) ); +#endif +} + +void spmv(int r, const double* val, const int* idx, const double* x, + const int* ptr, double* y) +{ + for (int i = 0; i < r; i++) + { + int k; + double yi0 = 0, yi1 = 0, yi2 = 0, yi3 = 0; + for (k = ptr[i]; k < ptr[i+1]-3; k+=4) + { + yi0 += val[k+0]*x[idx[k+0]]; + yi1 += val[k+1]*x[idx[k+1]]; + yi2 += val[k+2]*x[idx[k+2]]; + yi3 += val[k+3]*x[idx[k+3]]; + } + for ( ; k < ptr[i+1]; k++) + { + yi0 += val[k]*x[idx[k]]; + } + y[i] = (yi0+yi1)+(yi2+yi3); + } +} + +//-------------------------------------------------------------------------- +// Main + +int main( int argc, char* argv[] ) +{ + double y[R]; + +#if PREALLOCATE + spmv(R, val, idx, x, ptr, y); +#endif + + setStats(1); + spmv(R, val, idx, x, ptr, y); + setStats(0); + + finishTest(verify(R, y, verify_data)); +} |