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