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