heh
| -rw-r--r-- | src/inp.txt | 398 | ||||
| -rw-r--r-- | src/main.rs | 40 | ||||
| -rw-r--r-- | src/util.rs | 37 |
3 files changed, 247 insertions, 228 deletions
diff --git a/src/inp.txt b/src/inp.txt index 780f10e..dae3801 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,200 +1,200 @@ --7 4 41 121 272 539 997 1790 3238 6096 12113 25120 52964 110690 225447 443645 840883 1535008 2702137 4594155 7553340 -4 6 15 32 56 97 215 608 1782 4848 12001 27235 57322 113013 210281 371191 623616 998482 1522475 2203130 3001892 -1 14 30 60 127 259 482 812 1241 1708 2047 1924 854 -1364 -2779 6693 61773 262974 871468 2514024 6601925 -6 11 22 52 122 270 570 1162 2299 4438 8451 16122 31239 61800 124158 250420 501360 989250 1920158 3677323 6993968 -5 7 20 59 158 375 798 1567 2933 5377 9809 17858 32248 57231 99015 166082 269237 421163 635178 922797 1289594 -0 -3 -6 -7 1 43 201 703 2093 5515 13138 28727 58310 110773 197987 333665 529470 785825 1073258 1297757 1240279 -4 16 31 51 77 110 165 305 716 1872 4881 12159 28649 63886 135307 273317 528748 983488 1765211 3067307 5175293 -28 42 56 70 84 98 112 126 140 154 168 182 196 210 224 238 252 266 280 294 308 -14 30 55 105 221 486 1057 2232 4581 9179 17987 34432 64237 116546 205378 351432 584260 944840 1488635 2289343 3443761 -11 22 37 68 148 338 743 1559 3190 6514 13460 28214 59658 126174 264919 549437 1122545 2256574 4461315 8672808 16575204 -13 16 35 83 171 318 572 1047 1989 3900 7783 15648 31591 64129 131249 271201 565159 1183779 2480632 5175309 10704255 --7 -11 -2 41 146 354 734 1409 2595 4667 8313 14965 27979 55581 117567 259445 580783 1290395 2812622 5992175 12490570 -8 7 5 17 83 276 712 1579 3222 6366 12646 25770 53931 114643 244277 516741 1079964 2226889 4532683 9117139 18139459 -25 41 76 150 290 533 930 1551 2491 3877 5876 8704 12636 18017 25274 34929 47613 64081 85228 112106 145942 -21 50 90 137 187 236 280 315 337 342 326 285 215 112 -28 -209 -435 -710 -1038 -1423 -1869 -14 22 37 55 73 93 126 196 344 632 1147 2005 3355 5383 8316 12426 18034 25514 35297 47875 63805 -9 11 21 58 153 364 817 1783 3810 7966 16336 33094 66812 135287 275234 560945 1138767 2288413 4528199 8789922 16701011 -8 14 35 91 217 469 946 1850 3620 7208 14641 30168 62576 129773 267707 547650 1110014 2231708 4462709 8905935 17791177 -8 19 38 65 93 119 179 422 1244 3509 8890 20369 42941 84573 157475 279746 477464 787295 1259702 1962841 2987237 -10 29 55 97 174 315 559 955 1562 2449 3695 5389 7630 10527 14199 18775 24394 31205 39367 49049 60430 -11 21 37 74 173 415 947 2045 4251 8633 17229 33748 64613 120443 218083 383303 654299 1086141 1756325 2771598 4276237 -3 13 33 63 103 153 213 283 363 453 553 663 783 913 1053 1203 1363 1533 1713 1903 2103 -7 9 17 31 51 77 109 147 191 241 297 359 427 501 581 667 759 857 961 1071 1187 --8 -2 22 78 200 459 982 1972 3727 6652 11253 18096 27698 40263 55025 68607 71081 37078 -92913 -449054 -1297721 -8 0 -16 -37 -45 8 222 774 1952 4228 8438 16189 30679 58196 110656 209648 392576 721624 1296420 2271439 3879363 -15 32 68 131 226 355 517 708 921 1146 1370 1577 1748 1861 1891 1810 1587 1188 576 -289 -1450 -25 48 89 168 324 622 1160 2076 3555 5836 9219 14072 20838 30042 42298 58316 78909 105000 137629 177960 227288 -6 6 14 56 182 492 1191 2686 5741 11717 22951 43393 79771 143892 257421 462023 840872 1563564 2977624 5789534 11411748 -6 24 58 127 264 524 1003 1871 3422 6144 10812 18607 31264 51252 81989 128095 195686 292712 429342 618399 875848 -2 15 35 78 172 354 662 1121 1734 2511 3615 5798 11471 27026 67417 164495 381118 833495 1724359 3389070 6355154 -10 12 13 25 76 226 607 1493 3403 7237 14442 27202 48643 83041 136018 214708 327872 485938 700939 986319 1356574 -12 23 47 90 151 215 256 260 283 567 1743 5149 13278 30341 62878 120271 214902 361551 575439 868084 1239849 -10 15 30 57 98 155 230 325 442 583 750 945 1170 1427 1718 2045 2410 2815 3262 3753 4290 -11 26 41 56 71 86 101 116 131 146 161 176 191 206 221 236 251 266 281 296 311 -22 35 46 66 130 306 709 1536 3152 6272 12307 23995 46562 89916 172870 331321 634164 1214667 2333799 4511553 8805034 -25 46 79 133 222 366 592 935 1439 2158 3157 4513 6316 8670 11694 15523 20309 26222 33451 42205 52714 -17 20 21 20 17 12 5 -4 -15 -28 -43 -60 -79 -100 -123 -148 -175 -204 -235 -268 -303 -18 43 75 114 167 264 488 1019 2192 4569 9025 16848 29853 50510 82086 128801 195998 290327 419943 594718 826467 -3 12 29 49 67 78 77 59 19 -48 -147 -283 -461 -686 -963 -1297 -1693 -2156 -2691 -3303 -3997 -16 18 27 47 82 147 282 565 1119 2107 3705 6042 9124 12866 17606 25912 47070 106096 258775 611721 1339290 -0 3 17 65 177 391 757 1349 2311 4001 7367 14814 32041 71732 160796 354586 765302 1619811 3378481 6978415 14323381 -23 29 34 55 137 371 930 2143 4633 9552 18955 36367 67613 122002 213983 365425 608715 990919 1579312 2468655 3790681 -6 8 22 63 148 303 570 1007 1680 2669 4163 6831 12899 28894 72134 185261 467246 1136558 2654320 5954663 12859322 -15 23 43 94 209 457 978 2031 4055 7743 14129 24688 41449 67121 105232 160281 237903 345047 490167 683426 936913 -14 17 28 69 186 475 1114 2398 4773 8864 15506 25842 41681 66560 108425 185762 340856 667587 1368500 2869679 6046748 -9 13 32 92 233 526 1101 2190 4207 7929 14928 28560 56075 112810 230009 468630 942605 1856477 3564216 6658388 12101797 -9 20 37 61 93 143 246 494 1109 2617 6263 14965 35372 81983 184799 402632 845125 1708254 3331901 6296837 11597563 -26 35 45 75 156 332 675 1333 2643 5374 11232 23881 50947 107835 224792 459621 919968 1801397 3450831 6469735 11878094 -3 10 43 115 234 409 680 1189 2311 4863 10404 21640 42995 81600 149492 269125 487274 909039 1778256 3662348 7866979 -8 20 47 109 238 481 909 1642 2922 5313 10206 20999 45662 101954 227416 497518 1057100 2172642 4316065 8294857 15448502 -1 10 38 105 244 505 971 1807 3383 6558 13298 27941 59630 126725 264391 537055 1058045 2019482 3736406 6710193 11717576 -17 26 30 30 35 64 155 385 898 1933 3850 7189 12904 23157 43537 88430 192703 435132 982422 2167632 4623809 -12 18 34 66 122 222 413 804 1647 3502 7554 16231 34465 72352 150787 313173 648982 1339442 2742866 5548392 11043844 -8 8 5 12 63 230 654 1597 3536 7347 14661 28505 54356 101720 186285 332571 576796 969382 1576129 2476582 3757505 --5 -3 13 58 155 341 677 1275 2366 4439 8494 16494 32207 62865 122579 239562 471597 939109 1894851 3867122 7944923 -0 8 27 71 168 365 731 1353 2328 3768 5854 9010 14356 24821 47806 101363 228022 524654 1205019 2727507 6050558 -5 1 7 46 164 442 1021 2158 4338 8483 16338 31194 59248 112115 211301 395803 734375 1344297 2418557 4262978 7343672 -6 18 51 113 214 364 571 846 1227 1840 3022 5539 10941 22106 44036 84980 157972 282886 489125 819077 1332488 -12 26 57 112 209 387 728 1412 2833 5815 11999 24548 49473 98181 192388 373478 719926 1378780 2620661 4932488 9168229 --4 -8 -4 25 106 281 627 1306 2657 5334 10477 19879 36097 62487 103290 164264 255098 396164 634330 1075909 1949772 -11 29 51 76 110 173 301 545 985 1804 3505 7403 16584 37594 83203 176682 358135 693543 1287303 2299182 3966754 --1 8 25 54 103 181 295 447 631 830 1013 1132 1119 883 307 -755 -2481 -5084 -8815 -13966 -20873 --3 9 36 78 135 207 294 396 513 645 792 954 1131 1323 1530 1752 1989 2241 2508 2790 3087 -6 18 35 62 114 237 541 1254 2830 6190 13265 28193 59904 127628 272524 582022 1240250 2631130 5545775 11591944 23985770 -9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 --2 -4 0 24 102 305 773 1775 3825 7912 15953 31656 62091 120417 230408 433667 800720 1447548 2559550 4425440 7484172 -8 19 44 98 215 467 1013 2188 4632 9456 18458 34449 61841 107806 184569 313801 534712 918433 1592800 2783964 4884691 -6 17 29 36 46 111 369 1090 2711 5832 11127 19108 29680 41463 50964 51899 35344 -8001 -81243 -166928 -199578 -7 15 48 123 261 492 860 1428 2298 3688 6163 11232 22755 50057 114512 262985 594501 1311829 2818870 5900153 12043773 -7 19 37 61 88 107 85 -64 -539 -1757 -4523 -10289 -21530 -42269 -78787 -140558 -241453 -401261 -647579 -1018127 -1563548 -3 11 19 27 35 43 51 59 67 75 83 91 99 107 115 123 131 139 147 155 163 -23 38 55 74 95 118 143 170 199 230 263 298 335 374 415 458 503 550 599 650 703 -0 4 15 38 81 153 262 413 606 834 1081 1320 1511 1599 1512 1159 428 -816 -2733 -5510 -9363 +12 23 42 82 168 344 680 1276 2260 3777 5966 8922 12640 16938 21356 25028 26524 23659 13266 -9070 -49320 +15 34 71 134 240 423 740 1277 2160 3570 5754 9047 14050 22517 40542 87994 223135 601424 1607163 4133978 10159334 +15 39 81 147 248 422 771 1513 3049 6045 11529 21003 36570 61076 98267 152961 231235 340627 490353 691539 957468 +6 11 39 100 210 397 707 1227 2161 4026 8085 17220 37600 81773 174330 362339 734970 1461479 2866653 5582890 10857048 +10 21 40 70 110 160 247 497 1286 3512 9042 21403 46799 95536 183913 336607 589690 995214 1631382 2631681 4270936 +27 38 57 93 169 347 778 1790 4032 8709 17982 35689 68709 129621 241968 450775 843758 1594525 3051300 5919610 11636474 +0 -4 -8 -12 -16 -20 -24 -28 -32 -36 -40 -44 -48 -52 -56 -60 -64 -68 -72 -76 -80 +1 -2 -3 16 82 231 523 1096 2290 4870 10357 21425 42223 78313 135653 217669 318919 413118 432325 232846 -458168 +13 12 21 69 199 471 972 1841 3324 5890 10472 18967 35283 67555 132843 266976 544707 1119752 2301727 4699093 9476243 +13 33 65 109 165 233 313 405 509 625 753 893 1045 1209 1385 1573 1773 1985 2209 2445 2693 +1 -7 -8 18 99 273 589 1103 1865 2893 4130 5380 6219 5877 3087 -4103 -18559 -44335 -86996 -153994 -255101 +3 17 45 93 165 264 395 571 824 1221 1892 3125 5745 12419 31491 86912 241517 647397 1647963 3973625 9099649 +10 23 36 54 93 182 365 703 1276 2185 3554 5532 8295 12048 17027 23501 31774 42187 55120 70994 90273 +12 25 56 107 187 336 661 1384 2902 5859 11230 20417 35357 58642 93651 144694 217168 317725 454452 637063 877103 +26 52 92 163 304 579 1070 1857 2998 4558 6798 10729 19368 40209 89648 200383 433154 894600 1763496 3328199 6038784 +-2 4 21 57 124 243 467 947 2087 4859 11374 25825 55922 114901 224068 415613 735200 1244058 2022171 3180313 4904132 +2 8 22 52 121 282 649 1447 3091 6335 12598 24686 48299 94956 187324 368505 717934 1379022 2609637 4880779 9081913 +20 24 36 69 136 250 424 671 1004 1436 1980 2649 3456 4414 5536 6835 8324 10016 11924 14061 16440 +5 11 26 50 83 125 176 236 305 383 470 566 671 785 908 1040 1181 1331 1490 1658 1835 +12 22 23 24 48 144 418 1087 2572 5679 11974 24545 49482 98650 194806 381099 739121 1424384 2738677 5282639 10285311 +5 6 13 28 53 90 141 208 293 398 525 676 853 1058 1293 1560 1861 2198 2573 2988 3445 +10 16 41 102 234 506 1054 2152 4351 8726 17285 33631 64079 119717 220538 404035 742961 1380936 2601168 4954146 9486849 +15 15 18 32 74 184 464 1152 2736 6111 12795 25277 47725 87635 159744 295021 560437 1100595 2221932 4556766 9371860 +17 33 61 120 248 516 1061 2159 4365 8753 17295 33424 62832 114560 202443 346979 577697 936105 1479305 2284368 3453568 +22 49 90 156 268 457 764 1240 1946 2953 4342 6204 8640 11761 15688 20552 26494 33665 42226 52348 64212 +20 36 73 141 257 455 802 1430 2605 4884 9472 18990 39005 80867 166705 338022 670560 1300620 2472769 4626995 8555831 +23 50 96 173 301 507 816 1225 1662 1961 1934 1707 2654 9616 35844 113649 316753 805908 1919180 4344905 9442347 +26 37 39 32 27 65 248 783 2040 4632 9560 18577 35201 67391 134001 279031 600774 1307683 2819725 5943834 12165623 +21 37 61 107 198 368 672 1208 2155 3831 6775 11857 20420 34458 56834 91542 144017 221497 333441 492007 712594 +4 2 -3 -6 16 117 394 1006 2223 4545 8949 17340 33299 63236 118068 215550 383390 663276 1115933 1827310 2915970 +7 5 7 23 82 257 711 1785 4160 9138 19104 38254 73705 137144 247226 432998 738709 1230467 2005325 3203521 5024764 +2 18 49 96 159 249 410 749 1469 2897 5496 9847 16584 26262 39135 54818 71804 86804 93875 83298 40165 +15 26 33 31 22 23 72 239 657 1604 3708 8453 19418 45245 106508 250980 586179 1345990 3021895 6612319 14080774 +12 29 67 144 279 503 879 1531 2686 4737 8339 14554 25065 42483 70775 115845 186304 294469 457635 699668 1052971 +19 23 32 47 59 55 31 16 127 708 2665 8203 22309 55516 128736 281274 583539 1156461 2200214 4035543 7161807 +10 9 16 45 125 309 685 1389 2620 4657 7878 12781 20007 30365 44859 64717 91422 126745 172780 231981 307201 +8 17 41 85 154 258 419 674 1059 1548 1914 1491 -1120 -8181 -22171 -42982 -60172 -35063 136561 696871 2159272 +6 2 9 46 144 356 768 1524 2902 5509 10696 21316 42928 85429 164786 303955 531245 873760 1344656 1929684 2599487 +7 13 39 95 204 419 839 1630 3062 5586 10021 18045 33466 65340 135201 293071 651731 1458387 3242246 7115374 15381672 +13 16 13 9 17 60 180 465 1108 2512 5452 11299 22302 41912 75117 128739 211623 334624 510271 751957 1072471 +6 2 -2 -6 -10 -14 -18 -22 -26 -30 -34 -38 -42 -46 -50 -54 -58 -62 -66 -70 -74 +11 21 51 123 270 550 1073 2042 3808 6951 12433 21930 38539 68170 122065 221025 402057 728257 1302799 2287877 3929316 +11 24 51 94 158 269 509 1079 2406 5315 11292 22869 44167 81638 145052 248780 413429 667890 1051865 1618944 2440308 +11 9 8 11 21 41 74 123 191 281 396 539 713 921 1166 1451 1779 2153 2576 3051 3581 +21 46 95 196 399 782 1466 2650 4690 8266 14709 26617 49028 91734 173958 333777 646619 1260214 2457923 4768850 9152061 +-7 5 31 71 125 193 275 371 481 605 743 895 1061 1241 1435 1643 1865 2101 2351 2615 2893 +3 17 47 97 176 318 630 1394 3267 7653 17382 37962 79934 163342 326127 639455 1234643 2348417 4395537 8079943 14556772 +1 5 16 41 92 192 388 781 1600 3380 7367 16390 36645 81173 176337 373376 768211 1534183 2974410 5603063 10268194 +16 36 57 83 133 258 583 1386 3218 7059 14511 28075 51691 92031 161701 286836 524079 996507 1966292 3976716 8123144 +12 25 48 88 169 350 745 1545 3042 5654 9963 16846 27992 47642 87632 180451 410268 981779 2364538 5581148 12758639 +19 29 50 106 228 460 871 1570 2721 4555 7376 11558 17530 25746 36637 50542 67615 87705 110206 133874 156608 +-10 -19 -27 -29 -20 5 51 123 226 365 545 771 1048 1381 1775 2235 2766 3373 4061 4835 5700 +13 38 79 139 222 344 567 1074 2311 5237 11749 25392 52543 104430 200766 376821 698259 1293730 2427213 4656039 9165638 +19 38 69 120 196 308 498 884 1726 3509 7050 13696 25837 48275 91545 179170 362157 745928 1537467 3123904 6198218 +24 49 86 150 269 484 849 1431 2310 3579 5344 7724 10851 14870 19939 26229 33924 43221 54330 67474 82889 +7 18 29 40 51 62 73 84 95 106 117 128 139 150 161 172 183 194 205 216 227 +24 47 78 112 144 169 182 178 152 99 14 -108 -272 -483 -746 -1066 -1448 -1897 -2418 -3016 -3696 +9 2 2 29 110 272 529 867 1250 1704 2586 5226 13282 35444 90674 218126 495443 1071502 2223126 4450075 8629042 +1 6 25 67 149 308 617 1205 2297 4315 8109 15411 29632 57200 109894 209324 396293 750976 1435741 2782551 5463323 +14 25 52 116 250 505 956 1708 2902 4721 7396 11212 16514 23713 33292 45812 61918 82345 107924 139588 178378 +1 19 46 89 178 377 800 1650 3323 6656 13448 27446 56064 113192 223554 429189 798757 1440513 2519946 4283247 7087950 +23 33 54 103 195 353 629 1145 2178 4330 8843 18140 36696 72368 138340 255868 458041 794807 1339548 2197525 3516553 +13 32 51 66 79 100 142 209 281 305 207 -53 -353 -169 1826 8384 24597 59190 126291 247792 456431 +16 27 51 108 230 461 857 1486 2428 3775 5631 8112 11346 15473 20645 27026 34792 44131 55243 68340 83646 +12 4 4 27 97 261 612 1319 2671 5172 9783 18503 35622 70173 140365 281103 556102 1076588 2029158 3716051 6611871 +0 8 23 54 123 265 528 973 1674 2718 4205 6248 8973 12519 17038 22695 29668 38148 48339 60458 74735 +13 28 41 46 44 60 169 540 1521 3810 8783 19072 39490 78366 149266 272961 479501 810760 1325705 2115606 3347448 +10 36 89 189 375 724 1379 2596 4835 8954 16639 31352 60365 118985 239073 485798 989906 2008729 4039473 8025686 15726089 +14 21 37 76 152 279 471 742 1106 1577 2169 2896 3772 4811 6027 7434 9046 10877 12941 15252 17824 +4 23 54 97 150 204 247 301 532 1486 4523 12582 31599 73400 162073 348415 742439 1584669 3397580 7296726 15609169 +8 14 17 9 -18 -55 -47 148 812 2432 5777 11987 22674 40035 66977 107254 165616 247970 361553 515117 719126 +-6 -5 14 69 182 375 672 1127 1915 3561 7468 17075 40274 94194 214185 469888 992764 2021515 3974646 7563229 13962050 +-7 -6 3 28 83 197 442 997 2271 5123 11246 23837 48787 96856 187753 357880 674949 1265048 2361413 4389658 8112139 +17 29 52 93 175 349 710 1421 2749 5117 9176 15901 26715 43645 69514 108173 164777 246109 360956 520541 739015 +16 21 25 37 86 235 599 1379 2936 5956 11806 23271 46045 91750 184157 372288 758444 1558423 3229987 6742565 14131100 +21 44 72 97 115 134 191 389 964 2388 5507 11703 23056 42466 73676 121115 189455 282748 402978 547829 707433 +2 13 51 142 332 698 1374 2605 4842 8891 16129 28800 50404 86192 143780 233895 371266 575673 873167 1297474 1891596 +-3 -4 -4 9 56 172 416 886 1739 3216 5672 9611 15726 24944 38476 57872 85081 122516 173124 240461 328772 +19 25 33 48 84 189 495 1300 3199 7317 15775 32655 65938 131202 258381 503887 972651 1859993 3535757 6721174 12868440 +6 19 53 133 311 693 1480 3033 5981 11400 21100 38066 67108 115784 195669 324052 526152 837953 1309767 2010643 3033749 +6 23 54 104 195 376 732 1399 2599 4721 8508 15508 29189 57643 119845 259373 572956 1267205 2767030 5916226 12338927 +17 28 34 33 24 11 20 131 528 1584 4047 9514 21640 49058 112038 256981 586879 1323687 2933530 6373928 13574464 +-3 4 21 51 105 213 434 875 1742 3459 6904 13824 27504 53778 102483 189470 339299 588758 991359 1622977 2588811 +13 25 55 113 225 449 904 1831 3718 7546 15273 30806 61970 124436 249300 497110 982731 1917647 3679267 6920687 12739335 +2 7 17 44 106 227 437 772 1274 1991 2977 4292 6002 8179 10901 14252 18322 23207 29009 35836 43802 +17 23 28 34 56 131 336 832 1965 4491 10062 22220 48288 102684 212226 423765 813665 1496731 2628376 4386946 6911520 +-2 12 38 85 176 357 708 1352 2460 4252 7004 11119 17476 28672 52658 112029 265450 653240 1588186 3726829 8377872 +6 8 10 18 37 69 111 153 176 150 32 -236 -729 -1541 -2787 -4605 -7158 -10636 -15258 -21274 -28967 +19 32 67 132 238 408 692 1190 2083 3682 6534 11681 21272 39920 77557 155217 316419 649028 1326253 2681698 5343402 +9 13 15 14 11 13 45 185 643 1915 5078 12386 28533 63352 137456 293614 618821 1285549 2626241 5263674 10332631 +16 26 38 52 68 86 106 128 152 178 206 236 268 302 338 376 416 458 502 548 596 +15 17 15 0 -42 -124 -236 -296 -58 1059 4308 12301 30382 69227 149452 309246 616213 1184609 2198865 3943522 6838250 +13 34 77 158 292 502 849 1495 2813 5560 11131 21914 41768 76648 135403 230775 380629 609446 950113 1446046 2153684 +29 50 89 159 280 490 863 1537 2772 5090 9596 18641 37065 74350 148120 289547 551359 1019298 1828043 3182795 5387918 +14 20 36 72 149 317 676 1400 2764 5174 9200 15612 25419 39911 60704 89788 129578 182968 253388 344864 462081 +18 33 48 66 95 157 309 688 1613 3806 8824 19824 42825 88716 176442 338164 627848 1135839 2013700 3516158 6070647 +3 11 37 102 253 583 1273 2672 5439 10784 20859 39374 72595 131145 233723 415411 746339 1372141 2597305 5048170 9976569 +0 1 21 79 212 487 1024 2049 4009 7805 15242 29878 58635 114950 225182 442034 873022 1740613 3507271 7129617 14561582 +14 26 46 95 206 436 885 1716 3177 5654 9845 17260 31459 60807 124182 262286 559538 1186104 2478626 5095643 10316494 +-4 -1 13 47 112 219 374 578 848 1281 2193 4399 9800 22685 52674 121271 276057 620630 1376470 3008722 6478201 +-1 0 5 28 87 209 453 975 2173 4961 11234 24626 51794 104808 205998 398114 765319 1474902 2856323 5544028 10724189 +2 11 45 112 217 362 544 761 1051 1612 3096 7268 18426 46373 112435 261189 582408 1250505 2592783 5203456 10128151 +1 10 29 71 160 332 637 1159 2098 3994 8216 17889 39501 85564 179013 360790 703924 1341902 2529732 4780667 9176991 +-10 -20 -23 4 95 295 660 1257 2164 3470 5275 7690 10837 14849 19870 26055 33570 42592 53309 65920 80635 +11 9 21 59 135 261 449 711 1059 1505 2061 2739 3551 4509 5625 6911 8379 10041 11909 13995 16311 +1 19 51 97 157 231 319 421 537 667 811 969 1141 1327 1527 1741 1969 2211 2467 2737 3021 +-3 -1 10 39 104 238 513 1097 2359 5037 10484 21007 40314 74084 130675 221985 364481 580411 899214 1359143 2009116 +1 10 20 30 39 44 44 60 185 677 2101 5525 12816 27236 54922 108622 216493 441168 918078 1927684 4024457 +11 11 11 24 76 206 462 893 1537 2405 3461 4598 5610 6160 5744 3651 -1081 -9713 -23857 -45532 -77224 +18 22 26 28 26 25 41 99 234 523 1207 3022 7991 21246 55208 139195 341286 816868 1912760 4381912 9808620 +22 34 61 124 262 539 1047 1910 3313 5620 9728 17964 36115 77645 171868 378894 815640 1699206 3416575 6633036 12456092 +4 10 16 22 28 34 40 46 52 58 64 70 76 82 88 94 100 106 112 118 124 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -10 39 84 155 274 478 822 1382 2258 3577 5496 8205 11930 16936 23530 32064 42938 56603 73564 94383 119682 -14 20 28 36 55 125 339 893 2188 5020 10925 22836 46429 93014 185790 373104 755626 1539976 3140634 6366800 12753827 -7 11 23 61 149 317 601 1043 1691 2599 3827 5441 7513 10121 13349 17287 22031 27683 34351 42149 51197 -2 17 46 106 224 434 774 1278 1968 2879 4203 6734 12972 29564 72323 176014 412622 924173 1979684 4070866 8068272 -3 19 61 140 272 488 855 1511 2716 4924 8888 15821 27651 47427 79956 132778 217617 352481 564623 894618 1401858 -28 46 83 153 270 448 701 1043 1488 2050 2743 3581 4578 5748 7105 8663 10436 12438 14683 17185 19958 -2 -1 -4 -7 -10 -13 -16 -19 -22 -25 -28 -31 -34 -37 -40 -43 -46 -49 -52 -55 -58 -12 23 35 45 59 111 289 776 1940 4546 10215 22320 47587 98760 198793 387149 728916 1327593 2342555 4012375 6685363 -23 42 73 123 204 331 522 809 1270 2089 3642 6606 12140 22383 42006 82571 173309 385056 879027 1999545 4440608 -13 11 13 39 126 334 753 1514 2825 5096 9307 17950 37204 81576 183196 409485 895339 1899903 3904777 7783021 15092756 --1 1 15 62 176 404 806 1455 2437 3851 5809 8436 11870 16262 21776 28589 36891 46885 58787 72826 89244 -16 27 40 63 118 253 558 1186 2373 4439 7735 12479 18397 24053 25715 15562 -21010 -109277 -290622 -629929 -1225416 -2 8 26 60 114 192 298 436 610 824 1082 1388 1746 2160 2634 3172 3778 4456 5210 6044 6962 -19 35 66 119 208 362 632 1115 2035 3961 8310 18388 41372 91838 197700 409748 816363 1565447 2896138 5183485 8999936 -20 44 88 168 310 553 949 1564 2501 4003 6763 12686 26541 59248 134022 297320 637610 1316534 2619234 5033652 9372744 -1 6 14 28 51 86 136 204 293 406 546 716 919 1158 1436 1756 2121 2534 2998 3516 4091 -1 12 27 53 120 288 653 1358 2617 4765 8374 14557 25775 47872 94901 199977 438633 977178 2169229 4741565 10139210 -24 32 47 84 172 371 797 1657 3309 6394 12158 23227 45369 91245 187908 390970 810062 1652628 3296417 6405494 12110442 -11 14 16 24 66 218 659 1783 4410 10145 21935 44885 87454 163330 294692 518407 898389 1550768 2695670 4764470 8622594 -9 22 64 155 318 581 991 1660 2882 5392 10886 22999 49091 103521 213787 432294 859071 1685202 3274052 6308883 12052900 -11 22 61 139 269 469 766 1217 1981 3506 6956 15133 34422 78851 178515 396967 866882 1862445 3944187 8243845 17014712 -5 14 21 30 66 185 494 1205 2759 6078 13050 27461 56833 116134 235288 474105 951045 1896610 3748735 7317076 14056480 -0 13 42 88 152 235 338 462 608 777 970 1188 1432 1703 2002 2330 2688 3077 3498 3952 4440 -4 5 17 61 185 476 1077 2214 4246 7775 13913 24927 45702 86816 170589 342437 691652 1389193 2756793 5394389 10415995 -17 28 46 87 182 384 785 1549 2967 5540 10096 17947 31092 52472 86283 138353 216589 331500 496802 730111 1053730 -30 46 68 112 202 378 724 1425 2862 5754 11356 21722 40042 71062 121596 201139 322590 503094 765012 1137028 1655402 --2 -5 -1 29 122 346 831 1837 3895 8087 16574 33537 66765 130206 247892 459757 829988 1458683 2497737 4172037 6807220 -22 30 48 100 224 484 1003 2030 4054 7978 15366 28776 52192 91568 155497 256018 409574 638134 970492 1443756 2105040 --3 1 8 15 32 105 360 1085 2877 6912 15476 33065 68676 140436 284532 571605 1135461 2221251 4263312 8006787 14692112 -16 35 69 120 206 377 733 1441 2752 5039 8932 15755 28740 56011 117280 257930 577399 1284978 2808078 6000729 12542125 -9 11 16 23 32 44 61 86 123 177 254 361 506 698 947 1264 1661 2151 2748 3467 4324 -10 20 45 95 185 345 634 1150 2034 3495 5961 10628 20989 46454 110042 263558 616093 1385974 2994218 6232675 12569356 -18 21 29 50 105 254 633 1501 3300 6733 12875 23374 40911 70322 121207 213541 388854 731069 1403201 2708962 5192037 -18 31 61 122 227 388 616 921 1312 1797 2383 3076 3881 4802 5842 7003 8286 9691 11217 12862 14623 -22 32 42 52 62 72 82 92 102 112 122 132 142 152 162 172 182 192 202 212 222 -10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 -13 35 67 117 209 391 754 1466 2823 5317 9719 17173 29295 48269 76930 118822 178217 260079 369955 513773 697525 -27 46 79 149 296 592 1171 2285 4407 8413 15894 29699 54946 101071 186214 346693 656995 1270352 2497601 4954049 9822324 --1 -2 2 24 92 255 600 1292 2661 5391 10921 22252 45487 92676 187042 372712 733159 1426452 2752264 5277040 10062018 --2 -1 12 46 113 243 525 1193 2777 6335 13779 28333 55290 103646 190259 350659 665941 1325896 2769231 5980153 13089536 --5 -1 19 69 165 325 569 919 1399 2035 2855 3889 5169 6729 8605 10835 13459 16519 20059 24125 28765 -1 8 23 58 129 260 491 886 1546 2663 4726 9145 19852 46961 114464 275419 640455 1429106 3059073 6296772 12504459 -17 43 85 154 278 518 996 1940 3751 7100 13085 23550 41841 74642 136289 258494 511481 1048509 2196953 4639266 9761996 --5 4 34 97 205 370 604 919 1327 1840 2470 3229 4129 5182 6400 7795 9379 11164 13162 15385 17845 -0 9 43 131 316 657 1241 2215 3848 6632 11441 19819 34620 61568 112979 216077 430288 880923 1821151 3740587 7547740 -19 24 24 14 -16 -77 -168 -234 -49 1067 4867 15440 41669 101882 232566 504784 1055569 2148985 4296498 8496059 16707712 --8 -6 -1 10 52 199 615 1618 3782 8105 16310 31454 59290 111441 212726 417455 843996 1744600 3640017 7568110 15525464 -19 44 93 182 342 632 1152 2056 3565 5980 9695 15210 23144 34248 49418 69708 96343 130732 174481 229406 297546 -19 38 77 161 332 651 1208 2154 3780 6702 12281 23525 46897 95699 196026 396694 785049 1511166 2823653 5121089 9024050 -12 21 42 99 242 568 1261 2675 5508 11149 22322 44199 86206 164800 307549 558899 988060 1699485 2846450 4648267 7411674 -9 6 -1 -12 -27 -46 -69 -96 -127 -162 -201 -244 -291 -342 -397 -456 -519 -586 -657 -732 -811 -4 17 46 97 187 346 618 1062 1756 2822 4539 7728 14826 32484 77244 187121 444340 1019516 2258574 4857886 10224905 -16 28 53 106 220 446 858 1582 2880 5334 10202 20079 40118 80285 159515 313419 608938 1173390 2254517 4347786 8466922 -13 39 72 115 176 270 435 781 1598 3551 7996 17490 36711 74412 148044 294951 598739 1248527 2665452 5759825 12430770 -17 40 82 157 280 477 813 1453 2779 5596 11487 23454 47176 93667 185129 367997 741815 1522010 3173022 6682697 14110922 -9 15 32 67 119 172 180 36 -472 -1693 -4079 -7987 -13117 -17108 -12104 23526 144519 481823 1333954 3351191 7890107 -17 20 38 90 210 468 1016 2185 4670 9865 20460 41494 82172 158891 300079 553708 999019 1765994 3071478 5293702 9134802 -5 -2 1 39 161 454 1057 2175 4093 7190 11953 18991 29049 43022 61969 87127 119925 161998 215201 281623 363601 -19 34 55 90 154 265 440 691 1021 1420 1861 2296 2652 2827 2686 2057 727 -1562 -5117 -10298 -17522 -20 32 47 78 159 354 776 1628 3289 6499 12757 25149 50002 100097 200860 402401 803348 1598842 3178136 6323201 12609933 --5 -2 7 17 28 52 124 332 904 2438 6443 16482 40377 94154 208674 440213 886617 1711062 3175887 5689431 9869282 -13 35 75 150 302 610 1210 2331 4355 7909 13997 24180 40812 67340 108676 171649 265545 402743 599455 876578 1260666 -16 32 67 132 241 427 769 1429 2700 5078 9406 17211 31482 58341 110406 213347 418786 830753 1662681 3364365 6907349 -18 26 36 46 51 47 36 29 53 199 812 3032 10058 29736 79378 194113 440564 938248 1891820 3638138 6713125 -11 37 82 154 274 493 916 1747 3393 6701 13458 27389 56109 114947 234469 475196 955891 1906493 3764126 7341668 14114472 -16 40 80 148 273 523 1036 2055 3961 7311 12936 22266 38262 67694 126062 247275 501350 1024946 2071592 4091096 7850935 -25 38 48 56 71 123 283 692 1616 3565 7532 15408 30585 58638 107764 188412 311503 485392 714412 1008488 1427223 -14 19 39 103 268 642 1425 2988 6036 11947 23455 45965 89980 175446 339407 649438 1227274 2290475 4225743 7716883 13965076 -5 11 28 66 140 276 526 997 1899 3617 6812 12556 22506 39122 65934 107863 171601 266055 402860 596966 867304 -8 13 31 81 208 495 1080 2181 4132 7434 12821 21329 34356 53787 82604 127367 206280 371838 768806 1774285 4323634 -9 18 35 71 145 291 576 1137 2256 4519 9166 18861 39330 82676 173737 361669 740083 1480624 2886941 5478659 10118335 -21 31 45 64 100 195 458 1132 2718 6217 13614 28847 59736 121792 245640 491198 974063 1913167 3714191 7111094 13399192 -1 12 32 58 95 164 317 674 1509 3439 7816 17487 38177 80909 166261 332305 650790 1262667 2458657 4861265 9826204 -14 27 54 100 181 331 619 1195 2388 4893 10124 20898 42785 86778 174547 348728 692995 1370992 2701051 5297233 10329738 --3 -8 -8 12 79 249 642 1504 3310 6928 13866 26611 49032 86770 147540 241478 382379 592396 916292 1457810 2461765 -15 31 60 102 157 225 306 400 507 627 760 906 1065 1237 1422 1620 1831 2055 2292 2542 2805 -10 23 51 110 230 460 877 1614 2941 5463 10551 21211 43741 90750 186443 375543 737860 1411367 2627747 4765780 8429696 -3 18 49 97 163 248 353 479 627 798 993 1213 1459 1732 2033 2363 2723 3114 3537 3993 4483 -6 15 28 43 60 83 127 248 635 1836 5238 13997 34750 80693 177053 370696 746640 1455529 2757432 5088111 9153132 -23 32 32 16 -28 -120 -291 -586 -1067 -1816 -2938 -4564 -6854 -10000 -14229 -19806 -27037 -36272 -47908 -62392 -80224 -14 39 73 108 148 223 407 847 1824 3904 8313 17801 38467 83342 179071 378052 780510 1575696 3122007 6109179 11895198 -22 47 93 176 322 583 1064 1956 3578 6459 11554 20802 38412 73511 145101 290630 579846 1135911 2165915 4002828 7160406 -7 16 39 76 127 192 271 364 471 592 727 876 1039 1216 1407 1612 1831 2064 2311 2572 2847 -2 12 42 105 217 391 629 912 1188 1358 1260 651 -813 -3599 -8321 -15766 -26922 -43008 -65506 -96195 -137187 -0 -3 -1 28 114 290 587 1029 1628 2379 3255 4202 5134 5928 6419 6395 5592 3689 303 -5016 -12790 -18 36 75 147 271 480 842 1511 2833 5551 11204 22950 47369 98511 206849 438313 932832 1978762 4151057 8560981 17302215 -10 3 -9 -17 8 121 408 1003 2153 4414 9142 19562 42850 93831 201048 416043 826640 1574737 2878477 5057525 8558344 -16 30 45 63 93 155 282 521 934 1598 2608 4126 6650 12007 26282 67260 181392 479382 1206027 2869985 6474071 -19 30 48 86 161 293 509 851 1382 2182 3348 5091 8201 15476 35234 88799 224921 545498 1248748 2698152 5528061 -20 39 73 127 212 360 646 1215 2312 4313 7755 13363 22072 35042 53664 79555 114540 160619 219917 294615 386860 -11 12 23 64 171 417 939 1972 3911 7453 13909 25812 47978 89232 165192 303042 550551 994426 1798527 3282128 6074521 -26 40 53 68 95 155 286 551 1048 1922 3379 5702 9269 14573 22244 33073 48038 68332 95393 130936 176987 -12 23 45 75 110 147 183 215 240 255 257 243 210 155 75 -33 -172 -345 -555 -805 -1098 -3 19 52 108 193 319 525 920 1764 3637 7828 17238 38379 85534 188923 409940 868373 1789219 3580508 6958696 13144865 -17 33 47 55 61 97 270 860 2510 6575 15736 35042 73634 147592 284807 533920 981975 1790865 3273077 6045893 11334635 -15 44 84 131 181 230 274 309 331 336 320 279 209 106 -34 -215 -441 -716 -1044 -1429 -1875 -6 27 67 134 236 381 577 832 1154 1551 2031 2602 3272 4049 4941 5956 7102 8387 9819 11406 13156 -29 47 79 131 212 342 560 932 1559 2585 4205 6673 10310 15512 22758 32618 45761 62963 85115 113231 148456 --9 -7 10 57 168 408 882 1734 3136 5286 8465 13246 21003 34935 61899 115437 220485 420367 786804 1433807 2536474 -8 13 43 123 295 625 1210 2185 3730 6077 9517 14407 21177 30337 42484 58309 78604 104269 136319 175891 224251 -14 21 37 71 138 259 460 786 1367 2600 5550 12739 29624 67357 148080 315462 656254 1344845 2734927 5545487 11231700 -6 16 35 76 161 319 589 1030 1740 2886 4747 7772 12655 20429 32581 51190 79090 120060 179043 262396 378173 -25 36 45 64 130 321 779 1754 3702 7500 14889 29333 57614 112746 219398 424500 819260 1586873 3107330 6185019 12529795 -7 6 2 -5 -15 -28 -44 -63 -85 -110 -138 -169 -203 -240 -280 -323 -369 -418 -470 -525 -583 -14 23 35 62 125 254 488 875 1472 2345 3569 5228 7415 10232 13790 18209 23618 30155 37967 47210 58049 -11 23 29 28 38 109 347 976 2491 6006 14004 31900 71212 155816 333902 700066 1434747 2872297 5614783 10716676 19976490 -13 13 16 25 40 69 149 377 951 2221 4750 9385 17338 30277 50427 80681 124721 187149 273628 391033 547612 -24 37 60 109 210 404 760 1411 2641 5071 10033 20303 41509 84771 171547 342454 673451 1306066 2504783 4766554 9027925 -7 28 58 104 184 327 573 973 1589 2494 3772 5518 7838 10849 14679 19467 25363 32528 41134 51364 63412 -2 9 15 18 16 7 -11 -40 -82 -139 -213 -306 -420 -557 -719 -908 -1126 -1375 -1657 -1974 -2328 --2 -8 -22 -36 -30 32 216 659 1677 4012 9338 21221 46842 99962 205876 409585 789396 1480256 2715538 4904886 8782742 -3 10 27 73 182 407 824 1536 2677 4416 6961 10563 15520 22181 30950 42290 56727 74854 97335 124909 158394 -10 19 44 102 227 482 972 1856 3356 5774 9577 15730 26695 48929 98377 211450 465398 1013941 2146626 4383766 8623131 -10 31 72 149 284 512 899 1586 2882 5437 10534 20547 39620 74630 136505 241976 415850 693899 1126468 1782913 2756988 -11 33 74 146 273 497 898 1641 3074 5923 11677 23368 47206 96055 196723 404751 833173 1706029 3453804 6877118 13417719 -8 21 58 132 265 504 939 1721 3091 5469 9726 17876 34585 70136 145929 304513 628138 1274073 2543782 5020872 9847569 --4 -8 -14 -25 -37 -22 109 583 1910 5132 12220 26671 54365 104750 192431 339247 576928 950432 1522070 2376535 3626959 -18 38 82 173 347 653 1153 1922 3048 4632 6788 9643 13337 18023 23867 31048 39758 50202 62598 77177 94183 -15 28 47 91 191 388 741 1353 2420 4300 7589 13199 22512 37951 64995 118188 236764 521302 1213228 2857007 6615220 -14 21 37 81 183 388 760 1386 2380 3887 6087 9199 13485 19254 26866 36736 49338 65209 84953 109245 138835 -16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 136 144 152 160 168 176 -3 8 23 61 141 288 533 913 1471 2256 3323 4733 6553 8856 11721 15233 19483 24568 30591 37661 45893 -14 30 57 99 167 295 569 1169 2424 4880 9381 17163 29961 50129 80773 125897 190562 281058 405089 571971 792843 --6 -7 -10 -4 37 154 403 855 1596 2727 4364 6638 9695 13696 18817 25249 33198 42885 54546 68432 84809 -1 6 25 68 141 255 458 900 1941 4312 9339 19240 37505 69369 122388 207128 337977 534090 820477 1229244 1800997 -17 27 53 113 230 432 752 1228 1903 2825 4047 5627 7628 10118 13170 16862 21277 26503 32633 39765 48002
\ No newline at end of file +9 8 21 69 176 372 699 1212 1959 2919 3883 4288 3066 -1343 -10535 -24783 -40075 -42542 1113 159039 557924 +1 16 60 158 358 738 1408 2507 4195 6640 10000 14400 19904 26482 33972 42037 50117 57376 62644 64354 60474 +20 22 21 17 10 0 -13 -29 -48 -70 -95 -123 -154 -188 -225 -265 -308 -354 -403 -455 -510 +-3 5 23 60 143 319 656 1258 2334 4412 8884 19231 43538 99304 222123 480607 1000995 2006303 3876685 7239966 13104153 +10 15 25 44 88 208 523 1256 2764 5551 10251 17566 28142 42364 60049 80014 99494 113383 113269 86232 13372 +13 37 81 153 272 480 861 1571 2883 5251 9397 16425 27966 46358 74865 117939 181529 273441 403753 585289 834156 +2 7 28 68 140 291 635 1395 2954 5915 11170 19978 34052 55655 87705 133889 198786 287999 408296 567760 775948 +20 28 50 96 174 294 475 763 1288 2415 5077 11414 25876 56981 119980 240885 463014 859349 1559953 2818936 5181974 +7 13 15 4 -22 -46 -20 147 601 1555 3301 6222 10804 17648 27482 41173 59739 84361 116395 157384 209070 +17 38 79 147 243 361 487 598 661 632 455 61 -633 -1725 -3329 -5576 -8615 -12614 -17761 -24265 -32357 +4 8 17 36 79 179 408 922 2076 4699 10679 24083 53127 113416 232994 459879 872908 1596882 2823181 4837214 8054279 +-6 -14 -17 -3 44 151 373 826 1744 3570 7093 13645 25374 45611 79351 133870 219502 350602 546723 834037 1247032 +16 17 11 6 33 172 590 1587 3655 7582 14694 27463 51007 96643 189932 388072 815806 1736311 3685345 7715308 15823521 +0 1 14 52 147 372 878 1951 4092 8121 15304 27500 47323 78312 125100 193571 290992 426105 609162 851884 1167323 +-8 -12 -16 -20 -24 -28 -32 -36 -40 -44 -48 -52 -56 -60 -64 -68 -72 -76 -80 -84 -88 +7 19 31 43 55 67 79 91 103 115 127 139 151 163 175 187 199 211 223 235 247 +18 32 52 91 175 357 745 1552 3186 6428 12816 25489 50979 102809 208305 420810 840554 1648848 3162100 5914471 10780879 +11 17 30 73 191 465 1027 2076 3901 6929 11845 19909 33795 59746 112848 229237 492797 1090457 2421002 5299149 11321357 +14 21 29 38 48 59 71 84 98 113 129 146 164 183 203 224 246 269 293 318 344 +-4 5 35 101 221 416 710 1130 1706 2471 3461 4715 6275 8186 10496 13256 16520 20345 24791 29921 35801 +7 24 54 104 190 348 660 1307 2673 5543 11461 23347 46542 90617 172651 323416 599235 1104514 2033496 3745154 6892958 +14 33 59 95 154 263 467 833 1454 2453 3987 6251 9482 13963 20027 28061 38510 51881 68747 89751 115610 +18 36 61 97 164 320 696 1557 3426 7359 15549 32578 67840 139937 284216 565080 1095282 2065110 3785205 6747735 11711788 +17 33 68 134 253 481 956 1980 4146 8531 17018 32923 62344 117095 220838 421203 812439 1575645 3047096 5829844 10969911 +0 -4 3 45 163 437 1033 2283 4804 9660 18569 34155 60243 102193 167267 265021 407712 610708 892887 1277009 1790043 +10 31 79 182 377 719 1314 2397 4488 8673 17071 33558 64819 121781 221434 388961 659958 1082315 1717031 2636830 3920909 +14 16 34 83 178 338 590 982 1624 2777 5002 9372 17764 33343 61654 113513 212633 414525 850169 1820632 3990833 +22 34 60 123 269 581 1201 2367 4472 8145 14347 24491 40682 66416 108613 182895 325854 621100 1250690 2590843 5381575 +12 22 52 117 235 441 816 1531 2906 5484 10120 18085 31185 51895 83508 130299 197704 292514 423084 599557 834103 +13 15 25 52 98 149 162 60 -243 -759 -1253 -927 2193 12653 41110 113380 292561 730027 1776413 4211078 9695696 +16 33 71 147 295 577 1094 1997 3498 5881 9513 14855 22473 33049 47392 66449 91316 123249 163675 214203 276635 +12 34 79 159 284 454 646 795 776 409 -471 -1813 -2921 -1652 6989 33242 96632 232776 504815 1022459 1973298 +-8 -5 5 22 46 77 115 160 212 271 337 410 490 577 671 772 880 995 1117 1246 1382 +27 45 65 79 88 116 228 556 1337 2967 6075 11621 21022 36310 60326 96954 151399 230513 343173 500715 717428 +19 29 35 31 11 -16 7 244 1058 3136 7629 16255 31258 55035 89131 132154 175973 199327 157687 -32129 -514491 +-4 -6 6 48 146 346 721 1368 2386 3824 5586 7278 7980 5924 -1943 -20534 -57360 -123458 -234538 -412380 -686514 +10 16 22 28 34 40 46 52 58 64 70 76 82 88 94 100 106 112 118 124 130 +-1 2 13 43 113 264 586 1280 2780 5992 12771 26881 55911 115042 234364 472995 946217 1877326 3695649 7218859 13985161 +12 33 65 110 170 247 343 460 600 765 957 1178 1430 1715 2035 2392 2788 3225 3705 4230 4802 +2 2 12 46 130 310 667 1358 2732 5616 11941 26010 56943 123223 260866 537596 1076622 2095565 3970036 7340823 13306956 +13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 +-5 0 10 23 41 87 236 675 1835 4679 11284 25922 56925 119712 241462 468036 873883 1575810 2751654 4665065 7697793 +24 48 97 178 306 515 878 1551 2863 5493 10828 21713 44020 89815 183426 372443 746638 1468994 2824479 5293880 9661890 +7 18 37 71 133 243 438 806 1571 3290 7299 16693 38385 87208 193646 417621 871759 1758470 3425433 6442527 11697805 +-3 -5 -7 -9 -11 -13 -15 -17 -19 -21 -23 -25 -27 -29 -31 -33 -35 -37 -39 -41 -43 +3 6 8 9 9 8 6 3 -1 -6 -12 -19 -27 -36 -46 -57 -69 -82 -96 -111 -127 +12 21 31 43 64 119 264 596 1264 2508 4796 9197 18226 37530 78957 165768 341020 680471 1311741 2441911 4396260 +4 3 5 28 113 330 780 1593 2922 4933 7791 11642 16591 22676 29838 37887 46464 54999 62665 68328 70493 +-3 -11 -15 -5 39 166 486 1225 2832 6203 13146 27299 55836 112460 222393 430337 812703 1495793 2682079 4687259 7991389 +2 15 44 105 228 460 868 1542 2598 4181 6468 9671 14040 19866 27484 37276 49674 65163 84284 107637 135884 +3 11 40 101 203 362 624 1102 2027 3813 7136 13027 22979 39068 64088 101700 156595 234671 343224 491153 689179 +8 14 31 75 163 315 572 1036 1948 3855 7982 17025 36728 78840 166482 343879 694468 1375852 2689261 5219099 10111301 +11 3 -7 -2 59 262 781 1951 4373 9055 17611 32574 57932 100100 169798 285943 484107 835051 1484409 2734358 5204293 +5 14 38 89 186 362 690 1343 2704 5543 11283 22391 42971 79763 144129 256634 458380 839057 1603913 3225958 6774521 +26 44 66 86 105 151 313 808 2113 5202 11927 25568 51546 98241 177780 306554 505084 796680 1204120 1743314 2412607 +11 33 60 102 190 391 841 1805 3768 7559 14517 26739 47549 82604 142745 251264 461497 896897 1837070 3892788 8345232 +1 11 30 55 97 192 415 917 2026 4480 9893 21594 46024 94927 188628 360754 664823 1183201 2039008 3411641 5556675 +9 8 8 4 -15 -66 -156 -237 -108 783 3719 11405 29158 66855 141981 284214 542091 992418 1753218 3001154 4994519 +5 5 17 55 129 252 459 846 1653 3444 7492 16579 36599 79643 169694 352720 713885 1405871 2693995 5025999 9137181 +0 13 44 102 195 329 521 849 1583 3473 8319 20037 46613 103696 221291 456385 916926 1807321 3514066 6764684 12917467 +-6 -11 -13 -4 32 126 332 745 1560 3245 6975 15596 35578 80698 178596 381901 786366 1559421 2983795 5522420 9912764 +-1 -3 -7 -5 31 163 501 1217 2559 4865 8577 14255 22591 34423 50749 72741 101759 139365 187337 247683 322655 +21 39 77 152 295 563 1051 1904 3329 5607 9105 14288 21731 32131 46319 65272 90125 122183 162933 214056 277439 +6 29 65 126 248 503 1024 2069 4175 8497 17505 36341 75339 154532 311548 615478 1191847 2269281 4269830 7987834 14947253 +20 40 73 127 227 424 804 1497 2686 4616 7603 12043 18421 27320 39430 55557 76632 103720 138029 180919 233911 +15 38 75 134 233 416 790 1593 3316 6923 14248 28714 56658 109863 210647 402612 774114 1510081 3005673 6111536 12652594 +7 5 15 45 96 157 201 191 120 139 873 4093 14036 39952 101162 237550 531921 1157605 2477551 5243665 10982708 +13 17 31 67 147 310 634 1286 2613 5287 10517 20341 38011 68484 119032 199984 325613 515181 794155 1195607 1761811 +17 33 54 81 115 157 208 269 341 425 522 633 759 901 1060 1237 1433 1649 1886 2145 2427 +28 54 99 175 307 547 991 1792 3153 5286 8362 12600 18924 31165 61765 144619 361520 893414 2115587 4769009 10261479 +20 36 69 139 273 505 876 1434 2234 3338 4815 6741 9199 12279 16078 20700 26256 32864 40649 49743 60285 +5 8 31 94 226 478 942 1781 3298 6123 11687 23304 48451 103329 221681 471406 985175 2015814 4035247 7910522 15218324 +27 35 51 98 222 513 1138 2401 4856 9517 18251 34532 64911 121863 229160 431651 812377 1521391 2822579 5167286 9306748 +12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 132 +5 14 30 60 119 234 466 966 2094 4650 10290 22218 46247 92318 176623 324791 577635 1003771 1730224 3017395 5437035 +-4 2 15 37 71 129 250 540 1263 3047 7341 17400 40333 91193 200824 430390 897530 1822532 3608915 6983275 13237359 +24 39 59 84 114 149 189 234 284 339 399 464 534 609 689 774 864 959 1059 1164 1274 +6 8 15 26 40 56 73 90 106 120 131 138 140 136 125 106 78 40 -9 -70 -144 +5 12 38 98 215 420 760 1327 2319 4138 7527 13771 25077 45463 82903 154219 295579 584290 1184142 2442474 5104989 +15 20 30 67 165 370 740 1345 2267 3600 5450 7935 11185 15342 20560 27005 34855 44300 55542 68795 84285 +12 24 49 91 167 328 704 1596 3655 8207 17801 37071 74010 141751 260934 462706 792350 1313466 2112529 3303523 5032193 +7 6 2 -4 -4 22 111 328 805 1860 4298 10072 23590 54100 119775 254360 517539 1010538 1898906 3444916 6052608 +24 41 68 110 172 259 376 528 720 957 1244 1586 1988 2455 2992 3604 4296 5073 5940 6902 7964 +4 -2 -4 16 84 230 492 935 1688 2998 5296 9266 15904 26550 42872 66777 100220 144878 201652 269956 346748 +10 4 6 36 129 338 741 1461 2717 4950 9122 17381 34440 70266 145074 298276 604163 1199220 2330420 4443939 8357344 +-6 5 46 132 274 482 787 1296 2299 4470 9269 19793 42598 91531 195593 414745 871234 1811092 3723960 7574705 15246840 +14 29 56 116 256 575 1274 2734 5619 10989 20383 35781 59259 91989 131979 169563 179100 104581 -164174 -829374 -2243510 diff --git a/src/main.rs b/src/main.rs index fea8e8f..d878a4e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -9,39 +9,29 @@ )] extern crate test; mod util; -use std::mem::ManuallyDrop; pub use util::prelude::*; -pub fn p1(a: &[i32]) -> i32 { - if !a[1..].iter().any(|&x| x != a[0]) { - a[0] - } else { - *a.last().unwrap() - + p1(&*ManuallyDrop::new( - a.array_windows::<2>() - .map(|[b, a]| a - b) - .collect::<Box<[_]>>(), - )) - } -} +/// generated by passing 1, 0{20} and 0, 1, 0{19}, etc to the original +const INTERPOLATION_P1: [i32; 21] = [ + 1, -21, 210, -1330, 5985, -20349, 54264, -116280, 203490, -293930, 352716, -352716, 293930, + -203490, 116280, -54264, 20349, -5985, 1330, -210, 21, +]; +/// just the reversed version of [`INTERPOLATION_P1`] +const INTERPOLATION_P2: [i32; 21] = [ + 21, -210, 1330, -5985, 20349, -54264, 116280, -203490, 293930, -352716, 352716, -293930, + 203490, -116280, 54264, -20349, 5985, -1330, 210, -21, 1, +]; -pub fn p2(a: &[i32]) -> i32 { - if !a[1..].iter().any(|&x| x != a[0]) { - a[0] - } else { - *a.first().unwrap() - - p2(&*ManuallyDrop::new( - a.array_windows::<2>() - .map(|[b, a]| a - b) - .collect::<Box<[_]>>(), - )) - } +pub fn solve(a: impl Iterator<Item = i32>, interp: [i32; 21]) -> i32 { + a.zip(interp.into_iter()) + .map(|(a, b)| a as i64 * b as i64) + .sum::<i64>() as i32 } pub fn run(i: &str) -> impl Display { i.行() - .map(|x| p1(&*ManuallyDrop::new(x.κ().collect::<Box<[i32]>>()))) + .map(|x| solve(&mut x.κ(), INTERPOLATION_P2)) .sum::<i32>() } diff --git a/src/util.rs b/src/util.rs index fa37f19..47da62b 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1,5 +1,8 @@ #![allow(non_snake_case)] -use std::{mem::swap, str::FromStr}; +use std::{ + mem::{swap, MaybeUninit}, + str::FromStr, +}; pub mod prelude { pub use super::{ @@ -226,7 +229,7 @@ impl Μ for &str { } } -pub trait IterͶ { +pub trait IterͶ: Iterator { fn ͷ(self) -> impl Iterator<Item = u8>; } @@ -236,7 +239,7 @@ impl<I: Iterator<Item = u64>> IterͶ for I { } } -pub trait TupleIterTools<T, U> { +pub trait TupleIterTools<T, U>: Iterator { fn rml(self) -> impl Iterator<Item = U>; fn rmr(self) -> impl Iterator<Item = T>; } @@ -260,13 +263,16 @@ impl<T, U, I: Iterator<Item = (T, U)>> TupleIterTools<T, U> for I { } } -pub trait GreekTools<T> { +pub trait GreekTools<T>: Iterator { fn Δ(&mut self) -> T; fn ι(&mut self) -> impl Iterator<Item = (T, u64)>; fn ι1(&mut self) -> impl Iterator<Item = (T, u64)>; + fn Ν<const N: usize>(&mut self) -> [T; N]; + fn ν<const N: usize>(&mut self, into: &mut [T; N]) -> usize; } impl<T, I: Iterator<Item = T>> GreekTools<T> for I { + #[track_caller] fn Δ(&mut self) -> T { self.next().α() } @@ -278,6 +284,29 @@ impl<T, I: Iterator<Item = T>> GreekTools<T> for I { fn ι1(&mut self) -> impl Iterator<Item = (T, u64)> { self.zip(1..) } + + fn Ν<const N: usize>(&mut self) -> [T; N] { + let mut array: [MaybeUninit<Self::Item>; N] = + // SAFETY: mu likes this + unsafe { MaybeUninit::uninit().assume_init() }; + + for i in 0..array.len() { + array[i].write(self.Δ()); + } + + // SAFETY: init + array.map(|elem| unsafe { elem.assume_init() }) + } + + fn ν<const N: usize>(&mut self, into: &mut [T; N]) -> usize { + let mut set = 0; + for e in into { + let Some(y) = self.next() else { break }; + *e = y; + set += 1; + } + set + } } pub trait TupleUtils<T, U> { |