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