805 149
851963563 676261954 425884809 300457521 218620700 529872240 137355253 162205843 449687536 873559742 359892680 682590556 759684878 503925942 648455248 808566625 49055245 398946260 717115788 595560998 938415845 383114032 499439046 995636388 463334305 720505432 266093928 43017258 330140105 883864073 704591003 81457733 896474021 715130398 323620783 732524901 345019380 166179974 74104488 69324953 570122681 434509665 641167165 367695819 7258743 365143419 565299957 989692326 349171989 408158040 369058961 507854433 851128382 897876116 727619319 692685595 882020654 386570211 453875216 147777362 55029445 586299945 244640240 159040184 813811600 698952836 893285088 129695345 659747791 414738275 556466082 614940286 997399609 210331917 615364790 212455621 41346651 602676687 893792710 736948596 560599989 833860063 739004655 825711628 507298797 924111218 421476629 394251781 699644678 814161868 444257554 380328884 784902550 459192757 489539230 57463098 557024049 447444709 19852418 133687046 160357943 869528902 870230848 693539376 467539954 991425315 842808759 803790793 768856369 210033705 550775098 440602482 135174398 328855466 293033788 869106363 701147611 339924268 379721534 151260236 228437984 143315526 563118271 494160955 296080092 160600403 778651774 78999112 64617506 709343931 590650640 164797703 182956650 373754337 508570988 734503302 480088310 741783226 80965491 612127472 956775009 3819919 51880259 868118175 903376169 895571780 832573022 844822034 579464094 641025158 174196628 661120472 340402822 397261387 788231340 728172557 737618647 857686115 983005571 958048068 527084645 987543188 735378823 737643342 141008960 162326055 49116375 800192229 788416046 554618223 305953969 277825070 93868677 364942464 794835071 529771233 217164232 671294818 994674048 849895996 149983070 872412671 297782276 776090953 31715863 845251216 28455407 984993690 437744130 689285905 812093862 530696235 360544604 460437586 984197347 138537538 87696534 423347509 135740425 144823220 544659735 307621476 200233118 411987533 310280384 711880030 819477707 350476295 213665521 703359894 405297556 468299271 784342075 626650052 17297653 588527795 862862161 681222874 663256516 398262455 662061839 459171589 578870485 234170401 185165463 209581624 488148556 247410583 476070084 101319815 735026169 933817742 220725672 400322829 722230895 114393611 902139631 577473394 116223634 889696595 345943781 684859808 190540287 416524832 929226255 981563995 769243353 629610230 752072941 160444942 71060207 39518484 741435852 998645485 61189598 424451791 873992898 674057887 175395648 771830084 749992159 540034164 417560085 176750864 305322971 671225081 252108673 699796868 936641322 449767070 33197756 198126469 99665603 131875291 582473174 671198082 71164991 556827661 702479288 956396664 56395441 705146466 591996082 639191610 292126021 337472163 129876974 304168672 515143812 303008158 124729822 186242945 867996655 164505422 297371197 10940660 672108263 343564040 755319872 587616383 687678343 460902474 287732783 157983228 504481427 780187166 20591900 546841775 125908921 169131249 616958492 463498033 586464760 829236206 698238580 248203575 946547780 658266074 65643476 834426383 628187482 44039144 421289580 160592557 359058927 135542677 741606738 456107141 431525978 512340865 742295779 916395158 763975431 265752017 570322135 79665747 405660731 222824180 143517604 19446284 501587874 190335744 178124408 351932780 230071540 46797304 202887414 753715632 814031193 282344489 954426662 375517307 90783138 412193225 323759976 832656185 681170001 283883222 334129100 704033430 245147421 379369879 764413911 338739144 871572741 88963359 289207739 467935266 966957731 197765172 867558617 488352315 4395623 711578349 567933988 773907338 623568695 359386074 952207517 159229481 880360848 784978799 875215522 395214656 605361605 94113253 790469065 238667564 546020267 333350690 623089537 244762598 208645381 453668040 688690170 763821729 957862916 167486941 663730601 150088186 740253919 475801883 213797189 488261585 593695765 377926059 196898758 945718907 992108072 793563860 266669732 723923272 595721935 424844726 34541623 206444416 677952715 984561047 409839052 917131795 144641072 242345180 171750176 28193958 25954252 276946542 364155539 39598994 280143171 820033580 980823863 522296280 556239408 36727393 473370469 202825469 66713741 558446547 854523298 857451276 298121416 841797258 366529922 833097002 142323124 101252482 349174723 644160722 140898963 53484639 959354676 359181405 407879834 346421694 889628484 966560536 28212719 614410593 761101644 550614736 457826060 222631683 813895173 521679073 217709021 877645193 554049674 899959616 713526356 504879097 610973568 889509636 957931929 783472167 887413472 942873368 927998402 310654019 530353272 184466054 229277222 934199653 266949985 830256710 10000400 860581335 961999774 521588320 210755812 832950731 869750947 170153597 897596172 828039869 678883493 362438783 14087474 716676213 280609038 785305838 934199836 113685680 476589927 413668799 248965470 543491361 210612078 869039511 285942947 336600650 812807269 343076662 281684681 482191643 154129914 567033009 863696137 113121777 754835028 993155507 498018265 688175937 861280437 702492207 685636840 735373470 269930970 233523598 90642316 297054251 385358022 939596399 520753435 326914724 421723940 909027723 608605895 144698831 82222193 689843507 230229573 581419622 48733741 416899965 120031517 868810640 316493284 549544852 266723142 360546995 970763492 332105383 690104816 624950366 43897907 635646504 284447216 986740071 91513248 38342453 164469961 91456565 283412464 597413702 141861844 412012238 975935977 107304697 110625916 107357052 242490919 777025480 387608864 675997258 248451843 245301556 174655067 465637638 672888257 431673607 881082693 780879311 60617447 600041451 916563738 67446173 847230208 385079880 316694985 478178826 682545820 272639523 993801201 808082030 583502378 765024571 490303306 904738045 799575409 660676130 109676147 290387228 809496706 104673728 647088693 384988170 415803384 891931399 207340392 333959529 673627803 238124817 762828257 460578572 561738975 135256800 795142297 569793336 961231667 408910510 401202324 238747396 346073459 664708841 656190662 580872714 722944675 818715428 656925112 18260455 485942827 107635343 945110704 89143951 560990552 319818969 324019593 595998150 956456311 424992937 270448304 458111209 877119966 549624340 200199 603194321 360555003 485167905 766078931 615459443 486651798 669752941 37965370 702956541 464908409 273715537 445563155 69863224 738941922 276781653 573405355 231289130 320786804 268955105 10841690 51847766 350992740 95693787 302129673 541870612 528362478 976002908 967925479 292775232 663000935 44521533 667281170 102500908 825341497 157646204 969191816 372013179 422920750 736661795 845982996 477302512 112348194 479514085 801903347 590500132 491493808 676220896 360633477 299463771 673291904 841592316 886038819 573372499 545592533 145626409 70141588 964489725 700617231 133380050 10485627 923752309 325208457 439619559 655687058 610051762 836466271 863954441 532839543 890779858 252161412 211997778 974556700 684269447 765801348 234932881 503454886 444539085 631113059 116068768 391182872 232690689 289719734 986720762 543947416 168668454 345247298 408091891 54943427 197815409 752668671 853483673 806992765 619286126 623986574 309882078 509342636 480503795 488717162 427003045 449737190 246320574 339074650 102294953 868680012 797511272 857803472 199289175 916403360 175073079 386760314 865324452 837419026 422891110 700515269 396415792 342790696 702199835 548062319 38252237 663106465 170736623 751323443 210422706 507152552 548589516 152603412 117515200 595055116 126013360 838869460 121646348 185277092 317409854 264134250 561505188 624192337 862721714 247049940 308745610 677055075 408853362 423929000 256808599 124572557 481269328 194524281 690774009 445889150 856133806 165340127 977865525 758120697 465419172 324787042 641890778 421571485 535516053 904877951 51238603 103894075
query 366 371
update 53 119502532
query 336 412
update 259 827024614
query 123 283
update 426 376990205
update 660 749469790
update 283 663351419
update 501 195697903
update 44 3222385
query 790 800
update 359 78750375
update 612 623263079
update 534 883302164
update 265 444041628
update 651 634121909
update 82 525350867
query 112 512
query 224 456
update 752 981016829
update 586 658464834
query 738 783
update 479 780224016
query 97 183
update 171 971560365
query 629 749
query 353 602
query 59 710
query 691 792
update 113 215363000
update 177 356091578
update 721 241272401
update 270 532323254
update 266 712643491
update 63 460710564
update 572 345023706
update 402 586828645
query 357 678
update 450 879412795
update 175 249429242
query 405 761
query 14 137
query 596 705
query 169 597
update 87 423380160
update 51 34784845
query 75 450
update 699 463985238
query 134 498
update 100 708975385
query 520 569
update 307 859623175
query 532 789
update 380 302752233
query 274 330
query 504 513
update 617 246671838
query 253 676
query 705 722
query 734 751
update 654 187412514
query 518 592
update 445 957833577
update 33 628851766
query 64 518
update 757 395472154
update 195 111933174
query 419 805
query 417 444
query 116 209
query 640 794
query 452 469
query 380 701
update 144 995628276
update 138 283879
query 72 119
update 46 23412685
update 614 196794102
update 652 591749474
query 777 785
query 757 769
update 406 757770275
update 713 592341323
query 691 726
query 390 750
query 48 637
update 671 361371701
query 386 403
query 57 86
update 123 827112697
query 386 723
query 29 643
query 249 385
update 359 690348624
update 266 967931168
query 488 511
update 777 109964449
update 560 629491406
update 4 917731188
update 573 43911467
update 577 234167660
update 256 275275207
query 493 516
query 70 357
update 614 801936268
update 786 197427098
update 278 387664537
update 546 549006927
query 273 751
query 251 371
update 133 637012872
query 496 562
query 23 766
query 769 784
query 157 762
update 72 121124747
update 730 828672684
update 6 16694060
query 698 766
query 212 622
update 11 914667185
query 255 584
query 355 536
update 149 94522539
query 677 793
update 796 130538453
update 658 127910713
update 791 653347646
update 463 808017671
query 110 226
update 725 151531332
query 541 693
query 700 754
query 106 221
update 368 65540275
update 4 494004104
query 792 799
update 183 654056119
update 257 128190534
update 132 559960659
update 630 141417469
query 461 633
update 428 897877857
query 453 473
update 121 975064235
query 218 535
query 781 794
update 352 363125007
update 189 242934610