题目描述
In the college where Utkarsh studies, all the students live in N Row Houses. The colony containing the Row Houses is a straight line = x axis. I^th Row House is located at x = i and Ai students live in it.
Every week the students of some Row House at x=K organize a party and invite all the students living in Row Houses from x=L to x=R.
Utkarsh wants you to handle Q events. An event can be one of the following 2 types.
1 K L R: Row House at x=K organizes a party and invites all students living in Row House from x=L to x=R. Tell the sum of distance traveled by all the guests.
If a guest is at x=i and party is at x=j then distance travelled by him alone is |i - j|.
2 K S: S new students are admitted into the college and all of them start to live in Row House at x=K
Input format:
The first line contains 2 integers N and Q.
The second line contains N integers denoting entries of A.
Output format:
Print the result to all events of type 1.
Constraints:
1 ≤ N, Q ≤ 10^5
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ N
1 ≤ Ai, S ≤ 10^5
NOTE: Row Houses are 1-indexed
SAMPLE INPUT
6 4
1 1 1 1 1 1
1 1 5 6
1 6 1 5
2 1 1
1 6 1 5
SAMPLE OUTPUT
9
15
20
输入格式
见题面
输出格式
见题面
样例输入
1000 1000
23653 78735 47442 76716 11261 70906 91997 65247 67721 40711 93150 80320 28733 19036 23947 28339 36687 21854 86295 29 33011 7729 46328 1635 55166 66651 82083 80746 88006 89825 52589 4567 16479 40807 27818 6736 52767 94163 42353 22424 43226 65418 2325 18742 6725 97008 28045 21646 67030 67275 44652 71045 13249 80735 21672 83648 15195 9106 87574 34405 20410 48713 87499 2167 42162 1897 82588 43709 5209 98038 28190 81146 93347 74709 49094 98581 81254 11629 86824 7602 73622 79937 79547 46550 82472 13622 36338 91719 75409 44594 28355 3880 41127 23834 39523 64032 61599 60787 43655 64210 73645 33665 68292 71685 36678 67114 23631 10493 40575 17234 58300 82495 81934 54271 77314 71633 99944 71574 24724 57590 85376 72444 59561 15989 5774 96533 53844 31057 90276 76198 33515 14385 35161 45877 16867 37081 14721 63079 41681 88622 68434 38113 36970 12982 1088 22279 73058 53876 70337 1119 61232 27631 63784 60654 84839 45706 2797 99800 33278 74348 55138 30371 79752 27769 5982 84883 26939 1942 22198 68878 44 24873 82046 13369 39312 31765 83755 38232 11004 67521 33714 75761 30820 73456 32233 65961 73311 76873 7109 35588 8864 81808 89050 2632 96766 40298 70909 23577 32524 29596 22371 92446 57440 8268 61826 26937 64591 33757 76143 8722 9102 42934 98077 45772 86738 78875 41507 23725 40143 34097 88918 34073 5532 67645 64906 10198 91660 48228 10932 46633 20726 84523 5930 52342 12685 61048 54240 88227 10119 58798 70283 69941 17657 43028 39041 78672 99384 63374 92726 72122 34649 60609 23456 90007 27249 19890 14963 79949 66260 12615 69829 42977 52281 82179 26249 70776 51251 39405 8151 16566 59480 11081 80993 22848 19198 56380 19966 76093 42360 93483 77955 22384 41372 61723 49539 71454 66622 88529 98645 80654 42677 38355 89678 98787 981 68868 64130 87170 146 48843 61798 5201 28099 75116 29296 88693 35227 96588 64532 467 720 11120 63400 85199 31159 17501 735 45359 88869 79385 97585 86391 71119 14280 92880 74477 12394 40814 90643 80374 1802 14034 71439 71638 7398 47704 74456 3923 74257 92453 14627 35986 57474 28607 7942 2935 41260 60521 5589 41000 33189 69322 56229 7273 96194 86181 23660 45089 34776 51329 51582 82002 45563 65442 51889 22052 36290 56845 83480 1626 18145 69096 64523 49434 73228 26582 51901 55944 41657 64894 85315 41546 27069 41859 70994 88741 46862 22412 60672 29245 56543 28605 63777 17496 26309 34171 27435 56698 39671 35852 49330 84458 80041 52083 29100 18859 86703 47447 11661 61730 55104 6171 88266 33173 84879 33830 58329 67113 80146 99964 35246 8546 82463 11170 54206 28934 21929 48798 46559 10266 83877 22131 49413 25890 68298 56551 22950 43972 31500 30048 57270 88613 20959 82978 42346 78441 87194 65586 58872 81302 20368 60437 47764 38769 34712 87984 70900 67582 71525 89705 37675 7331 91245 32163 44625 2180 55781 6501 91833 90823 30369 31763 17560 74833 54200 94418 50307 94471 67230 11111 58064 10221 70343 94423 35251 87368 68265 14983 44354 94943 32922 26173 31953 90709 50733 20924 11318 72879 53464 32683 9732 56243 72336 34734 83571 27174 60906 5834 41557 48269 37274 59812 99425 43116 47127 9122 62220 46537 30804 39783 50858 94728 19816 5946 67664 28911 93254 12735 39987 15587 18692 49627 31817 31304 52471 90259 38727 56388 1620 94732 72032 44124 63632 51595 74412 78324 61888 19990 58717 67730 26520 29232 78666 74491 59695 62528 48167 16115 71448 22378 79626 41408 30410 22611 63271 49734 72600 71904 51348 3083 76664 70806 66021 34356 53183 68155 62703 36165 72450 83922 98088 52229 26805 22914 92100 58134 42415 23727 47864 6816 87620 63678 43418 93158 59880 90100 86270 85357 40305 43479 97498 88283 90420 40874 49058 6165 84902 59412 31563 93984 10780 86488 99787 76608 1835 83549 56182 41531 69384 8039 40866 96885 26504 84059 15939 3636 53887 87167 11694 44093 19012 10646 44185 82996 70282 10887 93368 68511 30471 55637 34656 95139 98128 44295 67559 85956 30938 86561 47202 78152 23482 57288 97380 5716 45061 13730 80484 85708 77808 24082 18903 53846 39791 10591 65073 55286 24281 1580 66151 49075 9249 94464 8815 57231 60765 34143 52701 39506 82914 38766 41446 57503 84229 31442 66304 1436 89339 40753 74815 93517 3961 9230 56121 90136 25460 36240 67394 46850 63872 87867 37743 25871 18996 93620 36022 21861 11331 18624 61195 26120 94435 2948 23044 92254 96073 24838 98197 95212 75466 44841 36755 20279 90043 27508 72564 30179 30289 35883 13420 9654 44225 2643 81936 70100 42175 94321 89622 77027 46338 10378 82739 27784 40189 87683 6874 26791 25478 58530 96034 10886 52243 3466 96288 21770 12823 12610 25864 26071 8616 12334 32495 6483 64826 21523 18123 78338 97956 18614 19792 30090 21242 47805 11859 58352 94800 72331 42538 36697 59869 27751 39369 77993 94068 30741 1574 21509 63531 83962 85973 17236 12375 5563 78251 93273 53453 69629 64766 58137 9218 77093 54562 86203 71018 5401 50540 73186 32220 58588 5714 19 5452 94389 50857 40276 92782 67752 8420 75274 88120 12090 85882 5146 33311 31408 32096 87016 58041 47759 42 42586 78424 69981 87021 37556 10452 90045 54271 9020 27073 71446 54196 89623 62804 92140 83841 50153 19265 51012 70492 29912 93535 22499 55353 92201 50817 59151 69326 50336 30717 64683 94351 27395 24488 80798 51985 6422 69495 53675 60042 19263 66271 64025 36014 74467 68821 73196 4115 44743 78733 50313 89645 96207 42686 42806 47473 27681 97851 1270 66485 46081 30267 16880 14637 25429 11153 30023 71183 32354 37395 22402 48367 99244 74326 17957 38626 42105 23279 20885 2302 46541 58835 51064 52823 48431 15158 84593 79330 7265 12335 19271 10965 65835 35089 30525 72164 4688 2323 68218 54277 16502 30056 72354 86060 35745 85638 88122 36686 92183 73794 11943 33761 30717 58961 18831 90521 75959 1320 92597 6412 77355 91707 60960 92814 28030 20545 61140 10324 89140 35469 438 76372 94803 28758 41547 76546 78240 23279 50264 1908 58687 87662 10851 87198 7926 50472 6319 53653 14281 3986 93923 54063 37598 53825 40547 96064 80058 54153 1491 62558 1857 35745 39771 16412 20825 81565 83613 96498 16103 75025 67839
1 999 999 999
1 913 424 685
1 99 202 983
1 925 763 768
2 182 10089
2 104 98074
1 13 20 434
1 795 460 769
2 48 38130
2 832 36447
2 355 71791
2 86 93678
2 335 1331
2 584 33409
2 860 50748
1 428 648 991
2 946 23370
2 332 79846
1 697 685 947
2 304 20364
2 33 84584
1 224 623 658
1 979 415 670
2 380 1719
2 201 42730
2 351 58826
1 495 586 835
2 673 50983
2 940 8198
2 636 12656
2 376 85944
1 620 314 652
2 775 27116
2 745 77924
2 3 53399
2 49 75581
1 948 884 976
1 320 171 521
1 209 741 756
1 723 347 860
1 946 266 706
2 489 11837
1 860 853 861
1 770 330 956
1 957 899 990
2 306 43302
2 232 41055
2 890 85343
2 125 85204
2 598 41916
1 327 799 853
1 156 914 970
2 424 37458
2 736 53526
2 639 62523
1 723 476 704
1 164 270 729
1 250 650 871
1 440 876 984
1 1000 983 995
2 192 96081
1 894 893 967
1 18 101 413
2 318 74100
1 542 646 827
1 163 76 230
2 834 9100
1 231 199 365
1 732 682 859
1 974 815 931
2 683 92587
1 880 418 834
2 988 92837
1 379 30 177
1 474 412 501
1 789 363 663
2 230 16200
1 989 857 967
1 242 617 636
1 320 242 374
2 288 51358
2 816 39037
2 52 10300
2 888 13729
2 668 609
1 969 623 964
1 873 133 749
1 759 739 783
1 177 393 679
2 21 71178
1 731 197 953
2 759 78283
2 581 4282
1 715 706 746
2 262 57816
2 253 81499
2 37 10114
1 794 760 938
2 147 96819
2 383 72281
2 126 46134
1 745 452 778
1 785 486 972
1 916 568 911
2 617 98468
1 12 4 591
2 714 57906
2 184 57286
2 426 21382
2 319 32609
2 761 74288
1 32 553 761
2 692 3264
2 788 68432
1 915 811 861
2 541 28341
2 314 48328
1 569 523 899
1 994 753 926
1 821 520 652
1 10 190 269
2 825 31731
2 265 56225
1 942 70 915
2 603 45313
1 696 610 804
1 965 923 969
1 996 949 985
2 927 34422
1 156 542 922
2 615 45136
1 312 962 991
2 595 90241
1 437 360 625
1 918 396 917
1 819 506 626
1 643 728 793
2 465 90314
1 920 875 994
2 802 61380
1 11 52 781
2 125 21338
1 991 659 781
2 888 58646
1 109 197 807
2 709 87067
1 208 546 586
2 562 56493
2 685 57083
2 655 91035
1 948 539 747
1 959 915 938
2 778 82445
2 478 91805
2 253 39483
1 786 220 653
1 798 325 764
2 677 64054
1 447 310 449
2 712 58875
2 780 44264
1 931 632 925
2 16 66865
2 143 63937
2 958 83429
2 578 4393
1 596 431 610
2 848 74323
2 371 43935
2 309 51354
1 440 823 855
1 984 702 915
1 577 209 529
1 889 881 958
1 631 74 576
2 10 32614
2 367 38621
1 195 174 672
1 434 769 849
2 657 93346
1 577 539 685
2 662 38432
1 476 381 515
2 288 19012
2 601 71344
1 546 543 761
2 366 61390
2 68 12558
2 254 65877
1 748 186 730
2 593 12690
1 13 545 725
1 994 540 763
1 932 197 398
1 189 112 829
2 583 10398
2 641 33754
2 291 81599
2 391 19685
1 108 606 730
2 264 8806
2 880 30951
2 150 6895
1 820 356 656
2 454 98272
1 87 143 294
1 960 873 951
2 695 89255
1 405 390 476
1 872 640 855
1 946 865 889
2 334 46515
2 683 30018
2 800 37519
1 612 555 642
2 917 73923
1 991 754 875
1 285 711 734
1 403 319 408
2 1 63065
2 673 44226
2 1000 23379
1 777 561 831
1 907 901 923
2 282 57793
1 701 697 961
2 344 74020
1 830 217 562
1 14 16 334
2 232 64117
2 625 15990
2 348 32351
2 518 42227
2 991 1564
1 992 776 976
2 594 727
1 71 250 507
1 509 135 679
1 887 646 765
1 185 299 488
2 344 86814
2 92 19825
1 986 920 939
2 883 34279
1 19 623 839
2 563 34564
2 815 77096
1 961 714 856
1 226 381 806
1 552 128 244
2 73 52155
1 94 183 800
2 547 72941
1 175 190 867
1 977 775 880
1 470 598 628
2 828 43300
1 208 217 367
2 804 25843
1 969 940 959
1 996 951 990
1 190 104 705
1 36 507 526
1 723 398 527
1 719 690 804
1 769 237 584
1 840 759 904
1 330 954 958
1 994 470 856
1 657 462 583
1 365 217 705
2 764 26925
1 724 237 642
1 111 539 587
2 885 79218
1 828 11 635
1 758 737 768
1 69 154 646
1 721 389 757
2 4 72397
1 452 864 890
2 878 98064
1 83 120 551
1 427 54 167
2 670 43795
1 949 781 917
1 534 238 381
1 628 584 718
2 124 24571
2 618 61692
2 124 92595
2 619 95162
1 427 975 976
2 701 44584
1 837 788 945
1 799 765 843
2 786 89253
1 414 314 904
2 987 95995
1 242 621 636
1 708 139 190
2 293 6698
1 21 419 899
2 452 79809
2 529 30955
1 44 136 880
2 526 91544
2 408 98941
2 788 7202
2 120 30980
1 921 310 856
1 64 101 285
2 266 30251
2 607 8746
2 431 66670
1 890 889 1000
1 151 240 858
1 664 613 721
2 17 3057
1 337 643 990
2 295 86557
1 641 556 646
1 174 226 898
2 810 71085
1 259 503 852
1 56 38 56
1 669 699 895
1 902 884 945
2 372 19563
2 781 69862
2 459 71684
1 670 199 711
1 976 966 977
1 536 493 554
1 74 151 512
2 258 73614
2 920 69350
2 795 89623
2 176 43455
1 235 232 336
1 515 466 535
2 226 53190
1 467 222 526
1 8 34 473
1 382 195 654
2 899 64799
1 26 129 301
2 722 76139
2 490 40896
1 414 447 813
2 980 24770
1 326 468 552
2 391 10851
2 83 45694
1 943 461 938
1 209 111 408
2 309 95129
2 876 7922
1 968 931 968
2 580 37262
2 399 75706
2 51 36324
2 650 16840
2 178 95603
1 438 344 794
2 741 56439
2 414 10192
1 43 94 441
1 537 966 986
1 72 75 613
1 699 405 951
1 753 988 989
1 923 914 927
1 901 394 807
2 646 74060
1 933 70 739
1 536 499 701
2 268 36515
1 490 411 516
1 475 461 540
2 97 14805
2 532 35912
1 804 686 912
2 584 98608
1 245 306 376
1 617 423 602
1 80 137 299
2 510 30432
1 748 865 998
1 710 657 714
2 582 77012
2 358 47823
2 912 9699
1 96 343 680
1 741 736 750
2 297 21984
1 852 841 855
2 504 11363
2 126 30531
1 942 866 915
2 512 30917
1 997 729 892
1 219 230 356
1 43 74 549
1 866 847 888
2 562 27840
2 696 16680
1 244 335 557
2 203 64252
2 940 43529
2 994 32576
2 89 11901
2 82 67137
1 588 469 918
1 188 140 635
1 696 687 696
2 611 56476
2 318 69203
1 992 681 780
2 102 64271
2 250 79917
2 907 25892
2 5 99087
2 731 8430
1 346 800 823
2 276 10647
1 778 581 714
2 6 73614
2 812 94261
1 230 984 989
1 926 835 977
2 890 24213
2 24 71903
1 978 885 962
1 920 919 920
1 940 915 960
2 467 80403
1 690 462 766
1 883 875 914
2 423 75610
1 571 357 578
2 140 52429
1 943 972 986
1 735 128 560
1 984 208 891
1 44 324 833
1 27 333 443
2 8 61122
2 793 18076
2 172 38470
1 515 495 851
2 642 14167
2 397 34042
2 245 29156
2 416 4091
2 919 82699
2 6 14910
1 963 675 829
1 671 432 467
1 998 808 994
1 189 219 602
2 78 97347
1 732 138 909
1 534 477 604
2 26 5090
1 189 311 873
2 530 26414
2 522 55988
1 35 347 853
2 57 13294
1 603 371 570
1 570 361 716
2 595 35985
2 297 4355
2 824 48911
2 130 48655
1 981 459 905
1 977 531 958
2 723 68615
2 985 46235
2 98 62417
2 963 14421
1 32 666 784
2 715 43059
2 317 10301
1 886 852 931
2 593 91125
2 624 3389
1 453 503 591
2 152 11903
2 417 70507
2 998 43901
1 215 661 948
1 979 666 827
2 150 35853
2 752 11070
1 4 34 66
1 20 372 467
2 964 46520
2 25 87712
1 50 582 842
2 24 32655
2 577 6798
2 937 78631
2 965 28114
1 508 150 601
1 760 721 976
2 750 37364
2 5 47631
1 969 871 957
2 544 5234
2 13 57530
2 843 95400
1 293 17 76
1 214 414 420
2 901 51184
2 445 58133
2 383 42470
2 859 32388
1 524 644 893
2 493 2988
1 952 913 938
2 743 79060
2 245 13333
1 23 20 30
2 368 9132
1 639 27 996
1 797 405 717
1 244 597 774
2 328 57212
2 643 36304
2 860 68388
1 833 743 919
2 828 12517
1 142 678 897
2 506 62730
1 910 960 988
2 111 97377
1 919 975 995
2 427 11221
2 891 7387
1 555 347 550
2 831 15101
2 460 25342
1 722 119 689
2 397 20548
2 250 17888
2 329 35008
2 782 42038
1 96 332 385
2 707 8262
2 195 78023
2 10 77171
2 711 34170
2 956 69776
1 902 380 886
2 608 2715
2 119 57323
2 223 87158
1 256 614 696
2 928 60746
1 354 234 647
1 996 902 990
2 899 92809
2 641 80975
2 722 75561
1 795 786 819
1 240 926 980
2 819 45047
1 794 259 443
2 973 79906
2 577 48875
1 848 787 927
2 734 97131
1 965 948 968
2 340 87923
2 119 82745
1 420 426 828
1 793 767 970
2 870 79971
2 75 23424
1 996 972 993
1 866 865 869
2 288 96091
1 48 412 529
2 891 50408
1 956 784 875
2 281 87160
1 711 674 1000
1 956 52 632
2 274 39893
1 238 127 409
1 1000 912 955
1 132 155 984
2 506 22326
1 445 404 477
2 89 84100
2 413 73320
2 371 90717
2 374 81797
2 954 65206
2 942 29039
1 713 700 746
2 425 86295
2 958 81344
2 126 78913
2 622 18766
2 965 7726
2 2 2612
2 665 8346
2 279 18943
1 998 852 994
1 260 340 946
1 988 944 978
2 633 48517
2 426 38470
1 374 584 900
1 488 488 508
1 620 809 891
2 134 49186
1 109 198 738
2 729 57128
2 28 1219
2 184 32581
1 568 414 739
1 3 8 966
1 905 589 685
2 925 70937
1 53 377 939
1 481 667 985
1 114 596 896
2 50 45586
1 981 950 975
1 925 81 515
1 718 700 731
1 736 657 721
2 509 79679
2 558 27203
2 793 34008
2 796 54037
1 475 233 549
2 199 60766
2 884 4606
1 717 174 662
1 988 129 626
1 22 132 943
1 576 608 733
1 182 379 593
2 212 83846
1 983 914 969
1 918 917 940
1 123 158 184
2 126 26191
1 716 692 848
1 585 889 905
2 220 32575
1 954 841 895
2 943 86486
1 967 960 967
2 63 57449
1 857 672 810
1 258 505 594
1 641 54 856
1 967 964 970
1 75 733 787
1 286 93 392
2 964 10248
2 132 40771
1 723 193 548
2 7 9670
2 687 40543
2 945 85165
2 451 31612
2 58 58941
1 987 563 844
2 377 64981
2 589 38453
2 310 39222
1 166 516 929
2 508 1719
1 535 487 607
2 40 82805
2 934 25997
1 892 125 829
1 776 769 801
1 374 277 384
2 695 81708
1 720 361 640
2 374 60611
2 308 27350
2 671 50617
2 171 47334
1 766 13 258
2 441 70124
1 16 111 323
2 428 20713
2 419 42630
2 616 45850
2 715 68306
2 714 70927
2 832 16997
1 2 3 858
1 240 322 889
1 392 662 690
1 37 194 876
2 707 36393
1 993 595 964
1 1 30 995
2 336 34966
1 777 734 947
2 456 4967
1 447 566 913
2 595 94575
2 207 59932
1 999 269 858
2 120 6465
1 894 375 811
2 833 14397
1 157 484 920
2 492 91356
2 518 68981
1 620 320 998
2 198 8285
2 633 32241
1 258 799 820
1 974 969 988
2 818 7404
1 885 417 723
1 535 697 897
2 370 64655
2 511 20658
2 60 83032
1 110 369 385
2 816 39245
2 234 38551
1 736 28 708
1 713 562 622
2 390 66768
2 924 22316
2 265 48858
2 717 22097
2 553 19108
1 982 1 977
2 909 85613
1 116 125 834
2 978 40318
1 214 218 809
2 40 41599
2 881 5137
2 845 10803
2 744 88287
2 415 70413
1 724 563 715
1 991 972 976
2 335 95277
2 137 98316
2 622 52697
1 999 959 994
2 173 14083
2 325 21219
1 320 286 378
1 977 970 982
2 154 32499
1 266 34 313
2 727 20504
1 238 280 295
1 135 359 528
2 239 90797
2 2 1624
1 759 187 713
2 553 27472
1 945 919 944
2 110 97233
2 204 75570
1 167 353 365
1 107 42 116
2 376 26967
1 178 285 809
2 392 24817
2 853 8125
2 935 46195
2 522 63086
1 999 844 993
2 749 15226
2 308 66192
2 23 58444
1 838 902 930
1 573 592 907
2 966 99516
2 741 6228
1 997 916 957
2 627 23946
1 982 775 975
1 568 856 912
1 661 465 898
2 653 53626
1 711 705 750
1 536 43 755
1 729 414 714
1 995 848 952
2 660 22373
1 311 919 975
2 261 11457
1 151 675 796
2 681 2845
1 794 761 870
1 65 80 185
2 541 25855
2 659 15553
2 954 20935
2 164 19195
2 13 70780
2 492 83031
2 177 16551
2 456 5327
2 845 35350
1 176 185 427
1 877 60 466
1 978 871 929
1 160 795 994
1 767 95 684
2 859 99979
2 252 77802
1 919 916 980
1 733 522 542
2 682 23377
1 735 682 756
1 944 76 490
2 921 74461
1 827 781 845
1 996 863 994
1 938 504 927
1 460 572 761
2 95 16861
2 139 28376
2 177 11926
1 980 409 846
2 543 64671
2 47 39493
1 283 525 772
2 460 79801
2 731 16794
1 23 131 585
2 629 2969
2 708 47830
1 188 661 751
1 715 640 888
1 594 441 987
2 834 17519
1 973 141 972
2 343 26011
2 187 61451
2 527 92731
2 285 19600
2 348 29263
1 857 770 871
2 401 74829
2 405 34914
2 597 3891
2 287 75955
2 814 69176
2 498 19770
1 836 285 745
2 1 20487
2 506 82846
1 740 607 747
1 889 596 963
1 994 979 992
2 955 33518
2 272 73928
1 209 407 549
2 99 40086
2 620 18051
1 38 110 748
1 849 844 857
1 983 950 975
2 82 11132
1 703 667 778
2 37 86520
1 934 43 58
2 217 74826
2 10 48766
1 785 382 752
2 527 86738
2 600 17070
1 982 145 613
2 714 63539
1 264 326 573
2 406 1420
2 823 27311
2 657 99115
1 9 10 221
2 836 82990
2 654 21632
1 516 867 963
2 800 25732
1 71 80 628
2 863 79034
2 986 74895
2 652 78658
2 211 91003
2 618 96490
2 737 24998
1 46 288 837
2 217 80982
2 726 24874
1 958 665 730
2 493 61586
1 991 934 943
2 739 96338
1 989 940 993
1 974 408 436
1 633 308 481
1 394 355 878
2 828 69777
2 917 93572
2 954 118
2 440 10937
2 387 7990
1 133 247 490
2 23 53416
2 268 56169
2 361 36443
2 299 13775
1 978 959 983
1 381 99 460
1 843 181 803
1 999 952 999
1 996 995 995
2 263 74312
1 438 258 505
2 658 30587
2 311 73402
2 338 48842
1 797 755 766
2 54 95785
2 20 62680
1 612 245 556
1 980 972 987
2 457 91586
1 978 169 332
2 17 94437
2 903 27834
1 805 370 724
2 160 84850
2 884 71832
1 63 142 340
1 586 497 591
1 996 215 875
2 766 26301
1 458 59 463
1 620 225 325
2 705 76117
1 412 90 700
1 86 535 869
1 55 649 853
2 376 4317
1 661 274 838
2 669 88867
1 258 513 900
1 591 344 643
1 714 710 720
1 244 244 253
1 715 366 769
1 106 94 113
1 978 473 728
1 98 87 666
1 680 437 709
1 104 981 988
1 533 82 908
1 1000 686 865
1 681 507 977
2 811 8212
2 429 10829
1 306 125 410
1 986 148 630
2 856 31586
1 714 125 186
1 346 721 979
2 486 69636
1 185 302 930
2 74 70945
2 184 86619
1 993 38 915
1 872 551 821
2 518 21405
1 646 630 649
1 943 199 975
2 344 6492
1 995 723 978
2 392 95510
1 372 206 375
1 963 937 947
2 879 48690
1 134 166 669
2 624 96543
2 756 99562
2 628 40199
1 407 69 825
2 404 24446
样例输出
661652
70267189
10371674731
18617056
7201483636
269724768
835625256
2564366659
5487771968
1015157349
543519923
976544173
2565565967
2013418110
2063325390
1246194853
946145493
1227506193
199464912
11654176791
213899156
9291021261
2592639075
2574189634
1383059491
269495579
1940210293
12375910814
4771463823
8796547630
165253401
808567776
2148960164
2644772026
1847611667
241215111
24074208
1454087970
447186643
228893559
1904431672
4585414783
1149387490
564289610
2177669203
8664974220
2124930352
3165530271
9671252930
30620234
740840668
6356415801
3776064775
319611003
8030944114
2341017856
14897675218
14651635397
21334401702
15468533800
3393791013
181379
4047914958
920817343
6488707776
241787789
14277822015
9784518424
5413828140
3026955183
2883541751
5015218653
474064758
12495595
1433267660
896864004
106787372
775708681
28960416
7329892609
206534836
1038962042
5426103390
4635796162
22682766
1275203415
218366462
642013624
12055843635
659204385
4241877909
4576451721
13808080076
1585278856
13418855313
417306888
4465570060
15449998766
44790901
254379461
114604250
28901832
1330871811
1242703403
2953291986
831067839
1567214106
146714610
818088833
14587275742
203823417
56537351
3494443554
204651811
1328096126
3772191935
4912673366
1461877631
12889189686
1233654157
1265305423
9337855
3426862618
1885222040
1441529769
1970179721
2494883679
513102701
331739
18269485243
72154596
2318391603
69316086
1773254549
2139226320
1589039799
2874264638
2544849922
363335859
12601071262
2001175019
389473351
909954515
14867299
1798064838
11031909706
368178268
247245289
1837222645
1576545478
29234130
979275711
205045315
4493586513
1496492449
260062770
3886188082
3003047985
2134302828
470561711
8977079439
213151584
227319598
1569541965
6030248107
6381050105
14203878976
4123043364
2151256083
5932590
54109553
84870680
4738744414
1435305119
1763528207
3796208022
4113871673
78260446
8607377904
6919649634
17864768
3922577547
89645156
13664364953
240892750
33715650
761283761
1662954787
217364010
1713603590
394957505
4146163693
430561217
836119337
11280556082
18995773661
101225212
145413189
101087950
108077603
14325898764
1259654311
5569917223
3043108576
4603436742
1442644922
990674841
5816844789
62405797
3869218368
292182015
94699362
1563288466
4807334162
12685250607
21945021475
5842636346
9846461296
8240386
2029070234
125070141
13429722179
1587947432
636132165
3281417266
1141004641
14920090333
6268664256
806073550
1357064
1050391756
2356634922
11420050182
8987658365
1668434977
45108189
724018028
574496240
909253263
9365601304
4067833034
19435476660
227785715
1295793
1085767299
943736667
1474888710
871325598
3285000000
52262748
106934554
1619025906
2938116412
6038972927
955215512
7876368454
47301818
9803896852
3049003194
109029128
15979105357
1245876408
10979211848
1780968373
64272
498613820
0
2493076380
65784951
9380390152
29439413
1040531748
871324091
1122332251
2419494285
1081341880
928035614
16824981354
9759522203
2712172286
45626225
3183843384
5995289
923321328
8648186260
402009628
6241805551
1298033938
240375558
208898130
5947768659
12348171407
1713160224
5501402201
9328567
58236898
35574759
28992133
4808440025
16955503535
3924950722
77286459
270367116
99807
23396174
396610914
4206575794
1277931455
1628954565
1459087
97954520
3503296471
6096025583
9970831327
1560899902
2760749670
14822619684
13325225331
4476380057
416328026
667879829
5724263462
487433805
404324621
11444459103
1470414902
180484569
114689933
1531222988
32372603
546793669
117061689
1078719069
551185684
13938323980
2699843134
470924424
1545024106
3722966370
9034253246
790052095
19190000760
19508890949
310128080
67621203
1317639735
3466277872
58252371
4746948516
6646300578
6568058
2755447982
10282474192
1912264503
5945385401
1293469179
962676071
119591503
1400547
14649735602
2899395415
2611121546
2961624134
751862262
2116759712
633184
1890870176
11786245070
1613326464
4004740331
964920
2451806289
2956373593
7902017
8337513179
7735302
714325971
5741629579
10073385749
13516359264
412564023
14738428
3246713189
320321835
3218369300
1224209831
6196609935
318146209
181661977
875706704
3261387303
687604724
2838978268
18599
5061895864
360601950
3217040770
101258661
3055159933
3498777431
2467107433
13802
457813102
712191443
494059104
313208985
8861243203
5988523487
104871164
1949694936
551032601
551317203
630876787
0
7609946366
2340145181
771457924
166461199
964758993
2942231925
1096213056
1101226277
529829597
1356194906
6185083806
53448077
62906021
16036104164
12202276787
2182142243
2390394531
2667011017
8455780004
489832332
139394811
17092781186
6195043457
2252000430
94444747
322845
12870499817
3306434423
8212214884
77967795
11654086097
369594763
5365223415
767066906
149606797
280253380
1361600930
79821309
1576894437
292373290
39274417
4535557809
8753302324
171973789
5055581466
7780939545
4408880463
4788713798
94406895
7926264615
4490882
1054165150
6643631520
13317306821
17596562
3322342420
4407733675
11150080660
3740662953
249049634
9601649385
560931066
604643639
365790371
6174803043
281341869
12448780207
7782803908
10411012049
9282272418
7663310587
14531260688
26722479
7844336388
4831191096
794496217
856211379
17591874
2149921173
3458756373
12399481594
89736367
2013414669
114843513
1901751089
16275135707
12083323314
235222867
203427175
193926082
3210856
7746945615
3546549732
5004128790
591095915
1362289858
2318185399
1318155127
9957007325
818384349
4716636
9554181
2917154167
6539657048
1911254738
396049
2148255788
682598542
8282927273
401907645
1821966868
33684564
5696533380
226014342
15740014
3585452875
3069186247
451559331
972739939
5970080799
6271093066
2879254269
213625492
9281232444
790635394
57989429
5696246499
4704039
2575136810
801355656
2736670663
2501611137
7089428
2700293165
5086798799
10032597372
1298683755
1648096994
5090862771
101078047
830703180
1692815982
5401056961
9184073162
3933965372
1885129085
1120043993
4225803224
75452926
12931045690
2069180527
1785615217
7032541879
5074976934
841420415
11280759916
14922622887
596492023
1730741168
3351860895
1584559019
5128443155
866601744
212788914
65616143
962375724
1222071423
4744559766
15037747533
4940052120
1673350038
5568706054
192970406
999598331
6710489913
5673100559
15722251317
871295591
4571854625
2199675931
196518
5850461593
1734291818
9085424474
452007275
5635270776
167127087
1243745234
8492442039
4034983731
868080398
8660964408
529150679
5786795831
782933353
5781370373
172773342
7737997246
265965242
6534320141
9915887
1481330324
2070621059
1745023600
1827017312
5267578359
3359287332
10225667463
2819068534
121313640
1344437458
3472391928
534981968
8760127018
11058525878
8076137486
787592082
1177371389
9241121
126868131
1530817283
4085563956
2664748
20262607163
8130633509
5988919592
264438422
44421513
445053773
1221466464
1644470658
11330876244
16536469
679692490
204502390
4156267
180954964
62280233
144615911
9381560408
3510050573
2752203358
8296787375
798236352
1170800464
14941036556
1881542645
11673614589
1282767840
1934736033
3120240694
9654651560
282615102
13096554225
2178481031
6785629803
10691483825
5486141165
379343399
10276194
1333422
325645708
6962780922
562469987
440804744
6105406513
9705740851
57219586
208216
23784339860
936614823
28630432
411001372
1677396771
514779218
4331046488
43806174
102381530
31555471
1933629428
2695192718
4663064437
2877902045
298624479
1497163743
13474520567
815132550
4978957000
474853285
125783774
501929883
8469240604
3201369170
12582967
1496798975
4035359180
4573091529
7679507843
5812351900
4348488562
4833888765
374269999
2672752755
1251432691
5370052065
247689114
465195
4461375170
2274672903
15139107516
11934546717
4873164622
14882245
17235008990
7636343396
4282374116
122023501
152078506
2227699766
5800438861
5897625063
3985766530
1374665942
135878485
860956451
5425750990
186772167
7681395382
39609096
9868858971
9079920658
5676554210
124612238
2534086
3165901027
172450103
140191661
4159820256
70699121
6121871725
8700395668
4149612156
1390161343
7604541095
8409256299
1595883259
2918706520
2568837262
9650915920
49458848
221326553
3526889699
22187
840010871
742881525
3303045098
6482402324
83416631
2251973217
8820463444
1831194666
2064607058
551643580
1000656417
43732173
960874793
4206456
3226922119
3296635957
10244794784
11525887284
58815905
56896885
5804923219
739623467
4385587533
1758133241
14032342287
547410
1388563279
3100518241
2910804803
775163257
2624995050
9826038266
793040746
5047380393
478715103
4061942886
9594717493
245778655
348660675
187640165
6746661095
2642712323
268755438
5249211201
621044285
7254424571
1963412107
9777632914
2871381901
52435499
5183994
3636032560
189251
2040740393
22396569890
10249013895
485219000
607307343
117945058
4498234344
4873166165
6981375702
6743402877
72101329
37135931
6380592
11127486
6393606981
4760441
1019307748
1036181061
3743299189
2185321786
8550755539
2970893330
341217460
700183845
7936452896
1153036022
504625375
225094945
2175165816
117945018
8289177371
1978884820
2169921441
2787260769
339920
15337933367
3906005727
1845942083
860455387
1776955036
5417029580
25354787106
2166751341
1636796
3477494451
2349108722
673640167
8872818464
1880973289
246458633
3520122345
12715162164
532254694
3181803277
9907025446
880906524
11206894157
156440898
1816641752
4335102444
1136507536
14643304956
2428144549
662109662
110368230
2333662245
6445621479
11427547531
699716328
171392103
66202143
4094058349
3145564244
1181881550
7243516317
6607965365
19306389173
578304774
2134393881
1810081437
862475356
1800257957
1892727416
306064459
1179444477
1106190613
618518081
6722531
118373
16975197642
12062052956
1503765610
205600556
4846974680
194483395
547571667
6057984770
2702158691
2689983879
143652366
7064408798
747405309
488797770
5116854052
4421639304
4504973984
329006951
8163255825
20779891118
1228601790
7983970781
358622658
129390918
5129477309
826782754
8963369990
1279928578
6459860925
1153528981
5694935936
80927683
854599254
5766147165
14858706132
1905808538
4148906382
2285606023
1508807948
974718944
9402839629
2976333716
19332718830
132868168
3033742731
3266487631
14781728184
108088533
8548221
15048511731
12025332476
18974662924
12555147456
2578632298
737000016
1150201463
3362375853
1105575566
721892110
345917445
777875833
7388547252
414314312
9983320
333066782
2429054979
120407009
3152028706
2530147560
246032814
2372507673
4316368182
262052531
273389657
3930490347
526671162
8569428923