dists_test.go

/*
TODO golang allows benchmarks to be added
*/
package main

import (
	"fmt"
	"testing"
)

type addTest struct {
	profile1                   []int
	profile2                   []int
	expected, expected_missing float64
}

var hamming_dist_tests = []addTest{
	{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}, float64(0), float64(0)},
	{[]int{2, 1, 1, 2}, []int{2, 2, 2, 2}, float64(2), float64(2)},
	{[]int{2, 0, 0, 2}, []int{2, 0, 0, 2}, float64(0), float64(0)},
	{[]int{2, 0, 0, 2}, []int{2, 0, 1, 2}, float64(0), float64(1)},
	{[]int{1, 1, 1}, []int{2, 2, 2}, float64(3), float64(3)},
	{[]int{1}, []int{2}, float64(1), float64(1)},
}

var scaled_dist_tests = []addTest{
	{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}, float64(100.0 * ((0.0) / 4.0)), float64(100.0 * ((0.0) / 4.0))},
	{[]int{2, 1, 1, 2}, []int{2, 2, 2, 2}, float64(100.0 * ((4.0 - 2.0) / 4.0)), float64(100.0 * ((4.0 - 2.0) / 4.0))},
	{[]int{2, 0, 0, 2}, []int{2, 0, 0, 2}, float64(100.0 * ((0.0) / 2.0)), float64(100.0 * ((0.0) / 4.0))},
	{[]int{1, 1, 1}, []int{2, 2, 2}, float64(100.0 * ((3.0 - 0.0) / 3.0)), float64(100.0 * ((3.0 - 0.0) / 3.0))},
	{[]int{1}, []int{2}, float64(100.0), float64(100.0)},
}

func TestHammingDistance(t *testing.T) {
	for _, test := range hamming_dist_tests {
		if output := HammingDistance(&test.profile1, &test.profile2); output != test.expected {
			t.Errorf("Output %f not equal to expected %f", output, test.expected)
		}
	}
}

func TestHammingDistanceMissing(t *testing.T) {
	for _, test := range hamming_dist_tests {
		if output := HammingDistanceMissing(&test.profile1, &test.profile2); output != test.expected_missing {
			t.Errorf("Output %f not equal to expected %f", output, test.expected_missing)
		}
	}
}

func TestScaledDistance(t *testing.T) {
	for _, test := range scaled_dist_tests {
		if output := ScaledDistance(&test.profile1, &test.profile2); output != test.expected {
			t.Errorf("Output %f not equal to expected %f", output, test.expected)
		}
	}
}

func TestScaledDistanceMissing(t *testing.T) {
	for idx, test := range scaled_dist_tests {
		if output := ScaledDistanceMissing(&test.profile1, &test.profile2); output != test.expected_missing {
			t.Errorf("Test - %d: Output %f not equal to expected %f", idx, output, test.expected_missing)
		}
	}
}

func ExampleHammingDistance() {
	fmt.Println(HammingDistance(&[]int{1, 2, 3, 4}, &[]int{1, 2, 3, 4}))
	// Output: 0
}

func benchmarkDistance(dist func(*[]int, *[]int) float64, profile1 []int, profile2 []int, b *testing.B) {
	for n := 0; n < b.N; n++ {
		dist(&profile1, &profile2)
	}
}

func BenchmarkHamming20(b *testing.B) {
	benchmarkDistance(
		HammingDistance,
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20},
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20}, b)

}

func BenchmarkHammingEql20(b *testing.B) {
	benchmarkDistance(
		HammingDistanceEql,
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20},
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20}, b)
}

func BenchmarkHammingMissing20(b *testing.B) {
	benchmarkDistance(
		HammingDistanceMissing,
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20},
		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20}, b)
}

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