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