1000 1000
793081902 187122875 86019153 225815809 537496882 466331181 577398051 248422530 599232558 89281511 990618783 37741201 80528739 423433893 676312939 673234843 923627196 491780012 63114879 98320145 503465120 810987986 583896952 205731213 193456270 896886277 383791171 949681915 242469136 734853505 490712354 688162428 768390909 357112150 257850320 142236756 717799882 666974368 81954927 558165350 117609269 423981211 283248712 360015181 904117005 324017547 182551772 988279549 270445331 457582598 558827916 834039489 767423154 18102887 61728178 725995043 640458357 19735610 11521212 571500932 834875878 351949197 769281487 411419737 202013567 738706332 977080555 471552568 375017639 213079802 317760820 60840200 671549807 480604004 364108689 588588652 439000896 589045490 56039864 363438109 76667157 353893917 617320557 236597627 172549494 209959669 98326398 13001433 360595291 769715747 258648256 469418137 255771625 244052428 884508390 439019584 288092831 779499110 889503516 969460967 877559213 463443122 163315665 491154852 34949666 108656942 516218140 496491119 918828471 150986491 673019534 468450849 752055799 690307370 243370634 440539840 379828791 843779873 949270967 356131641 861065690 555365798 512739105 416220974 213197736 566131062 189352065 850307831 870808700 857066322 996160300 153266768 337668147 871167357 779961044 192808114 547831323 444476202 100282644 726954163 288102691 86730253 88629106 834224762 464959201 504946406 106963181 187481060 403258327 221730709 687326643 47724719 897872937 421803448 973303273 854297505 904014801 551170424 178858906 581407719 535978322 751773378 257179613 997937086 818606837 887033517 368550779 375518632 560507630 124175039 240955331 540095840 556077560 609707259 470421450 599594596 696179870 885838100 732765736 510705981 190513290 208847282 305966269 702622820 652179988 172193531 694645593 457677466 730617361 507617544 190878645 18164941 293487735 450288518 973655330 621846601 540688133 719565469 189709545 786215691 886290454 891371706 840909500 864814373 390653882 502978768 945507150 527589724 417233720 983026549 581286183 357337680 970647007 350106676 745960042 688949421 642853556 56458132 519670748 18012320 51058864 273648169 51960338 636961929 466788617 785340459 271658348 50843586 377605847 740176554 696568180 22182856 830595227 564073623 410299809 401258271 706197621 899681375 337033317 921579039 986051282 810677624 223097356 528794800 252306521 537653660 359767664 809270401 922954524 952809137 513772823 634511848 852220780 315481960 35136368 577664174 540523901 500498681 833452816 720165741 410182106 65762881 229952222 881802748 646146532 36310516 132693401 12517957 944659188 582760482 31033620 708884308 869772436 748465180 828610916 186546211 985647120 836711893 742373647 194324763 433879852 367224326 33234474 176234452 444497456 193508679 786002493 629724015 535991435 841979785 303255724 269997140 330194871 464727913 891746050 889125692 91907925 317077561 280272308 504030429 257322107 436412090 713618661 144888229 224018258 208604532 998998268 840976194 421154799 846351555 838357281 711796646 317385757 77499310 86665245 156545826 235307977 360802137 532239163 410232479 752075607 324583124 819343290 622103275 410640959 383959517 993902330 922938864 12529625 969555539 181903986 771877225 858575660 868863460 18680419 384049090 811619580 33491276 264825184 93917167 619304537 275978943 857418035 313600788 89513715 307033796 113407573 394758034 125932168 85236019 199828842 776680984 926817762 225459025 718455283 897811197 707458001 192268374 98263084 843217050 517630549 97478556 202717011 887115921 475781136 139081482 389843549 131406412 414008704 987428857 983367687 868796684 114520255 512193860 997651718 281055242 447696113 255525659 835425766 374133662 834848931 254585051 420633253 940645960 412149032 7464940 943703094 328587083 596186436 673921296 579152207 827805555 480374068 231880933 144149220 168481902 992513384 374054668 710810141 191960699 479955367 926887619 822608533 486464944 466324456 819625380 112922158 731389555 840898279 134730800 933264719 337964822 134753328 11471278 166999672 176292893 440805398 367701913 256920114 462217405 3032664 737449188 493419691 65673951 248409223 229376383 790052704 282694003 202054144 804359260 487872616 530516915 602494203 290148115 47984134 55375716 725328336 118209698 99198324 454405031 345309305 630484057 111327387 267892915 735838593 961184247 919314187 629515746 417437215 215449376 849011089 378783245 907732053 863612887 453340347 765650689 921388055 967842586 344792177 522752058 842705015 901099105 164884821 499030000 764619624 412361455 490347017 225104186 636367738 880965223 769871226 188151582 253322639 247019144 990891063 768591260 454465902 287294565 196567684 761847655 735445186 657204835 788684099 704959691 177683078 698396911 567884743 725041141 176855860 818209248 616983241 423455081 924860707 405554711 275820075 99888927 715297495 649857201 227595921 55558481 470426527 319580631 692220125 286765379 911029576 223403689 964871023 992659994 427556632 432157468 153010999 196172232 188052959 297720809 639439026 807145482 134976912 188110168 602452014 372335081 168411740 299148391 506833077 193214931 509779592 70586163 70201463 335790381 267009815 129779106 621369201 461852916 132168924 783058625 555487181 516398978 404966173 381595543 748469669 494127117 51856932 277839324 874491646 168774562 911623483 634589139 857236606 464769022 50293353 906152824 204336109 810759294 846188470 719334024 963403065 765593443 239343158 459433018 791692229 307108867 767207139 147514601 514105591 81941858 265872059 319024262 789026936 351133060 400178032 321685796 651290374 789917383 938908998 213128924 948082530 244237850 227941577 942281075 570874353 194404502 430258777 137383839 622635112 491609050 801400594 810329736 164395245 582004724 390679047 902358160 47206162 559955291 842707381 360407526 524397142 699263896 734397326 291409854 321490011 59064458 766026360 395695230 300677129 848497951 239638240 343184788 127209367 75803723 20706750 732074388 926638514 310107618 684882322 808088216 475099263 482313571 527089356 599861008 321420164 885190028 95827712 910246463 338882910 263116522 515040191 164138643 375872990 13800901 979029208 853829913 469857847 867104278 604029656 902555835 880627769 624880229 168660739 457513779 677575334 759352104 810196174 365577969 975965444 925060451 207554392 936290936 922269202 992233944 888617153 552351793 334219265 960003408 699828133 52703652 480109163 380770523 704223330 615963165 62359454 631500313 397564028 692640480 609066241 855055585 327864196 880866343 510657456 85603847 563703744 872007174 804300333 354677883 969096649 870606471 909717743 151416692 973011254 727052164 183481148 799715847 267736743 410970459 891570331 497936729 452419248 112078190 315902816 127335606 873478386 815199376 852241922 222633621 957640464 546110457 159566680 805043105 358035660 863633066 514147934 76048508 227774226 679041782 575662369 296422628 170925562 555439502 183251390 142056866 683989331 404799519 340359057 614112439 401178121 583724786 512693635 827303230 511020930 982397197 823993033 858488472 196790898 946015994 891417657 714229852 833324696 364401689 414190207 427595766 517118822 839115405 187822754 892353384 517965821 737835641 959926686 320162531 299918035 909456149 138593708 243859650 696184957 966059742 905436014 716593286 808439483 262530309 952445543 341560494 804987359 7835355 395950325 499724163 646911511 938723136 349939108 749876602 455063391 50919056 250882668 189774983 957050276 483597135 294507106 131678807 766231048 810010941 478917728 292540031 768809341 606620354 228639664 927620484 726774363 735223739 734968143 214521998 280458405 492800001 4835069 217674738 410027267 534458277 189378157 509641598 105137707 562023477 403786853 402720485 641330293 640842303 93677864 903281778 45923949 577594626 473083414 254993708 535209871 351575007 294151461 608186486 936194348 598307555 888467047 413554751 190322287 257584521 110245341 181632754 840798028 480166149 502406493 381857541 570276905 612829357 537763027 719129984 295570389 962244170 86139020 210381745 544867560 159311736 908525828 906926166 127482101 626370761 868228482 560349700 100830918 308394019 692837920 592840303 851353549 818589811 209121466 635788517 145717857 25417298 563990699 510813407 598905128 450507927 166630496 955698 154990318 457088386 457532163 247935989 445659638 871481835 478176726 768496532 211801408 830766280 771271574 795976211 276762873 28082264 350233491 341595533 395590365 390546050 488332802 395855108 643236091 449280136 126109520 480653339 26032351 819383004 477481239 811632351 271194871 307322270 104907584 700402414 948887063 72754361 255262542 671669302 738354305 134035931 449170418 818551317 812476732 290945963 236092700 497976551 318241331 967433235 26236920 236607677 87096839 282457701 155668191 511251994 565553869 959253594 86667680 957890508 95921464 798000686 135273106 914960877 572337272 287185051 174393841 886421364 737973698 656620806 958947424 51893208 159913215 267946234 799090722 409088657 812305047 487434208 853259328 599915545 436063710 670933693 170326073 787926407 38361288 725687734 416536812 799240696 433501697 429291590 117202242 753149631 868462308 543075456 253275273 204730498 138990051 696870302 886078354 234894314 264960607 534018305 380956524 527286908 679045157 344466071 949851060 20099825 899090886 3074901 246666338 713534576 671849586 575722572 672813667 897172155 141283420 353726182 477696663 93142510 77233904 757805160 716325477 100428324 651550244 149026213 8435071 771040029 295421052 721220377 305990460 323109307 794190641 785891339 864359524 695657550 15338225 101079342 574062766 106582620 404632639 940899802 451457418 117223313 255785301 711138438 469765824 797252722 497495564 787151430 708688348 122014686 945453861 25309580 611824828 328877058 905199549 765664186 730111528 952951796
query 66 918
query 966 970
update 241 669072217
query 418 951
query 948 959
update 804 552687082
update 10 255115669
update 711 418717544
query 535 984
update 707 973725662
update 936 7328297
query 170 243
query 289 635
query 487 847
update 34 950302509
update 390 205439848
query 810 893
query 750 952
update 942 789427560
query 326 857
update 255 752417938
query 104 676
query 292 880
update 503 735924140
update 882 903156227
query 2 737
update 598 636830063
query 124 140
query 864 867
query 70 958
query 346 680
query 558 734
update 855 398842694
query 46 510
query 40 244
query 217 357
update 421 522862499
update 397 526089948
query 476 885
query 8 61
update 879 642585031
update 144 795014269
query 936 945
update 636 306031081
query 338 689
query 135 595
query 653 994
query 432 696
query 836 837
update 97 80798175
update 388 117305114
query 520 816
update 100 58508325
update 136 39490246
query 743 918
query 592 793
query 720 820
query 335 755
query 828 832
query 556 623
update 148 745497027
update 974 453027250
query 25 388
update 757 545508223
update 585 210911592
query 942 990
update 447 811707341
query 902 983
update 9 707974542
update 898 788161377
query 598 832
update 284 739800407
update 595 954453828
update 345 892998715
update 117 190018158
update 370 578144953
update 119 961198948
update 243 236094456
update 994 733490833
update 516 284114730
update 683 455630558
query 586 607
query 669 908
update 994 116188810
query 95 578
update 883 615759621
update 32 958244677
query 843 995
query 31 785
update 497 578955996
query 128 987
update 710 656927982
update 192 270309211
query 158 865
query 406 893
query 12 726
query 38 867
query 305 570
update 999 617681440
update 267 54678890
query 280 469
update 659 184186491
query 612 962
update 603 996023458
query 10 71
query 106 628
update 400 33343219
update 174 116455758
update 800 884535919
query 557 861
query 60 723
query 134 216
query 818 899
query 405 817
query 633 738
update 992 485316009
update 629 388847502
query 82 271
query 694 931
update 456 779073232
update 759 616946676
query 338 379
query 349 389
query 942 995
query 755 974
query 726 750
update 724 342598227
update 657 796658344
query 54 399
update 926 853123025
update 292 849753346
update 93 5770692
query 436 611
update 795 158552797
query 242 536
query 775 933
query 848 875
update 756 340619370
query 957 979
update 440 738112373
query 587 749
query 870 909
update 936 807783202
update 311 32584892
update 97 128934244
update 577 586903379
query 249 371
query 594 859
query 752 830
update 268 209662698
query 656 688
update 877 461207713
update 24 317854475
query 403 799
update 917 843889700
query 33 840
query 69 339
query 492 733
query 92 195
query 504 538
update 715 449119305
update 409 679617844
query 47 194
query 306 769
query 25 29
query 503 844
query 498 662
query 155 769
query 192 253
update 95 559690831
query 288 470
query 151 276
update 778 840438190
update 782 678478558
query 557 592
update 504 767036900
query 50 743
query 631 936
update 881 440904470
update 301 879558263
query 794 856
query 120 734
update 839 133302885
query 122 169
query 923 983
query 511 915
query 145 325
query 33 249
update 849 636309487
query 1000 1000
query 858 897
query 894 961
update 446 208814401
update 734 873673288
update 105 512844648
query 39 959
query 959 962
query 21 587
query 490 551
query 485 942
update 327 130330357
query 923 940
query 760 770
update 207 616717050
update 812 745454317
query 784 850
update 447 583115650
query 530 595
update 560 22159638
update 522 840042370
update 881 892930875
update 344 727164258
query 968 998
update 80 486819624
query 960 964
update 592 637071723
update 143 723793448
query 578 960
query 359 690
query 622 754
update 761 847236372
update 754 821456055
query 804 945
update 433 74573606
update 737 585639039
update 787 702101156
query 235 470
query 788 888
update 755 525565071
update 494 674690648
query 313 936
query 826 876
query 332 743
query 944 951
update 454 505756151
query 963 994
update 554 992200682
update 94 563555583
update 723 634955262
query 331 648
update 947 240081787
query 135 160
update 644 727026840
query 803 826
query 72 815
query 95 282
query 887 928
query 662 724
update 283 101700237
query 412 594
update 669 656118164
query 936 980
update 853 819982555
update 168 991956674
update 152 361392935
query 585 785
update 324 531032115
update 797 477595226
update 889 134513750
query 127 742
query 498 881
update 872 999737279
query 191 984
query 629 741
query 520 549
update 94 456592334
query 693 721
update 465 659842720
update 814 331116802
update 266 455939831
update 646 701090948
query 200 847
query 167 889
query 550 914
update 920 232707583
query 147 621
query 800 977
query 410 469
query 428 513
update 453 274324054
query 646 949
query 448 813
query 513 917
update 560 745379574
query 314 795
update 487 374644263
update 265 807212291
query 578 887
update 346 583490019
update 387 51716660
update 337 350147051
update 383 361930795
update 692 434945469
query 597 806
query 377 671
query 798 810
update 730 694189550
query 332 416
query 927 969
update 409 170176364
update 462 827837372
query 485 659
update 143 46707342
update 838 892556422
update 390 323103911
query 578 873
query 711 807
query 142 571
update 202 920465428
query 625 871
query 873 979
update 747 18637726
update 317 934842285
query 553 903
query 768 970
query 605 920
query 9 223
query 113 122
update 947 501441534
update 762 209399534
query 195 772
update 579 422551501
update 628 338061759
query 910 949
update 736 690377382
update 555 102865142
update 948 347412330
update 568 101494910
update 687 601659019
query 711 773
update 947 897916214
update 717 743865088
query 85 937
update 439 747832088
query 450 869
update 673 652012644
query 889 917
update 651 756551522
update 509 333473194
update 346 253049792
query 807 837
update 587 865679762
query 213 691
update 664 299201514
update 456 303142275
update 934 757263973
query 789 978
query 641 667
query 365 410
update 121 668420837
query 589 904
update 690 703554414
update 920 648542452
query 281 525
update 922 328553669
update 686 109109973
query 648 754
update 961 820522955
update 22 928305092
query 261 384
query 651 807
update 276 62053079
query 395 592
query 983 991
query 815 951
query 303 883
update 346 422736264
update 989 379454057
update 850 410937822
update 26 153974794
query 958 975
update 491 611177320
query 291 896
update 296 852049958
update 123 785252472
query 554 684
query 129 210
update 46 282883569
query 328 856
query 39 867
query 658 974
update 281 286222865
query 300 654
update 617 833220568
query 553 692
update 541 689219651
update 658 252389838
query 928 991
update 386 181858603
query 129 497
query 125 385
update 750 125219851
update 284 872712794
query 921 945
update 410 854552525
update 849 229414045
query 364 855
update 733 733279316
update 908 387170340
query 214 405
query 672 788
update 439 318704804
query 167 581
query 553 871
query 877 947
update 686 387843448
update 873 48191013
update 500 425852183
update 286 100638119
update 350 655362003
query 635 867
query 137 343
query 946 962
update 353 476556933
query 18 190
query 272 836
query 421 716
query 869 896
update 132 738895655
update 879 608550158
query 502 686
update 55 256005066
query 495 929
query 414 646
update 800 116624737
update 297 203554925
update 669 128759006
update 569 456759492
update 233 331774315
update 152 110095355
update 638 49979526
query 421 652
query 751 963
update 608 421486714
update 765 197818154
update 698 869316874
update 554 700647816
query 680 870
query 703 925
update 35 122949527
query 24 359
update 407 174219330
update 804 832313863
update 531 107772624
update 703 48245348
update 580 442270966
query 770 990
update 606 213408974
query 877 958
update 843 932612806
query 557 980
update 971 346923020
query 783 878
query 812 942
update 726 46624893
update 1 493841920
update 108 495208301
query 822 848
update 195 191736413
query 740 919
query 35 995
update 59 416897223
update 7 703266645
query 744 945
query 551 787
update 36 281072393
query 480 821
query 160 882
update 561 186184824
update 774 157364375
query 365 539
update 963 906307922
query 755 947
update 474 525205145
update 916 271973363
update 288 406205298
query 262 757
query 949 958
update 904 262435614
update 531 152308216
update 790 812702203
update 579 968596546
query 209 911
update 139 598793816
update 69 181348090
update 289 488885331
update 300 669957680
update 538 106095241
update 236 339937596
query 187 542
query 605 620
query 672 824
query 848 994
query 772 857
update 960 310690824
query 423 636
query 207 641
update 904 279389131
update 803 276412037
query 535 711
update 824 512509992
update 832 579454975
query 440 908
query 7 287
update 510 921544173
update 150 554872415
update 571 916328853
update 929 881856019
query 980 1000
query 805 938
query 103 708
query 315 702
query 35 769
query 806 903
query 807 820
query 461 542
update 793 268937103
query 702 973
update 87 509738849
update 338 639896573
query 15 565
query 355 531
query 590 911
query 271 911
query 775 979
update 990 135570657
query 132 928
update 488 995929765
update 699 693105148
query 703 899
update 248 240981918
query 138 769
query 969 990
update 190 943598319
update 522 422812392
query 728 849
update 154 206840894
query 566 797
query 302 645
query 945 970
update 748 291951418
query 87 806
query 542 989
query 953 978
update 856 860624353
query 679 726
update 271 870750577
update 472 320070188
update 91 800407278
update 842 545435560
query 210 545
update 430 328826419
query 715 734
query 161 501
query 340 788
update 439 588907217
query 947 978
query 392 741
update 645 128501801
update 831 880722153
query 627 963
query 550 583
query 642 707
update 829 349014165
query 460 908
update 711 186184023
update 279 341370401
query 386 696
query 696 817
query 870 887
update 206 43992066
update 521 585256840
query 772 818
update 560 494898787
update 38 860339791
query 751 793
query 40 525
update 318 319194118
query 682 916
query 824 853
update 542 273339649
query 408 848
query 880 909
query 777 861
query 167 506
update 811 844579530
query 972 997
update 73 39237072
query 22 285
query 205 770
update 256 992231375
update 520 922080666
update 489 266534927
query 897 942
update 754 459877020
update 625 338122754
query 398 633
update 405 48777157
update 429 444453929
update 682 582255881
update 230 556489400
update 154 120780599
query 310 638
update 474 887295397
update 646 617590523
query 387 672
query 255 273
query 453 997
query 593 964
update 149 855484490
update 477 50077993
query 893 997
update 711 131894791
query 286 823
update 444 850357860
query 656 658
query 252 869
query 910 941
query 479 748
query 514 657
query 472 489
update 487 460701190
update 133 192312565
query 418 495
query 985 993
query 624 631
update 466 217712061
query 500 912
query 932 935
query 887 953
query 725 808
query 227 253
query 367 649
query 807 946
update 624 84458407
query 152 537
update 193 811769811
query 546 785
query 835 915
query 562 600
query 838 888
update 140 238230632
query 769 884
update 97 829622686
query 917 954
update 307 927243128
update 327 580377974
query 370 765
query 505 549
update 488 317236772
query 329 686
update 901 717967737
update 816 569248448
update 145 750079327
query 693 775
query 51 820
query 503 907
query 232 618
update 385 15358134
query 559 943
query 581 634
update 907 981464909
update 853 615619640
update 117 255122905
update 893 824580521
query 566 982
update 671 581015386
query 410 978
query 778 838
query 393 750
query 713 728
update 750 152221585
update 327 693508144
update 855 537787032
query 901 937
update 656 703768117
update 50 73315583
update 642 278412475
query 604 990
update 106 635718530
update 172 525085148
query 667 991
update 235 539056145
query 758 908
query 522 588
query 236 331
query 379 890
query 848 965
query 162 590
update 73 376954904
query 179 659
update 49 515351322
query 291 453
update 969 522576010
update 539 336802029
query 773 813
update 267 868546050
query 589 903
update 283 210215917
update 411 822466358
update 148 368569920
query 356 413
query 599 881
update 58 666794938
update 165 236467645
update 197 401705674
query 913 985
update 974 373279909
query 708 868
query 641 970
update 144 113655931
query 113 563
query 688 791
update 685 966938135
update 356 536808780
update 364 524125823
update 66 589994947
query 703 925
query 74 514
query 297 620
update 353 456553462
query 281 815
update 967 547207092
update 556 928911406
update 219 401543237
update 441 803839455
query 149 592
update 797 686415760
query 547 744
update 219 634602342
update 806 688989020
update 907 403059408
update 14 883846211
update 736 361911752
update 332 125397509
query 739 823
query 663 731
update 570 988836528
update 213 358052843
query 951 969
query 882 940
query 903 977
query 201 918
query 50 271
update 515 536015200
update 155 748179909
update 233 819112844
update 342 732526355
update 372 78305945
update 366 59187459
query 622 758
update 465 866632915
update 798 27487054
update 56 173155946
update 267 290569076
update 428 995052447
query 100 829
query 326 797
update 630 82933282
update 569 248002059
update 294 143679480
update 389 826543474
update 96 814684509
update 176 538582738
update 127 763586569
update 181 427242361
update 382 10600328
query 881 977
update 688 116480533
query 399 922
update 428 776372656
query 356 975
update 969 460112643
update 152 240048948
update 269 461117992
update 217 357516600
update 769 884709204
update 103 521343690
query 963 963
update 177 319533764
query 18 950
update 735 155858314
query 710 797
query 40 925
query 216 594
query 829 849
query 585 588
query 597 980
query 455 890
query 118 411
update 343 798577082
update 965 598245511
update 185 820982886
query 709 763
update 50 760165022
update 739 172822469
query 525 818
update 934 914335310
query 723 935
query 175 322
query 408 421
update 304 730128779
update 180 295170042
update 39 962741863
query 500 777
update 804 546721981
query 440 997
query 26 118
update 475 942885721
query 148 933
update 667 229642308
update 275 738852541
query 835 966
update 30 80853914
update 381 189954909
query 545 831
update 468 511281992
update 501 493671633
query 802 894
query 895 907
query 993 995
query 588 932
update 426 640545884
update 472 637614940
query 844 946
update 508 270651385
update 786 172875389
update 260 348859072
query 451 971
update 570 930964302
update 296 157235338
query 835 887
query 112 673
query 26 521
query 339 385
update 176 239061986
query 769 961
query 836 920
query 617 825
query 841 923
query 536 973
query 769 790
update 374 564848849
query 775 952
query 585 865
query 537 655
query 236 649
update 724 868940354
query 465 550
query 684 931
query 245 476
update 84 707157855
query 200 908
query 167 225
query 676 963
query 728 946
query 588 999
query 855 995
query 896 953
update 727 731349664
update 853 560325889
query 755 834
update 949 920604889
update 368 977064638
update 190 284447028
update 531 191984966
query 707 843
update 289 955294349
update 101 67260253
update 209 742295027
update 829 681779189
update 475 28129845
update 968 510258899
query 35 179
query 515 601
query 596 690
query 598 728
update 295 819273179
query 43 534
query 219 994
update 776 304555292
query 195 827
update 507 533930293
update 953 549449672
query 228 526
query 508 776
update 265 214416194
update 138 999703304
query 562 750
update 820 920878849
update 490 388296823
query 326 450
update 36 7915977
update 750 802246951
update 616 580591940
update 702 985078654
update 678 837116969
query 968 982
update 244 307910483
update 971 825759136
query 137 141
query 698 972
query 335 865
update 566 879400265
query 567 857
update 857 415797356
update 515 242746079
query 596 622
update 481 215256225
query 279 994
query 982 992
query 241 817
query 6 119
update 835 144745783
update 302 553334896
query 747 787
update 475 506737145
query 773 903
query 113 831
update 483 505738354
query 478 887
query 45 854
query 159 533
query 196 716
update 565 948433938
update 358 898538537
update 873 986595962
query 934 958
query 269 372
query 336 449
update 19 849856971
query 494 709
update 197 945821085
query 861 982
update 299 549287298
query 111 671
update 296 403577057
update 603 859394828
update 624 328275843
query 766 840
update 427 860913479
update 989 3153554
update 218 648007579
query 35 39
update 490 688646773
query 189 705
query 713 905
update 992 182767681
update 463 272494047
query 545 906
query 133 406
update 60 329540421
update 974 674140766
query 79 528
update 353 789333701
update 989 27353666
update 325 242944680
update 42 212491778
query 517 788
query 471 1000
query 275 367
update 798 248458364
query 315 498
update 396 156203664
update 227 599354085
update 739 816542231
query 328 725
update 794 871255478
update 821 587238095
update 954 322254952
query 595 873
query 443 693
update 108 64154140
query 625 817
query 864 944
query 419 903
query 525 601
query 862 994
query 189 380
update 279 870375349
query 469 633
query 301 548
query 611 709
query 188 338
update 642 741234770
update 138 37540944
update 336 444951399
query 507 748
update 21 764884913
query 856 939
query 177 911
query 216 435
query 645 786
update 197 958831580
query 814 874
query 161 774
query 884 977
query 428 568
query 169 762
update 196 854255308