OI-codes/S2OJ/1036/data/data6.in

2000 4
473399085 784488038 488345733 737214275 527160382 259991330 692545312 40670622 444322786 725402261 364115186 148515730 727876296 350053560 37968718 337600267 395892095 854102259 115970465 140916004 286773743 645973311 136580970 442301303 110075832 499561866 622705739 920522120 536056430 599498423 569702215 503029179 561271792 546830520 143519058 500672225 957156629 131463926 901015166 100194896 348437824 6602599 448215396 576505474 28769901 937862688 921206814 513311675 580490304 75309585 653305590 816142597 930574390 40371629 68619798 680183703 585021918 76218438 541507363 78553955 701362427 53550784 25357173 769223083 273779619 149579590 428302140 901860814 635120372 474366614 13362412 682232705 869881602 31416038 875857151 323715250 106128899 89957061 665793895 253687326 967848787 593420731 501147827 153643433 802813315 36609682 911580910 584995250 628009362 864200707 189377888 96377340 404262120 588170310 511173029 350510403 273678078 590463650 400632763 73614396 79551478 79840890 294516011 773769120 724117255 241855814 477100705 75094684 981926708 977837808 620667143 224598922 350809206 207714227 37581745 276195997 313960412 158302383 648891026 989514516 657108044 653982634 457802870 651907467 147230875 608154781 382728194 592212371 519594130 150034208 272110856 19967260 582289888 463168237 987822531 930182138 37726853 6016015 179432696 658281284 45274491 157632708 485586605 609190213 250859573 686444350 788038766 35889113 538395962 472328523 118905327 720512688 143945430 662728997 636059237 866980071 657508402 940348599 899723698 16812337 683063711 951697562 515700256 923181878 348473971 614125228 796299514 287843694 655792014 803281472 314989793 486261096 414963637 59940181 244791624 781640563 668452220 982482661 377300222 558600141 741548750 7732640 113461660 777619662 15667239 764754448 538380241 208105676 174214147 996957768 201792882 449267739 83365099 750859627 876819795 470487429 240409527 939158860 231133148 649879591 424457295 60565378 601016524 314621958 746509192 980524170 27701759 165469270 843676603 985629127 572863109 941083462 572685679 106501099 110092942 141634705 481079568 228368421 634774558 104721657 706255815 899365736 650017366 385536651 549308936 996067477 271057574 644809509 903913579 569181953 141898911 626622516 384821524 622092751 207967392 352063675 609716818 511575220 667683599 949171396 8101234 304443586 477302748 968842669 910704907 894398358 560652484 875539199 422346927 744327332 610203727 105120195 523559531 17514336 744142669 654056333 903483385 781362336 494279747 892961233 383717795 44567202 362149789 682848125 475827307 447321 75673106 320552096 275585727 794570757 90374431 90596897 96142156 953513348 175865922 634031360 144189684 827443750 535986856 784673274 99618469 43342401 458777274 203351388 873274317 11180799 523085013 839246320 333285322 682034056 471650084 660820711 775751140 469167621 533232941 596780456 340492502 406540437 579643552 876334250 899867202 133716771 109875435 633478203 791719642 416324860 463178672 808698507 371805286 901512679 19444946 979650234 17339867 166347255 922090038 118250492 452119078 968200860 68260701 294312787 653150646 359482436 949802841 90400536 883848701 493709986 699901272 472743885 509959873 288350334 580955906 310747811 58229973 566096826 829776950 95373610 714441186 824921303 90893067 571882630 287537016 796422162 201704983 326454315 689932698 434645133 134361815 213711708 52997150 103343701 376290862 128660866 473099489 44145360 69207305 24017039 74932484 403314955 56058753 227119216 114222593 681718711 821119032 817655202 583122861 578043566 755173312 569501014 268927619 560899245 373378963 433014607 1903813 371087542 368786084 342887124 998246745 36287782 3396326 247476260 450656159 3241344 790177433 473243383 669593240 832252978 907786913 96313434 684699047 164997234 707123561 451187229 339000246 303019031 157126980 221245628 181076839 167083852 62668866 8643832 40975006 472158802 413888127 311196434 948764371 609683000 90679741 926974773 818634473 654839960 41516845 988912287 65842054 91796882 936937228 753891192 288725222 84742512 485741223 267392714 179049605 662121788 20632162 19879567 48895862 892472989 767735475 41355727 866959217 307015224 749149674 54927135 535368313 126239308 576163476 368755387 826962645 247011131 430189066 757676460 483215088 760314709 874593091 553495300 843831943 94439791 52130782 781703676 936213833 126188240 72368669 262949190 13174451 818139472 925292741 466010060 151196389 477534100 562208439 902166051 470271337 903518577 372834280 661440592 456672872 987383904 355134159 675733878 958740788 779599053 716532002 458043816 761024664 921904894 361040353 363910096 996535394 545404005 144906639 992404553 985319669 814253444 37329555 332605961 208453386 930230245 698777555 913785089 123409704 263649282 687697391 166040961 862152652 920434433 62301021 268723858 76750343 98321532 75063781 817045056 858795852 337271655 108339730 385666610 586046202 111490450 652726475 27396449 683596463 961220769 865471849 871603590 848559521 93948298 381542519 991925469 375805822 419044527 282486776 461879293 799377193 267765697 5323945 432714088 39026852 380262738 164504094 8854169 428625318 38546166 891307724 510479443 223807314 78639079 423031357 717145529 32173870 727837693 494231517 875338201 546162257 796924699 850888332 786590551 318059725 543000692 554614341 117179785 784099352 43646003 266448794 494455341 342180875 72759459 950032270 651446445 988768709 7231677 76689685 19304751 770876516 145740639 124540671 944458828 467887219 488352997 66321745 125555422 381036200 72156624 201097591 855435206 689469155 86328873 377906786 15703054 928223644 126551478 380353725 693722603 500047636 990086119 319600008 660733309 306785726 39460435 786567769 728141229 507815197 542981379 22999328 588606392 43447193 72532771 435054348 569587379 720464174 121549210 59097682 117296460 804593852 104345405 386565883 667741984 782964444 651105139 340384639 95675712 142397137 764877379 249976489 669815669 275649887 518402808 247816755 878388330 63051410 434083408 637889397 768729555 776010533 740839900 186013994 748490773 718196263 866496101 906337778 510505253 657595984 57834204 795331693 201545323 583510920 303195169 969994699 945520294 773572036 559210114 255946726 79857519 781021036 200501588 221325951 176560431 421742241 525809387 176138482 919979986 14344880 369208274 996183513 866769557 59861829 75413207 247396897 264285865 649329637 564293583 794464329 656144104 278407161 615266692 653532139 683289415 95632327 974751933 650478615 547814006 847604153 423968920 87876272 260732946 271983542 27684509 437075011 171132068 736063543 514160481 813987217 212324729 216877567 781519610 990100218 911066970 537140258 488042796 295224479 943572561 250278210 652894644 351824116 85437421 73153482 129925890 466542809 722195666 364985618 99985894 923687082 42481589 816474097 852622527 15918505 692814816 482278478 51095968 569453954 625473846 199456235 831947256 271505975 945655597 900125910 541359902 540639153 518934014 792882831 845710982 817698628 105962221 81578493 995165065 136604619 46791468 238166452 747019334 964546176 921012476 187535134 189981920 865429998 168213833 874390357 441112256 453115726 331973198 104002458 710601526 923286515 107108030 11837533 384921607 949682663 11031115 154829672 619600787 275201384 422863828 48969273 333313088 1213571 69134974 955833569 517114623 72127930 866321180 113924178 108708747 145284388 898781055 413218387 146799558 387418059 957878487 526313097 52057864 703654497 921665628 634663985 246321246 720193753 871550757 960595290 90464531 604907597 287376459 38402888 985223094 191117419 622408868 225978517 62825901 938920939 734383617 196931610 350247821 155429698 759798112 782081900 496068591 893291283 488417204 145448794 514469050 705139106 103685327 30053172 237983337 964372823 947930830 485261295 791177406 892898996 337700536 81113178 203023957 665108794 831118123 368653173 256535594 239543760 627619842 759989008 50008747 269378361 546585451 674116738 549272572 739402798 447939375 586892890 309390137 655101750 939432659 744927069 159586673 113621655 112150558 9743396 341477978 937050040 147933760 684124741 250054527 833916688 159494894 364070580 546306335 70959998 209735810 9093943 163539642 624673512 987649648 172021204 647386766 477220460 585828253 950410323 355910853 844728054 122991839 37548237 298984197 708643577 228292377 504186697 688323995 166977576 778476850 35535357 242291233 559758319 879693573 377950394 103127779 835235680 498451899 147359546 623244631 594766798 502175779 457584943 491197094 622419790 616565993 16047576 69132535 707819874 62196516 659791970 311065260 98628022 576768848 12845778 150626146 483394587 482187108 662924025 411906117 211809069 494619604 955465469 772908864 943675123 181059166 870053741 777072564 410525741 634149754 193575417 131791961 410321979 711510536 168632056 313529730 716786019 432340241 405252686 56743896 211920804 225066102 760252525 829466603 528843944 638330453 739106806 915652772 301303180 29085212 1865146 282737764 385267315 524567500 985601565 464133644 826527382 166975409 742056081 91993816 537796828 785596551 791770901 484856295 72288278 620827791 422621142 265112965 518013808 359366118 142329862 634186454 810392317 922382545 946469769 699012832 218613265 36108485 723392450 151981483 787707076 549121155 342020926 324958841 532326366 392359960 619051430 632092873 130798449 892234971 62334243 265559521 580829559 334717429 336157710 566135291 683279627 78609058 65952057 940617303 120864532 436616418 53494105 72753220 845173397 372442121 512875220 41947129 69234396 833840545 672738071 207357842 844775060 913021681 30229683 264141489 370285852 779684136 206059758 502713742 702173074 793193031 409770019 24653404 32900804 498989058 585456271 140959790 22685045 601419305 996216353 271227790 565167596 244593869 398434503 427659153 832596540 446603928 616871631 857938148 954226056 62425974 14303860 472763712 843192262 287760881 263953923 719852806 436221822 70991496 300649187 774843096 447079064 12547795 437393159 430299632 468475575 786917701 166997412 111860502 429739498 644238025 95938001 817247557 967262865 335764265 750461186 622672849 367739890 939373742 902192697 563605590 116267860 489761406 908110269 443011854 374426029 851183693 455755584 602910017 280809173 183693083 395645242 793189760 354794322 613565782 776603758 121237887 269142962 678180330 126586612 532377354 42293854 601674177 630377694 221072407 210213717 244320882 105309288 199656866 56468826 469743764 626533754 833460815 733066902 541739075 825453892 452181802 667898059 465654744 828872740 137723091 872102618 645788529 178433543 838364567 546048180 27116207 61515041 382133389 539764393 642206801 109873163 595292699 105564367 984780903 349147870 995906064 498651508 199293 202033804 203476499 828531247 633679759 677282618 71126557 423135767 117459330 39961226 613427518 600284357 101014493 238502721 103725123 137378053 160994824 803590326 417953099 118725556 408111629 69380085 134951921 980162171 31530438 296589235 465727958 59380438 13082767 631711553 809899081 222499681 576087718 95490681 741591258 76669665 682828611 940834087 676407348 747354265 944259130 259046580 846517591 341990562 169136162 196104684 691509490 811479444 13856858 402452039 585415070 93989514 281281253 675490702 19165403 137864818 545098169 92666859 319233716 739893184 99922289 61699269 892496229 803825086 68597125 860645083 205042367 583292381 925177490 676470150 448362410 899886125 806260701 994767715 900794110 34379067 721835182 541760549 831862341 991823217 804740105 414935929 948756894 691038483 692220805 236153836 280720574 842093337 145481229 59604095 477118672 229582406 710867630 893707727 838119149 716275148 436065932 745915560 386264312 101226903 513510297 978268033 409007777 891532570 994498871 677300296 722745772 813661150 820062532 240928878 284977951 528868225 46421220 457859257 599603776 192886439 289556950 178693126 906208754 489482532 516042245 583045129 64580420 716855783 604863789 551095403 163468710 787024457 168266926 619240761 873716765 64491169 571319295 556983906 140269447 364529901 30684863 910374317 633139522 394475369 665508494 106425082 625453801 69581342 222511026 766763133 731589262 476847359 757570687 59993346 138335779 77626530 146515981 123328136 454262397 483741294 14324363 817357633 669826550 665548276 775041156 273884768 123840255 264490420 792318228 93846596 465215583 37828401 712733251 36945169 107659978 52998050 118470001 200944616 77362959 11645478 97515447 205073646 754493465 28214367 190937338 536249726 553257001 133707944 399993555 67863775 65628446 3675942 652015078 601343883 728598799 608259599 996920673 578337217 602619797 698048927 405152528 875377106 845533523 982628862 894038204 157016569 867556667 403917717 449261452 184720912 490498069 404303428 489455288 412657406 101305057 265518084 884397900 341184413 298070379 382489980 90538389 53260425 233239332 688775727 109764937 716800542 676428302 99528143 465695544 160093271 38079653 640558321 321157214 855869365 543928527 761846588 58101102 193140507 264710532 196773318 44339246 32882013 744695212 557733368 58596821 289260221 486536117 742274290 464465185 956286028 531658448 51564016 638980680 930053760 673056385 262293946 383401709 381582163 658222177 844841720 885892654 693711127 514191926 549504754 346718378 965623313 490079790 964222863 575036757 759341977 558271896 519702329 821051154 824313303 609655302 625159455 210453992 194676935 317652164 928552484 417935839 976120383 820676226 610844279 487964493 772164536 525677731 317901159 25465577 650706886 443902478 103736646 538066536 230633035 41436410 637041242 546173999 994272493 960511122 468831533 327052866 12361120 594913728 824144642 129474944 684449397 618602047 669247380 314351252 491720744 833470752 107099483 429714595 225693304 771239726 14781590 473563725 404108871 159998014 437095254 865861238 973613572 490893042 954668767 60618810 351564501 17055410 827929397 108321397 639070370 82968521 173519053 51931145 928393333 38052276 180433082 84878188 411542686 546075193 688145120 101087676 321005755 664803021 134442253 4106683 887501633 611512347 978765134 173849696 107059330 340820280 620537989 994369869 449625907 660643734 948782348 118843861 41958695 618129227 165012581 965060590 976833986 929299965 95947124 970577818 8583092 167601473 172390425 410433172 432847640 343173091 362043173 38436660 405345451 822866673 125486431 221504463 236349390 272429358 285084502 379208657 775917550 118536844 969869848 201654606 272746654 115889658 575771333 220458927 636873592 668942674 635608451 880554357 960245200 294447773 774376701 991291465 250497407 834949907 137916029 258317799 482797206 972401454 593662286 265995418 317015850 178462743 536150389 31183689 911229733 332235774 222149996 141382864 543355175 69959181 923378736 155077661 492584616 113160505 11074871 451763255 75829571 9797126 97034441 917761814 595255144 119872413 355984405 140454293 530774398 78237548 678477272 29344934 426550575 528078917 665423546 826187693 900273327 871513774 339022009 668789772 420289606 733693059 328141539 336840477 511003447 647829376 326232142 457859803 815801820 645586292 74403578 103926401 786816596 969714393 529384646 135974379 191766023 431572992 395000625 696530076 440606113 536304913 480784910 363997287 668975953 47444957 690959262 508237105 44054547 690396861 438876664 386742981 703765845 645607817 643195675 550009305 236772447 940297416 246512439 638607210 95594411 923454877 434779448 244310373 135705947 182218115 228178183 732411786 61601276 38506456 578406823 417982770 617406053 102550467 283813975 293276416 414732425 468927391 145159694 743511222 778744839 599164255 395791580 105208879 305061381 123165078 654208816 171297872 375247724 422004607 640427455 269175999 85949542 444941610 388558994 806220209 668723740 103468360 678456097 466435287 62557059 69965808 680253656 967743411 615344877 967587434 141323085 100176013 31071243 375854880 243562333 241278127 505333531 635810210 183571998 508053294 249710364 492020088 215072997 516882678 675817031 415831034 960401100 974196848 911099608 292708546 460475923 835257720 868878179 346754853 785680060 840801595 910009905 157939401 197724915 5444496 104309676 224542089 750122044 572185618 84889038 593898636 943362574 223015417 861149504 447416595 35958949 919151036 321589181 526004146 508990770 973483967 460105454 51236178 571458355 746681679 377524463 386956403 788760683 77224828 630539986 446725335 509875433 16650901 471797575 785196879 309913116 854875215 15118653 134604134 991399847 131611456 85584582 753509831 321641836 410976731 771487743 681214593 938342394 748196037 59535605 35017380 712543538 143406072 187673679 725529157 349372611 478160757 357014403 64740081 105310916 434040084 57226576 320346132 108916073 689350245 28270728 345218087 372552593 576599546 107849289 146802155 992592329 639282185 347975932 626496921 214408584 880490200 88979923 836947549 559568193 831729538 907286843 636076601 158816819 705082290 503283884 901636502 953054460 698764825 699831979 101115012 573420485 364462237 893456015 109584281 35020219 174301455 316859677 848630426 138164986 709097295 411479862 637675872 120477105 929108261 961923868 590533438 219054610 863859312 894003064 359397167 664170405 884978307 358666627 123402860 710148665 547481207 696702301 40224394 741524800 752688637 404736160 319931071 575436787 247216668 382660709 812497045 582302620 677154961 427584074 718227434 35882029 419335174 872423611 598266939 554008519 879569088 433214646 68991992 700218742 366011234 157644830 334815990 845188790 631152272 147481549 112222561 72414170 589210988 614957577 546182206 339228964 645093741 593054931 795598168 30718285 886140715 567905060 363016152 4404115 798495385 479604170 994136577 823654557 275529515 642794251 245727078 323946765 702234210 27727205 593140192 81096148 123822169 167540440 501113863 937315554 315460264 951016252 802341321 900762534 503681235 782958749 555389274 109093187 725643018 115550791 529906027 308890258 843569985 986678979 244877919 84516981 783187578 899329561 835002719 878043666 919755925 543518947 320486469 527097807 562798374 434290430 615319435 539983740 33804536 10132322 81201250 97292905 759777546 436429138 53362792 367764345 350388927 379514593 268311539 589355851 109207793 149837344 465406324 741623672 266946694 272726053 769648651 983850054 736754256 238071990 513901569 111925596 523774356 333110817 896612168 467956577 861074325 183883142 294999561 665364451 625956606 723268967 224086349 325929383 811840231 280647957 976124487 96673576 88133278 78244072 581104718 664347448 920077783 865040481 64052555 434963316 187096202 402786384 555279122 405252170 402576553 176133152 37420098 499857093 142134987 860911045 734603476 390113107 156393636 780834902 219631097 962941733 517921317 745332106 317571169 714753166 625918222 432654148 31615272 722394273 200984751 106416973 282144416 150285714 204204904 185932200 166757593 21684794 177091346 109401127 44696813 186016797 441095725 382300631 55633393 875049706 992394086 809400800 83320433 207179587 996326922 336582395 261365145 952912478 459956998 703619833 339067780 438062969 743356645 328252847 60110386 957943412 470023925 247253809 6889496 620620912 447594505 85630094 370946368 350579735 645962424 953603161 330847944 519211303 951290338 113937429 183934657 160812166 28624614 643507726 499683168 159439737 791551950 745409063 818008890 878084714 462166014 175846099 507887621 967232969 626280771 83564250 803023190 623516582 515974892 451043258 66763296 104252138 612005992 685522061 112491650 654530768 80356420 369094133 77815726 31365859 32498698