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