3000 5
653 27 358 1216 94 397 657 69 1446 199 413 1369 157 1089 386 1433 1298 1407 989 916 1289 846 1373 1036 1439 1047 1070 938 58 376 1219 908 215 1316 392 1066 746 1465 1199 646 1396 316 1367 519 160 1016 779 1296 957 1140 98 1391 1235 1307 997 263 180 1249 1498 1394 249 951 190 1062 980 917 1189 1331 233 656 927 1476 451 639 778 425 561 1469 1237 418 1115 28 743 1272 505 1085 251 63 381 1239 27 449 1468 1427 757 1457 1351 440 1459 1118 944 1042 270 534 678 305 958 123 1059 725 1282 242 564 48 609 483 913 1068 178 318 594 1185 977 1286 1335 1223 1113 358 260 924 47 282 1055 659 270 344 1161 935 867 1081 241 1122 381 220 1097 341 139 1463 101 1203 826 10 281 716 314 525 782 1265 30 119 1406 1477 487 1020 337 1123 1006 883 856 1236 102 1399 1413 699 234 211 1364 777 741 784 768 382 697 92 1014 663 300 1439 769 733 558 1250 1234 453 949 1240 158 673 1449 1500 1032 354 1398 1039 1325 892 1190 880 774 1060 255 367 282 1100 836 1260 809 648 292 466 383 1148 320 993 1033 407 1409 1277 1171 181 687 507 1326 1366 497 1183 468 1124 702 631 1370 448 47 701 461 1000 990 306 1268 372 1365 518 1188 276 889 308 157 1169 1181 1470 488 507 1467 321 378 752 1062 410 1217 478 876 134 756 678 880 44 1163 147 798 563 604 953 320 1341 135 142 885 1493 895 684 598 759 52 154 559 864 574 113 725 1110 110 390 187 210 308 87 780 900 555 1008 884 430 490 238 661 1273 1009 8 1002 586 1352 322 127 1052 822 580 1080 1128 824 964 1486 1259 326 1480 164 984 330 981 406 1050 1297 1026 333 1247 223 1013 1103 1134 355 1254 114 586 1266 221 194 1091 1131 198 10 1320 429 804 862 328 1063 397 1310 174 1115 313 280 1313 538 1175 785 1380 412 753 503 1287 776 1140 622 540 415 1207 740 1376 1093 854 432 1384 934 1315 106 1434 750 8 1257 417 1109 385 364 1275 1211 487 1421 1005 502 786 40 697 575 1226 506 1237 943 1244 74 1191 370 1092 669 951 752 546 1136 1177 1444 1044 1461 1003 587 408 360 721 1210 1300 1170 858 989 229 810 203 1262 843 45 69 345 1118 211 566 1337 104 310 251 941 15 374 1397 222 233 343 838 869 438 928 903 437 981 607 958 920 695 1359 1292 548 433 227 694 49 401 465 791 1246 953 914 970 627 351 508 551 910 151 1481 1187 239 457 385 808 399 1245 1333 591 1099 16 1011 95 656 1381 414 1482 1205 1004 1393 1256 1376 1224 774 1209 1119 1201 583 470 201 200 1469 1467 457 166 1226 1462 444 1296 365 272 237 1178 936 209 918 238 396 460 97 927 830 1269 1264 810 1254 907 1385 355 146 398 1046 1278 599 887 543 641 589 1183 1431 242 1317 711 941 1386 176 916 590 362 1192 570 1037 1472 1305 121 311 902 1415 894 713 428 568 674 760 872 1313 1017 562 79 998 1009 602 169 584 485 750 636 799 856 615 1463 1490 560 1484 638 428 1471 336 1292 651 898 324 442 498 972 557 893 1260 1131 316 517 401 1142 809 82 1350 296 878 849 423 197 1093 43 1388 644 593 572 795 707 1178 71 289 377 299 323 128 123 151 565 813 1255 20 28 32 904 985 767 886 595 1241 1041 1171 435 140 362 567 420 1105 273 484 754 191 1488 585 252 1324 772 336 775 882 888 525 901 696 828 657 934 107 515 1198 921 1107 624 506 1456 865 720 817 1277 676 46 161 1147 173 1090 1287 260 890 561 842 1121 445 5 788 1246 435 530 1044 293 868 1482 187 1012 642 873 283 713 608 1330 966 906 1419 431 168 675 714 56 342 922 1241 1493 1170 1414 731 1271 1167 228 1379 1464 389 7 1186 956 500 826 1019 1185 208 723 88 866 837 655 552 602 369 374 925 1283 770 661 474 831 625 68 95 1071 446 846 11 543 1414 1023 3 917 651 447 333 51 983 566 163 1071 765 740 329 1123 304 926 26 203 649 730 224 1368 535 870 681 541 117 668 1080 1085 728 394 1230 666 129 1033 547 1380 658 491 1002 533 1032 61 833 589 546 820 431 372 876 686 332 1149 1405 291 935 522 110 23 145 610 1378 1154 133 430 1389 743 596 1010 1448 1392 783 700 816 1374 25 167 274 969 539 1249 782 1197 1354 806 840 1186 1305 185 988 423 773 284 1354 1300 426 708 905 1162 45 667 130 108 956 972 159 729 1216 99 1437 1086 1311 1285 406 1225 600 62 209 48 592 1056 763 1295 1291 998 449 481 531 15 1233 154 707 1065 787 149 64 672 1319 483 382 1054 443 37 350 853 170 1394 228 1421 465 604 116 764 409 476 850 403 742 961 367 679 1280 949 1488 1120 532 1495 1352 1200 1465 1326 237 819 441 1293 290 1149 1001 1058 1455 284 1172 1205 1104 758 1361 66 480 1273 1031 1304 764 1342 1472 41 696 683 1432 1074 1193 1263 581 819 454 865 1492 393 596 1069 195 598 870 343 1025 611 1336 805 420 391 306 1497 1489 822 1129 100 1423 843 1492 1288 5 718 1322 693 829 717 219 868 952 38 288 140 1307 43 1087 294 693 1013 1018 1401 1267 1320 1059 1322 253 1408 287 1298 969 440 1483 1481 1339 912 1312 301 899 805 799 309 62 993 97 860 349 344 797 1259 521 1137 275 53 1442 1253 595 1340 973 802 215 536 888 102 424 1007 208 1079 156 253 6 755 407 186 121 494 1253 1043 463 453 1362 760 650 389 1075 948 356 794 1496 1360 1076 855 1333 789 950 482 291 1310 125 585 1121 682 690 1413 148 705 126 250 1458 767 1306 648 1344 775 1047 266 871 388 1157 1486 1281 990 301 1061 643 632 380 222 155 1257 877 1242 521 633 1 980 1221 100 107 77 551 1302 599 312 985 404 715 156 1165 573 112 1101 776 1194 417 170 1154 1083 999 421 615 1332 1435 205 736 279 370 495 820 268 352 1045 1319 1388 369 177 1392 118 2 1371 58 1111 234 773 853 29 1014 1342 175 704 1358 519 731 153 978 583 116 670 727 791 1120 1441 812 814 1113 1119 65 1019 572 961 1353 1169 334 653 1214 1329 1338 631 612 131 698 682 1207 1096 553 929 539 171 1386 475 692 831 230 1040 394 103 1389 542 665 553 847 1152 439 325 1112 422 1184 605 175 518 859 67 1410 339 1209 1157 1269 42 341 1490 611 1105 399 1001 688 1284 7 20 1447 529 741 120 933 254 1347 460 728 1416 1144 328 183 872 522 278 1220 852 937 34 243 1066 255 1267 245 419 1443 1438 322 132 1166 613 1011 617 960 353 723 12 719 141 1460 340 1464 668 911 939 482 687 1079 545 1184 335 1104 609 979 245 947 884 1049 309 231 929 1377 1147 783 986 1024 1432 1028 493 492 1204 1361 1479 635 1182 448 185 1435 1106 1290 486 384 839 467 545 380 703 495 163 1228 781 1012 1135 1073 150 258 1314 950 261 966 514 574 319 896 1294 38 1007 52 1480 1280 616 1103 1301 971 1286 231 1429 909 1424 523 841 40 1244 642 61 1127 1289 1346 910 1039 915 105 1363 1193 1295 331 1015 592 479 296 1135 186 975 1097 93 331 864 314 946 800 119 659 300 295 387 1420 729 1456 771 1344 257 848 179 792 881 165 477 174 427 852 938 106 1466 1489 970 436 1437 914 807 29 1156 1106 528 1450 786 1279 897 218 1271 266 1461 65 747 404 575 655 74 365 971 1212 1057 244 160 83 78 996 1328 13 720 1372 650 925 763 1158 188 665 901 1036 685 432 748 1242 751 908 1331 450 378 556 963 968 268 317 366 994 768 928 1146 1440 647 802 1379 1153 1107 297 117 690 472 299 871 1060 1034 1139 57 842 1056 588 1434 1411 1308 672 686 845 1363 405 24 461 89 608 701 79 332 1064 1451 511 60 286 1195 1213 232 792 560 6 246 821 1083 360 835 1460 584 1229 1356 108 84 145 1348 265 239 1202 70 467 976 894 310 1043 977 379 1443 346 395 1390 1405 1176 1419 745 1004 918 1415 202 342 323 418 112 637 840 623 375 1452 1358 992 570 217 254 1159 275 578 664 334 204 1323 19 252 177 497 179 549 1479 722 639 1369 1317 162 1077 579 176 272 620 103 463 236 1453 11 1166 600 803 295 269 629 298 836 1144 1450 514 452 628 811 1021 1227 63 1228 12 1084 1328 348 790 363 180 480 1069 1251 515 1355 735 544 141 1067 1220 620 81 710 761 1219 75 1445 758 207 1008 849 285 834 80 1065 138 727 797 582 933 858 405 499 1031 946 1274 1258 181 565 1049 755 1111 30 1202 1316 986 377 1315 1444 942 527 131 1335 289 547 683 59 1092 250 347 794 1338 1224 1364 923 1290 1251 227 1417 1174 73 195 719 674 890 548 1497 582 520 1155 1447 1459 321 552 34 806 21 692 823 1145 1090 189 698 573 670 134 216 913 1385 395 1302 807 216 630 1341 579 264 202 654 269 1021 1081 1279 359 1217 1054 92 1038 1243 1029 475 979 473 56 945 410 454 1243 848 371 996 271 429 114 526 1208 844 874 444 326 384 1052 531 833 838 905 706 149 1173 303 1227 498 1143 137 1068 562 400 813 667 354 839 669 302 1345 988 398 468 350 54 962 1150 1470 756 1332 376 288 542 118 709 781 1381 556 591 652 137 618 850 1035 1240 1082 717 1431 785 732 1499 1264 1336 1498 873 1299 357 1403 261 126 488 1130 844 1088 1034 198 739 144 1232 1179 1473 529 46 485 1248 172 1494 101 403 317 458 70 94 1353 130 197 1130 19 182 612 1409 671 434 1221 436 640 1022 212 352 1017 793 1407 1095 1261 113 999 501 178 1374 122 109 714 1045 371 1357 53 538 85 1101 1334 1471 481 496 264 135 626 635 766 945 244 930 1162 1425 256 581 559 1337 361 473 68 1125 550 637 243 1195 909 267 1334 882 1321 954 564 1064 900 1293 14 1114 736 90 1487 292 1225 978 1345 789 1234 790 1455 1299 54 439 527 437 1454 484 265 1391 897 1303 206 346 77 1357 204 33 1084 987 965 902 1430 1309 866 624 409 411 240 1275 753 132 1030 1424 517 1430 613 1231 703 675 812 845 283 1196 654 967 1351 554 494 1478 759 98 1094 861 393 1355 1112 287 973 502 1412 1484 911 184 1078 1200 1402 329 33 165 366 1003 259 1223 246 262 76 1143 37 55 241 276 607 891 1343 1312 1072 974 196 1308 516 861 1088 825 744 267 210 1404 644 1114 248 1387 1265 885 1303 1304 1172 422 446 590 960 879 1318 85 188 207 1098 606 258 35 1095 997 948 496 627 1192 892 1266 815 1189 1215 64 891 1476 1483 1005 535 1347 1179 1177 477 746 689 796 854 1018 936 1362 1132 1146 984 416 554 1236 1462 125 1053 780 489 544 66 1022 1191 1494 811 825 1042 1373 962 509 31 800 745 50 821 937 249 427 576 837 610 1057 1375 67 464 762 991 337 569 91 770 737 662 167 1263 1122 983 623 619 1278 1323 512 511 447 1096 823 1291 580 1129 89 968 1458 425 36 1231 4 1030 1006 240 1210 1324 1288 630 1218 50 867 633 1076 44 1053 1208 1411 466 1365 787 17 1230 184 1160 213 193 386 115 1159 73 9 907 221 738 349 808 680 1438 311 1077 1037 1452 1372 212 761 619 18 618 673 524 247 388 226 122 441 182 236 793 1478 1485 947 1073 827 779 628 271 658 666 875 24 944 413 677 72 1138 1058 1406 1491 1181 749 921 887 699 878 1442 338 660 471 1425 22 226 550 903 146 1024 419 621 704 715 96 1199 834 1418 732 959 1475 875 523 273 433 1142 1495 39 424 105 1239 549 1382 1139 605 1098 932 1182 1116 192 889 1050 571 516 1117 327 1212 1448 22 702 1196 919 348 931 1165 31 832 1174 1067 1370 832 1020 742 1384 646 318 528 503 455 963 1156 881 330 1168 1276 124 136 124 603 373 1128 1089 84 76 152 190 847 593 747 1203 1285 1232 563 1198 568 298 508 587 660 724 1356 1133 1485 469 706 83 681 751 1016 3 1382 504 1213 617 36 60 1151 1164 766 171 1428 286 1218 734 509 1329 72 1422 280 71 857 1091 801 689 1145 339 279 230 324 537 1402 1215 213 726 994 1164 259 218 1074 722 450 476 1426 685 127 80 1158 192 1255 734 1314 1248 505 904 1383 957 229 995 601 919 470 886 1134 588 1441 297 532 1214 824 1491 1048 857 256 1023 442 1168 445 1268 1321 1393 199 225 663 995 955 1180 1094 1468 1433 220 536 136 641 1125 486 735 778 391 915 1075 606 1487 1137 795 859 479 315 471 39 1116 688 421 1109 49 458 139 1348 621 695 1454 1141 1276 302 168 712 1346 726 893 1063 798 1325 841 35 1025 111 345 1473 679 1078 277 472 1284 152 733 1397 932 1422 835 1027 313 954 863 874 769 219 99 1229 632 851 1477 510 1161 1408 1046 415 709 975 82 13 1420 912 1108 474 305 257 959 1330 577 1153 1086 1427 777 133 41 150 1449 526 1396 869 451 159 1070 818 57 1000 1270 643 1167 694 32 691 1367 327 1035 183 1256 576 1395 1250 319 744 142 162 462 1136 469 294 96 161 724 1138 638 493 402 379 1048 863 708 18 860 411 438 1474 191 78 1270 1306 351 86 829 1247 1349 677 1133 443 1368 111 1274 307 1383 721 1175 452 347 1340 434 1152 1297 788 1027 143 144 1429 940 557 1117 577 1151 1499 1194 1474 4 59 353 754 636 387 274 1281 173 896 1398 200 883 625 223 1082 205 855 1126 196 895 396 499 217 578 765 1206 1378 626 285 9 25 1127 1238 1283 757 987 189 1343 1371 281 737 684 335 1100 368 1010 1446 898 801 490 922 1038 368 128 115 363 1 555 748 1028 375 992 158 164 1500 1222 459 982 91 676 1102 109 1173 357 691 464 510 645 816 982 940 400 492 75 1029 1403 771 513 1072 86 412 541 262 601 225 462 1108 712 87 1360 1445 1377 1400 55 478 1272 926 155 906 614 1197 235 1124 304 1496 1387 597 21 533 1327 500 634 17 153 416 967 1204 1211 622 247 739 955 138 711 1187 214 42 51 1163 862 1201 2 964 649 1238 169 232 1190 1252 491 976 172 1188 166 104 652 716 90 803 1252 1160 1390 1041 1222 1366 325 1426 1180 1318 830 879 1206 1401 456 645 1375 1051 804 923 1412 705 1026 930 194 359 818 718 943 1040 942 1466 664 513 390 1261 540 680 383 1141 1350 1102 1416 991 569 501 520 1457 634 1453 26 784 1055 524 248 772 1428 558 1417 23 512 534 924 614 312 567 1451 16 1258 640 899 293 1110 1061 373 1311 571 456 459 1132 700 224 730 206 88 1309 1233 392 290 1327 827 364 81 647 662 952 1262 489 671 828 408 1155 1150 1404 1015 749 315 1400 120 603 356 965 974 597 1339 1436 338 307 143 815 817 1087 710 1440 1301 629 193 361 616 402 1423 1418 147 278 796 1410 1176 1245 920 1395 1235 504 877 1148 530 14 1294 340 1051 426 851 455 277 594 235 537 1126 214 1359 814 93 263 738 1475 1399 939 414 201 1099 1349 762 931 148 303 1436 1282 129
2 1 3 5 3