P19478 [HackerEarth] View Russian Translation
提高-
题目描述

View Russian Translation

Probably, you have already read some problems but you still have not met any problems with queries on segments. Therefore Benny wants to fix it.

She gives you an array A of N elements. And then you have to answer Q queries.

Each query consists of three integers L, R, X. Your task is to find such Ai, that L ≤ i ≤ R and Ai xor X is maximal. For each query output the maximum of Ai xor X.

Input format

The first line contains two integers N and Q.
The next line contains N integers Ai.
The next Q lines contain three integers L, R, X.

Output format

For each query output the maximum of Ai xor X in a single line.

Constraints
1 ≤ N, Q ≤ 5 * 10^5
0 ≤ Ai < 2^20
1 ≤ L ≤ R ≤ N
0 ≤ X < 2^20
1 ≤ N, Q ≤ 3 * 10^3 holds for test cases worth 15% of the problem's score.
1 ≤ N, Q ≤ 10^5 holds for test cases worth 60% of the problem's score.

SAMPLE INPUT
5 3
1 7 3 8 2
1 5 10
3 4 6
2 5 8

SAMPLE OUTPUT
13
14
15

输入格式

见题面

输出格式

见题面

样例输入
1665 2020 954471 686408 36359 820266 597071 114080 554266 2436 59041 354402 533101 805876 962262 563687 6749 190939 482632 863892 865491 475546 265332 904529 171464 315002 1034452 658676 551460 27594 312122 871977 431727 944339 261845 1018554 847943 194689 585590 84520 771534 485436 809527 462476 797522 14574 641708 582742 455947 109867 9099 897274 928712 822503 436715 891919 54743 471515 668175 823518 714903 794849 177796 839588 284112 917062 51674 266641 872018 74289 786467 858511 595779 419286 514247 589248 743787 755498 450110 576704 680604 100 637433 46096 887754 307917 451542 532627 183781 754436 428542 892749 368379 561399 353855 772162 558403 330951 657992 596915 624113 563265 252700 412547 507872 405308 470972 982063 955159 722518 859692 528541 716871 315264 188942 463415 854529 772858 729658 277985 689696 769533 417259 9072 431340 730050 562694 101286 480174 446110 466135 434170 55186 585026 46217 823782 956514 424467 562862 829532 80591 796290 276678 749895 665902 378182 694144 29359 619263 839966 337496 551818 807931 893265 654965 54528 13413 1466 533278 633551 860485 223888 609102 985997 1018821 79968 805807 845755 123513 753763 653121 519651 197331 945011 31103 568647 537069 391726 794891 876969 446306 605642 513664 230273 964780 935109 323099 803127 890656 833277 122173 256919 2151 503580 616427 360011 432389 537156 795036 168264 19645 932887 725294 326311 271599 323029 685052 320754 195525 1001504 547125 571645 598281 525185 930069 561595 496431 7692 310274 223274 765639 1030236 45723 919776 582733 308270 86277 934181 468277 775162 643660 889837 713053 118892 682632 542467 930876 482745 663642 133628 886796 983338 362511 508187 449026 179842 624835 120948 643844 833602 331884 610496 304322 839808 834406 215916 834943 846676 918732 853950 491846 540645 720328 747500 250162 745035 762404 141324 223495 287898 579787 74145 452578 122351 96862 580892 824339 885277 617171 280695 101045 633379 64650 261478 85453 711474 838395 153072 530873 61714 199452 953975 737677 835992 652683 494598 657618 598474 617628 622414 320897 500264 456070 91728 278685 928631 498608 949231 693016 991422 969009 717164 1045123 700103 574429 204420 555486 584549 418517 183441 290436 253323 395004 312133 1984 844664 658514 980666 544444 607666 968426 349769 261821 616458 893026 830156 81735 88367 411607 438186 458745 1001447 642519 589938 805304 782954 529662 676379 302310 576021 731549 595339 364246 304412 261745 378642 42246 153337 789021 790914 107127 84102 37114 927829 662626 886002 223182 279707 270172 447563 758749 567367 1039741 416990 726618 554531 265721 98965 271442 832373 642489 77300 1045415 365975 7690 287337 592249 852802 58081 1005769 929291 69243 909226 470628 444870 585396 1017635 68891 230232 267125 630554 826782 950 252716 667237 796498 626740 687864 385647 324281 753623 405122 490746 920321 301606 280280 473394 797329 963535 987084 405004 598689 40481 887904 719185 422037 614823 664001 929081 726183 582829 859346 1000442 527149 382624 902024 14971 1020669 740390 299888 764472 289710 634033 576200 594512 87228 132331 63256 951023 416235 612924 217681 83963 837264 18157 31405 400086 782847 828408 62431 703787 611819 510605 204252 890284 880449 206942 1002236 256400 717445 538576 543432 376518 1038864 362723 924033 813670 877135 88020 874768 156458 820054 181102 826253 555241 665340 362701 543585 855277 764799 547857 291383 440707 881540 716495 299786 106489 903566 757392 834586 91419 316073 158559 486108 566311 78170 989871 56213 5645 517494 646810 361807 205503 944830 127969 156662 47510 535998 215055 1043622 627041 496431 6666 895146 799293 418281 405384 706433 1045000 731537 400491 257602 999445 544774 910776 306528 173970 490205 230384 722192 619059 558338 287975 824505 529905 567440 175031 502919 1037076 721791 179927 993069 341040 355742 1036371 402071 599764 273621 756110 256315 342088 135192 972651 60173 505246 314134 79459 630428 795378 681766 651978 184193 338617 520797 579607 198782 170485 648243 316680 928345 946832 226083 799675 548634 766714 227800 287072 329850 1028969 775823 218086 609140 584680 512242 444209 1009813 724941 679242 183259 379531 296121 368663 98133 962953 639754 261220 992160 778059 62301 617900 999688 423607 792616 388689 71920 802063 833348 261108 165229 376427 556050 634835 413635 953636 286677 1033916 27882 964537 1045386 912442 1047847 333440 540164 1030374 268996 609619 238451 1043061 646930 270236 474955 812165 744994 72374 45023 682450 624446 928309 341255 816995 141237 852160 808675 818906 794248 555098 357482 924535 862644 847243 1009541 360009 401245 342219 247472 611549 175185 985198 165020 20546 345146 155739 275705 126629 705669 790573 665713 349102 585790 300143 864644 911513 119706 739133 135834 216461 552412 301779 38634 267078 878894 289075 434874 366314 458723 641123 191984 209429 856325 561607 696392 59854 393406 715176 143316 148943 348886 99466 306145 22116 517892 1038328 784552 129286 272673 548957 949919 720780 1003231 204783 368056 381986 668759 150017 574797 88478 170127 916539 701029 400069 496233 873233 570070 330643 721115 353757 169417 523034 432734 50294 152830 658220 230159 86681 388658 607989 103284 510411 93977 325930 145588 573533 865067 686431 423010 194149 958573 429665 898608 277230 590766 51505 585699 864379 648089 880745 984318 49368 320034 679982 30018 161019 924242 141187 15946 625740 651227 150587 711940 289063 234347 234347 232181 519516 16404 977282 295130 499367 59197 876787 526299 779085 522657 390618 1046134 912926 793523 960403 768055 734164 501661 872489 645685 322728 857676 191584 833251 718749 426478 809621 994349 874479 534007 303024 1464 493632 152198 515177 497790 820365 155704 733041 504172 91793 320020 439620 438673 240415 500917 959479 964269 741330 369483 242410 481013 926233 39185 83329 669914 689565 657123 668676 848594 645124 329420 93809 645866 216112 989804 1038580 818628 326053 130313 745274 588412 328570 482384 887451 448404 215440 173743 872094 301913 200768 2511 262348 34553 873977 493059 1008154 109650 546839 1004597 93422 441523 961347 904739 549133 770043 603520 498915 851049 1010171 454231 638711 556384 994611 33203 206101 493210 393849 814588 588892 12952 631469 469259 510979 198024 10721 884814 168184 762939 740448 225313 443528 51967 1000571 589138 1003444 650648 905956 35179 910179 759716 37817 168470 320427 992052 15164 68943 50835 856169 29185 838759 1024797 907343 286014 375765 962527 822803 234162 267883 787915 23380 786604 14956 767924 634695 160728 233093 116299 104481 701934 934722 117944 476464 1010139 966304 342069 873118 729977 391663 775680 973683 623628 811934 14197 591434 793659 92294 351883 140990 901864 474837 934773 974575 938338 72662 688821 735610 700843 420877 1036124 435970 956119 79267 558789 524527 355699 310593 328204 621690 736025 334887 747594 783734 12829 663494 788908 987349 665901 347637 82145 697293 518819 882268 373051 446896 37777 535468 731554 689198 781247 155588 871554 650113 289935 205006 973326 909397 193793 202864 629609 666381 34768 299555 413091 212079 316472 578423 207901 344114 640770 548968 99769 146348 773682 940401 136356 606556 135847 433122 268400 25071 900703 883467 607814 315198 128051 475796 277473 471618 309046 540886 581902 1023637 292485 75466 644870 250233 879325 198448 858891 699617 782091 705868 986246 1001713 904639 967120 412012 947673 730185 743309 70655 517085 65861 686944 661670 546395 895919 165672 495297 871703 16728 129423 475257 651137 730399 137529 403943 593493 794713 1029311 239262 2813 107320 181567 254927 89923 345469 341955 7805 116285 920968 680767 647290 29464 276981 606701 474741 370320 682641 677768 578044 131416 416938 902699 865935 589689 826597 46649 744488 1017394 223992 252714 633763 227501 507088 862045 220432 183226 863735 311610 647991 278254 1030393 595501 989664 776736 890125 308562 805206 178313 90351 206867 797525 59341 157931 401373 389330 367062 451977 507604 97224 363115 174306 895938 491275 383396 239164 438920 205876 920563 171092 349248 938849 273227 413585 127795 380319 955500 153632 510886 729933 709208 508682 379669 523907 421086 365094 919253 174879 45595 867282 160325 806436 934044 254212 650578 766873 789904 954394 439122 449524 176434 1008395 1012300 586482 393379 256192 377198 935307 513273 1002478 129636 904660 282225 651737 324251 247050 861686 485158 338001 662283 371869 504778 837969 325435 228879 597691 38943 219908 817399 635501 72301 919769 460956 424412 686717 1029279 748209 633220 543982 183586 629832 215483 905635 941403 202356 466441 331031 950291 692065 738616 881723 642444 371038 158579 808961 386086 360216 732802 681045 82558 289163 874169 571419 995311 268740 504925 164716 153835 781558 147218 716381 474309 449367 678244 177627 91795 344993 722200 760581 945427 721856 217930 80076 516236 473253 526032 477681 490046 697217 296119 338307 561311 979639 66353 569490 16952 759148 984431 914222 549825 870107 455855 660464 195403 10820 454796 699862 715112 109573 294497 340584 23288 298694 617404 15404 961589 777753 158037 92853 309640 43244 151616 177228 718587 854051 93325 906681 686369 430365 68377 1025196 269455 994258 398148 716835 765919 491240 832336 26194 890141 575144 672571 265645 919655 637769 451713 266239 411123 678666 980760 33075 159876 589711 139626 1042333 993328 493906 562453 251274 557137 34583 336726 204665 484715 228946 681330 679562 312473 466599 878675 810647 406466 10764 559292 587509 886800 1041572 773705 272641 10025 721240 346319 989795 878757 86277 940886 957304 72142 347078 125250 597348 575496 297253 526910 557683 819544 1044459 27394 95556 645860 116157 853217 752502 442602 216004 211169 741682 1036939 506594 944310 829461 981697 49853 81147 701475 565782 620725 250071 259595 937950 895820 606687 236916 406915 218921 1012449 1003199 721534 46814 378940 855616 170129 941725 375416 350507 73924 938928 555120 729026 129526 102800 769725 489350 525896 294243 259583 735561 911621 880935 1044787 296176 248855 787713 833699 922902 679944 454191 1016501 938351 294345 930277 910270 193346 44841 768213 243260 88524 953581 411147 43880 349889 171021 219594 788568 517211 81459 696323 1000762 651791 190196 570048 1014668 541154 878440 5671 956914 846948 243294 647283 967612 305841 160830 898182 458457 352537 643841 783952 537805 178274 479121 586277 97176 614450 697016 67317 1031957 657270 10 183769 551225 283094 579237 269219 160494 492926 857320 507946 606096 799037 304946 846196 181687 174476 604429 50496 404209 866823 836999 800510 945131 1000303 277271 225631 541187 387762 217393 496603 797946 853915 944455 115224 915255 85607 156264 708261 314585 314755 30255 987512 260633 560311 940795 477568 686793 205775 258715 832868 587838 123271 888577 506350 1036910 21686 624677 612114 227776 940593 227527 940254 819128 341774 109734 919406 650019 811545 819687 298686 485533 350196 99741 726405 119514 664154 351648 381792 556424 617478 199665 327999 321761 341242 607712 689985 383523 288933 158210 902073 836323 978229 487340 298266 773864 845627 68236 759897 993787 861591 976881 889113 77209 573188 306471 263661 69393 284630 181111 980725 487908 412612 542461 834785 298236 262333 831565 706879 151699 524609 689622 573160 893798 178325 282114 881621 1038240 350460 338324 841048 695039 400448 576879 474993 404503 575312 349673 734989 740864 912316 1023140 316779 492674 818394 585033 158375 537468 807552 813859 908718 321182 37358 842517 217935 170881 1004480 235111 487979 550538 262921 223972 965207 773184 956513 403434 425131 183147 583606 290426 74938 146596 739020 339712 46237 117624 698 1657 748203 1653 1658 729822 1180 1299 729953 1127 1610 59838 1289 1385 65460 433 1235 912169 600 1245 633565 1493 1576 962286 184 226 366568 112 269 223258 726 948 602538 147 350 356330 59 1457 823864 1454 1629 397203 45 812 255954 1347 1365 45056 344 852 698379 493 1061 132054 1614 1658 745126 1073 1414 1041877 946 1448 427478 257 1399 806600 424 512 460514 981 1192 570438 2 1613 549270 1069 1365 716644 351 1236 360428 788 895 864554 997 1028 900979 712 1031 367307 631 1548 830273 1376 1568 963396 363 1616 1039499 798 1043 415846 1203 1513 149629 887 1215 423904 1322 1498 111934 1484 1578 662350 685 804 364045 1447 1626 815488 905 1334 275337 909 1106 294038 1401 1625 603703 1306 1524 907163 262 849 411691 997 1307 501780 946 1598 230094 345 1568 705552 69 1537 481409 1278 1464 369437 824 1490 393660 1418 1636 1021952 1168 1544 884159 759 1389 738701 1097 1175 663514 1527 1547 1020661 888 1210 161266 445 1355 76283 1412 1563 456235 687 1177 94254 876 921 538425 786 1556 244449 1569 1602 396934 27 1042 381651 1597 1639 99956 62 1165 676882 1601 1614 681959 478 1470 676121 6 641 418590 649 1024 260550 1434 1623 10767 1079 1089 653685 183 1536 922924 304 846 301275 1342 1384 267898 56 586 321565 402 858 254018 600 676 182043 542 1126 334551 1212 1212 302201 358 1621 761960 1434 1549 226606 1150 1516 237335 1427 1584 971157 121 696 428123 1424 1482 813 1348 1607 849124 737 1098 374615 1163 1346 252832 1519 1660 651962 694 1571 370034 1379 1665 118242 865 984 253709 608 608 639641 1122 1225 479720 882 1052 1041776 221 1615 964494 854 1626 648933 970 1060 565459 667 1276 620302 1616 1645 596582 55 642 181902 593 949 653361 1224 1546 11775 276 618 857463 736 1218 1039587 1394 1596 371801 1171 1182 834914 879 1233 794104 1537 1540 56330 383 630 761239 1473 1595 21704 1311 1339 265408 692 707 872031 291 977 1007422 499 1350 925615 1297 1567 423622 1643 1643 580201 1256 1403 218031 1433 1550 284115 21 840 17116 1365 1385 778306 35 1072 432370 694 1195 636148 1338 1517 108582 1513 1651 442665 634 1428 270466 465 955 457256 347 1471 564523 944 981 776407 856 1023 632935 1458 1607 578990 438 922 213840 6 1587 490416 1357 1658 677066 1068 1547 395317 1603 1663 113893 1516 1619 813847 1455 1525 791181 994 1601 814426 1639 1645 252365 172 1035 78630 1013 1283 194273 666 777 793681 1291 1443 815228 169 614 825551 1519 1664 225958 1052 1402 820200 1145 1260 597957 453 1076 844863 1261 1493 860125 1623 1651 272261 334 699 878714 1537 1644 8231 285 1224 812614 978 1174 886276 740 1190 494147 908 1254 898051 105 475 131527 1594 1627 560296 31 798 933138 1654 1660 28207 965 1295 584501 1368 1659 96734 512 1587 459492 1066 1356 579964 74 141 666555 513 1665 174738 1363 1661 629619 804 1059 1024816 1467 1551 476745 289 554 529801 1577 1617 163500 1046 1640 263645 987 1230 846113 622 832 786500 894 1271 1017027 1297 1322 459274 1073 1632 894447 1441 1571 91804 370 1335 853492 1104 1115 627953 78 1112 979526 510 642 865899 347 1496 815246 786 959 1001897 956 1351 579112 1369 1495 391204 233 1417 808764 1363 1573 654298 1245 1450 544407 51 148 382747 586 1158 1028570 939 1098 824237 896 1234 140715 1199 1625 624076 1362 1576 264349 444 875 430126 209 1356 198540 1185 1227 187444 345 1497 210238 30 370 422264 1240 1660 618164 141 889 1008384 1190 1325 491093 1033 1067 807642 954 994 192157 346 477 671351 872 970 604236 1024 1047 312918 1059 1488 761321 1106 1285 568485 1418 1480 634398 1382 1556 588818 721 1552 74290 216 1489 826132 405 621 970547 839 1037 416108 1574 1658 365618 118 1036 903165 1446 1657 1037908 1081 1438 977147 583 635 1009695 523 1308 1013944 894 1399 1018946 1234 1472 237413 680 1018 796656 548 1065 382090 83 536 850812 1302 1600 795690 1097 1424 692540 1085 1619 48600 781 854 503538 1185 1391 193214 278 799 441039 1193 1390 807889 1607 1651 748671 1395 1524 581211 278 960 217149 1336 1603 715506 735 1627 208366 1484 1574 360739 747 1002 557054 1492 1621 958223 546 1425 819992 257 766 142317 382 1483 411815 1530 1648 925823 454 1304 505416 595 1233 484319 672 1600 214791 1269 1541 880164 1657 1658 231279 363 749 872819 1262 1453 644276 1505 1556 553349 500 1018 11986 1406 1613 76085 1108 1623 967923 1655 1664 120584 176 812 554365 1024 1655 412330 1391 1550 256346 417 624 928704 328 1085 568518 756 911 169391 594 781 145352 1116 1496 904327 222 1040 4397 175 1622 569284 1236 1643 44135 1222 1532 321345 419 1028 58537 203 613 702744 259 317 171671 591 1436 442044 1074 1213 466672 262 1148 505331 784 877 556213 1030 1062 690831 322 488 944518 1469 1659 707639 920 937 769687 1518 1565 313131 955 1634 922405 1009 1283 602099 1 341 261473 959 1520 32575 1395 1457 995284 896 979 339781 778 1233 897694 580 1535 397661 489 758 303739 1124 1155 999753 1643 1656 302784 1654 1657 690453 881 1455 308189 882 1059 283380 460 1156 1029393 1234 1591 785825 1581 1625 1015469 1466 1650 875265 1605 1662 430931 1338 1588 148354 63 1561 846257 467 1173 911709 873 983 948105 452 1196 1048022 133 297 100687 573 1116 779402 439 657 401836 1338 1553 604856 534 1158 441299 1310 1566 1003075 29 777 653275 1017 1658 763316 710 1661 238289 698 906 544700 1318 1461 72894 1162 1436 614920 1041 1148 1000704 226 1299 687836 56 313 552604 108 1414 642375 1094 1447 29980 720 1484 966503 208 953 328714 1583 1664 724096 115 233 815627 360 1116 182597 521 928 396088 545 856 862558 58 1097 834039 88 1359 848501 760 1514 940191 984 1612 879431 29 761 721438 1546 1614 477521 304 455 20064 1150 1514 962125 82 1084 744385 455 1258 477462 771 1125 577671 1199 1598 790037 929 1409 670182 1624 1658 1003876 740 885 417851 1641 1644 417721 854 1109 351830 620 1147 942382 780 1438 1032278 795 1521 20786 1631 1639 83061 517 1354 860314 1107 1444 861915 79 1589 367639 917 1181 889412 889 1660 470806 853 1061 158065 1581 1630 246529 138 530 808371 761 921 791129 269 1360 458940 1187 1450 640428 877 1498 93284 1663 1664 541360 1469 1490 84394 387 777 820854 1081 1268 303517 1660 1663 983238 1208 1636 861306 245 848 320124 1235 1609 1003104 610 1581 668393 1600 1650 811888 635 1570 291669 1484 1594 261849 751 1010 579835 1485 1536 1047307 1536 1562 715474 410 1286 257010 1455 1515 846993 951 1566 277781 1257 1491 732270 22 1244 297665 1630 1637 464078 740 1396 342394 1373 1629 108367 180 250 761431 279 1413 265388 20 1326 747650 532 904 188518 1411 1468 175252 366 444 176625 332 372 397722 700 1529 380555 1128 1511 304621 680 810 297896 356 1263 869829 788 938 200011 1492 1541 95219 805 1621 1003985 434 1610 1012929 865 955 552712 549 1572 466527 646 935 749382 401 1189 808543 1035 1636 38088 976 1344 504029 368 976 4079 221 236 473155 302 1188 718719 752 1079 480870 404 1036 872596 1530 1559 1011111 1577 1600 371464 226 1007 7610 1374 1659 839523 1543 1608 744153 713 1469 285792 1596 1610 150372 204 1470 1004536 783 937 190876 1501 1607 372670 950 1116 42990 1321 1601 1002314 1105 1229 293571 265 1006 695762 1007 1527 491618 946 1643 933848 57 715 1038594 277 1299 958375 1656 1657 488144 1564 1618 1016429 136 158 913547 1266 1534 256820 244 1476 1035669 1489 1506 240231 621 750 275216 1127 1333 260085 337 1483 398793 783 1527 795139 519 846 94546 36 1026 955240 270 784 572348 749 1579 469631 860 1614 316383 1593 1623 360091 682 1592 608655 900 1561 900662 1071 1234 61795 775 988 718025 238 332 16310 928 930 776940 157 1548 410270 1431 1580 597137 1288 1386 777051 1291 1374 744110 818 1042 806161 1276 1444 57700 1462 1502 937995 353 416 247728 290 1623 755289 147 983 133381 1525 1594 374972 878 1097 344024 1212 1221 383891 724 1197 157307 725 844 443616 495 1565 4243 1659 1660 1044874 376 1623 468808 1073 1544 110160 996 1258 647122 360 1570 761982 418 628 762295 505 1068 823696 1273 1381 566656 80 1519 494561 943 1323 225042 105 684 675205 684 1163 478227 1081 1232 513746 655 1099 572055 1585 1665 993370 1617 1647 779619 1295 1307 136860 1602 1627 472712 1294 1313 991187 642 1368 197923 1506 1542 293836 1295 1402 626920 208 483 92338 233 646 167415 59 1001 588353 1522 1636 554010 1630 1633 600777 375 606 457165 220 1182 1003935 1444 1584 92945 443 1660 817139 413 539 987977 976 1340 124802 1159 1585 584418 1195 1658 213052 1523 1566 726534 257 452 184838 772 1091 848172 530 557 718496 229 610 944067 1050 1260 703616 840 1378 381026 325 1116 447142 1028 1544 942567 1171 1452 902998 144 754 1037871 679 1418 596248 342 1146 741520 657 753 976598 937 1659 780685 471 1389 591917 1375 1625 669312 1159 1533 954176 824 1197 67674 582 1641 584811 1518 1579 31548 1286 1358 918420 1039 1189 67633 505 1473 963897 463 977 978389 274 982 250481 1098 1130 975532 1472 1484 788710 432 1092 316292 794 1065 221135 1263 1297 467028 386 1156 396698 245 1137 2394 1448 1572 919370 667 993 756082 784 1594 731180 1573 1647 148957 654 931 1042624 1278 1556 911251 1354 1580 667481 1639 1652 158533 1009 1454 805689 1567 1656 825180 704 1220 627984 819 1577 669892 1262 1518 556257 45 117 579477 256 627 631886 1171 1353 142835 1154 1632 854041 848 955 922742 402 1485 597063 176 1574 111671 844 1572 942511 1012 1609 176649 774 1129 655652 1017 1455 1035966 463 1506 30996 398 998 83222 340 1502 435615 346 403 575562 896 1005 114260 1560 1591 1028395 46 1336 994490 248 628 360326 1576 1608 783392 478 1043 103438 733 1375 280545 1585 1589 419788 711 1125 1014088 1476 1548 497604 665 1520 946942 876 962 85688 847 1545 316095 952 1133 532998 334 632 207609 74 1100 853904 1482 1525 705040 1008 1489 3213 712 831 277173 1115 1643 891570 734 1484 561928 829 1205 888771 718 1060 923468 507 1021 829565 1552 1558 93768 962 1313 108610 114 1136 1000954 1272 1426 350513 1393 1481 683669 568 1088 471398 1428 1572 17272 1167 1294 807874 333 641 922219 231 508 355295 624 1275 313119 422 662 176257 1486 1580 881552 591 1349 274159 1313 1403 701853 1341 1605 364502 1228 1575 658918 1665 1665 272034 12 437 409063 803 1050 956902 953 1393 874428 152 755 416960 1662 1665 1040674 164 744 513905 959 1180 201587 780 1582 53106 13 421 885067 615 674 609636 37 122 557754 710 1558 669678 570 584 218914 399 1328 851765 1408 1483 171838 511 1292 980362 40 633 757677 347 1414 555108 462 964 647433 1528 1654 811917 1541 1607 690027 375 926 223474 1233 1274 857388 833 1450 454241 195 815 1007432 1077 1180 792733 612 990 436945 1179 1460 37990 1055 1352 276583 578 622 778142 1283 1515 300360 1017 1090 644691 327 600 467881 188 1507 704871 1401 1570 685254 341 971 778435 612 1656 766434 1519 1640 163116 462 978 401639 1004 1642 815633 706 1409 115990 1175 1634 858652 1111 1565 903070 18 970 819497 928 1122 637639 35 1262 662746 1655 1665 1014441 440 1253 579872 1202 1361 90405 1429 1488 188895 828 1468 945682 321 350 315816 440 1425 871503 89 351 291301 1108 1111 771593 362 895 911121 1104 1251 766246 1424 1434 920491 189 517 1023205 447 626 405664 121 1564 653830 49 708 309834 335 651 655767 3 1573 219619 127 1146 656627 1227 1358 185939 354 1339 736942 1023 1344 1025008 1346 1518 887350 907 1205 995287 64 588 97219 1604 1643 393433 779 1521 1043672 594 1386 301289 350 492 268426 1462 1477 463932 1048 1114 607745 1201 1473 91934 1570 1626 441991 1555 1622 250011 780 794 661311 1482 1534 434540 442 717 464817 99 1422 761353 1351 1627 823128 1231 1602 706736 818 1478 611268 19 1308 967048 950 1610 692293 701 1490 705290 100 1391 404161 628 1224 672477 233 1017 273599 1459 1621 112145 944 1469 273549 582 1407 964863 553 1359 1004186 64 1068 538483 848 1609 23254 483 747 123197 888 1064 472671 1158 1511 549674 166 1049 270533 714 1132 9081 1557 1564 103041 1384 1461 391959 291 1209 101796 1631 1648 490919 667 1641 603939 424 1207 536298 1495 1627 751345 880 1612 893792 170 581 376906 1276 1446 1004264 1204 1629 411030 1476 1639 77755 759 1506 415536 778 830 938941 197 1582 431186 1020 1135 725010 965 983 8656 343 792 417810 751 980 420502 633 1665 528594 293 1080 647752 316 984 950177 1534 1577 682259 1238 1373 127989 1404 1606 70353 648 1298 694668 1366 1586 181099 355 1484 343597 880 1513 616635 829 1451 400283 1508 1651 147924 979 1060 120184 11 359 64232 14 1417 903139 1503 1660 815478 649 910 572848 297 302 91199 767 1557 189513 109 1346 35183 1059 1663 766117 1168 1397 584244 1475 1488 670017 438 589 777907 846 1184 981365 1369 1599 1020989 919 1596 310192 660 822 951315 378 1184 909548 741 1176 981857 667 1255 716512 1322 1498 83274 381 1511 666476 1114 1420 939459 1139 1220 807661 1435 1464 838766 937 1103 191035 1430 1473 606539 857 1526 768994 1153 1663 139951 12 509 1038226 1463 1620 746340 520 971 199251 1546 1623 181993 1474 1513 818231 416 1286 591084 224 329 683134 789 960 188823 1293 1467 98986 522 1644 630365 61 724 902070 633 1641 990865 901 1491 812355 622 1551 827374 1187 1577 82122 207 1456 784132 174 1584 841901 1499 1517 734458 1570 1609 850603 1189 1564 866810 643 1141 681099 413 712 345459 1325 1525 637159 1252 1392 960927 614 933 538714 701 908 762737 644 1409 600763 1000 1399 503630 1325 1413 240256 461 667 159244 970 1586 713296 680 1622 116736 254 1024 696013 74 766 201288 1411 1607 443600 180 579 239067 21 237 751714 68 870 614291 1310 1588 31803 1504 1651 60967 374 1361 192794 1638 1662 769346 890 1358 34190 1193 1322 896516 1357 1455 147129 617 924 890990 1575 1605 595476 173 1066 314929 1431 1479 283242 763 1633 1039806 780 1282 73783 1315 1532 692803 1590 1634 128113 1656 1663 12336 1456 1624 802886 810 1002 672253 1096 1435 304326 765 1392 151933 472 1238 642252 995 1644 482978 1406 1525 1491 1597 1612 944311 1272 1354 315458 1488 1551 47040 353 748 811618 774 1487 915948 1300 1514 488836 414 768 978181 1123 1268 989287 1567 1653 897068 224 826 408766 446 602 103444 614 1533 580740 458 1646 824614 1437 1442 252880 401 1664 575336 794 956 688433 1132 1661 514584 304 768 842099 1114 1589 490722 390 682 151562 70 1319 950264 1137 1646 165795 308 1056 132870 441 1620 709999 544 1359 402552 1112 1422 382591 867 1546 914326 515 1323 926943 97 643 810388 1092 1428 255947 1580 1581 123487 270 857 548737 663 1064 31878 981 1033 643882 1512 1563 725515 1238 1463 109247 671 740 1026125 1448 1506 1046866 1207 1365 583293 1300 1369 983232 90 1239 617553 480 625 448530 703 1394 444708 462 523 580780 1432 1505 238769 1400 1649 925890 506 1522 38482 365 613 566939 746 937 341101 1620 1654 716451 1447 1571 48754 937 1271 1048235 1619 1625 172481 788 964 699125 1429 1646 380751 1489 1559 171724 12 525 595136 1154 1513 205175 420 1589 52436 997 1587 643101 1460 1521 986665 1535 1539 39504 286 1647 715024 1123 1505 857131 988 1556 646716 209 458 244441 688 903 623665 554 724 466818 744 1089 256418 1151 1252 543436 37 1564 987587 308 1159 557407 699 1373 626642 998 1415 969235 645 1555 556328 1515 1523 429423 1266 1311 144125 365 834 852835 782 1300 431298 587 1197 739042 1367 1380 702682 1499 1512 920206 1420 1639 328162 509 1150 302582 1330 1609 109444 1164 1335 319364 1554 1593 100119 1040 1274 174248 369 1240 750405 396 412 112353 1021 1544 790272 586 1200 901360 363 1587 739884 596 1136 365572 1228 1326 109602 1235 1467 517981 524 679 677588 1485 1635 823012 69 138 502742 507 1479 957003 205 210 746538 1315 1625 564439 989 1409 446165 1334 1456 983985 504 1044 752705 1289 1372 632274 781 784 737919 81 911 202968 83 1619 364932 1273 1419 451701 641 981 656700 1635 1665 578809 859 1174 178078 1611 1641 540460 1319 1478 588605 255 891 169417 245 763 889652 1339 1439 560288 126 310 762623 409 1274 109753 1211 1279 193178 1454 1462 41216 1394 1514 1015430 614 1381 1009412 776 1441 666557 373 560 543612 267 1535 1002987 1271 1627 464592 829 1530 538354 141 1318 319275 360 647 534641 102 1102 417992 515 1338 543178 1393 1606 385487 1049 1487 801559 542 736 304246 1422 1577 84478 754 998 784295 719 1499 10204 789 1164 562669 1445 1652 350599 181 1598 120267 1530 1652 770862 1038 1638 307783 514 878 374790 1110 1157 117748 715 1017 546693 909 1190 690408 734 1556 200987 645 1040 166713 1004 1247 484514 1513 1623 911914 245 1086 748105 983 1538 554094 561 1495 935688 426 563 485830 1124 1451 938092 1442 1627 101465 758 1130 208334 1078 1214 545860 686 1583 965194 1655 1655 995252 1041 1230 677623 1393 1627 769203 61 203 480194 1082 1127 490395 1517 1651 414082 1142 1515 598727 348 725 831994 650 936 848850 537 779 343557 1407 1662 377267 165 1419 243750 244 1649 1030980 1288 1364 145179 230 1147 352636 709 1010 584019 101 1087 1011131 171 334 587649 458 628 854820 621 766 998087 1510 1616 255173 1117 1212 545923 1023 1385 33134 604 1552 38138 1642 1662 34494 1324 1523 561802 1007 1530 4243 1373 1565 675779 616 667 353785 1115 1339 386825 1195 1410 876614 1035 1231 711531 1492 1600 880973 1448 1609 239387 1561 1623 657163 835 1453 1032654 1136 1627 281169 710 1259 234937 131 1413 386126 1010 1334 892261 430 1416 93530 109 366 658386 1206 1648 1025853 1639 1643 728738 900 1057 378272 1265 1312 525600 1347 1367 500308 696 1200 703319 949 1319 373943 766 1065 709327 1517 1625 111520 373 1167 949826 730 1206 783130 284 956 148329 404 1011 278133 928 1364 915652 827 1295 916517 512 590 155783 1192 1589 733084 1605 1630 131118 742 1632 92622 1255 1255 585306 789 1181 312181 1263 1597 960486 1118 1379 820327 603 679 809910 714 1037 1038205 569 1513 572701 1355 1538 189821 1450 1569 619144 560 910 395203 1408 1428 189428 1066 1608 697213 949 1274 291397 716 830 157635 1481 1533 785322 1372 1633 578356 29 433 317659 234 1232 694547 700 1636 835939 991 1530 422170 287 1081 961572 1002 1276 809710 1380 1665 713214 1297 1436 251703 612 1485 23837 718 807 202200 141 881 927631 870 1338 222503 968 1128 1001468 401 1473 595787 587 1437 806949 327 836 176560 148 387 10988 20 1292 101391 1054 1184 358746 1056 1167 482738 14 834 715978 451 1106 813885 842 1394 892193 386 748 1047276 345 1440 108202 630 1177 401362 1017 1032 65393 47 1218 617431 1545 1601 812016 845 1175 672727 1490 1543 216080 1203 1516 244342 439 679 177747 1238 1644 845774 741 1477 128851 1556 1643 701761 342 898 759352 943 1358 476991 365 1092 738493 43 1620 377227 96 118 451080 245 1400 497901 865 1617 636620 36 1362 876380 184 838 938572 806 1578 256917 1606 1632 499068 1288 1353 568861 551 1397 701946 444 920 319767 642 1536 709739 1401 1474 804685 259 854 869934 979 1414 109169 789 988 358837 99 1042 882546 243 1001 973531 314 469 607090 1118 1515 811993 1620 1657 986065 502 1396 856047 1525 1613 395983 832 1579 20055 1591 1622 434340 1322 1353 1023829 1532 1620 303141 383 1514 635858 758 951 768301 1171 1284 622631 1077 1316 774103 711 1183 273442 1182 1415 954921 607 883 450526 898 1638 448188 447 464 389185 1072 1493 744638 857 971 200891 810 1526 75412 1616 1651 1043693 800 1111 630081 199 361 670024 1370 1514 774566 987 1250 725022 1234 1413 197599 26 1431 703967 749 1204 924303 1470 1472 129051 611 1027 319091 1094 1386 945854 918 1494 554992 1098 1425 417552 1148 1281 32316 799 1368 134679 111 129 314038 1253 1508 833427 1251 1367 44397 1053 1240 817056 610 1358 504738 620 957 548982 1107 1344 358178 877 1620 928482 1242 1446 549655 1090 1219 881883 763 866 227654 55 792 158775 918 1498 1012501 447 995 1037109 432 1185 822039 1521 1551 752991 5 152 666539 899 1460 738653 519 1250 937617 657 854 93403 713 1651 824865 204 998 658387 524 1593 955239 949 1280 36553 1601 1631 113018 81 882 259376 1128 1638 385099 905 1067 921208 1127 1132 988831 1616 1629 456402 954 1370 54315 351 928 717806 1348 1564 796415 853 1496 398502 423 427 399321 1384 1608 770613 678 1253 825952 443 1319 283345 458 1029 74658 1524 1637 683162 974 1533 220600 1262 1483 908580 335 908 944623 936 971 974205 1141 1192 542869 730 1230 151916 888 921 456292 183 326 1004046 1409 1555 908872 1564 1644 505614 1325 1567 640261 1272 1609 448169 1104 1649 116532 363 579 51848 1245 1548 277910 85 1154 217446 1000 1325 402919 1335 1635 138645 1247 1370 493606 1640 1647 959566 1420 1495 266703 1114 1636 905525 740 761 786087 564 1370 944719 1377 1398 113265 1452 1459 684249 856 1440 821172 1169 1221 538360 1524 1541 730032 1093 1315 423673 1353 1526 651379 890 1158 566083 945 1189 299085 1443 1559 441849 208 227 402037 680 706 95103 225 428 90037 1621 1661 2830 538 1585 767740 26 934 971130 1584 1642 579678 525 1357 881484 461 1409 45394 352 1367 505121 266 521 267770 1467 1476 704527 630 1578 933322 703 1543 228156 1293 1566 861629 1273 1504 758827 661 1208 454165 143 1559 130706 1398 1615 168311 356 1393 698257 247 729 1017301 1172 1502 878267 1088 1597 375126 143 1317 867504 441 782 666113 309 595 188426 1128 1262 661850 1199 1620 349735 567 1113 201492 959 1261 996237 412 1013 597640 915 957 875542 1177 1605 560396 1090 1458 107007 1190 1374 834811 1549 1620 224085 1643 1655 704747 664 1128 966606 846 939 825771 1503 1613 586039 448 748 797636 106 1062 817568 1025 1061 583339 130 1105 791596 216 1086 813689 861 1183 25966 1665 1665 369869 1540 1634 882032 1210 1265 77038 1602 1655 882546 785 1384 747820 13 1438 244583 578 786 918420 325 1382 690673 1637 1654 315642 311 1148 477506 31 1597 489855 253 299 708133 1525 1603 892846 1178 1500 477921 1306 1477 366814 983 1216 718800 552 976 355490 52 1602 309626 448 1186 496370 199 1231 807070 1546 1608 774818 30 133 958801 399 1594 507080 888 934 198336 1281 1576 495410 165 719 239762 378 1354 715483 773 1102 399290 17 294 842657 1302 1373 786895 845 1088 614315 1505 1621 599981 451 807 778869 762 814 295272 439 654 278090 545 1490 777757 1419 1600 635914 1041 1210 39545 343 1297 963647 509 841 690324 133 932 921642 756 1366 2870 1631 1651 170153 133 1473 316835 1413 1466 208823 1611 1634 897685 1532 1584 890217 658 1612 660394 1186 1214 943223 876 955 187498 301 1580 478396 1104 1404 1004878 1059 1216 6488 1022 1300 375006 44 1084 664144 1382 1399 924466 409 1203 783152 935 1636 352441 1161 1615 709844 1495 1630 814875 765 1665 477596 1419 1652 518468 280 1255 58634 1005 1587 685775 993 1310 301048 630 1069 254338 506 1169 277814 488 772 210849 1495 1507 730466 284 1009 552013 567 1532 935945 1592 1623 702426 185 700 969048 1362 1583 758653 1146 1659 1033323 346 923 598473 492 897 603077 1554 1576 299815 610 634 156598 235 492 585185 11 1552 917596 992 1036 731571 315 1131 42957 827 885 999488 853 1027 402154 123 1384 136707 742 1209 433310 430 482 585329 216 1265 673600 836 1588 152511 599 676 766590 699 804 56483 1003 1479 384526 415 622 572928 280 315 659500 276 348 31395 10 507 368833 885 1327 1015572 501 1391 314380 657 1084 221099 1547 1555 927753 1284 1295 270490 205 356 609292 998 1344 18292 1369 1458 664634 1585 1599 900042 1444 1493 659944 912 1327 461781 1362 1388 699100 1464 1655 348643 289 1611 273936 130 268 904115 453 505 45403 729 816 633256 227 959 465405 1166 1485 712804 1404 1653 896090 514 1191 795905 255 1052 954407 25 974 372256 1007 1302 342346 1354 1484 359014 967 1033 686214 1335 1488 247853 1301 1335 913397 1197 1420 790675 335 520 224951 567 1640 729085 1282 1503 757527 313 926 997297 212 214 564446 1143 1637 1021219 1151 1464 546729 588 718 652927 440 782 802690 1039 1491 584218 861 1106 419408 1620 1631 124089 1446 1568 251550 95 1059 736741 1601 1665 512072 112 984 266795 1577 1644 233219 184 1657 812911 1198 1407 999032 721 988 643373 1450 1630 235109 1065 1555 942596 1586 1648 38893 1032 1211 949910 1357 1364 920564 1105 1406 785852 118 574 200925 10 1395 802254 1524 1650 1006204 1647 1665 99525 989 1521 1041820 119 991 277148 1522 1619 36515 776 1409 992454 1133 1622 984987 523 790 1037179 328 586 411133 3 1017 149304 1515 1615 1038722 1077 1484 455512 16 887 613782 1036 1383 808556 1285 1574 635963 1267 1321 350690 919 1573 818776 73 455 192908 998 1242 891206 1511 1592 556349 817 1591 252755 97 1637 903929 987 1087 217035 1295 1558 24644 1010 1533 299819 218 853 567520 804 1510 542602 464 1550 315076 1333 1431 798294 291 1445 938719 106 1330 10270 480 510 298129 1640 1645 306653 1110 1176 684817 1018 1219 173172 1366 1468 538711 779 1357 401019 73 942 160602 1266 1307 896320 494 1436 684482 798 1547 203847 647 882 662695 601 1539 555493 383 1647 695091 161 1076 969193 299 858 382988 18 924 619553 1423 1563 242324 133 683 739008 1201 1237 638718 241 816 803495 963 1053 945396 355 645 518948 1177 1228 790160 178 1458 261912 1506 1559 487161 1052 1576 781245 789 1282 262425 1150 1465 422213 1267 1642 154381 1331 1589 675504 997 1527 764 859 1020 530963 295 1107 293741 1562 1618 46432 161 859 912128 1429 1557 800947 271 1329 588611 253 1571 128669 1317 1640 19476 1050 1294 900194 505 783 172834 1107 1559 548610 673 1478 311268 1176 1232 655228 1009 1264 445405 822 1478 104593 1127 1214 162558 1241 1341 380574 335 1483 661951 1515 1621 398131 1177 1601 403990 669 874 221569 1316 1412 94687 1310 1385 765724 524 836 490530 1498 1585 822519 164 1574 821474 798 1565 328490 49 429 625419 392 1410 832543 255 554 1009704 1329 1506 314546 574 1253 150797 1523 1590 31392 288 703 627862 1517 1565 802971 817 1455 729707 412 487 177888 1003 1148 606861 1510 1629 100468 654 1611 1016364 1625 1641 352846 719 809 456319 1368 1653 781877 1618 1652 384593 1487 1583 1044090 579 975 243532 285 368 318022 1418 1537 281855 605 770 103447 1159 1588 963648 812 1405 600897 366 692 51713 802 1204 177484 890 941 606274 482 715 828360 709 777 72339 23 410 363117 166 227 655683 358 1148 507748 1208 1211 1028283 171 950 799476 113 182 967795 1528 1563 317839 734 1115 385028 331 1148 316524 27 1357 880639 1531 1546 180634 1075 1659 959793 650 1385 313166 705 1031 203204 1619 1623 819335 897 1619 996724 307 1237 773399 1505 1507 487201 1006 1357 689256 381 720 5963 961 1635 126441 1429 1523 381502 361 904 786532 776 1251 378109 50 200 167741 1290 1358 438881 61 132 991821 397 417 653767 883 1506 813816 364 1431 689287 1508 1541 566380 80 1492 310864 1235 1377 920301 1505 1632 327824 872 1490 832058 1086 1489 147170 422 546 128664 886 1629 784158 575 858 758695 1145 1184 734134 517 742 381400 520 864 632545 468 641 846967 1381 1614 445580 1013 1615 105847 212 629 271713 666 1514 840026 717 918 92713 1223 1227 641878 11 1416 170546 313 376 281173 347 1664 394372 758 1183 299392 520 954 203111 1511 1515 462016 662 1361 855106 1024 1146 456444 1421 1421 1038889 454 1594 281555 900 1036 63846 639 1520 733370 641 1470 276001 410 1091 299406 842 1484 288287 9 988 699483 787 898 784568 465 992 173097 1300 1584 341329 1208 1276 1002687 775 1004 521354 936 1334 320982 1219 1453 417246 902 1614 94574 562 626 638947 373 1510 534654 597 1354 1039405 1591 1610 620568 1173 1457 939076 168 706 959579 809 1476 864661 517 1015 786379 33 637 658542 1205 1604 686381 1479 1549 776833 821 830 444973 1329 1520 624710 33 745 510838 550 730 524197 340 808 238316 51 1089 990271 246 1414 203438 851 884 547483 291 854 971161 1371 1524 476968 434 1369 68952 215 440 178510 105 1286 441099 271 416 113751 517 690 277026 300 640 268222 1236 1399 990648 711 1325 447301 676 783 694375 713 764 413321 888 1204 887894 1389 1636 519674 1434 1543 865245 645 1045 40003 467 1633 513017 556 1067 492743 636 1334 318875 1582 1620 164436 208 564 464782 1223 1621 250939 1653 1661 136966 1207 1643 986014 151 1034 394613 334 1400 957709 726 1577 125671 1114 1188 549552 1360 1373 502322 233 1043 41467 1542 1602 720266 661 855 71065 82 1313 595065 1073 1535 914755 548 1071 508270 1078 1238 1025691 75 103 126161 207 739 395862 115 589 63706 1379 1596 786437 70 1392 796855 1538 1610 714236 1071 1107 56442 1166 1631 794140 413 1628 566743 81 173 398826 1497 1620 791002 260 817 482063 377 1493 881369 515 1398 525467 139 1118 32777 37 882 325461 373 908 162634 1612 1660 819940 566 1568 325195 883 1093 744175 874 1411 828415 93 190 928286 1345 1535 148940 446 798 5675 124 1110 170000 1407 1572 679431 244 439 220493 443 1526 38201 120 867 71252 1342 1367 679534 11 906 176810 369 1291 797468 1556 1572 582509 474 1644 490003 1179 1412 449551 1056 1600 1032446 216 1659 133596 1486 1642 86733 568 1355 444653 805 1229 500761 36 1519 385020 1206 1397 284613 561 654 988447 614 1648 417999 1096 1163 622275 1139 1320 85675 896 920 183759 107 296 848459 1344 1650 694027 1310 1411 238808 1496 1533 135662 83 826 441145 1486 1641 505261 1625 1634 706156 1257 1278 783476 497 515 92738 789 1283 751645 1471 1620 298611 1314 1605 976710 1323 1445 947466 1147 1195 61658 408 1336 204080 577 735 499113 314 947 889950 456 1339 868199 1422 1577 817883 613 755 994828 376 854 42526 671 744 656682 74 474 877230 1657 1663 351359 671 885 247380 582 814 1006202 860 1184 682865 1458 1586 655546 68 1142 414505 1662 1662 662666 504 1053 44252 1611 1642 715578 903 1081 185120 14 457 995817 1543 1616 942275 326 398 726094 582 1573 543779 1315 1639 988851 91 1191 686538 247 950 270247 930 1531 80516 1618 1632 874641 430 896 295919 195 489 539472 1461 1584 553881 727 1604 765238 1320 1427 380440 752 902 11254 1622 1634 495547 877 955 894824 938 1566 173359 1178 1528 675008 981 1479 538438 374 927 141791 251 920 729959 425 1242 905386 1330 1504 279408 1382 1511 707269 409 1337 200520 1334 1397 978175 799 1256 482195 1576 1630 307478 1225 1510 836533 1501 1590 76552 1052 1455 720684 1566 1625 831613 1227 1401 297555 1064 1248 873014 731 1306 708939 791 1573 275924 1230 1425 513608 1078 1604 72338 1249 1634 259820 397 825 451225 1144 1577 535976 953 1142 919107 700 1619 67646 1004 1386 259168 323 714 505561 528 1632 134485 205 1657 204510 1267 1302 787963 1401 1578 483711 1229 1537 649171 451 1293 44000 1317 1526 552386 1059 1511 206901 1663 1665 682682 214 682 231987 1546 1659 566898 1642 1646 383941 1438 1539 80350 1206 1373 625245 179 1412 1023820 1272 1437 497051 1646 1649 452714 959 1090 1041019 209 436 959243 194 1169 693217 1355 1589 451853 498 771 729226 66 987 1028826 76 1512 1024616 618 1306 991112 213 711 538931 980 1242 152150 807 941 911053 742 1495 998186 1262 1496 437781 1470 1627 858471 1012 1014 133734 1665 1665 297363 741 1010 90911 1661 1663 609128 411 1148 1000610 648 794 556339 603 1633 120033 278 1418 360773 27 181 207223 461 1119 705407 1127 1261 584452 371 472 27629 1616 1663 542546 249 714 806490 714 1336 211157 568 993 388128 185 470 631686 1490 1597 285704 961 1010 180272 1635 1641 521221 139 780 368415 860 1455 508997 432 1372 209535 727 1273 74066 1583 1592 504202 93 1120 866102 859 1387 1038792 171 1364 759312 24 1598 731259 192 551 959408 659 1259 169228 504 1369 67215 407 678 809841 1545 1661 261738 821 1171 720818 1635 1648 1037988 1108 1531 783639 728 1296 356610 872 1602 1007120 1062 1346 218633 1381 1630 36214 228 1366 273427 1446 1530 543002 546 949 506508 699 1534 94415 82 965 637945 818 1581 104366 373 1288 579231 792 1316 677140 747 1341 214405 382 807 442387 1599 1623 691243 42 510 429093 549 1497 475132 369 418 40532 414 466 1789 1084 1203 1038252 458 1305 286940 1428 1654 872542 91 703 227879 1334 1504 1021279 1441 1575 151236 69 1043 721082 818 1136 160453 527 974 905819 1325 1651 20032 1193 1658 79800 1536 1551 252935 1392 1419 883470 1130 1475 423990 524 1272 667694 102 654 244499 1141 1196 884365 50 936 291800 1544 1550 470958 608 937 721990 1541 1550 574503 114 1519 109688 1222 1320 819768 1449 1453 662093 268 503 483530 118 860 201935 1012 1361 258202 1372 1655 357543 1358 1486 117743 61 293 434527 1339 1597 619331 667 990 616038 1604 1649 26830 268 1573 112357 1052 1144 601637 1453 1523 1015915 1520 1559 306251 1586 1623 966107 853 1182 284727 710 1589 959934 1614 1655 274244 1489 1577 528955 1143 1409 905342 1094 1523 99271 822 998 413309 20 1150 927038 995 1265 802977 516 1372 886408 1063 1485 435083 121 200 922686 824 864 324346 613 1317 593034 1653 1659 539520 334 805 761811 593 754 450102 465 647 17586 539 877 942127 647 761 808279 1176 1367 1002620 1316 1571 322978 843 1560 512338 155 437 550554 1041 1325 304902 408 1513 770183 825 1060 8130 587 1602 129408 1341 1654 692381 735 802 851676 1446 1566 942497 1655 1658 314780 555 1084 212816 1109 1329 333241 376 399 552762 1303 1628 568315 286 575 178601 1080 1616 288537 1078 1665 336438 173 587 907259 811 1349 928528 918 1137 590857 199 1476 1012810 634 1639 544259 527 1226 528336 746 896 475966 935 1515 520263 392 1110 61821 423 478 858126 1493 1540 859193 92 964 583050 507 1276 414425 375 1602 550539 1291 1304 292715 1535 1614 383279 257 854 975313 572 820 379121 1070 1132 1045753 1269 1345 870034 1618 1631 486795 713 1567 869956 666 979 256784 1418 1456 584046 183 1641 981907 878 1105 879411 652 713 425439 1257 1620 1031888 783 864 606306 1334 1430 17962 676 1655 861540 556 1185 372805 1322 1491 545524 745 1484 377552 1459 1606 771900 1254 1569 463165 1603 1643 107778 1605 1607 786552 1534 1632 356813 421 781 12792 1215 1353 834426 1650 1651 1036891 1265 1319 179529 840 1405 464891 530 660 469934 902 1356 292111 1078 1664 709004
样例输出
1046664 876149 1037402 1046726 1041879 1048461 1046135 1040521 1041428 1047036 1045794 1047794 1047359 1047964 1048570 1004708 1047461 1048557 1030200 1047464 1047907 1047586 1040975 1046226 1048369 1041011 1047897 1039690 1040567 1047269 1047656 1047843 1047458 1047243 1047803 1045484 1047264 1044988 1046354 1034206 1047995 1043250 1038360 1046257 1042424 1048143 1047926 1047771 1047718 1047959 1045427 1044015 1048275 1047557 1044232 1041626 1045948 1048208 1036070 1042169 1047354 1045701 1008256 1047734 1011841 1046361 977691 1047940 1047938 1047565 1047983 1036434 1047662 1042188 1038387 1048135 1048266 1044143 1045375 582798 1048509 1035661 1042400 1044390 1047204 1045022 1048341 1038201 1037872 1044218 1048184 1047559 1040289 44853 1024794 1040156 1048328 1047205 1040967 1046895 996977 1042379 1047112 1048465 1040044 1045762 1037968 1006694 1048119 813422 1048574 1043421 1024799 1024943 1047096 1044746 1048291 262524 1047482 1043718 1047168 1010023 1048345 1047960 1047446 1027375 1048219 1046918 1047053 1009046 1041860 1031475 1048394 1048307 1044146 1047098 992388 1022348 1025235 1044526 1028846 1047063 1043946 1023838 1043720 1048321 1045313 1048039 1033362 1047631 1046825 1010053 1044879 1046407 1045805 1045569 1046307 1043688 1039981 1047884 1044104 980558 1045820 1045811 1048502 1042185 1029440 1048427 1042392 1046628 1035006 1044735 1044405 1045389 1048405 1033972 1046491 944566 1048015 1048430 1048255 1034331 1048413 1047984 1048075 1038864 1044109 1048402 1047587 1036587 1047242 1048117 1044942 1032112 1048036 1047568 1048269 1047938 1047525 1046978 1047663 1046971 1048489 1047841 1044170 1016739 1022145 1046885 1047748 985188 1045602 1041748 1042453 1029522 1047773 1047770 1048169 1047489 1006861 1048393 1037918 1045142 1022786 1048424 1048410 1034084 1029442 1048455 1046959 1045757 1044004 1048247 1026345 1047197 1048445 1021659 1030420 1026525 1047281 1043405 1046710 1047530 1047037 1036648 1047882 1045575 1047242 1045157 1047849 1045016 1048484 1046197 745689 1047842 1042294 1040990 1048193 1043081 1047615 692676 1046907 1046727 1043547 1038369 1047091 1045852 1040209 1045397 1047947 1046833 1044232 1046659 1048261 1044305 990346 1048544 1043458 1048379 1047222 982026 1043219 1047353 1041321 1036974 1047143 1045668 1047874 1047946 1043817 1027568 1043802 1048284 1047641 1025668 1004160 849342 1048509 1046223 1045765 1045086 947233 1045133 980441 1046276 1048517 1048057 1044392 1046638 1040956 1048142 1048374 1047122 1047957 1046685 1046373 1045602 1047622 1048272 1043366 1045269 1045305 1047443 1047987 1048197 1046441 1048454 1047899 1042974 1044874 1048522 1047026 1042143 1045959 1047051 1047463 1046346 1047348 1046457 1039517 1048392 1048323 1047488 1046924 1047694 1046664 1032330 1043575 689324 1047963 1046799 1047674 1045918 973009 1044251 1043809 1048360 1047215 1048298 1042751 1015776 1038059 1030470 1048517 1046126 1047678 880048 1036376 1048494 1047989 926844 1042851 1046235 1046718 1048438 1045783 1042512 1036835 1044976 1047297 1039836 1047519 1029467 1045340 1042679 1047430 1046919 1047606 1048465 1030840 1048262 1047789 1046058 1039795 1028787 1039437 1047260 1045727 1035413 1047884 1048473 993544 1048312 1047978 1045483 1048401 1047337 1047872 1046467 1047603 1048039 1039374 1048325 1036451 1047749 997649 943584 1046479 1046402 1046526 1046619 981801 1047761 1048528 1037687 1044255 1047956 1034586 1046543 1046546 1048000 1047154 1048392 375227 962548 914737 1044021 1048456 1022810 1035192 1047141 1048136 1046825 1047670 1048454 1036640 1047770 1047901 1047373 1047755 1044086 1042563 1046451 1035573 1035399 1047657 1045182 1045082 1041190 1048571 1047303 1005310 1043745 1047440 1045822 1032821 1047188 1024494 1045366 1034062 1048440 972080 1048415 1048383 1046069 1048491 1048162 1042504 1039208 1048002 1045495 1045486 1048261 1022524 1048487 1030580 995336 834217 1047527 1029951 1046858 963945 1037595 1043037 1048179 1042550 1044632 962123 1044660 1048128 1045219 1047814 1041489 1044453 1045739 1047773 1039237 1037752 1046044 1032848 1046586 1048353 1047407 1045618 1044599 1046596 1043540 1047961 1048048 1032008 1045762 1047682 1048252 1047044 1038005 1045196 1026386 1027985 1034721 1046343 1046371 1046752 939157 962692 1047797 1042732 1028299 1048400 1048364 1042125 1040469 1047572 1042107 1043832 1033977 1047609 1029867 1047813 1047992 1046990 1046954 1046943 1046569 1047973 1047632 1047387 1042815 1046990 1047529 1046926 1048350 1046731 1045138 1048358 1047478 1048483 1041966 1047841 965543 1047336 1043614 1045661 1048240 1048534 917397 1048497 1048317 1046343 1044504 1047613 1034405 1043561 1047637 993442 1047998 1038840 1046746 1046115 1047942 1043013 1047451 1009958 1047331 1047660 1047216 1037549 1045547 1047661 1030914 1040778 1046727 1048165 1042833 1038876 1046767 1048155 1045791 1042880 388570 1046347 1048439 1048414 1046243 1004991 1047247 1019798 1043526 1038258 1004089 1043078 1048530 1008793 1047229 1046614 1046725 1047962 1048318 1048148 1045994 1039051 1047627 1024247 1046604 1047118 1047378 1048076 1046381 1042046 1031934 1044030 1048500 1047486 1046956 1035966 1048479 1048544 1045037 1048565 1044325 1042191 1047784 1046668 1046769 1046372 1048245 1035828 1044523 1040694 1020152 1048450 1046581 1047933 1044870 749616 1046281 1048407 1022523 1041992 1045418 1047802 1047927 1044422 1047067 1048285 1039984 1048468 1046792 1048072 1042756 1046828 978320 1047295 1045080 1042805 1025788 1011686 1048300 1047399 1028738 1041125 1032542 1047641 1048425 1048071 1048510 1045702 1048271 1047862 1047359 1048007 1046792 1047231 1044175 1047181 1047934 1047877 1048248 1048186 1047114 1041704 1043064 1048462 1047437 913560 1022751 1048372 1020142 1046473 1048088 1047531 1047716 1044015 1047044 1048287 1038670 1048244 996652 1048558 1040172 1044108 1048328 1044122 1047950 1048099 1047860 1030771 1047442 1048548 1047633 1046892 1047393 1046950 1047521 1041074 1024161 1047490 1048407 1042193 1043269 531313 1048386 1047331 1048276 1045651 1005656 1045094 1046576 1048383 1048200 1043210 1046997 1047076 1045191 1039922 1048398 1046982 1045713 1021348 1044784 1027940 1045907 1048321 1045730 1044376 1046657 1041278 972219 1047311 1041521 1046491 1042972 1048500 1043554 1046956 1046583 1045782 1043711 1047293 1047992 1020872 1044826 1047629 1047901 1046616 1048300 1046682 1045593 1034838 1047855 1046805 1045527 1047456 1048183 1047013 1047312 1048515 1048029 1043555 1035340 1047849 1048206 1048415 1048055 1037112 1046466 1048132 1039623 1046614 1007056 1048037 1043135 1047191 1048280 1045338 988032 751356 1046040 1047080 1046766 1047250 1044059 1047732 1045728 1009574 1015709 1045679 1040786 1046708 1047864 1046451 1048490 1040575 1048500 1048234 1045903 1048542 1008499 1048525 1030404 1044181 1047500 1048209 1046688 1047917 1046148 1047357 1048534 1048210 1035636 1045198 1046341 1048295 1043035 860348 1047977 1040915 1023625 1040264 1047504 1048105 1046872 1046746 1026092 1046717 1048262 1047716 1029744 1027305 1045016 1048489 1039430 1042793 1030986 1047837 1045590 947353 1045630 1043733 1025227 1046294 1042470 1044448 1047276 1035113 966827 1048464 1045215 1046491 1045345 1044563 1045610 1045913 1048209 1047246 1048148 1047472 1046248 1047474 970604 1042244 1045766 1048446 1047459 1045276 970702 1036103 1045948 1047275 1044742 1015929 1048081 1046524 1031648 1047963 1047388 1048446 1048213 1032497 1043811 1046211 1048507 1030987 1047770 1016024 1046972 1038584 1032460 1047707 1040417 831267 1048419 1047317 1046801 1047763 1025746 1047324 1031086 1041818 1047783 1046635 1047334 1043080 1048536 1025059 1041466 1037806 1048347 1045017 1042427 1048560 1044206 1047892 1047654 1046659 1048530 1047959 1042105 1048093 1047124 1036300 1046379 1048360 1043174 1047359 1048574 1033923 1047623 1041740 1032199 1045296 1041819 1047935 1047909 1039545 1030841 1048102 1047868 1043290 1043652 1047657 1042354 1040809 1043088 1048523 591966 1047146 1045169 1048197 1026663 1038759 1046928 1047671 1046106 1047168 1041385 1046801 1047977 1041058 1045092 1038214 1048106 1036980 1034314 1048241 1036859 1043031 1045282 1047841 1037694 1046497 1048440 1045947 986155 1047554 1041194 1045306 1038529 1038499 1039656 1048034 1046984 1046597 1048389 1046038 1047872 1044988 1048005 1046588 1044141 1041836 1004705 1048106 1043923 1043194 1043326 1047767 1045462 1045849 1042682 1046940 1047933 1034285 1043205 1043346 1048345 1036959 1047055 1048106 1047144 1046725 1048220 1048457 1044885 1018961 1045769 1043892 1048285 1042752 1036787 1040393 1043525 1047321 1047758 1047820 1043794 1048253 1047762 1040577 1036854 1048064 1024827 1048571 1046978 1044933 1046884 1047354 1042592 1046417 1048223 1031190 1024715 1047718 1046927 1046098 1046874 1048539 1048488 960000 1048379 1009665 1046530 1046900 1041633 1044291 1046711 1048458 1043901 1048351 1048356 1047036 1046865 1046971 1047340 1048480 1047027 1044539 1046446 1023037 1036533 1048124 1044186 1048040 1044849 1046777 1046800 1047592 1045486 1047418 1043672 1048237 1022527 1047278 1040876 1047272 976473 1046791 1029536 1048177 1041427 1047035 1046050 1047074 1048228 1043038 1044401 1002858 1046031 1043666 1048039 1015043 1044812 1048154 1034757 1042213 1028239 1048190 1044156 857215 1047818 1032891 1048226 1046164 1034915 1047865 1042804 1047639 1029902 1036700 1048396 1048273 1046595 1046584 1043013 1042575 1048011 1048538 1045701 1047252 1047350 1028486 1044205 1047765 1043881 1038966 1047769 1048073 1048554 1047685 945882 1048365 1047360 1047115 896534 932797 1048569 1047444 1046056 1048359 1013374 1046818 1044632 1047822 1047885 1032186 1045933 1047630 1047195 1033899 1046081 1047235 1004745 1040533 1031200 1044979 1046215 1044388 1046225 1043877 1045471 1047466 1045217 1048107 1043431 931232 1042335 1044575 1033289 1046843 1036999 992792 1048345 1040897 1044329 1043121 1038978 1042035 1046535 1043179 983932 826342 1043578 1021866 1046669 1047694 1042223 1046480 1048461 1048553 1042320 944830 1048530 1048497 1042532 1043018 1046584 1047134 1046047 1046810 1048440 1048106 1047149 1048542 1048099 1047768 1047932 1047537 1048223 1037376 1044703 995278 1047784 1048418 1045824 1043122 967650 1048367 1042826 1030327 1043828 1047288 1037545 1048507 1046802 1047547 290741 1035749 1027325 1043699 1047311 1047120 1047186 1047963 990394 1047444 1048506 961215 1048006 1047155 1047980 1040257 1043991 1048135 1048366 1047425 1038159 1043321 1048267 1034919 1046338 1048177 1047643 1047611 1038706 1037381 1046697 1010793 1048041 1028796 1042629 1046332 1044993 1046898 1047737 1047806 1048207 1047872 1000711 1047614 1021716 985600 1048427 1047960 1023507 1035267 1048188 1047970 1027559 1044310 1046130 1040015 1045500 1047110 1047895 1023360 1047388 1044236 1048485 1047716 1047881 1048330 1045252 1038890 1016400 1048418 1043249 1044262 1048379 1047512 1046599 1046109 1045748 1017506 1019788 1037523 1047893 1047947 1048324 1038673 1041896 1048218 1040612 992508 1047701 1046771 1043883 1038429 1045763 1037532 980397 1017888 1045210 1048231 1048536 1042760 1017007 969202 1041318 1048461 1043462 1013949 1011953 1046823 1040915 1045339 1046687 1041343 1047463 1039818 1047888 1043827 1047753 1048107 1048382 1047611 1047558 1038949 1034685 1035564 1032117 1042072 1045818 1048041 1045214 1048192 437707 1048097 1043787 1046209 1046834 1045693 1047865 948253 1047140 1048224 1041204 1044838 1045465 1047067 1047749 1037140 1045628 1045396 1033261 1039790 928989 1045059 1047433 1047422 1035154 999058 1047521 1043612 1025880 1044025 1040470 1043761 1042764 1046466 1028013 1047821 1048364 1044722 1045040 1047139 1044701 1047437 1045045 1044198 1047306 1045995 1011602 1041137 1046938 1048085 1047912 1047824 1048193 1048282 1048550 993262 618611 1046906 1042787 1039372 1048065 1048378 1047808 1047465 1045811 1045141 1048550 1048302 1048458 1048304 1048031 1036429 1047234 1034018 1040852 1042765 1048277 1044372 1048500 1040974 1046322 1045615 1043725 1046635 1045704 1045455 1044656 1046013 1023131 1047320 1045668 1045471 1048314 1045249 1041545 1044531 1043656 1047260 1048543 1039856 1045890 1044467 1039726 1047961 1046544 1046807 1041676 1043111 1029011 1046816 1047976 1047489 1045969 1047454 1048539 1046738 1046011 1047357 1026254 1046083 1030786 1046099 1044464 1038703 1041311 1046382 939331 1045969 1045910 1000622 1044080 1043929 1045467 1045546 1043080 1047079 1047765 1043756 1047506 1017034 1044526 1030910 1046929 1047405 1048498 993444 1045572 1048252 959302 1048514 1048061 1048327 1003163 1047805 1048116 1043222 695495 1048459 1047022 939564 1047408 1047870 1046783 1037640 1047552 1047591 1044116 1038813 1045983 1038149 1046602 1047455 1043948 1048541 1041327 1035829 1047425 1046729 1044249 1047219 1047188 989437 1046953 1042722 1041417 1045889 1046172 1047082 1047879 1039492 722548 1047451 1038728 1046155 1046986 1045740 772423 1047079 1046697 500313 1047655 1042867 1048452 1046632 1046980 1047834 1048565 1046644 1047865 1047540 1037472 1045605 1041942 1045594 1047939 1044512 1047687 1046121 996316 1046593 1047924 1047735 1048327 1046080 1036403 1040790 886271 1035853 1047718 1032609 1046649 1048286 1046998 1039512 1047661 1045992 1048559 1031920 1048249 1034168 1043629 1041985 1040133 1042117 1047994 1027344 1048462 1043643 1048068 1048153 1048135 1047709 1048290 1044865 1047787 1046721 823143 1035998 1047296 1048034 1048561 1039968 830314 1046834 1047733 1047579 1047086 1045531 1048426 1037699 816028 1048541 1047024 1047068 1047869 1041603 1009861 1048344 1046919 1043359 1043395 1048360 1046452 1048449 1042930 1046680 1047300 1042432 1046918 1043929 1048303 1046307 1044810 1047646 1047135 1041535 1046401 1047980 1048534 1015096 1047800 1047141 1018864 1048337 1032884 1047762 1048299 1032184 1047917 1047566 1048486 1046554 1048082 1047687 1035339 1041054 1039782 1046871 1046034 1047119 1042137 1048203 1046446 1020805 1011907 983292 1047722 1022966 1048200 1041562 1030964 1044667 1048052 1048321 1047561 1035495 1043066 1048279 1043224 1045478 924339 1039847 1045925 1046871 1042952 1048472 88646 1046761 1032878 1034283 1046579 1041758 1028434 1048553 1037326 1047685 1047786 1047380 750726 1039821 1047115 1046247 1047776 1026922 1045250 1001707 1037488 1046449 1046200 1047776 1047355 1046127 1048446 1048013 1027036 1047962 1045809 1041288 1048342 1047380 1033789 1045051 1031052 1044773 1047252 1046810 1047526 1039478 1047907 1048244 1044681 1046865 1048524 1048358 1047024 1047992 1048187 1047974 982704 1043912 1045655 1048533 1048089 1043890 1000890 1047888 1038230 690181 1047138 1045377 1048227 1046106 954080 1042566 1047076 1048210 1046633 1045890 1048167 1046844 1046709 1046568 1047033 1029195 1047993 1044426 1039568 532843 344811 1045960 812136 1047860 1044314 1048276 1048509 1046633 1047476 1045773 1046800 1033168 1043753 1045682 1045478 1048408 1033297 1029740 1034105 1048369 1044457 1048088 1048509 819042 1047789 1048289 1048475 1047923 1047199 1048529 1045560 1046530 1027306 1047998 1001290 1047272 1048163 1046268 1041753 1048471 1048553 1039041 1041814 1047586 1047598 1048344 1048468 1047626 1046229 1042119 1037527 1048282 1048481 1033885 1020928 1039697 1047513 1046994 1046897 1048157 1047106 1047069 1046622 1047951 1044821 1045508 1010019 1041311 1041534 1047985 1047076 1041113 1047880 960395 1048035 1015241 1048520 1036658 810054 1034381 1048475 1047818 1045478 1047050 1044895 1029033 1047608 1045610 1046843 1035180 1021516 972418 1029975 1047564 1047666 1041156 1036817 1044756 1044180 1044618 1047882 1042077 1046028 1040998 1046087 1031464 1047558 935723 1048243 1029018 1047636 1045339 1037912 1041552 1046567 1047294 1047850 1047342 1048169 1036446 1048405 1044868 1015251 1041468 797226 1045303 1047761 999774 1041514 1040569 1048384 1044590 1048567 1043803 1037753 1047841 1048431 1047949 1032034 1047161 1048241 990437 1038734 1046877 1047966 1048309 1026418 1047413 1047399 1047718 1048068 1045214 1026779 1048269 1047357 1023720 1047910 1047499 1029564 1047784 1045798 1026497 1044190 1043727 1042454 1047050 1047595 1044146 946850 560260 1046156 1046340 1045185 833727 1047442 1046261 1045433 1043978 1048204