link。

当输入为：

1
5000 100
-106 993 327 -336 285 -579 -847 -127 -754 -155 -973 417 -877 -790 76 375 310 17 -524 467 -54 119 -656 799 -866 172 427 671 834 -543 -249 -290 -554 -772 -592 -666 -700 -723 132 220 -438 589 -309 865 -653 -703 -238 -259 551 -929 -564 -621 722 95 304 240 -35 -208 -220 270 234 -290 -671 -154 210 625 -764 349 -676 380 -914 -851 -145 -650 998 -657 549 182 389 -278 -994 272 -672 27 -949 647 -700 -275 -870 257 938 507 351 -85 104 -69 -860 -303 -153 529 -165 887 33 781 -563 -606 904 -437 143 508 363 189 -247 47 -936 -861 337 91 965 -755 144 -416 723 -718 613 -264 -538 -475 -201 8 630 274 -524 804 551 -409 674 306 -37 932 745 -973 -498 995 -493 -570 -764 -500 -278 -815 -380 76 -389 602 800 -578 165 58 -134 -112 -500 -232 -420 -475 503 -949 -492 -316 -439 -155 -788 -782 -692 -622 -414 211 -10 477 814 -875 634 148 -229 -927 186 -399 379 -759 849 810 -914 -554 -504 -7 911 476 -860 -541 992 -103 -291 -126 717 955 -100 -299 735 -518 752 -827 -582 -105 -273 916 624 -866 -723 915 -761 -778 -50 431 -54 51 66 -462 -877 -962 -14 391 1 -59 -226 -137 857 178 -931 849 237 272 102 -660 483 436 788 470 479 205 478 350 79 169 909 433 -293 860 552 173 352 -974 937 499 216 557 -142 37 322 -235 -148 949 -912 -13 -627 -259 -55 863 491 -615 246 -843 541 -503 562 790 -337 914 61 -408 530 -863 -89 257 672 668 968 -484 93 519 -621 770 -119 635 -514 -367 -904 436 -412 -458 525 222 748 -765 31 -322 -67 816 -757 -877 97 -4 240 784 488 152 -350 507 694 -660 446 -832 451 901 -655 354 -312 -509 935 261 -838 -150 -213 385 416 431 -387 442 -333 -13 -522 -760 173 276 642 -831 465 899 -271 453 -683 -846 365 52 -141 253 -539 485 200 834 -554 -6 566 30 -573 675 -738 -286 558 -530 -616 -733 752 966 868 540 -57 -845 -862 -570 -666 699 -95 289 971 -261 648 851 -741 -170 -593 698 -678 280 -445 -734 -702 464 -494 -216 -458 347 372 -427 32 -639 -939 -718 340 3 -97 -498 22 14 -551 -418 364 724 -722 612 378 -486 550 -913 713 109 -592 -183 -933 -743 -146 415 -243 -796 606 28 491 395 -250 99 117 595 976 -908 886 26 -876 479 -360 -275 -712 60 991 -468 199 876 979 686 -12 919 902 -392 -659 -129 105 -377 189 162 878 9 176 -113 -461 742 250 -276 -807 279 875 -767 -324 17 -824 226 489 911 652 -138 -363 -986 -624 942 -30 979 601 -612 -601 257 111 -935 -810 252 -712 -406 150 -649 71 17 -433 277 -211 -353 10 560 -325 656 -22 826 931 785 -343 -297 -299 -657 -341 -688 971 143 -673 255 631 -880 -659 321 252 243 159 -498 187 -178 163 -102 432 450 -418 638 344 494 862 205 -378 -12 914 -58 -345 -393 613 -991 -915 541 -365 37 748 241 -592 30 80 456 -516 796 -109 924 -684 -285 411 487 -448 603 411 897 -402 543 -519 491 237 -965 288 412 717 -526 -95 -180 -309 -46 849 -34 -40 903 245 396 207 -104 925 111 371 298 896 858 709 441 558 -391 610 579 824 -560 -63 -570 252 231 473 57 -60 546 -36 438 -458 225 296 -995 -886 49 964 900 581 -790 -649 499 -199 -869 -302 -802 181 -591 -641 -828 359 400 242 712 443 171 685 481 -312 -393 44 -284 210 621 135 -926 -824 -302 281 222 -916 860 611 201 668 -507 -691 125 858 253 -717 161 -31 -140 403 18 705 -88 -71 617 177 498 800 -133 88 -617 -760 -320 728 -959 -107 555 984 221 -141 266 -650 189 -727 589 -839 84 -472 531 -621 -566 -166 567 -862 355 -548 -511 -972 -782 -656 687 -124 -665 -151 321 697 -275 -79 271 754 -744 -155 -218 -368 -659 -761 -823 -169 224 -132 -263 332 -342 -890 5 -318 931 -800 -379 -64 866 705 -178 -341 -74 -118 397 611 -192 -444 -257 246 -336 -712 120 -69 -524 289 -866 -910 -84 -631 508 -833 505 -513 447 49 -555 -917 -882 -219 -647 203 -587 -546 -711 -507 409 656 -341 -738 -325 55 867 224 686 -536 880 -305 -81 -591 -741 -686 983 678 -271 -60 865 -45 -886 -337 380 810 700 837 792 -893 174 550 524 420 -680 -739 70 828 -490 154 -873 -875 -435 -561 941 14 297 -563 -205 -961 -591 -134 875 -772 -127 270 838 210 928 -674 -885 808 -764 733 -502 -555 460 924 772 -753 790 -357 100 -294 51 660 470 -565 548 844 -973 529 -838 -649 -730 495 907 -496 -25 -396 -589 -809 901 -739 334 -45 -982 -427 -292 -766 490 -993 71 -346 -738 859 -364 236 290 -940 471 50 949 246 688 -307 -4 531 809 -984 779 245 -105 -680 522 -154 -515 847 49 839 41 277 -48 -538 -63 901 -217 923 -811 -685 763 131 -570 -590 -845 594 -694 -8 689 -219 -432 -560 -308 607 -330 692 -184 -152 -272 905 826 -211 139 -413 430 -438 343 -815 93 172 -628 -308 -748 -37 815 733 -75 173 -111 -109 410 -808 490 273 32 825 775 -601 -714 425 -279 -7 593 2 499 -867 539 906 782 -189 -938 363 178 -765 869 397 550 284 997 -307 -180 -854 793 -178 185 -401 -565 311 617 131 -589 313 621 -999 665 442 -25 -399 341 -993 144 240 239 -278 -779 746 -955 205 -779 738 778 -75 161 730 -923 829 -919 149 -207 -935 960 -648 -236 -829 -246 -121 -38 -46 239 -133 244 889 -683 117 764 375 -906 -488 716 -843 691 424 589 540 -867 -252 -182 63 -571 -790 807 122 65 -180 983 -602 326 801 527 869 -548 -609 775 62 -999 -961 -187 159 491 238 -342 330 452 432 716 -329 898 -671 -996 -27 -727 -277 955 -653 869 -742 506 -331 -605 683 455 899 -823 -845 -462 55 14 369 372 218 83 -530 925 511 103 -506 -198 964 -258 -283 -948 309 591 649 822 792 -209 675 527 361 -686 714 927 627 622 -670 -632 563 0 570 687 49 43 -910 -693 669 114 -472 154 -66 -151 454 875 -675 -523 121 -30 107 -936 -439 -403 -841 -546 289 -932 -868 853 -542 909 -222 848 -235 238 604 663 -837 -930 -641 -433 816 427 610 414 936 -158 -249 380 130 406 -964 84 -505 -404 874 -667 -492 -184 307 725 631 -129 722 562 -750 -14 -411 645 142 320 -495 -76 -407 374 -864 460 528 812 590 -258 -768 414 483 648 319 699 -72 298 748 616 290 -22 -757 -405 -604 -206 370 471 623 -667 336 330 -315 976 545 -522 121 -131 -439 -196 -671 137 797 -919 -18 -885 146 -379 642 -25 -758 657 340 -680 965 803 178 -582 -2 -137 -967 786 -221 20 82 -693 -673 364 -81 133 -285 -72 659 672 413 -949 627 936 160 921 844 -748 -615 -101 910 221 -402 -917 23 -159 -475 537 992 319 -148 -672 -352 118 -801 -644 593 -629 665 398 -336 -727 617 763 970 -519 -336 829 128 985 178 -248 70 -312 -790 253 -270 -857 347 902 -109 95 -431 730 -375 -843 -591 -856 -673 801 63 -461 -15 -723 699 -648 -609 -20 706 -962 323 -270 255 180 440 357 178 -143 -324 -46 -872 551 406 -453 -467 925 341 240 498 186 197 211 -343 -806 87 206 -34 962 -631 154 -815 -395 -16 -614 739 260 -209 146 629 -746 116 659 481 -984 -892 818 -735 -273 -164 521 -948 -487 17 869 144 -808 -544 450 619 -122 -451 -158 587 112 -788 -565 -262 -936 -135 -197 -296 470 991 876 -964 -715 -971 -125 909 774 -755 881 -858 -860 -200 -467 233 -859 445 209 822 -201 -532 -322 -961 -942 127 -562 -30 -69 604 171 -455 -377 -38 517 -190 720 -312 781 -227 131 932 629 66 929 894 -365 -486 327 -710 143 -408 471 888 -825 816 -350 -310 538 -679 -705 444 88 -606 -912 -271 -184 -558 611 -949 921 -124 20 144 671 295 -848 328 743 -69 -881 -607 502 -935 348 -862 334 -641 -387 73 -838 416 721 -54 76 422 901 76 -325 -870 -964 -805 715 -547 419 -895 384 466 129 391 198 577 -634 167 62 656 -185 310 -247 -126 844 -198 -190 899 144 94 -116 834 -534 519 462 -786 -948 894 -733 -406 458 -173 -40 588 -46 639 -833 -499 213 723 -511 465 -31 -337 112 -806 -492 177 -126 58 937 891 -174 -115 173 196 -539 596 925 584 -997 -987 -675 -101 -488 -493 256 67 -260 573 68 -859 -339 -675 457 24 370 -655 -105 -733 -342 -550 -795 133 -103 867 567 -816 -913 -466 -586 245 3 -36 -693 -372 638 -436 539 -201 -775 -514 -275 640 -278 105 -1 722 -526 340 -196 -305 287 384 189 -994 -182 -295 -372 -807 908 456 918 796 896 -89 960 182 615 257 935 745 974 -661 611 818 346 -714 -804 643 -550 -528 604 -353 -838 -375 500 430 367 -971 714 348 -817 -36 -93 21 255 759 387 238 -652 149 16 330 -245 387 -436 188 -908 -855 -527 -715 538 -39 -827 -206 707 884 834 321 -4 201 -58 179 -723 -188 718 650 452 -491 -443 -502 -282 -658 490 -16 -176 229 115 -770 420 53 -942 607 479 -182 -436 347 -383 401 623 794 -697 97 -247 -264 712 310 -731 975 -779 863 574 786 -830 -902 -373 -752 -353 195 849 265 -684 77 -653 801 952 621 362 -873 859 100 -232 822 646 840 332 94 -322 11 113 335 -80 893 -917 -458 878 860 -342 -838 -737 585 685 -619 -641 806 -186 791 594 -860 639 -772 -149 676 -277 700 339 527 -383 315 607 60 -283 -298 -875 510 -698 -798 391 -411 860 18 255 144 99 -524 -316 881 -388 -468 -867 -27 228 -81 918 513 -248 660 94 500 -52 46 816 -835 -391 618 748 648 676 350 -829 -472 -473 730 729 951 466 569 606 425 -206 -233 -618 -807 407 -356 467 981 18 807 528 -444 -906 761 640 421 563 416 908 -157 -72 -861 -676 -581 -610 -349 -782 849 -750 -598 -636 562 -596 608 932 -27 653 -884 425 480 -755 529 -711 -873 -795 -87 -421 -931 868 -254 288 314 41 537 408 -487 -290 -643 815 921 -329 -602 190 983 379 71 -688 -411 684 -730 -142 -533 413 193 -240 -870 818 -506 -440 -697 -677 259 -919 -978 -958 -234 637 472 -909 724 -251 -761 -101 103 -1000 464 -418 569 17 -671 297 393 -883 -186 -1 13 139 -632 525 -135 -618 570 -728 -17 949 58 367 -850 358 -568 -403 833 816 -201 453 664 174 113 723 -219 -663 -713 670 -786 5 -189 309 -985 852 41 -871 89 16 -718 -76 751 -591 994 563 986 141 -411 253 200 768 -890 -968 329 443 -338 -833 -157 294 -400 -900 -305 399 666 720 607 79 247 -648 41 419 475 877 -229 693 -377 869 582 568 802 122 -2 635 407 -149 920 907 -66 -177 -725 -273 829 -901 -675 -210 893 361 992 -82 436 459 622 753 343 773 997 -144 794 -882 411 997 542 -453 541 350 475 -77 -873 -656 125 512 457 -184 -165 -267 -317 592 -19 -523 455 93 -938 870 351 54 -631 -82 -380 -269 -162 240 413 -625 -130 -634 877 203 871 -764 901 84 520 -530 -512 884 439 198 581 634 580 530 -361 -14 -650 104 -828 93 419 547 -266 -324 687 -674 -758 -774 -147 666 -625 525 298 -679 594 364 282 -538 478 -208 -44 320 -671 651 -213 851 -565 -884 -213 727 -145 219 -621 -356 782 -326 -860 390 -729 -164 901 757 584 -315 -40 -89 407 -29 -393 106 594 961 523 690 232 690 -613 -533 -71 974 -689 -564 41 615 253 -490 -729 26 781 569 -837 343 423 592 305 937 154 -188 -929 856 311 -825 -505 406 455 30 42 -855 582 -337 -236 51 48 83 858 -403 348 -766 -226 674 -692 -261 649 274 -971 -72 697 766 -765 -482 48 710 414 -68 979 -274 977 929 927 -18 -137 -916 -680 462 -275 369 -173 -549 808 -820 727 -298 -926 219 -487 -445 -727 -315 17 439 -674 327 466 -95 -107 -334 643 731 753 549 -417 -910 894 621 366 -713 -932 653 -947 -946 -421 -947 330 -242 -922 820 39 625 -48 -803 -481 708 632 -727 112 -492 -888 272 -483 -120 -779 576 -399 -28 395 532 591 0 -133 216 -370 -75 38 181 -607 -995 -816 -910 -179 896 120 -756 -400 427 -802 714 69 990 -306 243 -58 337 -797 238 -260 -441 -22 -224 -418 981 767 606 -20 -728 -87 973 -635 -554 -332 16 -639 346 35 69 -117 637 -652 -369 339 -877 -400 783 -667 593 596 532 -161 524 -34 465 -353 740 -848 626 799 611 -968 -677 222 46 -317 -21 -420 -192 171 -101 -1 -697 -12 -597 890 -612 -408 351 -673 -448 -443 535 412 -238 -195 -21 -337 200 994 -408 -542 250 348 917 536 288 885 727 912 678 992 853 -160 960 -970 -625 -147 -159 170 -592 -342 866 832 -519 -220 5 970 394 -486 -278 -347 123 -423 937 -799 -915 -570 115 33 84 61 -175 -613 -377 -737 -849 -288 -724 -885 574 -381 -966 -472 119 -216 -650 135 260 -130 295 -801 286 -249 -961 401 286 589 -109 386 -133 936 -545 624 -362 -109 -113 710 730 -26 -468 178 -962 31 790 519 304 821 -115 60 975 392 -120 -353 -462 49 -533 -888 -62 -53 127 715 398 -553 407 -887 -356 546 -899 68 275 644 233 693 -113 -407 -872 -277 990 -669 128 360 -672 712 -315 -72 745 883 194 -306 821 208 -127 835 715 20 -343 438 344 993 -791 875 727 -732 -252 329 -251 984 881 -794 476 -325 787 -252 -745 178 913 -668 -639 -160 362 -535 -512 -889 -325 -831 984 -916 -749 -589 -447 853 373 -926 -774 53 -602 226 -765 -703 380 687 -760 847 -281 -923 -339 -428 383 -510 -448 623 -371 -990 -421 486 173 -220 359 14 967 372 -191 -841 538 81 -192 960 115 -113 341 117 950 -452 -455 -646 591 618 -788 -739 -642 -286 703 710 334 153 967 -40 893 872 -507 -859 -457 -351 -203 13 256 -154 -758 -840 466 -938 972 808 -155 553 364 715 772 227 -153 985 365 -964 87 889 -652 668 -353 470 -90 22 -909 -699 -400 -610 40 861 925 707 -792 11 907 -892 44 -148 510 -537 397 -597 -458 -647 -94 27 -575 -169 687 734 835 -82 -799 283 -558 61 -787 -207 -876 463 561 -252 286 -640 -478 279 -727 -146 501 -411 639 602 -370 -973 -214 425 -809 395 376 702 -495 235 -779 -368 -515 117 -280 213 -200 -340 -515 650 -518 -350 324 -735 849 789 774 -853 -959 522 151 -406 64 594 144 -565 203 -669 -36 -187 186 571 -665 -77 -488 220 -556 340 900 972 646 -517 -115 -231 -158 -78 302 639 3 -368 467 140 -269 -242 -452 536 366 425 663 196 78 221 -566 761 -289 -700 185 -303 -258 215 -395 -925 549 450 -935 53 779 369 457 -744 194 -106 -949 303 120 -701 -2 527 848 -285 369 633 973 -411 -527 490 437 586 -214 -248 221 -484 -243 857 -742 -599 -239 -92 -43 15 -352 815 -503 -928 -325 323 402 7 925 -33 -649 900 822 -47 -426 -47 -148 -988 911 526 -420 -473 571 683 -743 389 -739 -773 931 368 74 -215 -421 -297 854 -696 213 458 -610 274 -150 167 349 -585 874 -902 827 -340 -839 170 702 -762 -904 209 398 900 239 -100 319 595 132 -305 -39 894 -894 -798 -500 545 587 -751 -200 -973 964 257 552 611 385 -981 -529 -684 124 975 -337 -320 131 881 109 173 377 -781 -645 966 -727 -873 880 693 -384 919 551 -244 -652 -15 335 201 -108 562 -603 -521 -629 751 -278 -614 630 676 252 -612 314 -257 -869 -720 -136 813 -101 -995 -170 -233 -813 528 -498 -249 -978 -884 298 -29 -87 288 -20 -880 -790 601 671 -860 71 -723 -318 501 14 -808 -884 -997 932 -931 348 -843 -552 592 777 384 88 357 66 -443 -888 779 -271 -165 -323 -848 -722 -27 244 -822 -106 -310 -188 213 -42 621 801 186 -407 821 -652 934 381 177 430 520 753 788 -233 473 -745 456 524 -570 459 -396 -249 -971 -68 814 -867 -106 -312 604 -659 969 -871 -669 -832 688 -814 851 155 500 412 134 -475 -585 -612 649 379 -919 520 -340 -668 -306 -296 748 416 -895 -289 203 35 66 -662 -806 5 -132 253 637 -704 728 -77 729 -193 994 13 346 43 321 -814 -239 424 715 -508 103 942 -728 480 -177 678 227 126 749 -835 -850 -793 -421 960 771 150 -930 748 644 -508 67 944 857 756 172 -255 -963 -252 -8 -166 947 -460 966 832 -843 69 -443 639 145 -897 -281 532 -883 -320 297 -104 866 -210 -157 209 -748 214 -283 81 169 755 -927 -847 -208 -876 352 301 -445 577 -502 599 916 -347 305 517 767 71 485 -240 -120 993 925 -726 -60 -643 441 258 318 -76 -543 -572 -994 502 327 780 276 -967 182 -175 997 -856 -515 473 926 686 322 101 -310 265 -322 -978 522 -812 656 -441 -374 -950 553 909 681 131 351 504 -377 -723 669 598 71 803 -929 111 -525 -360 -161 952 532 942 -721 133 158 582 125 -539 686 -641 -423 910 74 -459 815 872 139 965 374 159 532 -212 -496 632 -707 -299 -542 978 -870 657 -155 328 134 543 -518 -662 884 -444 -830 -392 861 970 46 543 -660 933 885 746 -283 -606 -693 -683 -636 378 -507 -19 96 719 894 -401 31 543 452 368 388 -556 -183 -150 156 -935 -78 318 282 -731 -379 77 333 951 -834 743 538 432 54 -621 -693 850 951 251 336 -570 -836 547 -110 -45 -999 887 -260 56 410 47 951 985 -571 -161 131 -657 -940 -897 -882 -818 971 723 618 -807 717 408 674 -917 -206 188 793 354 832 -2 -412 421 997 -553 -339 -193 1000 34 421 -131 -857 -613 -605 -907 -51 641 -107 318 550 -265 -62 -644 278 -168 974 -372 -761 467 -357 176 -347 -447 752 797 -247 82 89 36 -624 -638 919 -34 841 671 801 473 939 800 602 -381 859 383 577 -139 754 -271 -627 724 -554 644 254 -94 -457 -865 -681 -375 -632 -134 922 651 598 -609 644 665 492 -646 409 442 386 -554 -324 -737 560 -85 148 -234 -529 -297 -105 499 -870 610 -613 808 -719 662 687 285 686 -541 171 204 55 543 -495 -753 277 -912 -631 -227 -632 928 561 296 744 211 -268 504 981 715 267 936 986 -571 -778 204 295 275 641 -146 -295 -171 -331 -834 838 272 -405 -392 125 691 -696 -964 -367 -937 -612 -243 244 585 -646 -808 735 -458 671 590 -981 56 119 -220 -43 967 -47 -863 40 -905 -841 248 93 -682 -887 0 187 9 109 -736 333 -254 -97 -707 -370 -618 913 -340 962 830 152 -143 -805 955 270 952 -757 378 -878 -348 107 -88 777 843 454 517 965 -645 -456 -20 -523 -10 781 632 414 872 -663 -529 431 -790 -804 333 711 -602 -35 -286 -38 -475 -27 451 317 -775 273 -412 474 208 842 -508 162 423 126 719 -220 406 178 314 -837 -458 688 -550 918 9 924 -370 892 -423 -846 -694 -605 637 -288 154 973 -95 -176 744 -626 956 -694 97 -781 -968 968 -375 -100 -590 -741 218 -166 881 146 226 -213 593 678 -408 355 800 -319 581 -848 440 -385 -617 -792 -351 75 520 222 -920 -404 95 724 -582 658 621 278 364 -305 752 -960 310 -959 831 594 -118 637 -255 981 -588 -310 713 -579 493 359 -504 -985 -972 886 -471 -723 543 -350 -967 -952 964 149 380 526 26 -330 281 704 -194 -738 -248 751 626 490 982 -824 283 -38 -192 -564 -739 -193 -177 632 185 385 670 902 -480 260 382 88 -689 38 -927 -462 351 -291 -758 765 -539 766 894 -753 -841 -351 947 31 -742 -150 937 -959 262 -302 173 -391 -895 -300 341 -594 -118 -424 -745 -580 -354 939 -156 -977 -361 636 7 123 -391 -81 780 110 835 42 879 -332 184 344 -413 -665 -872 10 -535 -900 -408 -789 191 -143 529 481 -360 225 -288 972 -631 950 643 -428 -411 341 823 -279 -313 -483 356 -54 797 742 -693 949 148 389 189 -102 512 -522 -701 646 -129 793 -612 -467 -783 329 -588 -544 911 -902 715 -997 -74 -237 226 670 -741 619 -266 276 200 31 725 691 384 6 285 588 307 -652 322 -61 -397 -854 -485 139 -834 -84 364 362 849 -715 -604 315 675 508 -246 -211 -860 -529 150 -395 563 -486 -530 -16 435 443 -191 -986 618 -314 -321 698 507 166 -360 -253 388 -313 574 54 478 609 -870 -293 -766 973 -481 380 516 713 180 956 -295 335 306 851 -863 655 -980 763 187 -727 -755 -688 -196 565 928 484 0 445 441 -62 489 -997 -423 31 174 460 -960 -223 596 626 -417 -191 -138 665 -448 631 576 307 65 -82 -647 -96 -841 -628 437 539 131 -922 -259 -259 706 782 -444 865 848 891 -818 -197 -340 -750 -149 -441 168 -40 931 966 405 255 549 -705 -332 641 -676 45 -601 229 337 355 -278 -487 595 641 135 -769 -790 -298 652 310 -779 730 -597 -692 685 354 130 -592 -22 688 -969 377 722 -604 699 -585 -294 237 -108 -571 697 15 817 212 -938 -487 557 253 685 -16 -132 -351 -24 282 575 170 21 -725 0 804 266 -512 -157 481 262 387 335 126 454 5 592 232 -729 -582 -400 742 276 477 224 960 472 512 -915 638 547 -342 -133 -249 -48 490 457 -636 510 381 -115 544 480 -440 -303 234 488 -690 208 -841 83 257 -452 886 -569 827 838 27 -184 168 -525 -696 889 465 -863 -646 -844 749 4 240 -192 -289 -126 211 242 -912 445 -43 -644 693 150 171 217 403 267 -597 -694 936 352 282 525 835 -159 -98 729 -99 487 490 72 -164 546 -231 -565 424 -443 -825 -205 827 -397 20 112 604 213 -243 -938 609 32 758 -353 -38 -650 -984 -647 335 32 -646 -844 131 -3 616 8 -108 833 813 -988 -20 372 784 218 -284 -64 -332 866 -873 -612 -217 -706 -493 -383 723 -240 892 -562 -391 -878 470 -854 -107 -889 38 -100 -182 400 -509 930 527 564 197 75 -659 909 -211 -395 -461 -357 607 353 13 -860 -34 513 217 162 401 809 516 546 493 388 144 -867 -914 -946 530 581 -665 431 -69 592 -853 -986 -921 57 176 -986 -208 -645 180 -912 268 -57 734 615 -74 601 -462 -454 -517 -539 898 -359 -310 -903 856 -29 132 253 -688 -471 -961 778 415 -585 -609 640 -931 498 -682 107 52 -78 227 442 873 -745 -520 -340 -112 -431 586 136 -501 976 -756 -758 862 -427 616 -504 243 731 -301 -625 873 -759 -385 250 41 68 -58 403 928 115 -372 -855 -184 1000 541 402 -750 -791 726 -320 412 -881 -148 598 615 220 340 93 -476 -311 -739 386 -976 -915 89 413 -882 -592 -230 -166 -189 120 -601 -140 293 299 182 128 527 852 648 937 -690 502 -681 527 698 -689 -104 -180 -807 -396 52 279 -794 749 -551 -501 592 765 -417 -185 -273 -319 0 899 616 382 -518 675 -305 562 -102 394 187 975 2 375 803 326 657 -577 -841 -342 241 -893 139 745 -520 -943 607 489 -100 365 -949 233 -43 787 -551 -396 289 -726 -894 713 734 726 -589 -767 338 -411 -56 756 -262 -251 -343 28 497 -138 -838 349 605 -801 -285 -178 -43 842 794 -265 315 -158 174 68 334 705 -91 -542 -305 -494 569 740 -166 -779 -202 551 364 -338 325 148 179 564 11 431 -50 734 -812 -174 366 -364 518 -529 573 347 -194 477 -311 -650 813 544 -575 832 481 183 -508 913 -114 -729 557 223 -542 84 -500 -697 -71 -412 -548 118 319 -26 -541 -621 -703 467 -158 451 -259 -661 284 423 476 -147 -581 243 -267 805 536 -157 643 -235 -78 184 -304 -799 -530 -927 483 -799 -785 291 -268 -930 242 -400 -8 926 -77 -5 418 618 -157 -733 171 -535 559 236 -853 673 567 920 -685 -670 -666 924 768 -952 -308 -634 -472 -391 79 71 164 -752 -164 861 -1000 -922 -479 -528 718 -670 -416 556 -77 455 -150 580 731 -584 -904 -292 792 -645 750 -175 -638 -24 -968 -854 -123 363 -826 690 935 -959 886 668 -699 940 499 -961 -595 563 -801 -3 -436 -256 817 182 -833 -40 -329 78 -520 250 -570 -72 -480 201 690 -617 510 271 -14 -907 586 -566 294 -339 783 157 295 81 -953 632 989 -344 -336 768 -921 -994 -25 761 145 -530 834 -369 978 -583 -814 -219 -106 869 -767 -438 46 -807 -333 -860 -578 -143 -708 717 -953 -605 -853 340 -137 -175 759 633 685 -661 947 17 -879 451 -782 -742 516 -402 18 4 -524 997 -38 585 -374 -644 -21 -804 -235 104 -554 -434 -154 -19 -360 941 703 446 106 860 517 663 -630 826 190 -269 59 -837 -826 165 939 398 -119 -406 375 934 -27 741 390 21 150 -254 199 541 427 44 -220 194 -433 331 -605 -910 831 390 -288 145 864 -619 -925 728 -741 -558 -492 -91 -776 -309 -690 420 310 -911 488 259 -106 -817 -234 841 -916 -414 871 211 761 556 212 145 -678 415 -450 312 -145 189 -396 -171 948 -411 -304 -186 -277 235 -669 1000 433 -788 464 -106 995 922 -926 -374 -675 -739 -401 122 742 628 -255 -781 -937 899 -698 -68 -267 -453 32 -432 -348 780 -966 -227 -227 87 -605 409 -306 -586 584 908 373 -78 -388 -282 296 -790 957 -354 -426 -670 -487 862 -296 -709 344 -306 184 -682 361 693 -576 138 -919 545 -315 524 170 -545 606 267 285 -180 714 759 -955 -798 -221 546 -752 -375 -742 798 -1000 937 430 -656 795 -923 377 221 695 213 -220 -948 -449 86 870 791 580 786 -921 -953 703 488 -971 305 -215 603 129 229 641 952 -255 -423 -711 -413 -93 712 -173 379 -729 -490 -171 440 -321 280 -386 -477 -382 -567 -552 -119 -67 689 -161 95 -522 194 -430 827 -456 431 836 -288 400 -311 -61 846 -652 152 -212 844 184 -466 605 -464 -173 -498 -532 -325 -822 -117 9 1 46 174 -867 792 100 -581 -132 -750 -165 -123 161 -729 192 770 -936 33 -688 767 -991 -114 837 122 751 -776 -635 335 -327 -22 912 68 -339 660 290 -301 957 -211 -417 211 229 740 157 449 -748 440 985 -99 -885 -335 -937 -356 -745 -191 538 -365 930 -855 972 -782 798 -993 -261 825 -448 364 
1 1708 4625 -147
1 2551 3673 -952
0 2516 2834 -381
1 1578 4035 -155
1 220 4588 -818
1 382 3946 134
1 2896 3158 -171
2 957 2357
0 2227 3847 -749
0 1368 4761 -600
0 353 396 758
2 1029 2002
2 261 1369
0 540 3730 -931
2 2253 4119
2 2608 4436
2 90 2176
2 287 4223
1 2338 2646 -106
2 310 1759
0 2761 4627 -116
1 1936 2643 -228
1 153 4289 667
1 1633 4370 638
2 886 1512
1 392 4522 644
1 690 1587 208
2 1572 3505
1 3458 4787 -677
1 3117 4300 -663
2 623 1865
1 93 2659 963
0 2233 2867 272
2 1533 3025
2 3320 4115
1 124 4515 915
0 2524 3941 -145
1 2253 3259 426
2 1837 2736
2 3374 3804
0 1175 3332 -298
0 285 2271 364
1 2275 2388 0
0 1628 3180 -870
2 3527 3930
1 670 2182 -797
1 2178 4731 559
0 1912 4965 -731
2 2306 2831
0 1117 4238 874
0 2963 4420 -211
1 9 3228 40
1 325 2516 655
1 1359 3327 557
0 859 3554 239
1 469 4816 930
0 818 1131 -829
1 155 4201 -901
1 843 4672 446
2 1358 2849
1 437 3110 -148
0 202 867 -747
0 2277 2919 988
0 2221 2419 209
0 2774 3680 228
2 2572 3489
2 1255 2290
2 643 4514
0 4386 4968 -143
0 1477 3229 -964
0 1823 2759 -9
1 407 2760 -54
0 1339 4666 875
1 2494 2718 882
2 750 2658
2 2080 2321
2 3439 3512
1 1440 2508 -42
0 3365 3606 949
2 3807 4385
1 648 2664 -247
1 285 2368 -907
1 1781 4444 -981
0 647 3936 -826
0 1334 1526 -435
1 2183 3496 -752
2 1709 2928
1 2200 4934 -225
0 3448 4439 -513
2 388 3127
1 3009 4620 227
0 806 3583 -592
1 1534 1553 246
1 2644 4347 874
1 2304 3442 -422
0 173 413 -478
2 1802 2583
2 2239 4052
2 1291 4471
0 1564 2962 53

时，标准输出应为：

Case 1:
1426967753
490721334
866878900
1421112758
1227532603
1717178035
3145438665
1238572923
43699392
3343841685
568114404
2893079618
348834442
3694484784
9061775
8494100
281073886
760615632
234401632
312521566
1789831669
2106596430
185281250
56656250
443296875
2181001488
4764021237
463827808
561394020
1019359207

而这篇题解输出为：

Case 1:
1426967753
490721334
866878900
1421112758
1227532603
1717178035
3145438665
1238572923
43699392
-951125611
568114404
-1401887678
348834442
-600482512
9061775
8494100
281073886
760615632
234401632
312521566
1789831669
2106596430
185281250
56656250
443296875
2181001488
4764021237
463827808
561394020
1019359207