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