#2072. Flea
Flea
Flea
题目描述
标题: Flea - Problem - QOJ.ac
#4536. Flea
The problem was used in the following contests:
这是一道交互题。
跳蚤国国土面积约五万万平方千米,那里生活着四万万快乐的跳蚤。这是一个晴朗的早晨,为了丰富跳蚤们的生活,跳蚤国王组织了一场跳高比赛,共有 m 只跳蚤参赛。
比赛进入准备环节。m 只跳蚤站成了一行,编号为 1,…,m。跳蚤共有 n 种跳高姿势,编号为 1,…,n,跳高时跳蚤需要选择一种跳高姿势。
然而跳蚤国王的助手伏特早就看穿了一切,他经过长期的观察研究发现第 i 种跳高姿势可以用 3 个参数 ai,bi,ci 表示。如果第 k 只跳蚤使用第 i 种跳高姿势跳高,那么它将跳出 aik2+bik+ci 米的好成绩。这里保证 ai>0 且 bi2−4aici≤0。
比赛开始了,但是跳蚤们的心态都不太好,纷纷采取保守策略选取那个使自己跳得最矮的跳高姿势进行跳跃。
然而突然间风停了,立刻起了雾霾,空气污染指数上了五位数。
这可难倒了跳蚤国王,他需要知道跳得最高的跳蚤的高度,然而他现在连自己的手都找不到在哪里了。于是跳蚤国王只好向伏特求助,然而伏特本来想手算出各个跳蚤的成绩,结果发现自己忘记了每个跳高姿势对应的三个参数!
于是跳蚤国王很无奈,只好把伏特踹下裁判席让他去测量选手的成绩。跳蚤国王每次会问这样的问题:“伏特,第 k 只跳蚤怎么样?” 伏特会去仔细观察一下第 k 只跳蚤使用的跳高姿势得到该跳高姿势的三个参数 ai,bi,ci,跑回来告诉跳蚤国王。
然而跳蚤国王推理能力太弱只能一个一个地按顺序问每只跳蚤的情况,让伏特跑断了腿,于是伏特找到了你。他想让你教教跳蚤国王,怎样询问不超过 n 个问题就能知道跳得最高的跳蚤的高度?
输入格式
你需要编写一个函数 find_max,以确定跳得最高的跳蚤的高度。
-
find_max(n, m)n:跳高姿势的种类数 n。保证 n≥1。m:跳蚤的总数 m。保证 m≥1。- 这个函数返回值应为跳得最高的跳蚤的高度。
你可以调用函数 get 以帮助你确定跳得最高的跳蚤的高度。我们会根据你调用这个函数的总次数评分。
get(p, a, b, c)将查询第 p 只跳蚤的跳高姿势的三个参数,分别赋值给 a,b,c。如果 p 在 [1,m] 范围之外,该函数将不进行任何操作。
实现细节
本题只支持 C++。
你只能提交一个源文件实现如上所述的 find_max 函数,并且遵循下面的命名和接口。
你需要包含头文件 flea.h。
long long find_max(int n, int m);
函数 get 的接口信息如下。
void get(int p, long long *a, long long *b, long long *c);
函数将会把跳高姿势的三个参数分别赋值给 a,b,c 所指向的变量。
如果有不清楚的地方,见样例及测评库下载,内附了样例程序。
评测方式
评测系统将读入如下格式的输入数据:
- 第 1 行: n,m
- 第 1+i 行(1≤i≤n):ai,bi,ci。
在 find_max 返回后,评测系统将输出你的答案以及 get 函数的总调用次数。
样例一
input
3 1000000
326 -421505646 271727651175230
765 -593058832 140861873339701
291 -633539923 472231112710095
output
146638735615726 3
explanation
第 831493 只跳蚤跳得最高。
输出的第二个整数 3 为总调用次数,你可以认为这是一个调用了 3 次 get 函数的程序的输出。
样例二
见下发文件。
限制与约定
共 10 个测试点,每个测试点 10 分。设你的程序 get 函数的调用次数为 t。当 t≤n 时得 10 分,否则当 t≤5n 时得 7 分,否则当 t≤50n 时得 4 分,否则不得分。
测试点编号 特殊限制 1n=10,m=10 2n=13n=24n=35无678910
对于所有测试点,1≤n≤1000,1≤m≤106。对于每个跳高姿势,1≤ai≤1000,|bi|≤109, |ci|≤1015,且 bi2−4aici≤0。
**时间限制:**1s
**空间限制:**256MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1000000
326 -421505646 271727651175230
765 -593058832 140861873339701
291 -633539923 472231112710095
146638735615726 3
样例 2
1000 1000000
768 -128595456 5383753281750
969 -131225856 4443555962408
940 -571933600 86997516084308
615 -684683190 190566343701981
861 -906483186 238593099180733
626 -473440044 89515926914532
832 -10335104 32914799662
569 -649302970 185235789852355
950 -598811600 94362994331600
807 -464875578 66949287282050
954 -834708024 182583959817288
647 -348542782 46941376167612
817 -221354712 14994033480249
693 -315158382 35832360102407
528 -228599712 24744016655377
777 -575861118 106698429702413
771 -916288782 272239980938532
528 -879678624 366399898064609
560 -681890720 207578758001720
688 -75025024 2046114939913
621 -504018504 102269187183636
569 -277128036 33744188696031
661 -857762514 278274739127045
563 -903470872 362460874625627
863 -900880522 235107037974387
691 -175703334 11170231049894
692 -570113888 117425059263961
587 -968886938 399805841123200
912 -688186080 129825291112401
932 -279247704 20918138744186
636 -25071120 247919363341
636 -223846560 19696981516838
994 -667001832 111894977064566
750 -371673000 46047823115145
536 -982243584 450001803034183
611 -944836958 365269425135068
576 -983665152 419964723326451
734 -249734692 21242983351858
765 -254215620 21120131623516
778 -973509844 304538643409970
681 -891283266 291625924818002
860 -886838880 228629652410324
522 -954813168 436623522793177
971 -224770964 13008568149085
516 -661709112 212141647074066
510 -267873420 35175687767963
647 -118372532 5415170673668
672 -394431744 57878887768006
577 -974077552 411104571527150
535 -491310830 112798497390816
557 -427914136 82186903209785
547 -926974644 392725511660808
901 -256902130 18313528699351
586 -746335460 237635883500965
783 -227973582 16594907469821
890 -204730260 11774958351261
972 -430319952 47628310230588
660 -716239920 194319076198160
624 -328745664 43299472163597
549 -42989994 842692403865
511 -996971220 486278489628198
603 -818161254 277524672966457
835 -754277210 170340392525993
518 -572466664 158165937466240
923 -240415656 15656340691930
639 -989249958 382870728080389
932 -63159776 1071236312801
739 -205959300 14351392424907
595 -469349090 92559253547182
513 -986717538 474470267054496
882 -328698468 30625110881154
781 -294601010 27782692291094
863 -674398254 131754195308092
646 -533430624 110120080635605
549 -974111562 432101757684306
809 -133520596 5509917157944
537 -747370824 260039497708721
968 -283502032 20758409281599
934 -524870640 73740306456502
564 -849532896 319906015061233
918 -243925452 16204627994713
519 -116629680 6553033556774
508 -997667296 489833335859032
565 -604620060 161755496425259
702 -533548080 101380225888094
712 -694318192 169269725958598
508 -510755392 128382509796241
541 -915797226 387563016210440
608 -28503040 334853308392
707 -71455076 1806236140222
602 -507015236 106755102207510
642 -689947128 185369451196340
702 -620569404 137146789718254
706 -602957888 128739554861505
585 -961669800 395218073566450
501 -938273802 439301312748220
582 -962316048 397789528993456
518 -241994060 28264239809644
630 -922992840 338062993712718
640 -665122560 172808770457260
520 -963571440 446380855898020
752 -735034880 179613756444630
912 -972108096 259045358787535
542 -100830428 4690216973706
786 -306955008 29969268973916
911 -893882310 219272297070180
853 -50318470 743119228670
593 -858541842 310748790609837
892 -252446704 17862054438126
562 -205630180 18810494673626
807 -336230094 35022895152885
517 -934887998 422639114236148
505 -439912570 95804577593595
689 -411206224 61354792296674
678 -354823164 46423886256147
773 -616196950 122801201366795
694 -686962840 170000269336612
640 -156549120 9574123573274
746 -878444840 258601862603024
934 -164070176 7206224368484
525 -635273100 192178188245630
753 -160315206 8533912043135
849 -194157810 11101302444130
684 -356841432 46541955692742
501 -993549132 492585851963806
567 -476287938 100023141661531
707 -606993436 130283893954743
890 -160858600 7269257279201
537 -717908856 239941949231660
582 -980969148 413360059070036
810 -663432120 135847225617215
845 -790127390 184705242594234
776 -661266848 140875273397815
566 -969406312 415083943205999
925 -335493800 30421340339583
741 -528168498 94117685163667
503 -984861928 482084850932294
957 -443112054 51293346553590
770 -473593120 72822453496966
505 -881221970 384432696035867
512 -801014784 313294059901352
735 -150575040 7712774543885
601 -863656232 310276075925139
874 -565824104 91578713132701
706 -534989856 101351270221790
604 -144084200 8593489686504
894 -624013788 108891804566156
516 -336368016 54818410062577
947 -640628454 108344506904198
670 -114872840 4924787157351
810 -381780540 44987197222928
668 -539154824 108791094408968
609 -385861182 61121215868493
595 -894480160 336175244539777
698 -88207656 2787842639698
563 -803605932 286760421711104
561 -970617516 419830648221667
746 -469119116 73751712785397
502 -997870580 495890365216809
503 -896631704 399577526463673
572 -973989016 414622531265414
641 -235703392 21668436494428
767 -812062784 214944175821513
648 -128292336 6350666201567
502 -757900524 286063009125703
702 -610221924 132611437561923
500 -999109000 499110195621925
789 -907540938 260973707101628
525 -768150600 280979614021246
802 -555538984 96205216101587
526 -928484680 409736442131728
643 -904919620 318383191935346
532 -891258536 373282001763586
565 -903290360 361033598880160
855 -471373470 64969845284345
773 -12667924 52910091716
569 -746715770 244985018264917
617 -967590506 379349036728373
640 -812335360 257769748930784
676 -933051704 321962742061083
808 -506594992 79406195352541
898 -556133196 86104263385351
527 -959701782 436921289412818
527 -972379294 448540342257945
742 -265900152 23822635207394
504 -677398176 227613932345029
837 -876904812 229678698003892
513 -577218366 162369723285894
561 -327695808 47855105683416
592 -599197536 151621735179402
699 -768223368 211076191812338
1000 -828400000 171562369567701
741 -577919238 112683400929803
672 -602663040 135121172576315
616 -860717088 300663815497966
883 -334298502 31641578728135
569 -560571972 138067954349330
940 -755517480 151811428620770
769 -918930392 274523850800579
854 -730685816 156295530373379
517 -340995622 56228153836594
528 -715367136 242306819950181
768 -805751808 211340749352109
541 -940788180 409003674220955
532 -865908736 352349390169047
503 -362749516 65402306581214
698 -876061196 274887378518504
632 -968226528 370832577494800
693 -935595738 315779982928683
812 -697969216 149989077227494
615 -294667410 35297375209949
727 -740535286 188581411516606
572 -249400008 27186338132773
589 -367564272 57345282642052
795 -864144330 234826379280023
635 -1270 678326798
517 -986378096 470475541828933
759 -160038186 8437094772943
917 -137731566 5172482322153
820 -448200520 61245680812746
630 -586886580 136681583182749
709 -190854292 12844967458599
865 -974526300 274481347234999
654 -551769336 116380914826914
682 -370470584 50311752019727
521 -970154100 451631917562332
696 -958074624 329708739809517
520 -964450240 447195086955111
598 -415447344 72156834104872
600 -822591600 281941522545997
594 -837484164 295194515497884
535 -983938830 452400581964566
502 -737362700 270769954429220
511 -840955766 345992334075507
612 -564833160 130326055897085
727 -448287102 69107047940662
955 -293950910 22620442431840
630 -678375180 182617179439526
536 -485848624 110098099079358
807 -498717930 77051652637505
914 -364680516 36377455246059
863 -592047342 101542074850712
658 -695723140 183902881428239
691 -259138820 24296535979206
985 -317270470 25549137391016
503 -955619520 453881729685122
559 -862774016 332907362865353
753 -4421616 7346867833
507 -703876212 244301575970103
802 -117011800 4268885532269
871 -256969388 18954083632174
898 -304501024 25814214717391
906 -710775120 139404968389049
528 -937751232 416372545445230
657 -715168152 194622718213328
590 -723521720 221816070412073
805 -890907990 246497162809592
712 -744384608 194561369187488
643 -827507564 266240568903705
949 -387005996 39456596462329
505 -984095520 479428669335618
686 -302029336 33244927237244
757 -753755498 187631922370826
863 -502307424 73092576994668
834 -924403932 256152743738855
668 -991449608 367879853140751
989 -278569652 19616979435894
763 -252551474 20899501973240
731 -633449512 137229944709342
552 -287116176 37335761536389
903 -351173088 34143126305465
831 -805745910 195315767097099
907 -79812372 1756554718554
830 -327031620 32214420331268
540 -181945440 15326742258639
693 -681069312 167337040193724
811 -398257770 48893957971015
626 -621792028 154403719001595
576 -381048192 63021031962234
751 -346886900 40057907385130
510 -997301940 487555493609202
515 -508844720 125691541572599
635 -927705790 338834624832673
504 -975230928 471764312002681
518 -639980712 197672618674328
586 -888523672 336807439925301
643 -653433318 166010032222972
545 -685807290 215749176514231
678 -369688992 50395525314167
899 -123067706 4212455374921
782 -732673004 171615267805743
528 -635658144 191317611757854
530 -703718100 233594779822038
547 -430502128 84704625134385
732 -400806600 54866540513990
541 -873985500 352981565317985
884 -683397416 132079977609982
784 -469137760 70182638849709
882 -599613588 101910644964580
541 -138473278 8861597600900
575 -811620550 286404148189436
519 -909849558 398761219901571
503 -974208388 471711791712479
500 -958699000 459552897505011
931 -939226316 236882334904271
667 -919754314 317072987075594
683 -324624436 38573741463103
707 -918572578 298365755730514
505 -13396640 89514686522
522 -585277884 164057379693926
959 -845030522 186152152616592
511 -773905412 293019111027523
501 -988788630 487876588002353
664 -210875776 16743562242885
629 -858046576 292625822682922
614 -928083104 350708585389532
755 -365873000 44326391363628
710 -563136500 111663754550624
737 -664461512 149766377007332
558 -898577532 361757996352356
503 -914915754 416040096338426
985 -114618540 3335154948498
902 -608759800 102713843994757
844 -739652904 162052767438721
1000 -98486000 2425734237758
510 -988807380 479285125155655
507 -730597140 263202417077868
539 -287174888 38252011683368
769 -847897862 233723769858509
931 -503090056 67965100671346
516 -963737328 449995936760704
659 -462843378 81269265605373
509 -893217632 391865995432859
698 -534832728 102453032984530
533 -189753330 16889204655143
703 -569100996 115177053497917
536 -997120800 463736632144916
876 -92633496 2449878554594
579 -949988460 389671849284620
940 -864743600 198878801544608
546 -754935636 260956742597951
558 -869455512 338689458453595
848 -275772992 22421258368949
753 -918087720 279843157083456
629 -207032834 17036830984291
501 -652565526 212496754082809
914 -420546024 48375858670343
504 -914663232 414985636632934
690 -704767380 179963371897387
868 -871367840 218687876927080
523 -955516816 436431077181161
766 -325736904 34630407535136
953 -88255424 2043956439627
511 -971648104 461889500613124
679 -716046240 188779101682826
606 -999110988 411808802113484
538 -980735264 446953280506240
993 -200786586 10150615256044
549 -275001786 34438726208439
779 -586668016 110456492753038
634 -836150900 275690262925270
804 -319525680 31747317385949
559 -535280512 128142906174409
562 -872337524 338511936812791
596 -330461736 45808100132799
633 -243994914 23513378141373
501 -833745162 346872489033477
810 -624733560 120461414893578
522 -641973348 197381028870481
584 -14601168 92260953972
998 -762505932 145645787941225
565 -830887870 305476278672176
556 -879326232 347669321763787
565 -80062760 2837114418167
641 -51653062 1041478667386
503 -929091300 429032113746792
748 -361049128 43569409621657
700 -282704800 28544519818933
695 -581321630 121559985589378
776 -89120496 2559460341475
841 -957567646 272573876663805
728 -922195456 292049119727251
736 -865313728 254338038232323
957 -756533382 149515558830766
620 -919032200 340573449721605
751 -993129910 328332334962754
569 -616723168 167112910114824
953 -59059316 915751242980
920 -803344000 175370808865797
963 -332204184 28650947356897
946 -874717008 202202124276918
831 -144743580 6303575545699
605 -511532340 108127030479198
503 -763535892 289755709310331
928 -510212544 70129278148370
502 -772525792 297209958475502
520 -371464080 66339924784235
554 -619774204 173340216314518
721 -962751300 321391129573173
526 -941045560 420897603221515
612 -62886672 1616621524674
501 -944863956 445493883365340
987 -617546160 96597604401969
527 -367060770 63916165850726
513 -747614394 272382640472087
636 -793560096 247539010975186
555 -821562060 304038597183146
991 -452189336 51584274655507
720 -1157760 1357809366
869 -965989090 268451894009192
917 -760658836 157744325702270
517 -985372014 469516605343768
506 -895319436 396046571517593
724 -160982848 8949797117808
511 -632251102 195569004293375
817 -600821800 110462132932077
862 -978204496 277519552710467
501 -867604746 375618882409190
652 -7082024 19893340907
609 -74642694 2287802841112
587 -520758224 115499055846233
541 -492898608 112269304635241
814 -518293336 82503414015539
769 -301431082 29539460232566
593 -184485858 14349436719770
588 -998286408 423714947269123
646 -904723000 316766847806198
504 -899692416 401512060442055
522 -944794944 427509064708618
847 -454984684 61102469279068
946 -408172512 44029687636371
557 -911129460 372602571804481
555 -998875680 449438883382811
539 -938968184 408934590248327
564 -271466736 32666571758689
670 -282666300 29814423074088
875 -242644500 16822583099613
958 -481174660 60420788842954
975 -84323850 1823847802575
600 -872059200 316870692813025
617 -30071346 367467178224
509 -973236504 465221593673217
914 -464441788 59001332716732
558 -976602672 427309399274116
697 -225761088 18282212354653
702 -29003832 300636642003
711 -945574542 314385820135108
828 -227786112 15666885260125
666 -772979580 224286838708437
966 -616476084 98355446882761
572 -629721664 173317880975914
563 -884959432 347759778045458
501 -999645300 498649063513175
922 -811140564 178403295550996
523 -642207390 197147099773230
507 -747816888 275755655144703
535 -542506050 137530156481800
727 -698719700 167885718087636
593 -888490714 332806882209536
502 -992256212 490325624584866
502 -996456948 494486037103401
790 -129108120 5275902683555
627 -610099842 148414803803694
570 -88006860 3397788573672
678 -989489472 361022281316998
500 -475234000 112924390510307
721 -909085828 286560173637383
707 -566230644 113373039835010
781 -235160662 17702566520088
760 -644343200 136572830298034
688 -442232640 71065233161330
527 -847599396 340809486416798
617 -786895886 250894634553588
683 -858520072 269787610810241
945 -280217070 20773967500984
728 -785286320 211770887804292
841 -671812666 134166053446670
778 -75509568 1832850364831
861 -717204390 149357216009008
670 -804560120 241537051706166
522 -864637668 358045889085437
967 -991314248 254060910966035
522 -993952728 473153088649166
534 -910989048 388531411231496
507 -743683824 272715640247458
532 -767404680 276744103154643
982 -166482388 7056910237900
613 -387249264 61159815748702
554 -950843496 407989622212404
508 -805894248 319619586361528
832 -180951680 9839544028326
654 -648414840 160720071464606
586 -458927072 89853428400081
606 -862385268 306811428900035
527 -991339700 466203141076170
578 -421847520 76970981004225
525 -390341700 72556537295178
582 -168644976 12217693567082
509 -899827506 397687452400016
612 -635088312 164762575209438
821 -115150176 4038818163392
939 -167598354 7479319316225
591 -756502458 242088797686309
714 -641491872 144087547832477
553 -648501994 190125236883159
594 -457355052 88036678083093
515 -705177140 241396318053458
538 -127522140 7557668880258
566 -888659620 348815616764948
633 -950419116 356752920916026
594 -299512620 37756540836414
940 -117180400 3652731380402
528 -968646624 444260380759695
984 -239220240 14540319685685
535 -816173530 311281110793202
579 -961890384 399496984170100
508 -910002752 407533052736161
974 -272823244 19105628604895
637 -377574106 55951759665421
526 -257514872 31518668653896
603 -495995238 101995365901618
505 -981002900 476420144953852
561 -695607462 215629412925687
543 -374840502 64690371174614
669 -669123096 167312316908810
941 -72193520 1385393725812
775 -44588850 642093558323
546 -609694176 170205755319974
540 -961669800 428153396208370
647 -841505022 273621484874784
675 -63695700 1503458955441
998 -456778612 52267063530480
547 -835756924 319237381907586
539 -793834888 292289307081207
506 -975976848 470618769398540
646 -906061512 317705085458532
553 -880537476 350519258387701
514 -805031940 315213399954218
569 -597782296 157005780826127
874 -559851188 89655699254770
501 -962716590 462487671539010
511 -329348698 53068723300180
510 -303557100 45170866610981
700 -454216000 73683830143679
620 -832186320 279248490337146
502 -989799424 487900511608297
503 -37594220 703144557556
841 -27493972 225538940092
711 -284974488 28555949751596
614 -139024336 7870722932160
504 -234374112 27248502483835
501 -982403886 481596192912025
669 -644317914 155137623540473
514 -857200884 357390441526970
651 -580089174 129226254127818
578 -915887240 362825107053449
692 -41710992 629243026116
812 -846505128 220619888016328
719 -653661594 148565836808207
579 -747978834 241569433698847
751 -174856832 10178710284171
537 -900700434 377682963622448
764 -3303536 4224477102
514 -938207284 428129845930161
501 -256470918 32823826313450
500 -754183000 284397068189384
581 -399402640 68642012609236
654 -463480644 82116207688363
753 -990365178 325639378540980
695 -680289630 166473583824260
526 -753996804 270205771237301
517 -987349022 471402559484699
717 -321637596 36071411459456
500 -970456000 470893095386867
731 -116479002 4641115767933
647 -432576436 72304681263814
611 -874409432 312845145038906
532 -641554760 193418423164560
787 -738834026 173404772375351
529 -23124706 253539698381
521 -749710664 269706247443062
826 -289628640 25389932443238
774 -339406740 37209430166673
901 -408443122 46289696168900
723 -590245632 120467434941958
791 -318271506 32016077926054
528 -999190368 472719183728815
557 -675305686 204685722650856
510 -796623060 311083473718190
704 -867106944 267001999826904
694 -132093184 6286164537362
525 -903974400 389129126067404
631 -691358936 189373840111680
713 -954671350 319565094157176
952 -583218048 89324024893224
934 -121466700 3950339007327
572 -705463616 217517809395948
947 -26470544 185833606724
667 -632586802 149988259772930
508 -922827720 419100651500747
662 -660180824 164592665018661
965 -452602370 53070459700702
534 -885538608 367125789364049
594 -964001412 391119660761722
911 -64835870 1154753822072
587 -684153196 199347296879407
657 -867906198 286629794314701
660 -826749000 258907417838046
514 -891190676 386295006808194
683 -945696826 327359072082817
651 -622400268 148764918790901
778 -146092840 6859225463575
630 -914423580 331814476888482
999 -906904188 205825494716398
747 -522746118 91454550864610
698 -774914016 215076609026531
539 -133122220 8220611517168
535 -646569970 195352432966962
902 -319915948 28367433640936
655 -826938810 261003649101793
534 -964430700 435453352220995
638 -757350660 224757724793368
551 -837518898 318257741240013
622 -905097080 329261462997035
876 -702905904 141004410611089
983 -22542156 130044987344
582 -212009796 19308302681326
722 -341277848 40330135540435
504 -967523760 464337162032092
516 -994203000 478896174227837
779 -28693686 265146345459
511 -98630154 4759895454838
594 -998592408 419692174694286
703 -830130520 245063761316966
505 -999168760 494227817807991
998 -417485356 43661612206157
814 -881060576 238412350542496
526 -907406808 391344517700091
564 -900319968 359298853594507
794 -102022648 3278132846194
579 -882290622 336113333366082
758 -299604048 29606104649577
538 -39149184 713072891216
706 -210266568 15656545987688
543 -809910564 302005825073611
547 -729211170 243030531524411
866 -790489996 180391970694714
884 -279303336 22062903191490
514 -954448656 443080721500014
910 -177739380 8679712094621
850 -451178300 59871825368405
784 -810889632 209676055831686
985 -301502590 23072861260775
663 -980433792 362463396146656
684 -500095656 91410313226647
500 -568138000 161391115507011
741 -900076398 273326523123280
682 -509598584 95195574401204
820 -950494800 275439828425841
708 -601414848 127719650570159
727 -61914228 1319177883453
710 -38381180 519380584626
762 -946266840 293774112141883
572 -988610480 427164724905907
520 -596463920 171043784345466
549 -719480970 235726187521310
948 -298449360 23490174794865
679 -386076684 54881431578925
522 -505245888 122258153390389
712 -244620416 21011669591320
603 -819005454 278098079728272
747 -537230448 96592649626497
505 -983270350 478624693477947
533 -961619412 433730978977475
508 -912194264 409498177753477
726 -443577288 67755977293585
503 -266028652 35175495173988
627 -415807590 68938563794832
574 -327361384 46675618376040
685 -686376850 171940072365149
533 -986523304 456486875479150
626 -522519696 109037185680020
703 -301816178 32395109286474
887 -893496388 225010856863772
689 -912288364 301985594391787
504 -7517664 28747426660
606 -878547288 318419182397683
530 -750877500 265952388452401
884 -241927816 16553221762881
553 -400023610 72342015362168
878 -979110480 272966908649347
616 -311682448 39427102417012
641 -554585508 119956302342553
515 -963435220 450586916703214
887 -378356946 40348456631530
766 -814019008 216263160565769
772 -570373672 105352547596956
920 -527666000 75661433343410
544 -934470144 401303798001048
719 -898193494 280512540210575
618 -572574528 132623057387148
701 -764370400 208368230477406
543 -907701606 379339210784808
620 -85796840 2969136863161
599 -841184086 295322371487093
715 -81112460 2301433987216
500 -999110000 499111194670337
513 -990401904 478020606917896
878 -847371848 204453779675614
515 -327149630 51955500846035
714 -420758772 61988719355910
677 -409119224 61809711420228
833 -167181434 8389280615569
572 -954936840 398560511159986
686 -523125764 99731508277340
642 -751265832 219782810334703
776 -295992784 28226363501227
969 -725544564 135814679678266
740 -224730600 17062798781555
502 -994619628 492664196717913
794 -897288284 253504422251414
523 -980266222 459332343592129
714 -971278476 330316667230006
640 -160992000 10125248411983
754 -870781028 251413022999174
581 -652445570 183170296184497
1000 -565668000 79996135153779
558 -833391972 311175670352607
939 -824855160 181147300571665
835 -447114110 59854514704054
932 -99861936 2675703482065
539 -10723944 54205799544
601 -856182196 304929133728544
797 -323951808 32919373383861
575 -874989000 332872758883666
701 -923256256 303996202487328
572 -909337000 361405430270031
580 -868044240 324785494062064
719 -999592626 347423084924503
520 -149509360 10747722271622
951 -821342562 177341336602503
518 -886303180 379119297628479
750 -856971000 244800431994062
634 -605121300 144390439123987
601 -887562810 327691203785760
848 -927008160 253345196385870
520 -961407200 444377513054246
772 -202094160 13226726444734
842 -210378752 13142222330517
736 -875869440 260580644585046
515 -885802060 380896709893528
551 -968498210 425585532055455
850 -129810300 4957028151055
589 -930432698 367448201631586
941 -29152180 226507103056
613 -200474294 16391439268050
519 -804433392 311712706203053
542 -580921020 155659883946592
516 -997356792 481939160216169
905 -432162840 51593203195754
867 -612266730 108094959871312
669 -560936430 117582764913863
550 -97298300 4303802174964
941 -806519808 172815399213185
598 -957021260 382897759216892
667 -206405818 15969367286522
609 -785672118 253400046228466
696 -820753824 241967944576212
981 -545235876 75760847720709
503 -844688906 354623044547373
751 -287502326 27516497120808
555 -851306730 326453075623531
507 -630691776 196141193134515
575 -82688450 2973904114914
541 -872626508 351884847374985
800 -83396800 2174178444683
695 -559758560 112709404710065
544 -944995456 410394537460229
620 -720763640 209476703140530
500 -996813000 496818752120841
627 -844733274 284520095936231
601 -853809448 303241496565082
640 -994694400 386491741336410
581 -655571350 184929377464107
675 -974795850 351936864449061
875 -217637000 13533799820216
536 -555316368 143833158526874
707 -646397374 147748090163593
559 -365673204 59802805826331
508 -992616760 484886492520826
890 -646310880 117337190674881
555 -904371390 368418837171822
545 -873417000 349935349089264
654 -945464256 341706583673026
683 -809686938 239969029670625
667 -5576120 12426255385
573 -901868766 354872981431142
529 -701389462 232490409689422
658 -745800888 211330086784622
838 -975463844 283870376156906
781 -202047824 13068481962653
516 -868779912 365688344077666
842 -465730408 64402590085913
661 -764513922 221060472978733
729 -12995154 58617512771
617 -872494764 308447799064872
521 -776208724 289108509176076
732 -654194256 146165307430457
718 -158086368 8702600330416
541 -360286524 59985540647107
580 -733629240 231988633124021
848 -930359456 255180100544175
518 -722353072 251832029601761
567 -842411178 312900421697096
511 -701466052 240732017787596
635 -828401950 270178145736816
510 -976734660 467653069907174
526 -926274428 407788164973534
522 -625019832 187093497932263
608 -744446144 227879054155109
522 -985706172 465334312836039
657 -59324472 1339831085303
506 -208534744 21486204784630
590 -205714120 17932262717909
639 -268516746 28209309915260
798 -524715324 86255768846310
729 -442440306 67131771944336
567 -958172166 404804012848093
564 -959265864 407887071535657
799 -211044664 13936922132980
619 -954179834 367714392411759
502 -876977936 383013810430345
526 -268203192 34189739218000
742 -839788180 237616849406092
558 -992443176 441283853560374
525 -925776600 408126078553200
544 -396107072 72106123842690
573 -321079404 44979968539190
1000 -895124000 200312538301509
523 -69862340 2334155343804
715 -293360210 30091887403228
711 -835038216 245179618909463
808 -832008912 214183986268649
537 -361648020 60889525531826
592 -966524064 394497729121891
583 -550242396 129832527558703
625 -338505000 45835322609051
811 -470225910 68161124774627
823 -709002978 152699946498224
966 -429663276 47778093790396
812 -216831608 14476065549080
500 -341521000 58319004117792
589 -952497816 385082477951529
536 -981534992 449353196542559
672 -534476544 106275408197952
505 -81322170 3274728182923
712 -420713680 62149712760000
505 -716257660 253973437621820
809 -596077672 109799423866027
508 -947759344 442051816832063
722 -967800568 324321799533652
514 -400036948 77836134924048
970 -20843360 113086498433
605 -349352410 50433346588309
702 -720522972 184884332775019
699 -458760690 75273448929736
513 -705212892 242362318463205
573 -913358562 363972748816083
512 -961728512 451623077008100
912 -214042752 12559518330309
924 -460436592 57360511277321
814 -745785172 170822600085104
557 -286596552 36866953115220
946 -139548244 5147030667663
564 -839101152 312097756865805
630 -838688760 279127690927484
510 -819207900 328972037312881
500 -104144000 5423719647443
678 -696954168 179110456860044
851 -616792886 111761777961273
763 -573046572 107596702749624
535 -982515730 451093192707611
642 -663210396 171281479820166
501 -997255530 496267566201066
945 -421519140 47005577563064
844 -416914056 51486854720083
569 -896495916 353122697203495
620 -772531160 240647747223044
677 -967822952 345895091583820
606 -202504596 16918336133914
769 -93212028 2825529144390
705 -905194620 290560252079055
583 -695585462 207479182752628
725 -86631700 2588695361698
608 -985015936 398954821106530
504 -928567584 427697995027370
664 -211985984 16920115926242
800 -808366400 204205832768280
710 -918119460 296811688320800
567 -867333096 331688404805920
879 -596299536 101130857042223
514 -964382220 452351576800359
516 -805155048 314087211757700
610 -634892880 165201065079764
552 -515154000 120192851473201
705 -574428360 117010787266217
551 -395297318 70899451422359
673 -105831942 4161443632912
568 -815410576 292648218482375
507 -985984194 479372009205315
550 -198064900 17832424694383
615 -553554120 124562992709209
503 -947680168 446371313534030
587 -65620730 1834681610870
508 -159043624 12449315823167
524 -949721704 430330726835803
651 -222448002 19003733608795
989 -960831302 233366909514264
625 -375857500 56508342475314
954 -711342468 132602430247932
739 -273670914 25337549808594
680 -558096400 114512336242743
694 -738572844 196502883234693
781 -324250894 33655852777834
613 -131723892 7077093253535
917 -355410860 34438487159405
543 -693756348 221592993133620
954 -886712472 206043620898483
791 -191200520 11555040766986
502 -986829592 484977255692167
512 -807878656 318686373504866
636 -354772248 49475673350478
774 -438820848 62198327234713
547 -517087852 122203611567381
594 -776448288 253734790074029
692 -24495416 217433249454
531 -627871392 185604494154860
821 -52143352 828935892541
515 -923455770 413967020756984
760 -89676960 2646448595196
504 -419032656 87098268214599
557 -530298534 126220343337239
529 -29433560 410446689707
626 -600509280 144014857252164
595 -925786680 360119102114187
725 -672808700 156094341587097
522 -705563388 238420104369015
836 -589055632 103764586284868
685 -20360940 152479313384
611 -854714458 298911325889396
702 -758863404 205083849854830
513 -969602832 458153793751740
624 -864956352 299740035378924
601 -465997370 90330864431931
890 -308066380 26659341196648
557 -707877932 224907333302600
826 -964292224 281435136235735
809 -455928130 64237771203439
762 -542022792 96388050932721
502 -988228164 486352758458790
524 -992549272 470017281169683
535 -955955120 427033451410663
560 -498109920 110765915741758
516 -863459952 361223218906017
677 -774896908 221738360714961
878 -130649912 4861343608981
523 -638950146 195152373287198
612 -350066448 50060935979521
695 -800733130 230638906432993
632 -284702096 32063884098314
907 -962397746 255295567862791
801 -545811012 92981426875033
917 -120455286 3956467569757
506 -959855688 455199910034857
526 -932125652 412956259899422
832 -997276800 298847484045248
738 -955413324 309219949059910
784 -324227904 33522520903214
540 -737780400 252000839375925
925 -64119150 1112023888748
506 -867435800 371762268336618
595 -974421980 398949751982479
604 -981886560 399049151789686
725 -987854550 336503002951088
914 -76300720 1593134467952
956 -978871344 250573118740302
623 -956876914 367422008844561
623 -456637818 83675825005625
718 -770560472 206743085807084
517 -931687768 419750444980609
859 -760714938 168419610253183
807 -41336154 530218864145
536 -963752656 433219030168510
577 -358773984 55771457987935
994 -421318828 44645938432544
661 -622466344 146545676861746
893 -788368976 174000317227837
761 -813067620 217175075284679
572 -37874408 627826520493
534 -276257424 35730395806393
1265525046 887