fork(1) download
  1.  
  2. //Author : Ujjawal Dixit , ABV-IIITM
  3. //Task : GCA QUESTION 3
  4.  
  5. #include <bits/stdc++.h>
  6. #define MOD 1000000007
  7. #define MAX 1e9
  8. #define MIN -1e9
  9. using namespace std;
  10. typedef double ld;
  11. typedef long long ll;
  12. typedef vector<int> vi;
  13. typedef vector<vi> vvi;
  14. typedef pair<int,int> ii;
  15. #define getcx getchar
  16. #define FOR(i,n,m) for(int i=0;i<n;i+=m)
  17. #define For(i,n,m) for(int i=1;i<=n;i+=m)
  18. #define max(a,b) (a>=b?a:b)
  19. //#define min(a,b) (a<b?a:b)
  20. #define countbits(num) __builtin_popcount(num)
  21. #define countbitsll(num) __builtin_popcountll(num)
  22. #define s(a) scanf("%d",&a)
  23. #define sll(a) scanf("%lld",&a)
  24. #define p(a) printf("%d",a)
  25. #define f(i,a,b) for(int i=a;i<b;i++)
  26. #define pll(a) printf("%lld",a)
  27. #define pln() printf("\n")
  28. #define getstr(in) getline(cin,in)
  29. #define getc() getchar()
  30. #define uj() int t; scanf("%d",&t); while(t--)
  31. template<typename T> T gcd(T a, T b) {
  32. if(!b) return a;
  33. return gcd(b, a % b);
  34. }
  35. template<typename T> T lcm(T a, T b) {
  36. return a * b / gcd(a, b);
  37. }
  38. inline void in(int &n)
  39. {
  40. n=0; int ch = getcx(); int sign = 1;
  41. while(ch < '0' || ch > '9') { if(ch == '-') sign=-1; ch = getcx(); }
  42. while(ch >= '0' && ch <= '9') { n = (n << 3) + (n << 1) + ch - '0', ch = getcx(); }
  43. n = n * sign;
  44. }
  45.  
  46. int Size,arr[1003];
  47. int Fsize,frr[1003];
  48. bool func(int special,int mid)
  49. {
  50. //printf("sp and mid are %d %d\n",special,mid);
  51. Fsize=0;
  52. for(int i=1; i<=Size; i++)
  53. {
  54. if(arr[i]<=mid)
  55. {
  56. //ok...all pancakes can be finished within "mid" minutes
  57. }
  58. else if(arr[i]>mid)
  59. {
  60. //To be transferred
  61. int diff=arr[i]-mid;
  62. Fsize++;
  63. frr[Fsize]=diff;
  64. //printf("pushing %d\n",diff);
  65. }
  66. }
  67. int idx=1;
  68. while( idx<=Fsize )
  69. {
  70. if(frr[idx]>0 && special==0)
  71. {
  72. return false;
  73. }
  74. if(mid>=frr[idx])
  75. {
  76. idx++;
  77. special--;
  78. //you have done this part
  79. }
  80. else
  81. {
  82. frr[idx]-=mid;
  83. special--;
  84. }
  85. }
  86. return true;
  87. }
  88. int main()
  89. {
  90. int t,D,P,c;
  91. in(t);//scanf("%d",&t);
  92. c=0;
  93. while(t--)
  94. {
  95. c++;
  96. Size=0;
  97. in(D);//scanf("%d",&D);
  98. for(int i=1; i<=D; i++)
  99. {
  100. in(P);//scanf("%d",&P);
  101. Size++;
  102. arr[Size]=P;
  103. }
  104. int ans=1000006;
  105. bool fnd;
  106. for(int special=0; special<=1000; special++)
  107. {
  108. int low=1;
  109. int up=1000;
  110. int mid;
  111. while(low<up)
  112. {
  113. mid=low+(up-low)/2;
  114.  
  115. //Can mid be my answer ie can we have atmost "mid" non special minutes
  116. fnd=func(special,mid);
  117. //printf("special is %d mid is %d and fnd is %d\n",special,mid,fnd);
  118. if(fnd==false)
  119. {
  120. low=mid+1;
  121. }
  122. else
  123. {
  124. up=mid;
  125. }
  126. }//EndOfBinarySearch
  127. //printf("special %d low %d\n",special,low);
  128. if(special+low<ans)
  129. {
  130. ans=special+low;
  131. }
  132. }//EndOfSpecialLoop
  133. printf("Case #%d: %d\n",c,ans);
  134. //write<<"Case #"<<c<<": "<<ans<<"\n";
  135. }
  136. return 0;
  137. }
  138.  
Time limit exceeded #stdin #stdout 5s 3108KB
stdin
100
1
3
4
1 2 1 2
1
4
6
6 5 4 3 2 1
1000
955 63 312 385 306 641 627 893 606 118 27 729 133 921 700 36 502 639 60 263 237 207 518 589 564 62 878 726 312 888 691 156 576 384 941 789 292 570 955 26 105 883 40 454 104 8 69 837 7 708 906 767 246 56 742 36 679 669 594 238 584 359 231 486 237 148 656 799 466 191 225 579 204 672 231 621 144 74 474 224 629 555 853 70 810 486 805 656 540 69 926 356 866 381 484 627 100 207 230 544 366 608 731 975 350 132 454 115 649 763 993 917 217 350 913 13 714 157 543 726 589 34 899 623 810 258 698 268 810 915 389 567 112 710 695 549 485 695 176 523 282 206 29 759 239 200 796 543 773 638 653 485 736 134 878 742 766 819 9 580 80 93 592 849 726 282 289 861 615 418 226 649 73 109 21 865 483 128 156 361 604 215 423 346 417 611 859 132 816 216 702 116 742 3 10 577 482 884 3 52 991 736 917 666 827 650 335 839 881 552 80 19 167 591 52 377 425 919 19 947 715 139 381 217 603 472 819 258 73 313 175 680 219 800 138 646 309 456 19 543 910 387 228 694 450 756 941 928 990 935 375 673 321 504 107 641 918 162 51 505 600 569 10 701 858 938 768 291 914 272 111 68 116 843 865 146 255 359 636 924 772 871 875 630 395 201 746 881 789 577 782 876 90 895 972 761 722 835 512 482 947 356 85 214 374 771 329 721 386 142 516 346 606 126 453 581 840 592 213 751 22 976 597 923 434 343 350 208 673 943 563 169 43 198 459 375 100 424 580 766 901 159 206 889 714 655 865 68 978 850 891 638 806 680 130 618 20 661 898 900 820 494 463 862 667 390 190 245 674 237 823 552 834 21 53 489 990 646 777 857 121 379 281 639 545 929 740 124 279 413 930 48 608 793 276 667 379 595 708 156 287 543 404 741 814 971 28 438 200 129 907 362 639 184 616 302 823 32 774 963 909 229 281 273 729 650 644 112 942 189 880 749 150 824 193 123 307 314 948 655 319 499 882 84 140 383 210 102 103 226 14 464 904 778 965 320 105 344 258 896 860 903 682 643 151 261 864 356 441 148 282 177 989 465 809 890 624 668 651 493 936 566 258 757 91 867 860 248 674 520 843 214 66 334 873 593 42 624 289 500 938 625 147 90 486 129 608 872 320 822 617 599 404 664 6 803 865 591 993 44 587 307 146 506 29 592 935 711 204 826 871 922 161 676 484 355 970 167 946 615 421 25 699 897 97 247 640 947 308 596 668 257 727 51 117 378 753 693 140 15 919 456 200 722 966 721 771 433 160 500 657 774 874 666 869 826 557 13 451 374 110 13 218 136 47 52 481 908 959 795 625 441 484 942 76 58 897 439 151 510 87 689 100 971 13 696 636 717 978 361 741 845 275 134 398 18 689 200 398 826 357 953 890 298 945 893 50 984 930 909 342 838 954 438 681 250 666 387 994 533 309 581 88 628 54 443 198 855 528 470 316 573 650 296 749 833 146 696 96 999 665 701 226 679 114 426 551 642 760 294 246 947 681 975 377 276 11 858 911 688 617 87 410 843 321 72 413 779 702 76 91 707 698 891 727 929 257 717 2 963 520 486 363 435 750 654 529 855 755 824 452 132 248 917 160 979 932 49 677 430 769 716 123 273 722 655 340 513 186 973 218 445 444 964 958 212 499 170 615 314 737 886 624 75 819 926 702 557 919 334 527 863 900 923 166 351 161 685 107 670 485 945 246 448 168 620 911 864 113 940 165 788 350 295 53 718 217 236 336 435 98 365 185 707 570 196 245 959 348 236 503 320 271 573 2 32 913 619 288 604 506 578 353 162 637 96 459 638 680 322 695 531 971 756 38 394 990 688 763 704 981 61 986 544 432 263 639 572 625 945 857 886 559 989 646 774 600 560 108 21 70 614 182 914 555 218 501 485 483 920 89 510 25 514 681 503 558 362 104 467 547 478 165 946 343 11 590 555 307 219 314 9 523 195 711 947 107 333 232 368 322 453 681 313 52 548 272 785 798 116 46 700 753 262 280 697 316 916 917 606 98 88 649 123 377 545 258 896 976 975 702 586 621 387 753 441 820 362 554 905 702 14 224 734 975 363 55 49 102 237 880 317 515 162 346 915 127 933 440 462 591 69 644 362 534 583 603 28 807 481 987 175 190 756 985 51 856 454 485 435 430 686 987 230 811 429 783 588 506 737 248 896 657 888 407 981 894 142 470 493 321 973 898 998 581 386 8 515 255 387 961 61 933 916 606 438 440 862 355 779
15
6 503 376 42 29 763 483 390 847 600 627 638 381 605 622
1
5
15
761 356 478 746 912 966 972 442 489 521 340 898 167 893 173
1000
119 435 959 207 599 23 84 835 852 548 313 484 864 883 880 371 242 981 596 616 47 735 651 237 634 165 415 703 720 81 197 107 160 473 601 50 719 211 677 928 540 218 774 763 408 157 184 777 835 385 400 628 387 641 671 133 419 14 60 103 785 959 910 261 527 205 984 728 399 791 819 821 397 998 649 465 779 992 694 231 805 414 565 858 667 144 875 775 873 512 834 962 318 714 362 59 556 485 62 968 163 363 454 194 276 963 737 916 927 155 194 494 788 845 40 24 181 961 727 21 331 894 3 725 69 100 657 3 859 503 817 679 441 780 920 920 60 157 765 393 438 757 759 766 602 65 653 169 565 52 380 279 548 149 744 472 80 245 497 135 579 372 791 301 17 63 986 638 214 870 396 8 575 716 454 973 732 25 125 528 203 268 418 898 457 895 694 288 998 673 278 20 564 924 271 170 485 480 411 617 27 111 832 677 977 936 925 160 39 973 334 212 741 924 644 561 816 317 968 365 251 909 518 613 227 641 557 561 669 520 727 519 215 167 695 938 382 29 772 603 3 395 801 601 491 729 990 369 891 793 309 524 441 563 692 125 700 559 397 613 840 866 303 610 47 781 994 150 359 137 59 155 361 3 672 724 479 72 7 425 513 664 153 8 316 154 252 941 134 814 159 951 137 722 978 829 620 244 829 988 333 845 371 70 907 944 242 208 698 884 351 128 464 447 826 202 696 186 417 601 174 324 825 261 427 233 148 935 469 417 432 361 878 938 931 888 73 171 387 211 309 552 1 533 390 639 743 694 483 15 946 388 60 324 985 459 216 254 900 294 498 498 697 121 253 379 646 9 844 554 458 937 710 650 494 240 681 702 680 538 952 877 640 728 302 81 843 358 649 970 573 69 245 87 300 388 111 560 845 329 302 755 519 866 405 29 265 917 459 628 253 150 728 233 455 755 761 182 742 526 232 301 367 878 608 646 942 603 387 466 650 5 388 319 784 110 643 12 961 498 424 829 614 172 838 558 628 838 188 656 161 167 255 236 431 742 767 817 868 104 147 816 727 192 145 443 316 150 351 962 362 860 458 929 366 797 738 84 461 762 855 389 688 308 763 96 742 620 352 224 442 806 77 142 571 792 92 206 424 393 46 719 42 608 952 59 237 629 37 290 342 393 128 955 950 325 842 963 128 723 394 317 295 1 89 895 514 814 442 960 208 8 528 808 284 701 22 251 843 786 142 539 48 691 842 751 833 823 366 786 203 731 96 332 534 767 946 968 235 443 884 339 186 61 310 42 368 177 457 612 869 94 385 109 333 244 491 878 404 314 718 141 20 93 794 466 249 365 297 373 418 106 370 420 937 693 258 177 531 16 54 698 401 717 940 611 803 165 218 214 490 350 633 714 321 530 868 470 104 629 828 207 608 370 506 988 426 703 217 879 44 863 904 276 655 88 49 77 935 855 671 381 941 652 991 399 518 623 847 365 67 751 71 891 201 245 721 547 126 312 34 486 547 788 62 609 84 94 295 139 885 123 712 101 931 97 215 934 105 675 133 833 988 306 902 774 554 274 186 863 299 62 55 367 877 342 777 259 296 207 469 466 883 150 632 548 867 978 723 701 841 461 429 935 565 979 359 928 420 252 510 882 206 922 995 248 240 440 403 980 377 731 896 485 734 170 472 819 590 6 417 806 383 193 174 69 468 620 552 317 322 661 300 163 368 121 243 191 134 750 777 15 128 848 996 171 162 671 117 868 454 357 541 954 492 511 351 275 229 134 82 408 230 285 817 526 819 90 303 712 880 493 214 370 101 104 196 974 965 848 789 85 962 798 241 413 33 443 272 435 848 806 478 242 780 333 375 818 586 809 132 375 637 657 904 614 424 794 575 200 808 307 630 729 717 790 295 821 432 372 141 240 154 195 852 788 120 653 257 968 965 395 517 589 692 42 885 802 670 407 179 392 582 857 687 503 295 167 681 470 647 427 852 318 961 872 280 740 127 238 77 384 364 987 699 405 305 642 857 582 849 325 695 658 921 459 290 622 970 686 48 212 119 222 644 595 627 986 667 219 578 316 679 839 720 472 798 881 658 918 659 744 743 840 542 229 742 483 233 150 371 811 848 546 660 126 781 602 871 5 797 518 348 165 368 914 355 147 911 291 209 757 106 22 614 833 964 167 242 636 199 122 655 185 318 910 924 96 303 346 477 434 11 443 410 741 706 21 322 631 974 236 22 641 900 980 627 50 521 92 900 11 491 491 660 859 895 928 652 376
1000
117 174 9 994 927 465 854 351 718 169 419 179 121 419 915 61 343 320 705 334 199 91 966 224 727 978 67 172 183 733 277 245 559 462 427 606 975 263 742 468 947 315 66 635 174 88 146 811 800 784 874 434 596 543 817 557 172 25 257 685 870 441 32 778 642 216 380 449 787 577 825 927 481 946 65 799 32 965 962 615 723 306 442 64 145 919 616 931 411 534 8 909 336 506 291 979 68 746 653 976 92 291 382 248 523 295 797 995 288 208 710 945 655 67 453 415 590 200 618 435 179 205 558 66 146 223 177 974 147 929 930 214 740 384 122 365 588 951 130 639 370 837 573 955 349 431 754 919 514 156 65 608 138 573 800 504 680 27 398 129 33 663 144 97 818 860 451 115 106 492 205 399 526 852 754 338 800 209 593 818 903 647 302 116 783 951 124 586 112 11 852 469 727 402 881 186 358 322 304 303 365 877 109 318 340 202 929 141 229 275 430 577 973 88 425 751 811 389 477 932 260 284 638 145 625 707 748 484 588 195 994 564 717 957 63 854 611 501 889 527 571 127 646 757 793 139 914 690 332 922 453 545 182 331 689 817 97 635 385 700 25 603 59 661 250 976 306 940 244 906 990 17 716 335 520 643 799 464 260 107 578 563 862 683 658 687 732 37 80 67 689 935 519 498 687 787 198 226 891 839 493 221 941 162 385 483 38 358 507 787 668 180 729 349 696 289 877 281 946 138 700 714 397 933 97 334 551 795 132 476 942 182 847 433 558 806 639 702 321 814 598 717 245 728 762 94 647 175 227 716 946 371 281 614 312 870 272 938 908 22 532 911 767 642 888 618 907 145 955 420 990 533 680 694 664 830 983 16 443 11 638 949 47 489 673 634 305 122 361 759 633 258 29 795 72 39 200 918 982 10 507 553 543 824 930 589 521 138 891 158 228 409 991 998 45 883 183 563 186 427 210 442 516 675 685 952 313 660 292 300 962 457 414 249 576 889 61 407 189 353 247 304 336 9 898 244 100 890 925 739 624 705 233 438 466 873 687 748 751 634 509 321 955 792 143 124 615 20 697 184 599 422 860 412 625 562 695 431 489 151 787 936 817 924 973 679 922 337 845 679 964 198 458 327 430 739 703 329 455 856 923 850 306 538 872 859 886 849 586 524 88 401 373 568 751 467 198 74 2 845 538 896 664 963 250 702 588 594 729 848 34 948 352 235 290 768 195 80 653 984 236 83 706 522 604 997 699 357 502 228 296 868 916 902 951 799 316 942 516 321 95 448 520 691 338 326 847 809 936 430 351 760 204 494 247 728 663 50 558 334 959 574 731 456 894 9 415 643 764 688 732 115 526 295 876 140 494 906 43 501 856 47 260 252 134 827 958 448 867 215 332 947 590 263 188 729 838 352 800 199 30 153 90 935 449 567 689 301 4 406 111 490 75 236 601 434 222 36 617 719 872 732 644 714 880 780 853 167 741 434 504 774 161 289 297 293 990 384 676 549 851 959 714 547 703 361 923 10 294 688 342 743 940 128 47 523 654 374 982 851 40 34 543 841 620 837 756 772 872 885 715 405 609 466 865 711 199 918 498 77 611 120 912 886 498 485 86 922 296 527 743 208 271 491 254 900 505 747 637 676 853 451 821 690 674 952 600 453 872 917 536 547 802 185 982 547 376 728 493 394 784 207 927 334 789 747 99 512 990 554 934 799 484 584 290 395 861 466 53 743 502 598 265 93 741 499 473 626 949 293 180 851 750 706 781 2 403 949 6 525 556 889 684 588 199 191 425 125 179 249 772 40 215 273 529 190 669 920 378 106 464 683 326 663 750 238 647 730 414 937 861 856 61 380 662 374 433 853 815 285 195 709 316 376 737 923 965 399 725 601 138 385 312 190 179 338 47 586 60 907 974 667 640 393 529 922 757 895 100 761 929 152 745 933 990 12 297 585 525 590 339 266 474 109 744 567 157 779 437 308 550 476 777 979 770 549 172 340 385 766 643 502 73 389 404 507 348 803 885 72 80 572 611 728 280 624 421 216 933 557 312 845 256 712 443 682 355 876 996 364 715 190 194 640 74 159 238 572 335 777 154 878 831 207 635 521 272 404 916 183 557 627 443 409 298 745 434 667 831 150 780 639 215 286 463 859 747 149 445 716 790 891 192 752 508 909 750 463 123 328 362 93 900 782 575 692 986 347 48 466 104 344 306 127 265 520 396 387 772 428 488 336 263 964 496 299 399 523 132 27 183 31 800 71 771 644 238 707 862 554
2
2 1
1000
748 423 250 943 629 778 845 267 384 581 513 232 863 435 542 875 561 864 850 898 506 45 146 636 232 476 121 324 995 854 649 628 116 330 235 452 290 737 939 215 109 291 334 745 682 503 162 640 416 745 689 664 424 637 846 320 124 126 505 549 674 40 8 12 488 793 286 5 385 82 25 28 18 256 334 941 442 967 724 593 65 141 776 252 26 633 648 438 355 498 819 748 804 248 664 631 537 32 745 833 730 442 892 964 511 133 736 944 453 823 470 835 868 400 32 104 441 843 559 805 759 464 275 926 423 999 680 483 817 856 402 539 995 940 824 584 943 653 597 468 126 397 775 5 918 200 196 89 748 546 207 513 334 314 169 126 305 215 979 668 259 539 508 497 441 125 133 848 137 172 450 325 315 336 469 588 440 648 28 810 648 117 613 810 247 281 352 965 166 313 124 124 103 595 498 583 375 546 599 5 500 128 362 188 949 779 490 351 590 853 430 120 80 185 490 666 592 311 321 306 966 642 493 750 951 970 642 478 862 54 637 788 722 67 628 47 716 508 413 946 703 20 141 345 378 516 265 179 929 649 858 572 323 847 708 352 469 290 406 38 975 187 81 816 324 925 726 834 540 626 399 739 16 177 886 921 441 653 276 824 55 854 539 928 548 720 288 668 181 205 663 194 523 83 468 963 508 902 843 643 605 862 199 465 267 6 186 389 775 608 875 774 908 382 147 251 137 357 936 283 26 607 544 144 503 194 345 564 245 63 387 342 96 370 871 893 737 405 285 598 812 811 772 509 605 986 822 522 230 223 964 238 753 662 24 72 710 75 975 133 147 908 650 399 718 373 680 225 431 208 324 664 318 284 560 341 522 735 259 640 803 697 666 826 438 795 335 868 473 258 127 467 135 287 452 621 441 2 337 922 828 632 760 463 255 226 531 207 96 447 64 42 550 474 714 31 667 496 287 798 677 769 966 831 479 595 873 515 411 388 556 332 83 714 653 592 376 190 794 97 229 934 502 760 950 53 900 168 798 360 620 509 237 514 180 446 505 125 321 545 803 220 685 286 400 470 660 93 853 370 394 192 911 484 826 981 90 442 857 848 418 364 997 126 889 241 177 989 134 562 207 335 485 958 639 875 577 926 585 125 884 135 217 148 189 368 486 933 72 33 116 38 731 760 218 757 363 287 788 413 411 567 965 285 381 724 253 573 531 784 55 83 252 495 940 112 747 137 406 550 931 577 893 411 928 234 803 719 646 389 240 934 76 85 991 785 916 567 33 844 879 721 503 794 755 703 693 889 72 115 54 664 399 155 780 111 357 282 613 875 977 909 980 655 197 856 523 625 747 472 5 277 154 79 854 834 250 405 781 846 737 42 128 711 139 515 903 997 767 381 320 908 708 483 945 583 796 113 829 635 512 843 792 924 888 884 183 221 334 390 549 524 363 476 208 847 235 876 62 597 670 980 266 395 245 462 441 893 861 162 996 325 25 645 389 369 745 577 506 195 308 532 528 517 228 197 117 27 868 527 142 964 984 709 734 530 508 715 739 100 268 766 681 942 253 990 429 894 708 412 929 183 135 829 990 385 882 566 495 299 753 778 59 386 442 384 215 197 65 154 763 829 405 515 134 833 127 551 183 603 920 933 811 821 912 964 472 316 787 40 909 316 554 242 672 152 275 436 754 845 128 199 186 2 889 652 883 867 714 395 67 685 478 306 56 191 647 238 998 446 998 394 577 268 854 995 937 455 129 520 461 753 216 115 773 427 404 516 925 534 281 222 819 919 440 928 858 562 363 389 608 410 398 229 884 160 489 629 738 492 790 184 486 462 364 321 804 201 615 886 660 412 921 187 214 191 386 491 98 361 876 496 869 702 151 394 603 771 283 24 959 584 788 172 239 587 888 505 144 538 111 721 627 388 427 909 22 665 158 573 96 637 958 806 591 486 363 227 835 833 934 879 676 41 362 717 133 240 939 38 744 345 76 62 418 26 683 886 371 384 753 25 590 75 582 384 615 348 795 238 370 1 777 734 49 442 64 291 133 796 728 484 591 913 58 748 231 8 713 836 252 424 992 879 903 149 619 702 410 235 90 614 656 728 464 416 326 522 754 299 576 134 861 474 540 980 359 14 588 427 164 548 678 299 306 661 696 265 339 873 140 794 137 322 752 685 978 477 171 432 485 72 429 365 739 188 687 969 478 83 588 171 334 574 229 265 72 985 670 985 51 596 936 222 640 776 80 99 624 262 23 853 102 300 507 129 244 337 618 505
4
9 9 9 9
6
5 6 9 6 9 6
5
8 8 8 8 8
15
754 17 91 704 890 286 502 117 199 325 16 436 663 311 116
1000
24 333 798 971 569 236 78 444 865 583 670 616 48 457 968 498 676 701 588 340 216 194 909 108 671 87 51 383 446 427 831 219 295 356 279 686 466 820 121 751 334 117 455 656 890 786 302 839 745 218 552 704 362 829 308 588 989 689 836 973 144 873 667 106 914 119 229 497 802 305 508 355 911 525 107 282 385 112 586 582 56 532 581 106 649 324 39 839 529 503 117 817 424 240 546 255 241 355 593 392 502 7 450 748 157 792 345 331 227 111 937 450 491 773 671 596 260 113 467 485 25 544 980 137 885 327 870 479 703 633 698 374 783 659 841 316 716 34 942 561 635 190 373 162 686 933 358 661 339 623 131 941 596 808 331 558 338 608 747 222 257 547 718 452 712 554 991 119 158 943 808 738 324 545 161 697 488 487 415 515 852 756 223 622 646 736 356 965 325 227 581 230 433 828 782 394 965 391 75 722 221 49 302 520 609 15 639 136 72 412 94 679 53 3 414 14 665 716 264 426 993 478 739 101 186 10 67 677 782 770 987 303 615 229 566 518 739 477 941 727 604 607 457 302 968 18 853 346 993 738 413 911 781 605 340 973 802 471 568 654 289 756 947 382 752 708 209 350 45 359 426 181 121 956 243 832 799 487 135 860 363 227 456 734 196 23 288 912 269 705 153 553 749 588 666 685 480 76 643 695 824 408 353 934 852 193 17 623 353 759 107 230 631 88 717 609 660 611 698 135 420 226 931 978 136 929 815 860 472 172 260 318 57 783 60 95 969 424 265 115 522 415 90 631 528 242 860 256 333 675 367 767 517 466 824 281 240 451 752 969 733 231 580 22 149 972 403 428 576 155 850 62 524 570 951 318 77 949 106 331 429 660 589 707 247 478 959 946 7 350 974 778 423 847 677 315 467 306 485 443 714 971 879 23 292 757 197 617 426 604 578 662 384 583 634 603 260 267 195 459 554 893 895 25 427 418 540 986 600 375 878 18 341 741 819 321 428 538 986 142 592 677 421 429 80 535 198 540 744 756 479 938 662 235 958 199 355 999 790 62 947 257 278 311 894 935 857 757 784 281 298 670 35 310 522 873 238 203 786 280 496 411 333 565 26 297 823 414 26 996 61 494 325 343 661 18 531 846 174 701 774 834 341 901 717 23 912 138 73 611 311 789 947 834 308 588 186 513 614 194 493 956 454 494 411 501 266 305 1 853 848 785 241 122 380 500 355 718 247 941 884 817 224 777 645 269 902 685 464 159 874 744 326 99 277 241 589 944 113 827 793 483 35 205 652 768 599 602 599 140 749 587 395 498 469 469 67 75 963 576 270 749 978 625 30 483 727 559 412 295 353 779 810 730 215 127 998 737 580 855 310 197 779 832 643 989 549 344 948 372 228 405 298 947 558 507 182 353 232 362 832 240 42 546 901 225 845 408 760 890 561 477 28 331 117 602 671 151 89 70 808 275 788 117 627 123 73 359 104 143 175 953 512 70 309 708 230 345 40 674 756 144 975 74 815 256 734 897 413 611 846 506 738 325 323 200 710 97 218 593 847 604 284 235 791 454 357 589 845 203 519 228 545 786 486 439 410 227 272 217 621 649 886 26 937 162 969 69 24 831 737 765 86 615 209 801 697 975 550 197 438 549 35 772 428 555 381 560 170 724 933 685 255 687 758 562 309 138 375 887 205 471 413 169 540 320 163 320 278 388 933 83 9 254 671 615 461 767 49 612 546 692 760 936 997 363 706 441 330 657 814 942 875 869 824 503 885 940 462 65 902 874 394 893 135 119 124 598 375 471 734 724 130 122 80 902 371 189 928 137 504 879 213 47 480 237 304 943 800 267 930 925 940 116 894 133 968 870 870 487 591 686 460 630 281 438 931 287 294 489 862 859 461 516 1 608 900 305 599 727 605 183 364 339 839 560 715 838 143 119 82 855 162 173 171 625 175 515 705 484 460 949 605 27 654 805 148 312 436 543 51 244 211 65 372 549 559 598 5 247 963 725 903 78 418 327 597 732 717 650 401 232 544 663 171 822 843 469 351 918 728 316 146 85 236 158 794 498 509 369 950 750 484 126 43 382 170 615 901 904 535 281 738 832 113 756 794 847 314 113 325 838 130 726 688 760 604 562 919 251 831 778 903 616 985 154 697 710 969 430 795 749 369 622 71 164 32 882 283 74 570 819 448 547 736 778 483 581 903 147 146 521 520 650 308 618 747 82 346 126 181 386 898 936 424 869 683 510 528 980 258 762 859 794 862 304 466 545 608 755
1000
468 678 151 842 773 323 133 579 127 681 782 123 503 326 230 77 235 22 780 677 71 802 743 672 307 351 139 503 798 870 370 51 572 125 402 358 427 826 40 977 964 814 148 947 764 54 219 971 125 988 737 931 687 786 166 453 590 408 590 317 180 528 935 533 947 230 68 519 9 475 983 845 276 369 62 178 635 549 996 785 534 433 594 69 45 479 319 328 779 842 262 730 586 523 300 561 549 393 861 803 617 777 477 282 52 783 652 302 993 882 322 619 107 223 607 890 306 780 940 202 44 81 518 902 847 791 776 670 6 23 851 133 934 969 695 669 690 725 658 32 962 919 923 236 112 747 905 643 429 970 182 445 755 519 282 912 368 867 873 169 562 26 904 63 715 62 11 16 301 93 79 584 712 870 848 638 941 792 838 469 371 798 228 87 706 885 938 931 365 416 310 932 975 451 134 265 453 825 464 707 281 517 812 675 696 912 894 849 470 247 889 383 35 608 696 276 495 858 579 793 483 256 695 612 49 903 209 202 265 698 132 372 776 187 715 438 192 897 892 372 924 512 214 538 167 276 427 926 834 690 666 683 455 629 125 255 608 292 512 60 383 671 561 631 277 624 616 340 39 146 910 44 498 693 914 673 879 197 293 815 494 760 124 175 996 47 887 232 736 383 78 511 69 631 283 451 206 823 63 886 476 610 960 383 12 146 215 878 976 428 947 967 489 68 683 819 824 529 728 844 662 902 678 608 392 626 206 415 106 518 197 72 806 138 778 686 377 973 432 86 952 931 858 368 534 90 771 290 603 395 344 65 539 549 704 245 161 514 191 515 338 70 393 295 717 876 245 136 327 949 252 450 96 585 495 429 664 202 949 764 670 734 711 498 368 570 133 397 473 748 343 48 921 58 379 685 511 599 228 875 36 820 506 576 61 80 449 402 456 759 157 911 538 246 730 505 138 663 329 795 513 166 406 186 682 891 355 681 584 616 969 775 443 639 545 135 127 919 678 887 43 881 870 241 515 852 101 242 527 579 35 438 505 437 589 588 773 302 779 561 593 508 210 958 963 638 396 207 719 332 917 994 105 206 548 646 381 591 829 958 258 477 228 343 342 595 812 519 186 323 895 209 94 729 467 549 287 182 181 48 313 343 176 972 360 254 602 619 721 175 233 12 591 197 231 341 949 943 970 209 214 360 403 797 557 787 759 508 502 26 909 219 755 23 18 945 889 624 406 547 494 681 991 786 377 456 197 766 238 421 929 666 323 530 155 905 962 777 69 486 281 241 541 517 978 20 212 983 913 722 467 275 399 55 607 605 932 351 195 539 547 718 119 689 193 996 6 387 998 570 322 172 723 793 300 902 397 375 304 319 497 867 252 551 800 72 739 892 558 375 405 837 340 64 519 661 609 4 785 467 692 923 32 667 420 183 902 857 838 506 497 906 837 219 187 832 54 427 283 403 56 528 627 843 567 734 596 522 720 492 895 290 282 260 453 240 718 821 18 479 719 894 673 424 72 380 208 514 101 126 14 783 116 353 637 395 680 459 743 321 895 632 792 126 728 637 216 380 936 759 90 68 747 478 789 17 311 208 280 540 580 142 198 289 650 542 927 345 937 699 731 612 829 153 240 915 17 174 130 784 774 169 365 58 877 600 250 469 934 535 950 878 500 21 197 641 487 763 291 473 174 361 821 323 548 683 386 892 930 856 814 515 629 207 434 280 377 554 944 869 694 694 847 113 972 398 451 180 522 254 518 178 139 704 953 703 567 102 592 271 278 65 86 12 928 850 42 520 470 585 253 762 835 516 100 866 740 893 850 969 156 207 542 628 704 4 358 943 677 631 647 158 374 825 321 483 815 273 838 408 379 703 449 505 776 98 241 274 47 311 35 534 458 994 898 309 748 100 628 698 61 480 78 332 663 242 751 700 270 537 378 232 154 745 251 780 575 158 557 365 403 450 359 867 392 53 852 914 818 435 698 284 79 976 298 263 282 829 359 879 600 333 425 249 865 415 623 488 731 124 465 47 962 966 806 39 907 107 852 116 547 504 965 341 86 458 107 836 146 353 656 589 551 483 129 496 219 361 410 470 893 921 983 216 272 816 861 286 957 278 374 776 889 657 208 767 813 190 503 788 519 495 442 314 353 953 298 196 273 802 609 383 104 960 131 645 78 758 733 657 170 368 281 72 976 282 160 612 51 892 661 124 765 228 730 528 707 864 315 20 100 280 645 89 230 819 757 846 978 397 432 446 971 844 263 659 815 768 736 950
15
959 910 587 654 514 107 64 43 877 896 506 936 750 852 521
1
4
4
4 3 2 1
1
9
15
42 178 662 145 283 925 644 229 106 145 766 352 880 510 766
100
589 487 875 550 325 722 721 552 916 871 164 500 808 604 886 333 272 560 469 66 472 8 205 173 949 819 603 87 764 722 72 656 614 104 388 948 810 369 130 220 886 688 702 677 829 342 513 900 365 987 811 65 935 339 248 107 451 669 100 703 293 777 480 993 974 499 222 368 535 770 864 335 190 440 79 962 888 741 196 613 679 780 396 584 119 873 579 125 186 916 215 757 73 431 579 382 886 300 506 787
5
5 4 3 2 1
1
1
100
29 925 179 107 270 446 881 177 656 15 639 457 255 468 138 595 987 510 499 163 444 387 506 712 1000 994 748 49 114 892 729 843 152 393 456 676 643 395 846 512 739 425 971 546 215 469 314 414 297 12 7 740 382 154 3 695 716 910 816 866 172 508 262 626 549 27 386 858 844 913 497 495 131 631 753 676 519 882 191 971 709 72 157 182 725 796 347 647 688 36 181 642 527 259 630 321 194 281 279 721
4
8 8 8 8
6
6 6 6 6 9 9
3
9 5 1
2
9 8
1
8
100
846 783 658 648 575 497 457 993 456 133 542 678 139 117 161 977 167 615 647 971 34 952 128 861 600 498 4 627 129 734 879 669 71 412 716 113 498 894 949 388 33 379 815 86 134 864 994 567 270 810 566 42 623 299 967 513 386 803 925 460 688 558 306 31 596 287 678 350 750 675 268 193 709 268 771 449 419 954 865 751 180 539 286 804 86 39 459 388 742 58 983 623 332 844 312 46 71 228 435 929
6
7 7 7 7 7 9
1
6
2
9 9
1000
338 347 161 196 122 97 347 789 815 890 677 907 94 666 296 47 271 683 909 1000 36 405 65 814 162 461 788 886 125 819 693 702 887 674 941 166 656 686 557 360 57 651 925 338 1000 882 412 39 703 91 736 606 175 4 853 332 72 77 358 255 517 768 986 177 908 221 787 809 420 821 107 894 996 343 281 199 864 138 665 571 29 211 914 710 889 256 231 919 98 669 910 76 312 124 129 183 77 725 37 514 160 354 612 276 59 752 215 936 289 811 558 916 410 417 669 905 405 672 673 273 543 36 640 725 473 833 518 996 150 457 139 619 544 936 43 526 398 578 665 744 414 992 169 770 231 356 161 742 541 636 502 41 231 826 195 128 499 274 906 909 715 716 110 41 492 453 500 800 466 839 161 101 517 577 519 565 109 629 204 307 453 439 799 542 547 13 43 661 537 415 555 872 523 292 740 85 459 996 44 803 761 779 82 465 667 819 719 839 93 365 167 416 97 598 539 714 494 517 87 443 352 137 131 390 395 234 428 633 196 6 617 541 235 13 515 133 225 620 477 851 854 991 89 742 759 224 944 30 531 521 47 647 772 516 936 969 273 724 197 101 273 894 784 265 284 661 813 982 994 976 124 186 599 976 283 484 230 175 472 495 180 183 653 994 340 97 151 592 411 295 724 854 576 651 178 380 894 109 530 765 157 845 836 627 551 837 276 847 139 427 412 491 688 442 346 488 238 195 547 63 469 817 507 384 32 266 649 907 55 537 863 801 294 276 41 499 93 858 397 549 808 542 599 988 815 463 8 551 507 304 720 636 1000 740 417 959 376 44 305 445 625 571 24 880 625 488 685 565 913 512 537 588 846 461 136 575 805 408 643 414 97 653 229 679 680 521 544 898 907 614 572 559 462 932 713 710 930 117 906 29 746 608 947 277 313 742 641 353 372 712 253 822 3 776 262 704 852 519 738 465 378 82 221 99 70 767 140 111 585 901 514 682 534 193 890 948 452 960 280 693 424 882 845 178 960 966 799 652 969 425 604 51 405 233 731 853 105 252 303 762 204 345 391 721 712 556 998 495 825 281 346 211 550 74 389 41 192 707 434 41 536 612 151 130 700 109 602 222 17 275 907 518 581 398 894 802 199 286 818 991 576 663 596 994 319 414 887 491 761 853 700 456 351 837 262 336 688 429 198 861 600 201 244 287 264 153 787 826 606 323 205 612 54 130 650 943 808 63 236 638 272 247 957 79 885 214 610 728 470 830 930 144 998 956 478 471 182 832 946 866 355 310 251 918 82 663 460 673 560 238 260 510 440 602 875 479 482 439 916 854 98 449 3 890 509 287 515 286 229 514 295 654 273 7 110 170 952 8 996 940 677 59 307 336 580 356 104 991 534 31 704 352 886 284 309 367 913 274 74 606 513 914 455 904 707 93 440 613 586 882 418 661 476 125 80 950 646 410 619 237 879 892 765 97 778 536 280 166 309 59 338 216 928 592 936 557 355 222 706 701 165 185 755 873 408 261 912 658 313 338 205 114 165 193 77 287 797 82 838 660 317 410 401 515 459 909 719 570 561 666 30 65 318 198 322 840 815 505 630 137 252 792 587 655 373 730 961 902 23 10 416 702 406 887 856 387 895 763 848 95 243 425 163 403 162 132 418 586 329 487 837 388 45 509 674 19 301 974 319 559 421 948 766 347 555 829 125 392 380 464 99 754 489 61 639 106 588 680 479 138 480 577 940 353 394 886 959 261 952 945 836 3 506 708 465 982 530 856 169 642 696 117 475 883 531 833 641 252 666 234 32 127 176 243 322 100 10 27 707 674 985 251 815 91 177 143 436 868 154 981 874 217 605 267 662 6 588 381 799 180 330 69 142 463 435 772 614 302 498 91 86 483 273 219 49 93 575 821 868 154 188 480 40 870 605 253 523 221 525 396 105 60 130 817 792 176 806 254 435 278 549 978 986 348 295 986 641 972 621 873 880 905 377 748 714 526 177 27 131 882 271 921 452 471 439 334 18 273 566 320 353 22 788 432 434 109 754 681 679 264 662 82 5 901 613 357 884 604 214 779 192 351 112 367 842 627 858 511 937 197 307 865 459 817 858 958 2 311 872 733 860 791 441 353 591 727 281 116 838 698 361 475 565 817 973 600 131 486 79 446 621 5 905 841 772 619 350 455 638 525 552 366 440 738 723 95 436 363 862 782 331 828 517 912 977 812 33 795 188 173 987 504 586 710 133 706 371 440 94 322 656 582 980 575 745 188 417 104 798 368
1000
832 877 810 643 719 736 251 755 638 198 473 732 240 175 66 648 445 395 699 270 589 855 54 612 193 533 381 226 402 242 195 799 781 853 610 492 68 326 768 760 840 947 914 129 710 208 994 164 327 595 985 154 717 110 398 123 621 65 191 907 854 928 664 159 7 615 933 81 181 357 821 185 172 577 613 331 490 352 382 408 102 332 811 630 604 424 968 866 801 265 208 826 20 978 794 375 582 397 505 849 621 348 913 829 608 866 808 262 656 298 21 338 799 624 326 371 814 832 80 950 752 824 542 754 725 305 961 533 385 33 422 506 632 502 238 504 868 704 234 83 277 610 704 149 208 913 646 148 333 975 544 728 146 501 729 898 745 385 487 391 7 876 836 867 781 88 864 820 375 594 725 516 18 780 933 137 620 306 548 978 339 509 183 863 386 903 949 954 587 592 6 785 329 851 926 108 944 509 211 128 331 920 690 150 983 400 856 625 996 69 431 229 350 253 484 226 101 408 235 814 64 151 469 577 166 97 944 951 975 106 96 369 432 775 591 254 582 157 766 838 200 913 432 61 222 906 943 337 522 630 547 355 495 564 411 670 416 689 967 636 265 507 837 7 324 965 128 185 728 466 402 129 417 649 583 589 555 664 318 254 531 435 606 77 661 755 771 160 274 851 547 49 29 544 171 483 517 865 750 972 972 332 254 738 26 691 717 503 563 507 267 131 489 113 365 620 221 660 535 376 632 563 846 786 737 579 226 187 364 10 542 459 944 485 836 106 889 232 17 955 467 437 448 303 875 301 23 72 895 928 265 641 519 331 410 843 315 228 673 455 34 595 16 581 690 406 770 980 270 273 465 274 886 509 27 156 619 940 660 400 30 404 663 442 882 512 958 461 47 99 323 763 832 281 912 180 328 428 686 221 657 529 516 370 393 472 7 660 800 164 894 298 185 378 282 73 648 68 502 614 924 237 829 178 692 468 213 549 357 390 14 216 129 923 72 976 527 924 529 201 365 95 434 170 975 436 130 482 761 566 616 575 547 295 693 658 893 440 725 16 619 596 490 180 175 96 59 560 364 827 78 678 991 171 78 260 127 991 763 300 725 507 138 945 583 541 819 66 101 882 704 604 376 874 239 743 660 132 890 774 590 143 506 719 27 781 937 517 712 143 11 89 59 512 477 312 437 284 802 81 220 433 773 301 525 199 141 220 412 628 76 479 333 314 661 714 389 577 100 310 250 406 979 195 624 488 837 216 257 634 271 663 713 246 512 577 919 909 891 38 257 210 706 560 258 815 885 311 528 639 175 49 915 503 138 393 856 454 817 580 810 153 375 886 79 218 86 466 626 802 425 349 391 930 173 451 349 232 801 800 373 897 291 525 43 172 274 654 614 217 479 662 278 442 910 859 217 49 950 784 422 301 913 254 749 175 422 798 435 105 79 655 524 994 666 91 851 663 163 67 625 182 606 237 863 135 330 47 177 871 720 884 567 557 7 334 926 651 743 780 958 101 282 581 190 392 228 146 483 225 559 289 809 915 289 98 460 562 171 588 125 887 858 602 789 180 523 122 360 548 237 87 804 209 759 52 758 208 904 133 633 218 83 530 152 765 425 867 367 902 711 824 406 459 52 281 369 165 157 975 159 866 215 652 183 578 141 529 935 653 297 415 867 182 270 648 298 386 485 839 509 15 493 533 561 981 50 839 305 942 451 942 958 142 444 499 947 895 180 989 27 785 81 252 765 686 534 654 470 755 592 841 271 468 842 731 136 367 749 535 330 833 268 705 988 652 482 358 405 839 653 964 249 255 676 828 841 1000 121 623 158 312 195 737 155 927 737 718 63 265 361 342 602 582 547 215 969 649 721 601 322 452 563 88 611 279 3 953 252 103 982 221 483 586 274 854 166 300 501 289 98 353 437 427 639 673 406 692 794 74 426 961 330 370 825 147 120 92 320 375 179 171 545 423 908 680 861 707 175 537 787 43 380 127 489 666 969 58 767 445 484 887 979 853 110 879 767 398 736 319 191 846 947 893 474 786 787 840 321 301 63 565 181 87 552 914 652 350 203 642 905 706 671 505 942 16 123 695 946 31 815 376 759 86 732 123 926 249 388 491 997 157 298 355 812 352 386 998 232 998 695 627 498 72 43 748 856 922 116 743 983 787 995 91 391 233 121 252 501 679 146 953 613 742 354 289 541 632 506 668 292 725 640 548 30 619 882 829 757 242 945 684 797 41 624 429 234 936 757 400 986 176 170 763 542 242 531 646 130 281
6
5 5 5 9 9 9
1000
20 23 53 46 93 41 35 37 65 44 4 5 5 2 31 30 21 85 12 89 63 57 84 65 48 79 9 58 54 93 85 38 63 78 12 67 24 21 65 72 5 47 53 28 96 5 81 38 100 14 63 47 15 85 13 43 32 31 15 87 16 71 22 37 5 79 38 3 53 98 15 48 75 24 78 72 31 99 78 29 31 73 4 19 96 5 57 3 81 14 39 70 38 39 11 21 100 31 26 13 3 22 92 41 13 29 70 44 99 78 51 19 53 10 59 54 78 50 34 100 92 28 83 34 87 40 76 57 42 2 91 30 60 93 81 1 74 11 23 49 17 24 78 52 42 52 56 2 4 20 49 1 68 70 94 76 14 74 71 19 81 42 98 73 20 1 56 72 25 41 6 71 41 92 87 15 43 46 34 89 67 8 38 30 65 38 7 24 78 72 33 96 26 65 100 51 94 1 36 66 60 83 86 6 53 33 45 95 85 64 58 70 98 46 22 89 10 64 16 45 24 18 94 9 54 78 58 95 47 93 54 78 50 1 28 87 35 90 10 73 5 46 47 94 83 71 71 29 66 91 7 26 63 84 75 52 4 94 73 98 96 4 98 91 99 65 29 8 69 23 67 87 40 3 88 14 29 53 61 75 13 80 70 33 35 13 41 9 88 66 53 2 60 62 82 21 81 17 87 47 55 45 30 45 97 13 38 14 30 37 25 76 100 83 3 49 97 50 47 46 64 49 30 74 51 54 29 91 66 28 12 8 98 23 97 25 4 52 65 100 55 90 21 60 42 94 46 22 52 53 74 67 30 53 31 9 4 88 82 86 69 57 82 43 52 10 28 65 78 8 50 63 13 2 92 60 84 54 83 95 11 2 61 25 14 42 87 90 34 18 96 9 34 86 62 35 31 16 76 7 50 82 43 69 3 72 53 95 86 7 1 54 34 82 12 57 47 26 63 44 63 10 21 27 55 90 49 24 14 79 16 72 34 10 70 84 2 94 24 33 45 70 53 36 72 61 33 50 60 95 85 13 42 36 47 68 14 92 17 53 99 6 97 53 92 24 9 62 64 80 76 65 94 82 11 82 37 19 29 35 60 2 10 93 22 28 28 92 32 57 76 91 14 27 88 27 93 91 43 75 63 19 89 29 81 35 55 64 18 35 54 59 11 32 6 68 47 85 97 46 41 94 45 89 24 2 88 87 100 76 6 33 58 78 87 9 71 13 94 2 24 68 29 34 31 26 43 36 96 82 70 60 61 2 67 40 36 20 67 51 38 12 49 95 46 15 79 44 56 11 99 88 72 74 54 41 16 71 60 70 75 22 55 16 53 71 50 89 64 9 28 72 42 95 74 91 47 13 88 89 42 65 61 65 80 78 68 83 2 67 9 74 3 56 54 9 75 6 11 20 78 42 83 9 19 75 77 71 98 79 7 87 91 22 78 12 39 24 14 1 48 73 60 64 56 44 26 44 48 100 77 95 17 81 72 34 3 88 58 49 25 83 95 43 10 79 29 92 29 5 38 71 100 89 68 26 71 35 50 52 14 66 5 49 5 28 53 98 21 58 70 88 60 92 67 98 35 85 10 8 44 45 17 50 49 68 13 3 94 25 28 14 34 37 51 5 9 32 20 82 17 100 24 68 51 36 74 43 15 87 68 59 63 23 23 16 54 95 95 54 95 92 97 10 55 42 67 81 82 82 94 72 100 77 64 61 30 4 1 92 16 88 44 46 96 30 62 71 9 45 84 37 27 51 39 7 92 4 30 5 53 53 1 96 86 4 41 100 88 33 28 90 98 59 78 63 85 42 36 97 29 34 54 60 11 20 45 71 12 93 2 43 47 14 67 9 26 31 97 54 59 52 23 42 75 33 92 27 87 86 55 52 90 39 2 13 45 54 65 100 88 61 49 24 81 36 32 75 91 15 67 73 77 43 49 27 37 21 22 100 21 33 32 61 79 69 72 14 10 64 53 16 64 20 96 5 21 27 4 74 27 64 75 70 37 48 40 4 68 72 75 4 52 71 95 56 34 64 65 9 19 23 96 9 59 90 3 52 50 70 21 77 55 22 41 5 13 63 98 49 57 93 44 53 42 40 74 79 71 70 100 63 1 71 46 97 11 41 47 16 47 32 61 37 17 67 12 6 44 10 75 68 84 100 29 38 59 62 99 84 97 68 88 78 4 20 80 22 48 34 1 60 23 85 65 83 76 29 86 3 40 50 38 55 41 64 66 45 50 78 2 79 88 22 22 50 3 28 38 40
15
88 625 794 898 24 576 770 408 881 502 845 402 524 860 577
100
888 919 146 906 546 364 518 18 242 993 515 709 219 805 567 245 477 334 9 438 515 704 535 976 279 54 547 285 983 282 441 232 930 546 668 76 978 261 771 194 884 790 561 754 913 112 343 18 803 868 776 25 482 797 469 402 188 184 460 57 222 708 193 996 412 454 837 299 123 376 396 172 866 337 959 426 791 871 32 51 848 217 940 356 692 988 154 141 732 647 783 84 491 221 777 897 495 490 595 126
1000
579 233 715 471 387 923 272 63 611 749 479 579 810 30 118 122 782 539 846 213 555 228 483 576 912 902 508 203 237 261 361 626 352 796 154 130 367 929 499 624 457 601 273 756 975 44 546 419 165 508 522 188 244 732 674 732 216 820 182 951 884 535 146 611 637 838 548 718 68 536 755 871 270 110 648 316 806 710 628 677 295 209 730 136 205 240 195 327 698 52 945 738 95 627 491 33 685 660 541 664 455 293 327 519 628 208 893 174 100 798 974 159 512 142 673 936 328 937 164 537 692 309 717 429 773 986 626 230 49 243 509 470 927 10 116 519 968 227 263 705 675 61 636 47 285 598 101 81 901 395 122 318 976 513 540 940 532 842 365 223 707 803 400 148 770 391 804 114 90 766 519 326 58 160 424 529 118 242 98 899 51 101 282 481 598 750 214 57 722 658 142 292 54 305 254 918 592 95 212 128 853 468 150 887 930 11 961 79 418 822 748 887 803 234 189 656 986 969 667 198 932 871 723 292 595 245 599 48 57 419 374 930 12 899 591 654 495 259 719 804 534 273 369 893 589 622 514 244 340 623 150 857 608 575 401 460 484 13 397 675 615 797 454 548 115 312 611 640 62 540 540 796 855 235 327 730 262 112 393 678 855 802 192 361 249 800 6 349 117 493 331 77 988 679 602 894 826 806 878 367 602 991 212 21 333 258 161 640 551 590 773 148 215 143 216 514 117 16 373 537 613 796 393 521 414 841 282 236 332 110 290 135 471 904 38 452 676 913 119 516 630 539 673 1 472 373 269 239 997 631 371 317 932 730 340 621 20 53 887 713 105 29 936 128 543 298 225 483 358 66 332 496 75 909 75 921 849 358 138 574 456 509 699 373 782 177 4 438 483 548 124 171 184 821 75 889 997 126 607 894 104 618 468 612 770 892 806 910 321 455 842 467 623 591 984 392 478 927 28 349 672 674 593 225 974 607 453 330 207 464 186 790 864 843 48 735 829 722 725 724 641 824 914 741 955 61 723 392 382 640 229 330 423 143 761 421 506 457 648 303 383 972 468 905 929 65 921 680 19 16 581 364 216 865 303 99 715 445 723 92 822 860 157 305 84 144 697 613 579 332 817 889 125 516 942 500 951 525 963 740 821 604 386 754 441 483 444 721 527 716 487 962 881 812 216 903 284 254 418 412 39 423 3 125 89 14 73 331 865 890 946 628 121 627 560 581 111 33 864 621 33 655 592 308 521 808 545 760 83 871 82 173 378 961 429 69 343 93 203 29 348 684 468 337 189 195 175 415 745 21 168 889 640 132 293 276 755 814 701 470 184 210 764 312 317 971 563 277 809 301 429 159 665 368 333 308 774 337 561 975 150 418 79 590 403 791 723 502 81 471 723 319 925 66 645 645 919 15 850 856 929 890 412 904 540 10 409 569 160 276 592 355 34 13 402 720 762 932 441 47 934 363 223 442 299 463 235 206 360 490 157 490 575 341 533 876 993 204 302 450 89 501 789 202 383 702 498 760 797 70 4 284 355 466 276 837 309 657 814 699 678 752 406 862 788 561 961 722 345 795 920 542 330 226 649 416 940 732 826 745 728 386 821 934 242 397 230 997 48 380 538 755 818 443 667 438 935 320 69 876 708 127 50 316 629 188 45 186 391 500 700 196 927 147 746 912 155 371 435 912 622 619 389 257 771 154 174 930 482 814 196 578 871 387 749 329 969 858 350 458 305 456 632 179 686 984 633 202 395 925 175 541 870 950 381 881 26 118 674 785 541 64 322 649 880 338 196 613 576 650 34 302 477 194 492 585 973 917 924 709 975 29 212 860 262 715 254 41 388 638 567 742 537 83 879 39 259 111 509 867 423 616 185 405 888 238 326 665 933 620 816 896 58 274 152 623 373 862 983 542 49 94 137 708 405 41 757 710 559 557 636 485 636 281 846 785 770 300 855 861 320 279 232 714 945 654 748 933 966 532 34 846 397 407 385 90 703 514 993 872 792 921 101 928 369 106 971 501 229 617 846 677 596 791 320 95 612 804 246 150 490 818 904 462 79 150 193 484 184 672 559 326 638 839 190 155 529 421 251 554 837 380 633 117 577 947 437 215 397 955 525 450 137 125 90 663 937 929 927 239 740 94 747 276 703 99 88 657 42 240 942 997 994 970 406 767 530 482 849 936 503 283 443 804 293 295 833 59 58 346 203 906 378 351 474 590 158 908 971 372 515 140 892 453 328 153 891 883 627 315 855 77 880 464 841 753 804 405 358 63
6
3 6 6 6 9 9
6
2 9 9 9 3 3
2
9 9
15
942 896 673 658 629 609 262 262 245 233 182 104 73 67 5
2
4 9
1000
67 63 38 12 83 4 47 36 54 95 80 86 48 52 75 96 31 12 13 75 95 79 100 89 90 10 40 59 66 64 93 79 23 39 72 66 55 89 30 62 38 83 100 65 47 22 24 21 76 62 89 27 71 89 66 17 34 51 87 77 89 80 93 43 63 85 93 14 81 33 39 66 95 94 95 79 66 98 66 92 4 61 12 22 78 40 77 81 71 100 48 48 9 35 19 9 25 71 73 57 71 75 2 34 89 48 66 64 39 4 85 80 93 73 64 68 56 14 46 20 77 11 90 85 22 57 29 95 79 23 2 69 9 62 31 11 76 59 35 50 70 10 78 45 91 99 32 82 20 85 75 22 60 64 89 34 96 38 67 18 38 92 83 53 47 60 96 10 84 35 42 76 85 95 79 72 54 62 87 24 37 80 67 4 95 70 41 82 31 64 54 93 49 19 5 53 63 91 69 12 55 40 20 83 24 6 42 47 26 67 70 88 86 99 35 63 53 33 59 80 22 25 28 49 85 84 67 49 84 71 78 69 75 95 90 12 91 27 6 63 30 43 81 92 22 50 48 74 88 35 71 67 24 51 42 30 93 70 63 35 30 3 49 39 99 97 5 48 65 63 67 58 99 8 59 4 93 15 86 76 98 60 71 64 57 48 63 44 43 52 94 23 65 90 92 35 9 4 62 4 84 26 96 66 12 49 75 23 34 40 64 57 33 3 5 53 22 35 48 85 99 33 42 35 23 72 34 66 4 62 19 47 90 60 79 14 34 67 44 8 93 92 52 13 43 62 62 80 75 77 14 80 54 35 72 10 13 17 92 88 13 87 93 42 15 75 7 74 52 54 70 38 53 55 48 88 52 77 88 3 29 3 48 98 63 63 15 53 47 31 65 41 51 83 51 44 79 39 97 77 29 82 45 39 22 67 5 38 43 49 96 33 42 34 50 44 4 10 38 45 15 72 42 83 82 18 45 22 67 91 42 43 52 37 74 60 70 95 97 50 51 91 60 42 35 43 21 98 83 22 85 92 43 33 27 85 1 54 80 51 100 32 80 100 3 7 11 40 46 31 12 90 31 81 85 95 41 18 31 98 11 79 33 47 40 51 85 6 51 25 43 52 99 41 14 59 57 23 18 98 68 1 62 4 92 20 67 26 74 100 96 57 16 53 32 89 51 49 41 29 19 77 4 56 43 76 18 96 63 33 77 88 38 36 60 46 32 52 52 55 88 22 92 47 79 9 48 70 52 96 63 90 52 97 29 95 58 50 87 2 74 72 92 98 12 85 5 13 71 49 97 60 86 56 35 52 91 18 45 65 46 3 50 98 88 5 99 30 99 16 35 89 51 77 19 5 13 84 68 74 23 92 14 94 96 93 69 23 98 51 12 63 85 26 90 99 8 3 8 7 71 32 74 70 5 85 31 5 14 73 5 68 46 62 47 9 16 19 32 30 19 23 21 15 25 90 39 76 84 30 59 90 8 40 47 54 51 10 97 46 37 51 19 27 42 27 44 20 22 59 45 1 83 81 88 31 87 52 36 83 16 88 95 77 31 21 53 57 3 21 43 21 46 91 38 23 84 11 35 11 49 43 47 79 28 83 22 24 94 73 81 62 50 34 38 1 30 81 2 4 66 15 70 72 97 43 68 72 19 73 86 85 49 58 48 16 92 90 24 58 31 98 70 59 49 62 10 100 26 63 65 31 66 46 22 81 63 13 22 94 63 62 17 65 16 55 82 90 77 57 2 26 47 47 41 7 78 55 59 51 51 62 99 51 4 90 43 96 80 23 51 16 54 96 59 12 32 26 88 77 1 13 7 51 17 14 81 24 72 44 87 2 47 35 15 4 65 17 49 90 82 25 72 52 80 21 76 5 88 76 2 34 13 57 80 59 100 20 49 1 31 48 67 30 46 15 6 63 17 70 11 64 83 2 76 72 60 33 23 70 90 40 27 83 23 69 93 2 27 80 40 67 11 88 25 12 97 3 50 88 98 28 75 40 12 43 6 5 99 59 12 69 83 21 35 2 17 46 6 69 1 97 60 39 67 89 27 26 11 52 76 48 52 49 49 91 55 95 45 46 33 41 48 49 27 29 90 24 86 90 45 60 70 82 5 15 91 85 65 92 8 89 73 77 71 53 7 67 22 49 68 92 60 33 25 7 27 32 43 68 33 34 92 13 52 31 99 7 19 52 1 70 36 63 15 82 35 3 6 76 97 97 91 13 31 71 65 4 43 17 8 100 40 6 88 29 41 56 8 13
6
9 9 9 9 9 9
3
7 5 3
2
6 6
1000
96 93 50 90 23 95 67 45 78 20 63 77 92 44 72 91 71 35 19 77 70 41 22 25 86 88 86 79 90 61 20 41 87 41 7 10 52 14 46 76 43 21 95 1 36 70 54 100 49 48 37 13 68 37 40 46 74 44 42 98 70 100 61 85 23 97 21 52 96 62 84 48 23 62 72 28 64 69 88 14 66 30 32 74 16 68 15 99 39 54 85 51 80 33 80 6 37 86 90 79 63 16 53 25 26 55 100 20 17 84 100 55 11 56 75 45 27 15 71 7 41 18 12 27 17 100 93 66 85 28 41 60 3 15 44 84 91 89 99 29 97 40 66 77 96 95 6 22 87 86 84 23 87 71 93 5 73 23 14 44 31 44 63 71 87 78 20 22 69 16 30 63 94 24 64 93 69 9 41 30 25 81 51 94 64 4 51 86 68 35 46 17 83 46 13 55 52 13 26 53 36 55 21 29 96 47 74 32 66 86 85 100 27 77 92 25 51 51 25 72 40 5 62 23 34 92 81 98 29 15 59 59 3 35 83 96 38 97 25 93 9 35 32 38 67 2 6 56 57 97 12 39 77 69 13 36 72 67 57 100 29 37 95 98 92 20 11 37 54 8 60 59 21 78 38 82 56 67 30 8 55 19 47 77 77 16 94 27 67 69 57 69 83 15 6 23 71 50 56 71 25 22 63 79 26 74 44 40 60 57 17 42 84 43 11 68 82 96 46 72 29 32 12 90 27 81 12 98 3 2 52 95 83 1 47 35 21 65 9 9 21 10 69 75 66 31 22 43 39 5 36 19 89 72 40 6 24 20 86 34 69 71 39 68 48 45 11 62 29 13 40 63 15 47 29 9 94 86 80 34 91 98 77 8 91 15 82 30 64 22 92 32 46 61 68 43 70 60 7 79 68 91 65 41 45 91 23 96 38 31 61 61 41 18 15 98 43 72 14 80 11 84 73 77 10 51 9 17 60 31 5 87 39 6 69 98 92 58 4 87 76 75 48 76 6 51 21 5 93 23 76 51 32 6 86 18 29 30 62 31 40 52 74 57 51 5 58 16 93 58 22 35 99 34 91 35 42 90 77 48 95 30 25 5 95 75 82 56 77 74 60 82 23 30 33 53 7 21 37 80 54 67 85 70 78 61 88 60 100 2 93 81 13 56 21 8 81 46 55 5 71 9 54 3 18 46 18 28 67 83 97 70 49 1 36 46 55 37 67 81 76 33 53 93 79 28 68 87 64 9 10 3 29 44 3 56 55 87 9 9 96 93 45 10 96 6 9 21 5 6 49 37 30 21 48 14 72 87 83 24 72 79 90 79 24 60 77 94 80 24 53 53 58 13 28 45 87 68 8 48 52 99 90 95 55 17 98 66 62 26 54 5 84 61 84 3 34 94 65 87 91 98 26 60 5 81 66 100 73 68 53 44 7 34 91 17 37 70 50 88 66 86 59 26 99 13 85 66 29 78 62 59 16 15 80 42 6 84 22 78 30 82 45 32 63 32 95 31 34 13 18 56 89 49 70 19 62 62 3 59 57 66 64 15 96 27 90 23 42 38 7 59 78 19 87 46 70 89 44 100 38 95 28 89 53 7 86 25 83 55 9 36 72 61 51 72 46 70 38 47 60 55 5 78 14 93 56 79 17 91 100 23 33 72 60 96 43 95 7 44 51 63 95 15 76 36 76 94 12 20 64 52 51 62 63 26 51 41 26 64 9 38 49 89 6 68 3 30 77 83 59 19 52 16 13 29 20 58 94 44 40 65 22 60 88 15 78 94 43 52 36 26 9 95 53 65 59 68 62 3 4 22 58 46 77 20 4 44 46 11 54 83 91 61 85 85 34 74 75 45 5 67 32 89 26 21 65 39 33 70 30 43 74 57 25 97 53 19 11 79 40 10 77 8 88 77 39 94 61 14 72 6 42 14 4 25 66 11 42 37 2 22 41 67 7 10 73 63 75 48 35 79 20 26 54 99 23 4 43 73 80 34 17 61 44 20 88 32 7 89 9 45 3 2 98 23 95 95 38 80 84 70 97 73 40 12 91 49 69 74 57 71 90 59 35 93 53 2 28 100 87 98 58 55 62 53 87 40 97 82 56 42 40 11 69 67 11 95 56 11 91 74 14 85 47 85 18 50 32 59 67 95 79 7 41 97 91 48 40 40 24 72 74 51 54 67 77 50 10 40 81 46 25 93 70 66 69 83 51 23 9 96 88 33 3 100 36 74 59 14 79 83 56 93 40 5 83 11 25 54
6
1 1 5 5 9 9
100
847 987 408 941 912 63 101 463 738 293 871 878 394 446 683 388 327 662 706 173 61 417 742 148 664 932 552 666 143 165 861 52 294 270 990 787 450 29 773 32 782 428 555 33 681 663 311 507 589 405 839 751 174 209 922 584 6 423 133 341 91 253 913 340 971 952 842 384 158 886 637 905 696 395 194 638 509 418 142 535 814 17 550 814 261 387 288 386 213 278 494 532 162 19 824 714 224 943 919 415
15
685 924 565 436 3 600 452 261 216 645 205 744 694 953 231
1000
69 555 918 451 198 198 78 346 295 30 389 663 811 670 824 581 309 110 421 41 18 672 726 876 585 383 393 509 68 384 459 994 710 19 948 795 646 729 339 621 281 464 449 480 358 89 416 643 345 86 100 443 959 220 912 926 148 278 837 335 377 527 171 860 631 527 37 542 981 872 900 656 413 815 435 156 514 100 782 896 382 205 755 721 464 695 719 506 737 182 913 937 646 93 823 345 42 496 830 934 822 312 189 700 820 340 245 142 780 341 213 943 397 593 37 91 174 69 58 19 777 772 113 688 955 783 832 285 909 255 997 346 186 450 745 954 459 871 586 774 484 718 946 703 404 366 13 634 208 941 960 595 742 420 148 801 359 707 438 144 170 707 584 396 92 269 900 96 37 439 428 397 356 469 19 496 628 758 809 570 735 517 704 775 374 82 555 231 821 375 191 749 333 66 318 500 709 747 97 932 496 188 558 251 244 551 320 532 400 779 316 141 809 984 117 483 687 349 246 547 491 850 127 425 274 67 164 340 798 771 430 713 785 385 357 494 246 584 655 374 279 91 479 977 262 401 827 751 951 120 38 669 418 809 823 256 940 944 780 33 100 699 172 28 365 38 416 945 324 410 510 521 555 916 708 433 371 826 28 82 449 250 901 424 944 472 858 795 891 976 435 189 328 96 705 34 98 649 894 138 395 688 715 961 487 246 525 685 20 339 623 342 978 434 740 382 757 632 381 578 876 240 82 162 150 872 884 988 626 494 195 236 923 175 684 203 331 564 450 208 324 264 153 573 90 957 847 295 686 103 536 473 48 265 815 669 526 302 196 76 210 133 265 667 294 884 342 158 377 636 457 571 577 584 637 980 885 793 16 958 34 296 380 889 800 660 24 491 609 205 815 896 645 859 182 243 46 683 43 4 763 342 873 723 5 300 421 904 602 133 414 840 346 799 282 207 716 160 153 926 270 999 303 869 402 934 456 180 192 871 262 280 557 778 415 590 342 529 293 946 938 757 802 298 666 347 648 672 595 523 644 145 225 357 215 363 566 979 864 621 237 24 228 163 571 171 985 597 591 126 754 21 245 474 605 34 5 224 348 860 555 463 358 878 745 887 529 916 595 443 295 56 432 84 889 932 368 246 208 526 63 982 205 835 35 845 690 193 344 227 614 839 944 720 812 659 222 852 798 125 699 238 415 616 240 362 831 82 741 899 56 385 676 980 950 621 340 51 639 871 598 186 989 730 794 216 479 595 268 169 169 984 840 234 62 764 476 640 663 217 263 167 320 708 415 793 208 585 163 399 378 885 16 532 711 977 640 634 381 208 594 357 468 554 293 821 835 127 333 86 340 558 841 290 966 981 116 86 569 595 724 366 288 671 298 266 455 131 452 846 217 315 47 184 769 479 720 309 757 95 117 124 286 949 516 990 453 812 935 572 265 15 248 9 846 610 412 197 338 533 491 749 511 562 407 157 14 741 561 933 429 174 510 361 929 156 95 264 293 44 327 693 711 842 726 300 110 370 388 936 69 160 1000 129 736 48 50 632 86 200 734 799 118 859 206 771 50 934 660 630 854 523 930 335 939 744 445 736 652 639 597 357 650 88 224 622 266 765 362 448 64 910 259 861 939 830 404 158 625 636 366 739 431 827 565 668 524 577 679 387 146 311 212 881 89 18 662 633 920 767 741 993 406 532 776 438 272 817 503 126 335 766 1000 158 662 195 11 387 195 766 947 539 509 750 543 799 847 400 980 368 618 896 318 40 775 735 841 159 685 623 499 828 880 423 595 962 755 637 635 888 862 262 768 593 66 66 763 523 350 203 371 220 656 759 722 206 193 873 924 928 310 57 213 678 369 476 526 791 115 204 414 865 827 817 25 783 621 949 472 288 732 159 449 225 270 666 293 514 849 557 142 816 529 803 95 400 842 675 338 198 825 511 274 595 763 370 622 242 124 334 464 927 821 557 684 63 219 88 209 375 513 702 283 989 501 629 45 408 136 559 448 161 658 629 262 745 669 192 611 314 592 213 240 745 479 273 9 365 445 272 764 932 978 140 466 712 857 272 295 391 356 322 34 400 590 87 791 250 896 310 779 872 482 562 794 633 58 604 170 941 584 665 201 776 511 657 174 629 247 899 185 449 172 645 731 546 837 619 29 115 758 79 600 410 301 552 896 333 962 324 884 608 444 88 904 659 121 936 330 36 873 37 321 515 668 696 986 159 396 262 96 533 24 987 169 697 625 109 676 595 519 515 597 591 243 736 344 806 448 822
100
723 723 851 553 129 767 237 208 388 365 309 929 827 19 256 203 154 770 159 990 422 301 422 293 954 694 677 63 897 557 284 383 746 57 264 198 181 203 414 905 47 123 586 800 736 488 433 94 595 789 601 60 213 168 221 167 16 400 417 184 631 579 250 570 69 167 141 305 378 978 778 121 660 405 551 626 982 200 899 555 572 959 863 472 804 294 332 476 385 115 581 891 934 983 937 750 602 224 16 894
6
3 3 5 5 9 9
1000
254 805 312 37 931 696 149 268 75 489 992 199 139 677 299 754 287 898 838 407 16 786 784 301 985 214 293 316 588 773 728 457 144 28 107 111 474 870 993 954 716 566 52 378 816 324 697 854 752 251 207 484 280 170 184 238 244 797 958 656 760 844 482 510 482 879 759 320 88 122 703 564 666 67 638 908 119 644 740 991 56 933 812 969 231 520 662 286 414 545 118 566 721 797 741 771 326 39 65 363 63 541 704 190 152 258 459 248 48 696 954 759 450 88 907 123 461 805 426 490 159 935 214 915 842 221 905 802 207 74 577 947 169 669 752 476 818 924 36 184 85 358 753 467 684 943 475 277 51 581 233 366 496 278 679 87 423 145 876 458 587 886 877 231 93 760 388 719 50 701 925 918 147 181 64 603 795 284 594 633 489 775 55 724 798 904 949 7 534 437 588 447 576 111 605 203 609 417 954 285 313 655 367 940 702 595 717 950 538 744 187 471 496 364 100 56 864 116 465 731 81 92 590 517 466 301 987 952 212 488 448 545 462 800 386 633 197 563 33 91 622 272 193 948 720 125 239 312 92 948 365 343 134 730 815 211 393 415 81 374 94 818 544 118 454 773 966 731 45 825 590 718 496 607 775 354 82 544 188 606 542 904 441 20 482 874 41 230 903 518 709 138 211 566 565 340 763 168 563 714 497 334 496 768 682 466 371 337 889 511 277 359 268 710 670 330 22 623 905 43 590 610 890 594 170 337 758 609 476 335 637 858 434 182 318 965 153 354 409 314 719 167 646 154 790 806 686 968 420 738 550 690 874 262 112 936 430 405 849 805 143 653 86 545 109 585 72 511 461 119 103 149 753 760 239 445 458 425 557 550 769 705 648 329 759 85 674 786 622 771 37 496 981 863 175 81 300 800 726 836 236 842 124 516 384 877 852 787 470 586 678 897 858 224 897 455 787 505 760 277 871 448 451 369 192 136 887 10 879 590 178 285 939 992 546 19 802 729 952 817 98 445 79 355 185 84 366 56 893 755 176 916 482 544 668 420 818 554 330 267 539 372 401 720 737 323 942 687 585 244 340 409 133 175 508 942 910 549 138 11 759 737 42 996 24 638 389 735 35 783 50 362 29 963 735 651 440 872 138 478 557 773 701 956 84 733 841 772 109 615 612 445 381 513 895 268 624 289 470 616 683 103 12 877 811 327 637 214 755 923 462 10 465 454 832 598 695 314 678 761 486 529 747 34 36 343 479 189 895 258 287 178 559 830 506 317 708 272 204 4 476 351 442 5 793 342 819 383 653 700 925 759 111 802 794 884 164 890 846 906 51 177 186 500 316 436 12 801 910 845 506 924 921 946 958 225 871 590 604 254 63 821 330 886 114 251 692 738 85 48 372 306 920 428 36 967 171 26 704 777 49 276 700 875 184 962 661 149 533 484 768 940 442 341 584 10 584 880 394 608 957 227 481 864 498 702 727 293 499 856 13 742 272 814 554 280 372 97 237 622 390 130 11 135 411 904 528 397 407 484 47 700 521 727 642 316 865 115 516 223 399 23 941 867 410 151 130 968 559 617 468 313 978 416 618 822 252 544 381 55 703 107 786 431 257 157 303 80 315 223 154 694 387 573 931 189 639 910 831 812 261 318 187 634 959 319 189 801 761 227 372 910 275 688 388 500 137 809 314 908 583 211 995 852 73 299 883 8 347 251 244 259 754 987 706 873 916 714 597 296 477 433 50 467 304 339 409 995 136 562 747 854 934 431 812 81 442 766 42 931 580 667 235 20 442 205 800 438 478 321 477 713 876 478 889 369 928 211 140 698 19 787 548 891 394 26 422 342 456 768 455 420 593 649 881 637 996 657 927 332 452 943 914 905 855 377 510 824 270 442 371 320 560 247 418 295 314 286 735 604 278 959 483 468 747 218 425 764 989 402 828 839 193 766 260 986 333 629 684 611 45 603 942 722 938 645 312 260 70 425 743 940 562 117 508 871 221 242 748 595 853 983 741 641 460 617 638 197 672 22 679 27 275 779 660 247 499 810 344 368 106 480 759 547 193 928 500 508 456 645 154 163 625 3 700 784 474 523 498 394 42 897 57 422 958 338 575 76 978 919 608 363 914 144 819 509 141 264 959 8 42 655 41 217 520 708 75 374 764 861 75 552 205 165 684 957 484 922 639 397 779 561 641 917 662 341 456 443 1 657 890 165 117 647 612 796 104 993 411 95 458 280 179 737 914 824 580 333 807 882 391 350 300 123 220 613 262 257 727 850
3
9 9 9
1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000
629 129 911 893 27 559 65 671 467 89 914 98 830 270 4 533 843 601 42 116 398 107 781 158 747 114 30 13 559 748 565 36 407 793 145 290 505 788 264 414 26 127 848 938 137 320 422 472 558 217 651 151 406 3 767 376 760 388 8 924 654 997 433 567 16 859 38 332 136 646 991 871 703 611 899 739 256 89 541 324 124 36 459 687 904 665 44 458 48 14 936 551 254 987 527 165 983 148 266 156 441 892 92 365 418 186 955 119 445 946 84 763 334 625 295 494 532 938 791 141 572 105 839 766 983 118 600 608 598 893 893 919 72 780 724 398 477 650 594 956 985 554 852 816 589 74 905 841 845 464 905 848 621 496 559 751 999 725 931 589 864 517 241 433 971 889 702 97 161 801 702 319 458 571 933 831 700 187 436 314 89 30 991 623 356 107 377 863 790 901 17 470 190 336 354 931 343 626 503 451 912 771 976 475 820 572 265 859 819 523 103 29 996 372 462 39 693 890 282 215 972 784 93 341 688 151 528 924 358 412 905 317 919 583 609 927 312 981 903 825 371 824 492 648 768 33 461 54 857 196 109 862 658 742 697 712 27 172 399 86 969 851 554 665 633 259 89 35 509 802 467 843 409 163 885 729 869 792 586 649 304 835 80 769 304 211 439 807 696 210 797 571 395 77 856 840 242 303 172 543 85 565 579 478 18 229 926 374 779 769 621 938 614 383 287 938 253 79 344 903 599 471 934 532 100 908 973 751 810 226 862 608 182 213 34 997 522 558 82 122 138 862 805 613 813 288 421 741 270 195 114 244 506 743 308 4 110 230 15 929 360 640 584 1000 933 220 702 368 401 570 495 880 409 578 291 136 430 365 36 562 351 643 716 926 367 410 412 503 484 898 195 186 483 182 66 634 507 102 289 541 732 817 919 414 778 406 220 830 753 475 87 553 132 33 718 819 165 923 620 396 73 467 381 855 936 866 864 765 209 352 792 487 726 874 162 71 759 213 253 687 610 321 947 541 314 456 654 793 921 378 126 517 23 894 217 804 79 998 500 627 507 923 42 272 14 555 351 822 44 732 803 972 315 829 925 415 37 956 399 155 367 456 609 996 836 762 468 642 801 46 96 745 559 299 412 94 660 266 726 673 780 521 946 37 599 517 904 985 797 548 639 958 556 365 116 105 636 984 483 982 743 172 685 813 551 818 262 594 852 365 36 727 973 165 212 715 492 263 986 409 289 98 533 103 500 847 499 447 141 930 774 222 642 214 53 644 415 507 261 10 639 377 112 440 514 43 659 927 336 651 935 228 542 508 364 368 540 440 239 233 150 666 161 88 648 852 716 346 300 484 725 476 732 113 203 183 576 813 192 161 448 167 657 447 620 830 881 853 491 8 201 756 688 454 345 758 407 421 141 588 427 128 675 331 942 982 664 191 915 8 98 917 581 278 683 536 238 147 486 848 434 205 850 43 357 411 896 264 54 783 108 308 7 932 587 175 678 986 264 500 207 157 2 165 415 958 135 719 613 973 120 36 806 530 29 364 502 336 293 895 689 248 215 515 104 20 32 243 737 149 460 234 753 167 361 543 887 686 90 49 562 503 848 693 545 266 985 213 538 827 418 526 98 70 896 80 883 269 81 134 279 922 588 796 200 789 246 712 638 491 983 18 769 481 814 261 12 8 945 978 545 613 752 658 571 992 657 941 262 443 996 395 982 671 304 773 969 415 510 754 150 250 70 843 107 18 147 889 344 713 336 319 111 302 124 366 870 771 454 308 81 52 247 890 412 23 567 779 451 521 740 800 171 992 686 398 805 758 657 527 896 169 934 847 355 371 237 704 130 108 455 231 571 824 38 680 640 426 917 366 179 514 775 118 85 996 12 850 466 790 306 388 914 956 366 179 72 894 775 681 69 853 237 42 169 576 338 337 16 845 549 945 844 135 876 60 158 580 841 469 944 257 926 55 887 177 292 822 467 136 439 882 938 245 216 905 994 476 711 687 572 598 614 274 818 98 452 124 850 341 19 213 684 738 920 766 516 414 885 924 420 769 661 5 453 73 271 33 278 361 828 452 322 519 303 525 904 254 139 675 6 358 210 971 37 947 497 584 289 858 127 196 71 828 95 112 55 111 285 785 399 841 669 734 189 130 393 209 481 147 290 541 770 512 814 600 181 988 567 46 97 330 551 663 29 494 615 561 832 308 93 828 764 508 853 189 766 868 118 632 508 897 370 454 281 923 829 201 118 354 777 809 312 363 678 385 809 705 834 42
1000
63 91 69 1 24 20 56 41 87 23 30 29 100 87 100 66 12 81 75 98 27 64 84 17 74 47 2 35 26 30 47 51 57 25 49 28 93 18 80 15 15 65 7 31 20 92 74 42 70 2 72 88 74 13 38 89 80 38 13 71 47 6 36 67 69 29 60 60 6 24 63 25 18 88 46 58 2 74 48 89 74 17 67 90 72 78 46 18 96 56 60 62 11 6 94 67 76 35 34 100 86 30 52 6 26 90 22 7 8 48 69 98 63 21 13 82 19 97 95 18 6 93 18 76 67 11 13 97 11 89 30 47 67 77 76 41 18 54 5 32 25 51 41 82 12 6 46 34 4 79 51 72 54 67 54 45 56 33 31 99 68 47 34 8 18 62 21 58 97 85 7 49 9 25 38 52 82 30 29 64 17 40 80 65 61 33 13 83 6 71 77 48 17 68 11 95 17 63 18 61 72 3 88 66 18 29 22 79 61 18 73 17 39 6 99 80 48 79 42 41 12 49 35 8 92 67 12 79 5 63 3 52 23 38 74 21 24 89 81 90 83 45 76 67 91 80 16 2 3 97 69 35 73 27 71 55 39 53 29 90 65 21 52 19 100 39 14 82 27 30 79 71 5 26 93 20 11 87 95 41 90 6 26 97 48 54 30 30 45 29 62 48 76 41 53 22 16 44 86 71 3 29 90 20 18 59 65 23 49 19 50 9 74 22 91 25 25 96 9 40 53 72 98 83 20 64 1 87 11 97 25 55 69 83 40 79 73 13 78 40 58 59 43 5 4 41 35 37 12 55 63 61 97 84 25 26 96 27 77 29 42 90 48 66 70 12 95 12 18 91 19 66 12 96 39 54 51 87 28 58 14 60 69 97 43 89 91 81 78 32 47 42 77 90 7 48 11 58 63 44 22 44 46 91 73 68 7 15 58 47 84 5 24 32 99 10 56 13 84 79 29 25 81 54 22 6 16 35 53 63 93 72 97 11 16 12 67 88 16 58 42 68 47 33 38 26 41 44 86 51 89 87 95 8 6 18 69 22 70 63 57 27 91 23 100 34 49 90 67 12 30 54 98 84 56 6 98 62 84 5 84 5 28 38 45 34 85 72 95 78 98 8 20 99 84 4 3 81 29 96 73 96 47 7 12 96 88 34 38 21 28 81 74 31 86 11 89 41 35 19 74 90 66 52 51 13 14 25 8 33 3 58 75 53 7 92 16 57 54 42 14 69 23 44 92 64 26 30 47 48 34 8 100 12 73 94 41 27 83 29 49 81 79 58 72 85 80 63 20 28 13 62 60 18 17 88 48 44 94 79 71 25 84 63 14 65 21 94 54 84 72 36 13 31 64 6 77 45 69 3 38 69 58 23 4 14 91 13 70 22 56 30 22 12 42 91 24 5
stdout
Standard output is empty