#1875. 轮盘赌游戏
轮盘赌游戏
轮盘赌游戏
题目描述
标题: 轮盘赌游戏 - Problem - QOJ.ac
#9633. 轮盘赌游戏
The problem was used in the following contests:
题目描述
一个有 n 颗子弹的轮盘,子弹依次编号为 0,1,…,n−1,每一颗子弹有一个卡壳概率 pi,表示如果即将激发的子弹是第 i 颗,那么它有 pi 的概率卡壳不能被打出,有 1−pi 的概率成功打出。
轮盘赌游戏的规则如下:均匀随机地从 n 颗子弹中选择一颗子弹开始进行轮盘赌,每一轮都会激发一颗子弹,假设某一轮激发第 i 颗子弹,如果子弹成功打出了,那么游戏结束;否则轮盘会向后旋转 d 颗子弹,游戏进入下一轮,也就是即将激发的子弹会变成第 (i+d)modn 颗。小 X 想要知道轮盘赌游戏结束轮数的期望。
由于子弹的生产都是 m 颗一盒生产的,而且生产质量是一致的,所以可以认为存在一个长度为 m 的序列 pi′,使得对于轮盘里的 n 颗子弹,有:pi=pimodm′ (i=0,1,…,n−1)。
为了增加游戏的乐趣,小 X 找到了 q 枚特殊的子弹,他将会用这些子弹替换掉轮盘中的某一些子弹。小 X 将形式化地告诉你这个替换的过程。
小 X 的每一颗特殊子弹都可以看作是一个二元组 (x,y),表示这一颗子弹可以替换掉轮盘中的编号为 x 子弹,让这一颗子弹的卡壳概率变成 y。
小 X 的每一次替换都可以看作是一个二元组集合 S(保证 S 中的所有二元组 (x,y) 中 x 互不相同),对于所有的 (x,y)∈S,小 X 会将序列上的编号为 x 颗子弹替换掉,让这颗子弹的卡壳概率变成 y。
而对于一个二元组集合 S(也就是一次替换),记 f(S) 为用完成替换之后的子弹进行轮盘赌游戏,游戏结束轮数的期望。
小 X 会以如下方式生成 q+t 个替换:
- 其中前 q 个替换的生成方式如下:第 i 个替换为 Si=(xi,yi) 。
- 后 t 个替换的生成方式如下:第 q+j 个替换是给定两个编号比它小且没有被选择过的替换,将其合并得到的结果。具体的,选择第 aj 和 bj 个替换(aj,bj<q+j),那么有第 q+j 个替换为 Sq+j=Saj∪Sbj。
小 X 想要求出 f(∅),以及 f(Si),i=1,2,…,q+t,但是小 X 还要去解决其他的问题,所以他找到了你。
你需要告诉小 X f(∅), f(Si)(i=1,2,…,q+t)乘 n 之后的结果,由于结果可能较大且不一定为整数,所以你只需要输出其对 998244353 取模后的结果。
输入格式
第一行输入五个数 n,m,d,q,t。
第二行输入 m 个数,其中第 i 个数为 pi−1′。
接下来的 q 行,每行两个数 xi,yi,表示 Si=(xi,yi)。
接下来的 t 行,每行两个数 ai,bi,表示 Si+q=Sai∪Sbi。
输出格式
共 1+q+t 行,其中第一行为 n×f(∅),接下来第 i+1 行为 n×f(Si) 。
样例
样例输入 1
3 3 1 2 1
1 499122177 0
0 499122177
1 1
1 2
样例输出 1
5
748683269
6
5
样例解释
12≡499122177(mod998244353),所以可以认为三颗子弹的卡壳概率为 1,12,0。
对于 f(∅),序列为 1,12,0,第一颗子弹进行的期望轮数为 2×12+3×12=52,第二颗子弹进行的期望轮数为 1×12+2×12=32,第三颗子弹的期望轮数为 1,最终答案为 52+32+1=5。
S1=(0,12),替换后的序列为 12,12,0,答案为 (1×12+2×14+3×14)+(1×12+2×12)+1=74,74≡748683269(mod998244353)。
S2=(1,1),替换后的序列为 1,1,0,答案为 3+2+1=6。
S3=S1∪S2=(0,12),(1,1),替换后的序列为 12,1,0,答案为 (1×12+3×12)+2+1=5。
数据范围
对于所有数据满足:1≤d≤n≤1016,m≤5000。1≤q,t≤105,0≤xi<n 且 ∀i≠j,xi≠xj,0≤pi′,yi<998244353,1≤ai,bi<i+q 且保证所有的 ai,bi 均不相同,数据保证 gcd(d,n)=1,且对于任何询问,所有子弹被卡壳的概率之积对 998244353 取模不等于 1。
- Subtask 1(10 pts):1≤q,t,n≤103。
- Subtask 2(15 pts):1≤n≤106。
- Subtask 3(30 pts):d=1。
- Subtask 4(20 pts):q=t=0。
- Subtask 5(25 pts):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
951 917 92 951 950
13133014 619316385 928269899 402448339 750819940 857430561 238267150 538264727 795126569 230524726 592432138 387840859 725283138 942095843 940362935 493343628 5282658 466839671 992842492 152463200 757252414 250391989 274243447 738676717 898281683 756853751 170485624 938831978 909158315 79127018 357730880 744902899 296993870 895033489 457849716 668659392 231206606 135623465 2556556 569708296 850962188 104329247 525319480 786440908 246835464 922703185 135364799 754165136 714177534 940835485 276811922 967922067 719468381 527989131 540874181 539186757 742074402 770532897 445331159 918991677 924836797 351788082 551848099 333000918 773300567 737999350 14079525 722799491 861482199 289966479 118349679 659569045 88590156 617010011 14825866 131649588 700980641 686400007 907338171 188468942 111608676 560519778 700057008 100545436 823501413 561083664 605880444 72970807 655651685 354188351 678461014 267600967 221322731 327559937 867335931 411987057 428157000 551636612 935390329 886166666 150690630 804536283 555882336 346665249 740949591 192438212 530986628 177458468 600670899 579633508 913259066 60457563 488724013 139737114 448559317 824947060 348652686 367799422 894843177 832643824 340486129 534864398 991102394 851034221 855620598 423880733 693885962 687612488 276351807 137801753 677930513 147025692 925162210 498251475 158071404 380868152 171534374 306899147 327486758 329912576 503096023 876886587 895850944 435307954 535449313 638179582 249147296 614796885 112295985 166149439 26203580 869404249 437632772 537740481 379142895 783996876 193757896 233982152 536402376 867151550 921729540 818758949 362990123 367294073 470083641 904302474 786373249 470429257 622661944 413571637 1945822 701568947 939652056 389245265 560376620 579510921 780386216 268735549 499635291 955373938 312424588 778422811 218149670 238130021 125191500 989214346 444319574 661637742 203827545 95413553 634537636 69917466 722145827 3728525 861898478 955542054 89792663 252011308 133126954 27438296 224922204 507837667 675649894 554078908 59711237 596058304 923032094 398192189 515702141 392178733 261935051 560675391 566621018 632314541 924561688 183506921 929488744 975579466 122590715 470561962 84959051 526801050 416696242 981138596 387930590 705563811 135572877 414343379 833556174 509211857 890368747 143290183 659621274 502407859 893895419 131670719 121648344 308787313 368608334 533668060 813862288 347938215 994492953 389914925 255304061 655728016 491108175 223197714 991392748 814921542 76887185 223778731 499306778 406424027 723660613 926752063 239296040 858596165 192079153 872357469 74806980 945184269 342949029 983086496 823014559 660116194 473514287 871665792 143573013 339395903 425314804 951287865 810495185 702210648 709516263 474716176 581359987 883185650 490259770 866933022 494123600 158180500 169021092 158289666 427024073 423987488 986642840 986814700 205439624 164724950 433215212 443333668 741809609 130886488 301661874 157558410 745083456 968721901 422917331 98906804 336208377 172412838 899306789 482651517 281579101 99421752 745694179 101359297 557010636 243751353 211749148 352696199 941767023 875818875 473522445 52257561 349751237 888310149 980847203 5667659 585192863 132579916 685936467 410676756 465189033 558071521 373739690 372751472 499997884 900006058 312428397 665946708 334866431 888853407 300579856 335265741 833101538 558557779 376277414 316692335 800715150 364584616 744932018 447209227 362569914 435368068 185154721 246504161 562700829 191588631 212163166 919840918 564101360 170774873 571509620 756393136 459906526 839512298 274853221 546801405 713572922 521932488 261710445 281090860 67017752 629564062 414325913 129739271 115661372 972877640 634075303 807755836 874492820 270186994 179167926 43267412 439961169 71485207 7115191 312082809 338558245 376037929 378097704 229206148 648622383 549997861 104678070 524076682 201477527 782329115 989275654 196640947 596516864 380772693 192108288 139466797 843730916 882517169 407560072 547367536 477441572 837795390 566211798 541640599 953280091 966561878 178931552 375765109 739407984 209697192 282016288 848059566 255790619 151556079 977881532 54419233 638373596 989726764 738298248 556822580 63701590 219625525 253639302 665566095 37590083 768630283 436036228 488887780 677268313 449530388 989555520 930799712 238621752 972247420 133946539 297685663 220713384 966216784 847357390 850189094 831338639 171603125 996728842 398447351 279481901 773664735 274676294 796723809 66615075 277093515 143925899 129245199 564782151 391628 410038019 15153788 838716185 759065489 586490325 69793332 189593711 767703396 294861593 102147722 621557346 27867535 382858902 547154284 81823520 737278644 190964700 825159464 332826765 764238022 206526855 953108311 586324802 251688185 662955624 509241166 436927333 633328503 297969746 24271413 179141392 513405610 127550735 57573663 706328882 472412158 685370640 398562187 665541209 713126601 751486650 519755234 667792091 872655306 62612030 247648947 826031181 363969526 202329389 434047985 597083833 459525223 371973558 347743963 777787281 727406338 21959645 366924571 891304344 82719124 816030992 428925160 162953904 7471613 865779392 3975249 552037405 291366456 181807632 37369892 755843999 58793403 588274538 753941819 668017307 665973538 143895186 826830101 844081820 40689149 173406040 447769013 944532672 237194128 119173056 555733318 599414660 223490616 298186660 878083839 277235225 74001475 572337763 288388046 365720089 514080282 811176690 10324718 636008208 728146950 810927287 906233883 371324961 211070846 410362339 610049935 563414324 949128238 824816753 981501077 454095077 91696432 941333406 851632985 944934363 16478002 488697580 784355339 506439836 448032429 878918872 445263710 786363705 522816006 537301798 909758341 280854417 661679891 59584025 616856163 230398252 630925038 967286943 589179902 383863764 536310262 894888035 524724749 829951772 212846096 249248037 830039307 283397728 264602490 988747888 977652162 519346799 89810020 527644248 610274903 601900353 127593377 238919411 466709298 97777897 913770115 997163232 734713010 320253883 414616327 437576114 158335784 431821727 371571217 633517309 897742542 862630912 511870141 646220995 301650101 651918526 752551543 221909734 599270743 780560398 599422217 191927808 495270839 520239136 328955889 329012114 202466746 756532825 976899795 995191671 958451755 519534509 559674394 340633465 233433237 931362059 265371428 406538261 355229809 945258373 197097602 549871733 661873499 390790835 952886909 157274906 425985002 365784479 42997177 669013564 923631274 465866570 584241122 137667286 826295575 133117088 800165948 370575835 263482723 371606516 106299835 869315983 902408945 649518202 390713226 892248204 903048785 471500289 756951782 564656873 172401490 249274018 403025817 692623214 126231514 160903643 664689474 348171350 393729716 155560092 365040487 55340155 393635603 206180334 723557683 146249721 146661766 221566490 263879607 60984876 903239308 118164375 137445193 529162977 591639826 828327156 656461482 315355507 22881339 368920723 635331501 558574097 37846110 748794695 451360312 223290631 757945557 579611941 750616856 114015393 355591177 951017915 257536450 181265976 502723872 969936640 768562328 630875149 383698052 718571094 847429505 721262121 673869475 337205027 4824624 286995843 403089015 722593438 38519902 481659444 448085496 236733582 743146265 803424861 878334274 187361194 597572176 38447735 664255602 293484053 19221082 242793931 516339724 799999280 805620865 118317992 464311842 894797865 875206074 656803011 811987244 965961075 223065508 111696778 739537395 504232022 628531454 913008686 845886024 403689553 788364304 692555322 551037498 671861230 362070941 715401757 818845076 939634799 881869773 306794806 822016182 626092518 564836135 225505906 26289569 374612434 689107136 370288861 690979055 852245072 754546323 609761778 310283518 666218146 873469647 547611830 343703087 956188425 631934673 995000198 719157660 207887387 46026578 386581344 568676109 906159232 210294934 314041665 776787356 823595560 811986540 4926946 393838923 184849631 669512965 593104505 378405106 511668095 380260017 102433572 368822843 625596251 941215787 885885580 764974122 266975628 447362019 52008223 45257380 821024663 38466323 332404809 598640575 442351310 317454909 813902204 47148833 798069794 45904672 697642052 515618665 145060307 890250449 13557192 495698487 870276286 327409412 93207420 595470392 822800836 576964601 242777458 239077255 113485650 600572923 119642911 708802129 261342778 924788221 817973137 779335439 11400380 687089703 97476935 832488117 470646656 759171812 293137406 331654466 188002391 3927555 572971770 481269936 615533319 601475494 117815867 898078841 933441873 600760273 342053963 380967809 305379804 415706986 345642737 524936001 405424970 554746485 909242734 576837430 951070529 916570879 484242312 485162063 464444509 20331662 770220687 608352789 932804395 388539559 216770202 75689666 348305696 87267375 684609352 102039670 289530228 617505685 797875996 94025272 561378926 658822492 929410088 734638166 285682735 903693532 408977795 436007662 779833847
341 284788198
830 778154715
897 643724888
189 67774143
135 663872696
246 173871099
616 755748370
687 28077952
706 298648032
605 977169326
809 64859627
107 830165246
480 202088981
682 573074212
783 630052615
487 777006035
273 179948889
319 980769660
752 955513876
645 531838991
45 786457201
603 347222751
661 362279751
669 662511561
435 906898826
852 112809180
94 152578724
363 202739671
734 371907105
940 424531167
745 944015182
106 173085411
930 476704884
606 932094124
642 214017492
702 510956934
346 898633088
227 189521839
459 15883757
326 39734236
402 242554827
733 887007479
191 50375958
207 666395617
371 795538065
223 351447070
316 9818515
848 729223980
445 74815720
641 936059187
846 874715746
610 722168563
297 498043332
674 838853015
849 142989167
33 178069756
314 631299071
181 235562261
770 623933668
143 922884923
635 206720092
175 143892732
699 139715340
693 729884466
35 613724522
32 831376101
558 448593824
458 160456380
631 437954304
252 154862994
875 869067327
321 158769289
27 555579085
279 663319156
494 868304783
506 700778107
229 756126417
858 984116840
456 987982194
482 924045006
819 811756795
221 943900196
774 539492008
72 382346175
594 102541602
854 804919211
472 333255985
216 618641397
763 115106487
294 167023277
833 192598739
36 283713381
425 704153994
96 692850462
296 68853276
416 519959759
116 541881859
287 720785475
561 407745384
643 482807885
862 78961544
200 294745948
433 351517804
103 483838762
673 40849246
518 559511626
361 321933161
171 581455274
507 291145483
249 776439695
455 469486686
37 760426883
511 620771516
623 112659850
228 804947124
141 861121121
261 963679887
387 271899943
473 91687698
909 225735248
282 5804531
429 166401455
746 778658415
793 975427281
676 211789455
255 429554858
530 763374738
926 646417769
929 684734227
352 836206258
14 549842321
301 689477098
356 712040963
64 245143354
622 59128843
125 883258159
785 951342697
168 745746917
257 389960284
748 429016438
891 532175938
21 850204622
20 259716952
513 767031490
467 585181134
914 944404940
380 20460902
118 496025934
111 110539458
441 477640668
147 29692151
69 443598382
419 739754868
354 507359378
510 880107717
182 97547830
681 518802080
883 397329934
410 112691820
335 659496133
553 405998069
596 372125019
860 257648553
692 48531721
612 251434518
67 626939681
87 253236393
586 737725527
322 5136274
601 419588171
576 922752670
590 65451959
86 347324264
154 903304425
422 460868731
742 214311733
568 492922350
323 872947082
209 562871144
600 34215396
519 704689181
84 931882894
881 567875270
834 407695725
744 752038296
65 574165854
771 723868741
741 649822596
440 755950376
697 980767315
83 810663929
711 353375011
239 321748757
241 416679176
888 735499238
772 157798373
3 617074038
248 862706297
260 241822453
78 51603331
749 90510625
933 211852416
417 468412510
284 46116176
98 157617352
70 385652767
531 295652893
584 338135155
529 131650532
573 133685749
532 849100027
912 430040008
683 22136503
592 748189263
489 495572702
790 11439230
479 355313322
880 759813864
469 449889413
117 957716143
619 664608017
364 57373992
461 445772208
1 659916187
656 448554544
723 573423050
291 918939358
719 917223511
714 652881079
593 469004831
700 286259815
863 300592908
789 871767395
808 11089786
471 41748590
646 907017078
708 878510796
889 439286347
667 663975086
233 917364377
68 416439254
58 591161470
817 22197014
948 901018491
779 433336234
613 275458989
923 937864388
620 145725260
344 209595545
150 738047035
762 587906334
678 780616399
686 159065234
427 48811571
383 587292720
541 88155773
886 975954421
167 922947231
492 276880232
704 429137092
390 156954717
890 786649462
26 699679819
77 145593589
717 510608778
887 703858959
666 899666848
99 474859228
251 866678450
104 852702374
564 798772992
205 792935741
423 516129976
343 586573431
556 532240270
81 842346184
477 834209344
30 557473852
466 760543099
632 517636965
265 407176153
102 468231358
108 838419457
709 205680550
807 454744041
650 510261117
203 47439798
811 399016354
626 279010701
114 129680099
332 743761386
259 306459212
615 961978388
289 157517435
498 272881976
500 116531826
638 57684778
17 754546952
362 537325585
100 655334186
270 162010910
11 765179179
818 490305957
307 212682862
905 647890435
916 913026443
382 203561592
617 874414363
495 210625291
743 280708369
179 38321185
855 106311883
188 599198256
827 755706304
267 734079343
806 238798925
629 471851595
766 653091638
62 239080693
579 917625637
222 691859497
421 246888848
684 432908541
918 655060997
728 792558049
865 717946025
451 482761052
788 374142803
214 175525679
398 273787053
309 838873391
162 823669741
219 155439130
585 896573932
403 748479274
185 582374351
407 589205228
552 338064811
497 467193774
127 3204117
698 942876794
411 230321043
718 361577111
436 415324314
204 692039223
464 640557811
651 810848741
220 800305169
876 209938295
95 948643
424 596087079
528 735368735
113 734811564
859 169568110
224 517809408
569 839131200
736 134061254
624 962630037
727 735585731
199 455312913
829 590658129
710 970321563
907 264480073
792 866167095
444 594161970
131 164058397
368 598705258
434 381565258
913 784213920
325 545583115
892 527135566
412 714571997
176 438320276
557 187623931
630 912118092
413 162475370
873 257868848
286 749350485
187 920598918
755 817617160
663 132762830
657 234696297
551 11881170
866 351950
178 453849194
392 485297347
91 478227192
457 190160840
283 116212311
647 935353720
935 974072123
376 360823187
146 631579129
272 252091432
300 699314776
130 286848930
931 640647071
405 840318277
563 297739332
348 664255877
764 468801794
571 128908476
919 612268590
565 90480532
831 109495857
293 532748626
370 361855334
879 364828460
298 710618661
438 971991871
313 673991598
739 658240725
545 722134494
937 912302105
934 74313359
872 546405386
812 510314625
566 516691016
51 269992999
911 613951772
928 612449129
245 797911466
394 646911175
691 731310790
761 83422136
6 352073665
338 27836717
218 391655719
430 33509938
870 3825198
196 71347230
488 537241423
460 693423704
340 374502219
824 960914171
140 46939960
443 645480366
941 877181430
202 458516626
8 772906012
773 901840791
832 28739919
821 52286079
861 106257878
550 474350810
381 394928659
311 481159058
826 454841218
671 865708665
757 887862711
853 515013436
582 141302223
74 752234734
677 941527490
904 201319241
493 777276222
539 220113195
378 185748263
169 783693695
73 187399849
470 290655014
345 923319374
442 631947086
305 599377652
567 394834459
502 610295460
446 948494127
120 789925459
857 293697211
514 591923183
618 570005888
123 898198044
122 567577248
597 240478982
521 249046021
310 836773075
173 971871170
12 666851388
794 611235656
496 587277122
871 529588003
501 950406851
43 668715585
54 811049143
134 544622935
396 391017372
525 764461880
327 489386244
353 104186927
29 464460390
868 561543146
161 858192888
231 902015027
660 901093139
867 822540528
160 720676863
384 715417203
22 577386642
145 414188194
944 152582090
921 813695224
627 954945905
79 213224762
153 370586081
404 278611150
685 939878202
798 203082029
66 195517642
878 748911401
844 54449242
320 718576475
393 145806892
112 249299223
947 683385403
71 458226210
350 387624762
192 969577495
240 782297363
474 278453813
595 508008180
285 996578706
802 83927986
850 605779017
277 784516349
668 851728695
688 775327547
836 843753805
238 449991098
170 121289446
653 784120988
448 931309114
292 94597309
611 629778587
280 402328702
401 283987139
302 710619184
57 434760325
825 786833231
155 31850259
243 845055868
484 60467617
536 747625131
264 290770209
787 867880320
18 851021053
90 855005595
731 792111410
244 352632819
269 298923997
281 498547728
80 352569688
696 924159485
278 205314178
357 292458570
938 655073369
109 349603076
747 570938569
235 819043617
659 240473689
837 978080063
491 537162165
242 175434141
526 4560083
82 803605220
813 332327254
275 142845275
713 167748830
450 650762103
225 527973046
331 739395005
374 652171322
942 797280151
159 78594689
665 455037463
121 422171281
409 332567861
894 718865620
55 243360710
139 926408321
885 301127956
760 301888564
193 932250418
452 270581277
360 185213826
365 915556814
540 453919592
359 75075057
901 182383562
554 599163950
232 77876659
675 961365249
25 926297436
679 158999735
730 342394427
253 205965037
317 842490837
499 862848005
0 95586217
637 661080662
351 931477913
213 278816300
16 630204980
943 767952424
922 799480893
614 43210942
738 307316436
781 398385561
24 79980678
707 669845771
835 923605391
465 161326180
197 356575842
449 976240206
689 440500132
475 255051315
908 372128979
377 250461062
522 268121041
92 132364573
76 369879113
575 182067385
570 249521037
431 736595607
559 216863388
144 100086033
420 962029394
418 553885494
740 464434393
52 512456021
577 9120134
19 786415239
397 135363101
263 839119317
190 667334911
814 666647933
599 97102535
375 905613842
515 466156255
183 776636598
882 843201492
184 719518667
395 459680939
137 744171338
129 587196088
840 228889178
217 906573081
318 1829653
572 660727116
910 965404631
453 541439994
636 645635828
737 352935460
843 603246189
119 608893022
454 742393327
391 385107200
769 261913258
639 143197628
266 30201586
201 18393437
262 202755053
754 678677168
7 274178331
372 991561607
722 364068763
580 487155801
306 969069460
895 324822099
925 70671358
784 800024980
533 199396137
898 579931862
128 185793934
115 255014756
664 329934103
778 696100561
581 898429269
212 72753723
782 94616489
750 26479480
753 882651128
538 204900569
621 80501299
503 889986276
516 213072889
485 170396628
10 935678424
851 939983768
524 536649188
797 463237419
400 603872967
869 517644698
512 813253134
388 530393289
23 869450751
142 802004946
271 463639398
896 799014299
662 593340181
329 272266282
578 967389063
724 93260626
776 280696699
535 479881054
53 913162248
60 487671782
337 936980432
211 439613230
924 670910954
439 971076106
39 925519855
237 29400388
478 120462695
920 969150055
644 413756770
366 884490688
9 127635791
149 407409456
101 774791139
939 552346155
504 491849576
328 496548027
562 513462934
215 671465054
428 603404110
408 250021098
856 439963465
136 949350124
2 629238561
315 892855589
299 145460029
537 105977381
791 336241602
334 276515311
655 221658874
732 508524718
589 488793596
508 192689823
172 843027540
670 7112302
48 845302916
258 580944386
138 982685007
587 449669120
680 513946706
49 362688995
695 569576605
180 434902259
85 298537202
34 338222747
61 724136372
899 380339139
124 280952216
276 927627092
694 472121660
583 445807699
462 450616606
156 762456305
845 945950075
735 834412084
932 547117016
609 954950379
758 813687468
549 188484810
157 837595283
163 609930425
534 883162744
406 547182930
379 134977001
336 15147215
148 815330599
548 19674881
386 801969347
358 715987501
210 604260194
186 581095772
166 439946448
903 130258383
633 617216515
399 201379574
847 897426216
839 299925183
777 400230079
690 191139185
414 740228069
50 393689718
917 926342459
437 975521073
206 734856072
767 384485520
672 126978888
369 287128564
598 387939754
628 603332883
640 689846880
721 397481578
308 38836584
31 24943319
542 699761008
432 634283163
151 844801367
110 348726788
132 186252843
658 653691589
56 8474175
59 369692
268 636474074
164 725233584
652 330789142
41 621004222
158 925966228
795 766823113
893 798467215
274 982296739
5 971753907
303 716902507
165 669002568
40 656684301
648 615028113
230 547771823
810 542068442
715 848287199
765 131613337
373 915898420
38 614250831
256 593392751
803 497371507
208 396820332
290 409897224
602 847500590
304 455271712
89 585267513
560 578193309
447 956995835
324 838746564
574 580249179
874 334629918
126 638445138
486 938070102
543 349614783
28 731516804
15 5143816
588 627857810
226 883555281
591 671314730
822 550275644
625 991065600
759 729227486
815 124977562
604 859602936
385 140199657
13 294070779
608 424144233
42 184035736
634 175365941
864 730104124
527 263837541
838 437205074
841 589400841
490 500463316
546 688087918
555 585200728
46 854564890
801 608576615
703 696725495
93 516091742
720 826637917
712 600856541
97 590351142
796 976791917
906 708883710
234 822065527
355 340986788
544 2323846
347 875737432
877 686246007
105 229726915
729 984530382
946 355689979
842 287733442
481 381433568
523 311248446
389 512668844
349 101189879
174 285091722
915 41169833
254 509972835
463 375714813
751 353099357
936 221543874
177 261194742
654 538501911
823 768708042
133 848930000
339 480910697
505 284651173
804 209005767
415 184346107
367 895744307
607 899705697
780 754612081
198 817743247
701 970952473
768 786160852
476 762494486
902 80088566
945 441381344
950 343104493
247 945653843
756 12747961
725 796027149
250 416296522
330 840721331
716 248487771
775 509645180
820 689478550
195 544788465
547 956290494
828 852935876
483 151374210
236 989639502
63 745892120
4 870946682
949 975716027
927 591310468
312 6345392
786 818782400
426 726002646
342 738131597
295 704504229
816 744810928
288 497398468
649 711130808
884 810764259
333 466526720
47 65761326
800 148645690
44 389421996
900 175323544
152 449054837
517 223346001
509 633142396
520 521664006
88 952069594
468 722202496
805 160376691
726 91129040
194 651869238
799 759053162
75 188223188
705 593547180
24 654
177 832
218 321
789 708
826 458
719 305
901 739
810 907
444 299
376 953
767 17
583 192
605 581
111 225
686 924
738 486
906 783
191 961
147 333
879 969
32 733
760 39
932 841
718 260
179 666
288 120
72 401
485 365
407 301
766 45
487 699
477 911
750 480
506 268
518 386
667 937
615 234
912 68
971 827
920 940
880 854
379 9
532 294
516 62
350 27
882 593
554 390
385 423
298 793
309 217
367 954
706 607
286 131
121 491
511 208
529 109
709 668
346 938
75 600
462 891
339 213
434 223
500 785
161 923
456 585
964 727
60 677
861 47
483 1
521 231
914 866
786 91
266 271
88 1020
262 447
559 984
388 490
474 549
776 310
304 464
837 910
844 858
642 787
56 519
182 237
241 488
631 359
471 517
729 922
803 190
899 696
577 16
505 1016
994 758
442 928
185 602
64 626
258 717
382 457
889 680
589 370
380 637
50 451
61 582
557 267
578 240
450 216
528 1022
42 106
123 329
415 640
895 399
816 257
66 481
430 553
1055 522
167 492
840 888
279 963
1033 1066
79 833
102 931
927 1042
881 69
619 245
1057 369
537 96
265 394
164 1074
384 475
561 976
744 958
1043 1030
955 1059
1045 791
340 1065
275 887
778 949
942 360
757 307
594 431
974 1002
611 1079
35 878
704 945
278 804
124 584
919 171
1008 1060
233 692
67 812
638 19
771 501
874 397
247 676
872 296
125 612
653 990
1106 224
418 852
822 468
105 538
873 987
562 943
40 312
601 613
536 1102
941 673
472 410
898 28
243 269
326 1072
886 393
424 848
461 320
543 48
193 330
967 1117
170 525
623 353
1129 1094
313 398
897 817
408 281
824 389
381 302
204 811
794 856
250 710
769 441
948 316
469 10
597 176
319 328
629 913
83 956
290 722
918 773
343 317
482 352
724 1148
1093 535
552 7
1082 574
228 747
497 551
567 820
280 859
211 576
894 1035
297 660
1006 126
1136 396
1064 609
82 564
361 1104
566 1012
70 1070
862 935
731 740
992 725
586 336
23 815
295 138
1143 985
220 845
116 921
853 649
648 1077
1062 433
429 1133
248 1018
160 426
1132 1076
930 467
1028 349
1015 419
1011 748
540 1051
198 425
1081 93
962 1092
652 1142
774 756
85 1024
1135 502
136 693
836 703
1184 371
1195 606
715 579
422 255
127 877
293 5
799 734
1056 1140
679 503
87 20
659 831
633 515
1151 355
440 507
155 178
1157 272
1069 604
618 839
641 1083
1212 514
90 900
1141 142
284 230
504 33
195 214
417 678
1203 548
934 698
568 905
1209 443
646 263
645 813
1134 327
842 975
711 1166
674 643
1107 98
452 46
363 1213
950 437
509 387
76 196
741 1048
473 1115
1188 108
1186 49
1210 414
533 669
122 445
946 1198
632 936
25 222
446 683
141 688
542 1252
712 1084
614 402
1099 1137
344 979
341 797
1068 100
186 348
780 687
569 1109
448 435
489 311
1171 541
412 1080
798 436
828 876
644 129
720 530
603 37
277 608
1075 338
1123 1031
1244 289
264 745
175 716
616 168
1041 571
409 43
117 1100
1267 661
991 466
163 1208
291 1116
575 628
868 1241
588 1047
1153 749
1090 232
1224 782
639 210
1211 1053
952 972
493 478
807 755
342 181
580 1088
1158 996
391 1200
662 1245
1223 743
1202 1113
1130 368
560 152
1205 855
714 1165
587 1286
1155 406
149 925
14 119
1039 555
183 998
1173 1071
539 1121
1300 484
1303 1275
796 1181
523 29
400 520
1131 1277
1263 1312
863 1319
1257 273
896 498
404 752
1230 392
700 1168
411 1183
63 354
1207 625
6 1201
1119 795
860 995
1228 235
1291 850
847 1021
1139 1214
988 875
1009 261
656 1114
664 375
51 322
775 215
1215 1098
1261 180
1017 1232
527 890
1308 1037
823 496
81 1306
21 790
1038 1316
697 36
730 650
670 1295
1233 627
300 1234
395 1324
207 1162
838 1340
449 44
358 357
38 1026
73 1177
78 635
1063 834
159 595
1169 345
362 702
512 599
1311 1305
691 513
1176 439
835 1334
759 721
1366 1023
1285 808
205 1265
647 681
947 383
851 110
1127 1101
770 201
903 1349
1003 238
221 695
825 917
259 1380
1027 135
1191 944
459 1149
596 622
1284 1336
427 1222
694 226
1096 779
169 558
1073 1061
1299 1174
1341 1124
1282 1371
453 1346
1393 92
751 1339
8 1216
1179 251
684 184
968 1164
420 689
1370 1150
1194 1412
53 1118
351 1144
115 671
658 1343
819 95
413 157
1235 97
1351 12
356 772
59 908
762 723
463 1246
1290 283
1248 884
54 470
1259 526
249 162
1276 978
139 1384
999 1373
524 556
1050 977
610 1258
754 732
763 1333
1270 438
1348 1036
206 107
1418 1196
1175 1328
1185 1410
335 1377
1281 713
1413 1161
1005 1376
428 303
1103 1095
1415 244
1420 246
1206 253
960 1268
1338 1287
148 809
1452 479
1054 1288
1441 531
347 546
1296 1315
1313 1225
982 84
104 1058
188 957
1049 323
416 172
1327 1426
454 1409
1122 728
1154 545
1236 140
1325 1467
800 1438
1394 315
933 1353
3 1365
1146 1000
156 1242
189 242
1221 685
939 781
114 132
1283 374
1086 1383
1087 805
1199 1347
821 1405
1190 707
814 869
915 510
624 334
1397 1462
1446 1264
1456 146
270 1323
1025 276
364 1451
1322 1406
331 665
154 1378
476 1386
1390 1204
1359 252
103 460
80 1217
1249 166
1357 1497
1362 965
1499 1145
1440 1360
764 1425
1044 788
34 1374
1352 1465
1501 690
292 864
916 1289
792 1419
1274 377
508 1120
282 112
802 1492
1461 1483
1508 1172
118 1310
18 777
13 1335
1272 378
572 1518
55 332
1156 1510
1478 1110
1231 1411
1434 200
128 1298
1237 1330
1439 1364
1485 1500
986 1490
726 1527
194 403
1254 655
871 1019
1292 959
150 58
229 1219
1301 1437
1318 308
1539 1342
31 1504
1537 753
1552 1493
1443 1468
1554 219
1040 1442
970 951
1474 1238
1326 1350
1414 89
701 187
590 1435
1321 997
1549 57
983 989
455 857
324 465
909 621
1255 1345
1544 1422
981 885
534 133
1506 337
737 742
236 1297
1472 1163
1332 1180
1486 1402
1480 1568
1013 1421
1260 1363
830 1578
849 1304
993 1529
1533 1428
1220 15
1491 1399
865 432
1541 314
1522 1240
1372 1138
1448 736
1229 1256
929 598
77 1594
1556 1595
254 274
1454 1160
1505 1566
1523 1534
137 71
1570 285
651 893
256 1391
1253 1167
1481 1361
1251 1471
1562 1218
1599 1309
1450 209
636 818
1509 1152
1611 1449
1596 494
1476 197
1503 1266
843 1052
1239 1314
735 1589
1513 1588
30 158
1243 1592
1532 1329
1569 1273
1046 1097
1178 1400
74 846
1524 1067
1517 1432
892 1010
1367 1602
1269 1579
617 1455
1535 761
1187 966
165 1507
1395 1029
1444 227
325 1385
145 1280
1591 1575
1387 1614
1034 1453
1557 202
373 1585
239 199
1645 26
980 1565
1531 1159
1279 1494
1519 1622
11 94
1609 143
1358 1447
1647 705
1379 1250
1293 1189
1545 1436
1445 1262
1407 657
1502 1536
1108 1460
1091 1495
1514 1625
801 1007
1014 1606
2 1583
550 1489
1521 1105
1515 1652
1512 1429
1646 405
1337 1663
1001 1632
1475 1543
1671 1417
1590 902
151 1320
1661 1520
1078 1615
1657 1642
134 1473
1247 1430
806 86
1627 1675
1659 1582
1553 1664
1182 1528
4 144
173 663
1560 1551
174 1294
1424 203
1197 1128
287 1369
1546 867
1470 1375
1640 672
1636 1112
1404 1368
1302 1662
1459 1563
1487 926
1593 1685
1623 1587
1577 1576
1648 1125
1620 1580
1573 1688
870 1401
1423 1610
1650 1674
682 1408
1192 1427
1626 1672
1416 1707
1598 592
153 547
1477 1540
1679 1639
1689 1711
1692 1355
1654 1479
1633 1126
372 675
1658 1147
591 1686
1616 1705
563 1655
1496 1597
1331 829
1714 1628
65 1388
1676 1726
1608 421
1227 1344
1709 1728
1737 768
1638 1584
212 765
113 784
1226 1530
1464 1433
973 1170
1712 366
99 1687
1681 1703
1742 1581
1398 1396
1731 573
1665 1637
1572 570
1641 1466
1403 1567
1525 1548
1564 1085
1723 1667
1750 1736
1717 1730
1673 1356
1683 1745
1463 1653
883 1747
1682 1690
1669 41
1613 1389
1484 1457
746 1488
1555 1757
1741 1643
1670 1721
1644 1542
1752 318
1715 1758
1649 1734
1660 1619
1696 1749
1722 1716
565 1733
1729 1746
1678 1771
1684 1630
1755 1629
22 1763
1765 1738
1764 1381
1656 1680
1516 1706
306 1550
544 1779
1724 1431
1634 1774
1766 1382
1618 1740
1605 495
1651 1778
1739 1693
1784 1547
1743 630
1586 1793
1767 1574
1604 1701
1559 1193
1677 1783
1571 1770
1708 1713
1271 1773
1805 1601
1760 1317
1278 1735
1727 1392
1780 1788
1801 1769
1635 1697
1807 1798
1797 130
1511 1787
101 1624
1772 1718
1704 1792
1761 1004
1744 1561
634 1785
1810 1668
1631 1032
904 1823
1607 1818
1751 1794
1789 1826
1782 1775
1698 1700
1796 1732
1813 1828
1809 1666
1804 1825
1469 1354
499 1756
1768 1781
620 1753
1800 1307
1827 1691
1710 1839
1811 1791
1834 1759
1817 1725
1815 1832
1600 1829
1831 1847
1822 1803
1603 1776
1850 1790
1845 1843
1458 1838
1824 1699
1833 1820
1806 1762
1695 1819
1702 1842
1795 1617
1837 1808
1719 1814
1621 1860
1851 1862
1786 1846
1830 1840
1748 1812
1849 1720
1538 1612
1856 1853
1754 1841
1836 1816
1867 1482
52 1869
1857 1852
1111 1858
1870 1498
1802 1859
1777 1526
1875 1558
1868 1799
1880 1879
1866 1854
1882 1855
1874 1848
1883 1821
1881 1863
1694 1876
1871 1886
1844 1884
1089 1878
1864 1835
1887 1873
1861 1888
1877 1890
1892 1893
1889 1865
1894 1885
1896 1895
1872 1897
1899 1898
1900 1891
534919390
857593489
872532819
351517907
936828323
636783889
412438719
798716573
297334007
483548877
100871724
823975638
35418693
190104526
417548200
245062539
350517861
164187056
295432969
451968639
97976971
965932136
31232283
634497408
676741465
901681533
85443352
711701047
960794366
716906580
186897699
101133158
432115262
769214905
22497825
624385130
802343495
851365455
426897034
326363072
84248569
273708424
997262683
449086469
788991077
144509867
583836839
665814235
260446043
789910166
345603580
414514425
321246375
8140865
473216451
949611621
25309537
293016220
324725732
110338694
94974793
286395365
740503449
529886332
853218819
553808218
134677264
800526625
474967514
99902108
927446083
862410772
894547621
375431988
797324590
939610890
198604514
286935643
898039789
989930559
845606954
807569143
548232267
438047924
743569373
257473532
262071347
756866390
840414550
348984171
796087633
809487146
469458870
488597619
562697244
730372664
249281292
577630620
344502377
199975092
177966241
279454596
365195332
859900718
354023224
671433976
312147341
778977485
439109941
384397692
256481098
399678376
473003125
6965703
149874024
665948301
646773468
278841646
7766376
600514289
520116196
202163444
757630024
84395627
85005275
499046186
221703235
198600651
531273714
930718368
350373719
228924835
954366775
973441339
651441748
866668074
901387350
235690274
907500623
108692169
232851614
206800768
11135408
230292057
871698520
352273373
694133218
323075614
388413843
404419180
903965327
35859084
393737798
744083555
947630996
139121639
130004746
266239100
264976550
259770697
935425756
727175312
560673223
117349364
624401910
656628430
940310089
261154510
30188356
69907657
53819289
218558760
233416924
416476150
912679990
665814840
940081974
91130301
633262497
750830073
421716784
428364153
518560601
847938587
469004944
229584515
576565526
506381787
337705545
736732127
248110480
291393748
381025629
752248749
179202033
368930106
318322256
172306260
717242421
639196911
658292948
590510704
43608480
603822787
848320778
857852366
219774439
763206910
468089431
60419690
868923168
886090353
65731279
138195508
736809057
146414937
626175501
23209453
208156208
507962704
151580429
783158811
670394845
685768879
310395605
672915849
286767045
970368648
307967537
794246488
556618939
289824460
398581123
91849294
979130277
262472176
341946929
459368746
228617265
545120950
908995670
957000161
856113684
303003484
904046692
551010158
789960417
221251559
981197546
432047880
544304509
254017787
14899881
859051922
929518631
883493612
557804188
704162501
641771818
575240037
308569499
49486075
616224019
104181066
606512762
2366613
161396140
446973637
735100571
594222625
457424398
875089562
434289932
614238757
82639976
273921125
382186679
456235552
531957237
335617853
805950260
630774060
134003206
657875592
788381058
985589675
887495096
488066855
195483870
609130937
357190566
441944979
201985203
22397952
825978311
732018799
183473008
136519383
960833495
875508194
99011437
660645630
219225399
679257182
489439659
680247377
952703446
749217489
489542782
548664963
966586201
101316513
194185764
334542039
80003922
788991583
615699413
579881311
347888070
405701734
485155887
332364447
245375049
547262810
16183023
35940531
890884622
777072860
347570225
758299981
291374006
118334845
608853177
481276190
119144838
93161802
656495970
51915818
935258002
631412251
942833329
343681248
65742626
926608468
941750572
614882646
299285210
208762914
241482517
393052237
252198748
107309685
347162420
533954296
182418903
389781136
789907817
315305319
218815032
341721356
163670219
902313710
228712728
459385632
253952554
532624154
763487272
309342203
206703081
232755325
967690892
140222728
120764112
736850553
547296423
567790957
502638547
531558954
910075380
272707696
866594844
673074651
982532790
518557118
833668393
754032399
163573216
173655426
123922644
165819082
619796031
786131350
969891981
891359936
153853702
560287374
296982613
927852476
22178099
774327921
61049580
375759342
527212013
14150388
501058009
361872197
526250272
188004552
841573242
930958783
527520316
570821788
817698033
892479609
582108113
658348844
201454276
208858253
815554785
314860857
940956081
193752803
744604816
685636206
323448757
713719818
189124363
498641751
254478067
39788804
554129605
699234537
601410693
912782542
901994420
39745484
911500618
311451990
11280587
500707111
917545818
864974428
180819116
211507935
846171478
835513281
223199065
847729516
49695468
249586903
442612320
546141310
157129177
867984248
278357026
488816354
718525665
708661573
671438360
776219335
606978847
789742272
81085730
186597773
281219964
917092652
243600217
677076321
446646355
699193627
941694627
837928322
268967721
637923684
418490708
9319542
985061228
871087979
720518842
376157264
515450672
533035409
540299528
81182742
562931424
827682203
722297498
106596365
986363631
962770732
415032367
479636103
903436153
314323066
3682177
376834314
897657699
884681500
171657047
835130912
50994619
460800505
79870428
911922575
934770878
365692994
81972936
726563582
395289263
632811155
31403630
261916693
901617481
320939112
907485778
962126222
536081734
807045845
137102038
660427291
607084799
569003531
713871137
4725826
460221418
694776994
433739675
136642714
832407341
582995389
247278939
294083152
387094261
326383045
746602117
232493277
34169976
124702259
916136477
726159210
741561613
968944490
410050321
607589888
747676896
369694119
254676055
948419104
612306643
303021246
394111152
649447381
5219168
747126894
292439275
738668436
108478378
923006222
361508279
18107089
724015382
232240818
630314391
139032659
699027313
542338172
174948540
499102853
505263932
689135454
82160240
671045723
99836450
10067062
699726180
904437230
558050648
377566783
118513284
487782984
295775824
347849662
336785436
958372564
155160902
808462148
828863142
67688814
541932719
628989149
199040175
358484442
300113045
600084005
670994125
491848741
668419803
988941167
320503516
895387185
746410115
710484739
312668017
345877387
526304444
965415559
689623372
50465570
141775292
873468475
231765616
657529526
139007971
716300842
851499363
297250849
818764924
192799352
458360109
181401997
233777008
35698738
119379311
807265677
22671379
757131261
249680700
382085865
723153072
580723240
864600752
886079217
931280142
173855408
467338597
431302606
360657957
596185225
995736516
960443789
362994227
286436348
348688450
974671887
372381081
502084359
597939828
97083790
679462314
969114596
477455129
556879722
563584312
309493904
616455792
699758032
732268278
962233439
668449872
610408360
86381860
954110514
470140205
618731995
471556371
558757524
400172093
611612076
320738270
850756153
462757518
212236649
48534
531540207
778164265
124130151
532608210
196392824
94404049
31169874
229259673
908274221
9579628
970008291
776688477
753142964
52041288
321788979
456554070
565593382
817581828
389789119
116283020
439076152
690199441
563368711
459529153
905348668
461000886
164611000
513028564
501882401
94312534
433187465
619687540
224973824
90423662
207684862
915184111
377651292
321107190
212803725
913848322
189345994
681736465
265032610
178716630
552772285
191532427
742939575
553833306
581896204
42638944
765197741
523387454
838064682
460315747
642517257
377958248
595634312
302065844
353981033
861042310
314593562
342051899
126874842
735839842
529242860
911133154
219384042
194059123
490308013
447807568
760715983
332858446
181667019
117161927
430057617
336648290
380433062
719390646
20991063
779760919
684446816
194390485
353144160
508871995
751688369
806738875
466230669
769508376
866463707
519576218
162977169
930172780
667239519
311084341
727486516
743647629
858088259
518108076
811150562
921293574
245337027
472490558
958703329
469698953
213111125
836046630
870665322
855551870
336874539
62870967
396482434
890377438
395676929
226180096
50593095
924384289
724254897
787916211
35019714
456618686
694617191
949338326
771415990
732046423
153290789
239704719
481077278
114359279
347896232
802866216
213444443
476290778
207993365
888634858
607012069
113620439
270002774
687407253
920593615
511281701
948310664
103104520
908857044
660459397
54554465
385141428
105126173
418332839
692461605
584940959
19328110
158207544
739284905
189783685
828769221
781375668
938474725
856458647
873243499
713301486
974888000
213719702
969265856
64926332
207774576
481045926
170967102
25569657
79330919
749953547
122780477
201690944
316513397
508348232
658020635
780397064
341226945
807735367
484043682
77979897
113530050
216200304
478500209
28193944
910637114
24164461
900238320
65317945
764188091
648952426
935868901
850167407
334967698
853029169
427766330
802886074
879019274
480004218
829306613
767518811
960557399
58412302
965255146
956822877
699198373
316644038
402379871
918877271
129653850
102157159
954620864
429841574
195494008
629486859
842079085
404181889
295759297
873844833
646069156
803003998
661620802
671297593
352303343
735543637
821928466
551703400
979166432
378210105
275299035
384550443
905434875
610555953
590422623
509914147
164300791
273520838
879440685
690080494
199820546
766379046
881958800
560874945
772186350
987349191
641675527
928651745
352853627
815410811
245046652
23841136
898885505
619357147
692942321
468006311
367813438
923832058
408950677
27669266
138367075
299415425
475059092
776045430
824328206
343041995
110146412
210225927
139071795
749498783
373982198
348015464
944416037
70838771
693851436
500024423
399876182
816867588
586466382
294928027
333114899
241530543
244317078
625730028
114071003
563188690
122247175
544005788
876398915
739175637
337640969
972593720
560463100
282147022
647378360
513513983
81215311
85005816
717847250
391980747
114295547
167232555
118364764
838888003
654472957
700608172
208493143
511247563
516241224
531565038
811122738
426855507
757299493
551895062
73307461
507718317
746471416
597454394
718835237
844681558
279422255
720653363
305752578
537996122
347674318
896004566
821051215
456197639
25956073
32187950
854331501
817824986
641168628
750096208
634793193
211395571
829474777
626712479
128593894
904412986
53020042
683465955
585666706
369914173
31238130
47217882
856001359
402753878
196360914
234035147
466172720
210764591
199158121
964519736
845901336
810034335
650875241
393747845
127514786
891911249
966875965
268899050
832985974
250767434
302683430
164019806
539476765
813133422
835462159
444818176
405078559
227718746
76223750
462910501
991799317
904567236
625838366
395896477
245507401
965598943
696464998
564491509
557264060
453058043
161678690
590210945
349776046
741703248
156769656
5049487
303132692
847685605
586044010
468961856
33955339
931565657
50348470
820065848
487535584
974751713
790081788
108526653
632194291
367286237
847109456
338786440
638147256
527759259
224815793
971715261
861746883
226167904
232479476
627430506
793282745
870121310
914622155
454466450
829092471
60038182
923657976
869518937
225452724
11889307
594962749
265277617
611967936
290616095
684031414
309664216
812034611
149860591
852036424
591801147
123447400
652879049
190746311
229175420
39183711
942564902
954898228
77126955
495603422
466684159
641401882
981834005
799545450
857083046
629631975
179975934
339307158
665575826
793590418
259029157
91572957
127435316
447017402
324462182
641524011
909476044
212667773
896658308
899805099
649414382
686854368
472825951
718969427
86735796
793462119
633725285
666863024
252985724
639291401
488959022
101730066
193484686
805466301
413597739
96405859
802632969
841151485
3505440
945696646
698059121
842297457
805047250
232080002
94262788
344418288
216938470
521278312
895586295
500136532
989211610
814237699
273351837
960178337
327556005
109374786
552374429
128188172
667262428
994280907
194842614
213314132
851430415
509202647
401887022
265663868
790795179
53823359
724701157
362471064
303591436
304564858
6171030
640567829
127100548
319156719
144956315
902729760
985655851
209202948
622302029
740740460
553173130
910872709
547013735
32160263
27254149
165806145
797697347
858375606
375346947
517936134
289024494
65665237
939952455
533945226
88362483
720993764
557004214
333018541
695129146
429160074
899951021
26217054
773290464
157371189
487902774
9206360
245194233
617050069
453322403
593585561
104910831
905547501
521122468
969146936
278506336
721127348
649539463
337694919
169245422
802693753
715668162
143916081
15672117
989459833
946370873
305713204
311728003
956328512
211215726
109088533
993866379
127868587
140695181
501341742
358723554
887189680
874547691
603343459
455345154
959072154
982101835
181729198
246670493
94445838
822913097
645901148
784884322
224966818
704375958
461482957
737630951
485839702
73856873
545951383
165379299
167787743
627248552
565722754
783819810
57015828
714161010
196273281
304507555
371479899
360409585
868495503
14719463
192083003
636567348
898317225
384313431
133427934
127966351
95175909
72775149
407536123
305788297
474467303
850059281
706367804
652643651
612500493
842946708
190454214
208249143
331919238
888310652
633675106
60912086
833400474
787390008
50837139
104170745
660379424
827448404
164620790
141464326
517633780
332339479
270397080
668280281
455600721
209742347
670315896
137715201
234388765
95436228
195510782
810958319
301326716
613318239
75024843
978237069
959319421
790888803
580850762
177673194
932348656
150865035
676024245
741072378
982737498
819625108
963566166
474285800
950045748
897865505
568327339
693912558
752588275
291624664
937177902
797301295
445614591
76006487
888940572
916061695
347690646
245333049
809454323
54039548
103383523
381338249
837283571
565688496
519889518
162870027
562232641
902223731
99989189
964370159
685952280
235921537
694284054
729219262
527546006
161534942
571751360
926573426
522368524
162142349
640715954
424329990
691941322
890218902
347923121
729325460
147325575
164519236
210500423
98362785
897265083
86986684
245743865
686353043
782793895
622228232
47752389
750230749
863381668
798259488
862380721
668094690
779202445
360541650
140210925
142951326
285087516
405864517
46334043
253281027
909208777
736559878
896499301
248542252
495037291
83905603
576940928
196075104
877711343
482628217
459854867
131532816
64142524
880920143
919869433
888500424
403833543
528831792
587486433
46941808
654993149
2269528
419650735
172128678
874190326
933221668
210130875
225185842
672155158
372201622
28433981
52295748
793786343
489717550
217981255
8376650
103793245
712839322
570645451
423178871
98064979
649720993
996047581
897593749
746297247
475262152
259616330
475321111
966997159
520105288
545332993
886802420
801631870
988708763
665902494
105138628
849948565
540138882
16013803
727235010
736389888
88173927
993007211
825601132
25800980
351963591
771790261
393798245
555598346
720828099
72788733
392692110
287319849
510708308
977832906
347455211
619586273
622602295
296100094
646485224
260359144
596962982
579544817
361488215
444622753
687252153
79209105
317497293
22631923
455397026
636464962
437002560
125394030
784888653
865025529
723290756
41278799
537324497
152042261
578459768
346423793
979878181
851862733
204995863
659941410
131531760
520707733
176493226
526072138
930642045
756196236
679665715
221586016
638343432
445429551
376876256
141372016
558974224
856968406
935894659
216396401
981972196
708265263
737070326
125521551
607133803
28241155
159106216
779442138
285020864
490289556
503020047
610763331
883935657
639026408
672030198
761724624
137708338
642548948
160278165
771420646
756852748
845266586
16649799
738904385
249280762
40831332
342395206
367053159
961926456
719952808
140875701
864208850
730103073
157253188
237394420
168239274
638648561
240743620
675247459
819718428
504479083
218959419
313489649
130303915
816578124
487110721
687604391
856181667
22706214
103151797
154359176
342497970
647901252
3782748
501921142
569788962
606345228
581356362
719459895
467334649
179909728
171212783
532445417
358264645
331022843
487089153
852152449
594939550
259790394
949114949
163272328
207327423
668819228
506736676
631390575
46755108
557310981
478898138
352704699
571665453
112615717
251539983
263247496
517654239
160092722
410487787
469139933
25923231
575774803
393483108
493415091
599070231
573408187
26171755
262530644
116219814
253276953
573991390
244731405
950290570
789210500
918681182
167013327
956200404
420043195
356781590
357653165
832749634
224443083
281839175
117272673
493656599
895349958
530225045
883760221
898172053
547435992
895953460
54822736
531214841
164628636
205201050
680968213
424754237
260627372
297975501
366784358
500880085
2491764
904923846
996989078
832284101
94514291
926809273
3771152
943215982
44705206
517290229
247961046
773524461
768743853
867520611
704275183
676103796
870552324
32944901
584159786
199013131
806864369
373639295
163788544
697747102
265424967
785626649
888660665
712188575
955523746
500067034
559019655
796969583
154974603
232914429
538372304
327909235
446064971
659627213
628480040
133490660
348144471
311443408
374168581
225363986
149154673
296569538
15367456
339183720
364396068
517888420
231357730
203633601
483979821
348250219
97270741
32598918
185320415
199073502
162960240
412336153
38498355
283434302
294118901
542863681
250977193
99593343
515711161
359259807
68677871
8877557
246746787
103604157
654516055
782480491
564308693
254826203
389045715
816774968
24391896
34024710
657419113
366623014
100634353
44965130
639111507
292049653
666993133
129819744
411771402
566847016
116809752
541172880
911156693
756171148
185130388
283593138
420114191
958890379
336525136
964097178
377669889
125351426
536058813
447479293
73765274
823302268
583426356
84350897
582405510
203578833
611429199
522272793
173754369
955650682
969728264
152351326
86511554
399929435
212283169
879114448
331344914
355107897
814987229
311930475
976909883
934809262
898261091
178030058
718708171
444214316
918770531
469908121
234311368
427872824
865188222
588253564
936747318
44803237
330905851
292678955
764287209
238748073
490496191
875850373
66223631
493907917
158872531
552972414
668511639
27417930
783837859
979730415
217195439
364345748
673815601
996056412
370085072
619838702
655415357
223762839
190650016
646975738
403991977
705101158
451356880
668735831
365952202
758501327
976971245
569605303
341659495
330282497
30785340
521424523
116233309
727069420
153117532
405570363
31544157
356152454
987754816
576290900
126514932
947888465
359350901
127481609
644239353
97778939
797342125
478227485
819581497
547208420
642345497
640244906
787748276
341839873
210919288
220070452
7799085
241652225
461572995
37492213
741674171
282876187
190413127
822841197
402475981
18293680
464440252
142323223
520194444
967661020
975648683
218651701
856225766
207153984
135767828
310593529
303049900
644345654
642525478
789359411
909996254
474704809
585229824
465970062
534247808
354190717
131643440
739104519
319934257
263728997
721148417
461324384
496027651
153007738
862027416
740182749
632157829
340726876
224883756
373628035
258651505
108617982
438291881
938510012