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