Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Accepted

Solution code:
#"""
N, K = map(int, input().split())
Ps = [P-1 for P in map(int, input().split())]
Cs = list(map(int, input().split()))
"""
N, K = 4496, 785964262 
Ps = [692, 1627, 3242, 2678, 1985, 184, 1000, 4188, 1676, 4204, 4076, 502, 3982, 3676, 114, 1819, 3820, 1137, 2299, 4358, 42, 1808, 635, 3830, 2378, 3461, 3469, 123, 4382, 3268, 4067, 3353, 2695, 908, 119, 1641, 547, 290, 825, 183, 245, 1685, 2916, 1660, 2960, 697, 3411, 2714, 166, 2823, 3464, 4457, 1476, 2591, 3937, 3210, 3086, 973, 570, 2146, 426, 420, 4241, 3530, 4347, 2750, 4346, 4001, 1212, 1206, 600, 
4194, 2352, 1267, 3728, 2282, 4485, 4138, 969, 2274, 2738, 2193, 3097, 3366, 309, 2736, 2997, 1383, 4308, 2583, 14, 264, 1486, 15, 3060, 1065, 2648, 3415, 1186, 2002, 129, 2214, 3955, 878, 3508, 2448, 3506, 348, 2069, 4454, 2488, 238, 3683, 1167, 1863, 980, 1396, 1022, 4056, 23, 2497, 1254, 2067, 2086, 2017, 1736, 3577, 580, 3772, 2350, 3347, 2547, 1062, 3106, 3196, 4211, 3066, 722, 307, 3995, 2737, 2716, 1720, 3633, 1534, 883, 2155, 3825, 2921, 2944, 312, 2734, 838, 4349, 3773, 2417, 2013, 1520, 2505, 2389, 1869, 3945, 2857, 251, 2797, 2140, 370, 612, 357, 2719, 3113, 843, 1233, 810, 1945, 281, 835, 195, 2240, 3569, 1669, 2436, 619, 3267, 3334, 2825, 3517, 3219, 1600, 2936, 1105, 3272, 1540, 2565, 1196, 3586, 2075, 3844, 1269, 1667, 1936, 3360, 1916, 1023, 911, 1110, 742, 1117, 4107, 3996, 1438, 577, 1435, 210, 1626, 3465, 645, 3295, 3406, 1959, 1499, 2888, 2866, 1120, 2496, 3783, 1040, 3719, 3153, 472, 4208, 1071, 2046, 2524, 1562, 513, 3522, 4170, 2153, 1118, 3714, 2758, 656, 3039, 4398, 452, 2557, 2014, 1536, 914, 1004, 1971, 1098, 271, 421, 2910, 1664, 3537, 2263, 3118, 3053, 2376, 3385, 3604, 3608, 2208, 3388, 99, 1453, 642, 3748, 
4228, 45, 1944, 1232, 917, 733, 1873, 102, 2435, 1129, 3013, 4222, 1466, 3597, 2463, 563, 2324, 4273, 977, 3917, 4439, 480, 3401, 2956, 1064, 3398, 3747, 3779, 1372, 1312, 3315, 4150, 633, 528, 562, 1380, 3891, 3774, 1041, 2174, 2890, 2855, 358, 2822, 3423, 3258, 1058, 3414, 2684, 298, 1950, 2606, 2092, 723, 2820, 3950, 3971, 646, 3924, 983, 1115, 1637, 2709, 1924, 1263, 3663, 4105, 374, 1746, 275, 2693, 4195, 489, 2908, 856, 2657, 197, 2410, 4071, 791, 670, 4385, 1472, 1506, 1614, 1482, 839, 2319, 200, 4009, 3504, 1759, 265, 211, 4230, 475, 2515, 2500, 802, 4028, 2535, 846, 1907, 700, 4285, 484, 3596, 2161, 4225, 4081, 3892, 939, 889, 4202, 862, 167, 4135, 451, 2844, 1921, 440, 2012, 2491, 1678, 1122, 530, 4328, 568, 3936, 4130, 4331, 2973, 2633, 2169, 882, 2134, 4034, 2998, 2490, 3743, 1456, 3875, 2665, 3981, 4252, 854, 2184, 
602, 171, 4145, 3713, 3552, 544, 1874, 4286, 4058, 3930, 804, 3566, 4415, 380, 2983, 520, 1557, 1806, 2531, 1222, 3776, 2522, 3137, 175, 503, 3838, 1933, 4248, 1708, 4077, 4256, 4263, 395, 2053, 603, 11, 2218, 
2362, 2231, 1500, 1722, 3528, 1016, 256, 631, 1576, 2690, 3966, 394, 4361, 2798, 3654, 558, 4033, 3983, 2686, 3600, 3143, 3961, 3737, 3881, 1856, 2182, 1528, 1306, 3169, 1820, 2984, 1187, 1542, 1837, 4445, 3048, 3329, 2403, 4250, 659, 74, 2221, 3738, 2124, 1200, 249, 812, 2198, 1052, 241, 1447, 372, 2741, 2694, 479, 2063, 2745, 3087, 2834, 344, 3634, 2501, 3088, 2593, 3594, 4403, 756, 161, 582, 3638, 2621, 1088, 3427, 4120, 3845, 2712, 2341, 289, 435, 1495, 1505, 2774, 3526, 2598, 2990, 120, 1085, 609, 2752, 2628, 1853, 4309, 682, 1504, 4488, 2929, 2759, 3203, 235, 2913, 3313, 2854, 1226, 2900, 4483, 1917, 1358, 2399, 1257, 434, 2061, 3605, 3056, 37, 1195, 3866, 3823, 2314, 3330, 629, 2009, 737, 3627, 2957, 2995, 1898, 2081, 
4245, 3483, 3157, 376, 4084, 417, 1215, 490, 4479, 941, 236, 2532, 2147, 2777, 207, 3183, 191, 3583, 3116, 1831, 3103, 3903, 97, 2974, 4443, 794, 2397, 350, 1061, 928, 2083, 1815, 1208, 3260, 2006, 3085, 1290, 
583, 3298, 773, 310, 3705, 2807, 1141, 3125, 1274, 3394, 3148, 572, 3852, 2748, 1674, 83, 388, 12, 571, 3677, 3438, 874, 3009, 59, 413, 1275, 29, 1513, 785, 987, 1182, 423, 4486, 3, 3435, 940, 4490, 3014, 160, 
118, 2862, 3885, 4151, 3489, 4154, 665, 1428, 3674, 2788, 499, 1938, 637, 3523, 2550, 3138, 2114, 473, 1802, 402, 3987, 755, 4161, 1711, 652, 2652, 2958, 2529, 3721, 2461, 2903, 3359, 3829, 3422, 2634, 1189, 2811, 747, 3759, 4434, 1539, 2526, 180, 3631, 4148, 351, 2948, 963, 4466, 2038, 1531, 2398, 4011, 1258, 1163, 2104, 2302, 3096, 427, 795, 630, 3503, 1692, 3533, 1066, 3567, 3856, 4348, 4025, 1852, 3450, 511, 4141, 2932, 3775, 1538, 1640, 2179, 2080, 1473, 726, 3660, 1325, 4173, 2907, 2801, 2659, 4353, 3641, 2429, 3291, 3915, 1344, 1157, 2444, 149, 2611, 2474, 3407, 3026, 230, 155, 3751, 1360, 2032, 3032, 2113, 1922, 1686, 2574, 1982, 974, 1619, 3601, 932, 169, 1761, 2244, 647, 1253, 569, 2868, 78, 2039, 3166, 1906, 460, 3221, 306, 2653, 1221, 466, 2877, 1666, 4099, 1474, 2746, 2670, 49, 1076, 2523, 4315, 3680, 3209, 3648, 1727, 450, 4101, 3340, 515, 2281, 2942, 4383, 2338, 1882, 3510, 2480, 1030, 1670, 2210, 1164, 2507, 3131, 4160, 716, 4, 1710, 1464, 3205, 1787, 3841, 2132, 337, 1056, 3083, 222, 516, 3101, 2482, 3564, 522, 703, 4274, 4455, 3063, 1586, 3787, 1020, 1148, 1555, 1926, 3236, 3128, 3739, 2656, 3023, 87, 4446, 82, 2245, 2424, 34, 48, 644, 2589, 533, 1849, 806, 470, 3494, 2479, 734, 2626, 2225, 935, 546, 3886, 3044, 1981, 107, 3253, 3734, 3999, 776, 3395, 995, 418, 1814, 2864, 142, 2186, 2074, 704, 4337, 813, 3454, 993, 3192, 1266, 1968, 4327, 401, 3477, 2333, 1248, 1322, 2149, 3132, 3667, 1029, 439, 2542, 3920, 2062, 4418, 976, 885, 751, 3686, 2004, 3072, 4453, 3104, 2337, 3729, 3409, 2257, 1596, 1143, 2744, 283, 1577, 554, 1946, 1198, 836, 3570, 2385, 4092, 2853, 4132, 2059, 4268, 793, 4255, 3478, 2025, 1749, 366, 481, 2212, 1765, 4177, 2838, 2400, 1210, 4397, 1854, 105, 1093, 115, 852, 2343, 1673, 4059, 3447, 2048, 3749, 136, 2604, 3310, 
920, 3603, 2109, 3472, 1773, 1725, 2228, 1298, 2093, 4344, 1956, 1095, 535, 593, 893, 879, 1841, 3642, 2887, 324, 65, 2369, 2816, 1901, 1972, 4316, 64, 801, 1288, 3091, 3585, 1332, 3123, 203, 3420, 442, 2317, 3285, 4065, 996, 294, 2640, 140, 584, 69, 2264, 492, 1840, 1478, 1362, 2552, 2837, 3114, 2949, 1604, 701, 
4495, 1622, 1498, 1766, 3119, 1522, 2667, 3501, 497, 2020, 1458, 297, 4231, 510, 4300, 1149, 240, 1113, 3681, 4022, 1301, 3894, 1086, 126, 407, 1772, 3255, 1941, 3647, 4185, 4452, 3474, 3696, 884, 3900, 3741, 60, 1318, 3931, 938, 788, 2619, 4051, 3770, 931, 1079, 2548, 3954, 4472, 1346, 1964, 1455, 1419, 1334, 736, 3288, 1277, 2895, 933, 1307, 1927, 3364, 3688, 2310, 382, 1648, 1045, 1564, 4277, 3860, 1437, 4409, 2252, 2578, 924, 4329, 529, 3708, 3094, 360, 875, 2065, 3871, 3555, 2930, 4233, 1707, 710, 2312, 1256, 1561, 2215, 3911, 1112, 1073, 3453, 2311, 1718, 3278, 3319, 454, 267, 4332, 4384, 2912, 458, 3175, 318, 4032, 
2187, 765, 2243, 3908, 198, 749, 1150, 3546, 2676, 967, 653, 4093, 3805, 2770, 40, 3817, 1990, 3350, 540, 3757, 870, 1010, 4031, 627, 2166, 1705, 3417, 944, 525, 1855, 3784, 3198, 4166, 1517, 1940, 2723, 32, 2963, 4144, 3301, 3958, 1404, 3944, 3036, 3551, 1414, 4164, 2518, 1007, 919, 1800, 1593, 170, 66, 3440, 2729, 4079, 262, 1758, 22, 2706, 2534, 3792, 2423, 2764, 4400, 391, 1126, 1377, 0, 41, 2899, 3149, 3637, 28, 1799, 3003, 1240, 4482, 2739, 3715, 2923, 4020, 3282, 847, 2808, 803, 1104, 2183, 4219, 2704, 2353, 3756, 1803, 1770, 2993, 1899, 2740, 1994, 586, 3827, 514, 2332, 4007, 3057, 1321, 2364, 1238, 3403, 1851, 4005, 3392, 223, 3692, 443, 2171, 1603, 2927, 282, 3348, 3475, 1996, 2600, 3358, 4040, 3509, 4247, 950, 4187, 3876, 320, 1319, 3867, 3460, 1133, 246, 1785, 4061, 620, 3305, 1607, 735, 3281, 3437, 2294, 822, 2112, 
1037, 432, 292, 498, 868, 3090, 1285, 962, 4390, 2322, 4414, 2135, 523, 2784, 2203, 4421, 2117, 3614, 820, 229, 4018, 2840, 3720, 1185, 165, 1643, 261, 2464, 2286, 3947, 4014, 130, 2572, 1439, 3832, 4320, 2200, 2305, 1835, 1545, 1387, 476, 1448, 2978, 1813, 2647, 4481, 3540, 3991, 2551, 1136, 2800, 841, 2893, 4167, 579, 2829, 1430, 2126, 1341, 1055, 272, 2776, 3979, 425, 881, 3918, 3185, 1744, 799, 1698, 2559, 4372, 
887, 4089, 1828, 419, 3666, 134, 3789, 2919, 446, 1467, 3146, 1988, 738, 1986, 2207, 2674, 3284, 1947, 253, 3687, 3277, 4463, 433, 1866, 1700, 3907, 1371, 2023, 1156, 2234, 3556, 2585, 524, 2713, 3379, 2661, 1033, 4199, 2943, 1027, 3224, 4215, 3100, 3610, 1579, 1219, 1662, 748, 1632, 3531, 2625, 3445, 3992, 4406, 
3112, 4374, 2016, 2673, 3904, 2238, 2099, 3252, 1605, 2828, 1388, 2379, 2375, 77, 4388, 3287, 2858, 972, 
2495, 270, 3005, 2280, 961, 2597, 2351, 1121, 2671, 790, 4118, 1953, 4024, 4251, 1272, 3795, 2107, 4330, 
274, 3299, 1237, 3622, 2303, 3816, 1571, 4112, 2904, 1747, 2950, 4405, 2701, 4165, 873, 1914, 3579, 2, 4419, 2361, 3436, 4319, 952, 2022, 3575, 1442, 1178, 3357, 1337, 392, 557, 2425, 1609, 2773, 278, 1846, 2613, 777, 3134, 3030, 2196, 1738, 2698, 3365, 537, 2120, 3412, 2847, 4236, 3873, 1843, 179, 2348, 1781, 678, 2267, 3368, 2247, 1935, 1570, 4493, 1368, 2883, 2845, 1844, 998, 3562, 495, 400, 2472, 3810, 1850, 4060, 907, 1236, 3695, 1080, 741, 88, 3304, 2931, 3200, 449, 38, 2570, 3898, 2010, 661, 2133, 1171, 1915, 408, 4393, 720, 2966, 2568, 2796, 2586, 2468, 1295, 3283, 447, 3986, 1373, 4257, 532, 954, 4116, 5, 4262, 1087, 1634, 2265, 2027, 762, 3071, 943, 1532, 3189, 2486, 3525, 2021, 4444, 4237, 2487, 1191, 257, 3684, 4289, 946, 2202, 2363, 548, 1077, 966, 4395, 483, 3276, 55, 1340, 707, 3554, 3391, 2467, 3081, 2871, 552, 2392, 1408, 2232, 3441, 2540, 2979, 2275, 539, 1735, 1445, 1003, 798, 4296, 2181, 1734, 3386, 3074, 94, 699, 797, 3426, 1639, 1450, 1067, 4399, 363, 3468, 4224, 3240, 964, 1190, 1646, 606, 1350, 501, 268, 2897, 
4235, 3910, 132, 1780, 3016, 2727, 3538, 2452, 3589, 429, 4264, 1006, 771, 2078, 3045, 1771, 4175, 3699, 
2178, 628, 3062, 1955, 590, 3837, 3218, 362, 863, 217, 2700, 2617, 3923, 4062, 2556, 695, 3182, 3902, 1515, 4090, 4019, 3179, 1140, 3735, 2051, 2629, 334, 2041, 3619, 4306, 2354, 1114, 2316, 3399, 232, 9, 2850, 4053, 2896, 2789, 3043, 291, 2293, 965, 2318, 660, 2669, 3766, 4378, 1008, 3156, 871, 1858, 2000, 2609, 
2502, 576, 1328, 1323, 1012, 4298, 3174, 2030, 163, 4100, 3433, 46, 500, 3592, 581, 2886, 3073, 4098, 3919, 4232, 2939, 3493, 4464, 3593, 4303, 4196, 1697, 1582, 541, 2914, 4002, 1034, 1796, 3154, 3323, 1059, 922, 1580, 3826, 3644, 2610, 504, 1429, 4324, 398, 2239, 1891, 1987, 1229, 2780, 864, 2951, 1361, 886, 608, 4227, 1822, 2121, 3935, 2386, 2223, 4338, 3499, 1405, 3029, 1130, 2060, 1827, 4426, 684, 4122, 4280, 4427, 2165, 1244, 2277, 2576, 4336, 770, 3002, 505, 517, 1014, 393, 3314, 3970, 3497, 4191, 1297, 550, 3322, 1753, 4291, 1276, 721, 2473, 4125, 2076, 3397, 1393, 3998, 1934, 4229, 3186, 1612, 831, 4139, 462, 3778, 1864, 3777, 3668, 3815, 3212, 1881, 3697, 2156, 2519, 3230, 3142, 4429, 2037, 840, 3643, 3462, 611, 1165, 826, 3217, 2152, 3879, 2346, 1342, 1553, 4050, 396, 3042, 3943, 2620, 1492, 4340, 849, 4394, 445, 1845, 732, 3485, 1099, 3656, 213, 2308, 2859, 226, 2344, 3225, 4254, 903, 1313, 3246, 4240, 3122, 3126, 4425, 1688, 2668, 4149, 2642, 35, 890, 4278, 4035, 1647, 1324, 2769, 2782, 3512, 1897, 2898, 2566, 1017, 2103, 958, 923, 2101, 4168, 3167, 1490, 1979, 2689, 727, 3797, 4134, 3559, 2986, 1878, 990, 1537, 3862, 4323, 
3408, 549, 3625, 4318, 1703, 1327, 3914, 4436, 4104, 3296, 1932, 4272, 1379, 3803, 1021, 3231, 1514, 4474, 2205, 2827, 2489, 730, 837, 2285, 2666, 1111, 1264, 2268, 152, 3786, 1867, 1279, 947, 913, 824, 1349, 3471, 2419, 1608, 4069, 1797, 4460, 178, 872, 2451, 3476, 621, 1516, 906, 1070, 800, 4282, 4066, 1826, 3818, 679, 1590, 2106, 2643, 144, 4106, 375, 227, 787, 4017, 16, 2443, 753, 1075, 1234, 2057, 3152, 598, 1743, 96, 1083, 1385, 3755, 4123, 2879, 1421, 2813, 61, 3736, 3703, 2157, 869, 4422, 3863, 325, 850, 4213, 3572, 3421, 1291, 564, 3657, 3289, 2052, 3389, 3024, 2924, 486, 3969, 2935, 956, 4012, 3500, 2331, 3545, 1833, 1884, 1002, 2035, 3214, 2033, 2980, 1252, 2972, 2217, 2297, 3843, 2258, 106, 2969, 2594, 626, 1776, 
2219, 4064, 346, 4242, 4013, 4492, 2118, 2366, 2646, 1427, 591, 1684, 1521, 3771, 715, 1991, 910, 2426, 1696, 1830, 2873, 1682, 2395, 2007, 1631, 921, 1838, 706, 71, 3956, 141, 1890, 20, 2836, 4172, 3985, 2261, 2851, 640, 694, 2396, 258, 1875, 1365, 2102, 685, 779, 2743, 3099, 2735, 2475, 3630, 1305, 1565, 3921, 3482, 416, 2066, 615, 2622, 214, 4201, 3669, 2961, 1859, 3547, 2368, 1661, 1245, 2970, 3746, 2901, 3576, 2722, 718, 2945, 1694, 1422, 3324, 2204, 2289, 244, 891, 2483, 4367, 4420, 2756, 2765, 2527, 4259, 1816, 3650, 1304, 4317, 3590, 3355, 24, 712, 2446, 1839, 2015, 4155, 209, 2168, 4462, 2991, 2177, 2040, 1857, 2682, 2814, 1589, 441, 3133, 3978, 1192, 4221, 1847, 3868, 3617, 1038, 3451, 1460, 3033, 888, 3928, 3449, 3220, 4339, 4126, 658, 2393, 3000, 3685, 3381, 3383, 3173, 805, 1980, 2982, 1892, 1043, 3109, 1910, 4143, 
2447, 2031, 1217, 2605, 4246, 657, 3916, 2295, 1241, 1024, 174, 3271, 2909, 3568, 2641, 3788, 3111, 1721, 4494, 187, 3012, 3865, 2141, 1352, 333, 759, 4356, 3964, 448, 4294, 4073, 263, 2905, 1097, 3082, 686, 1481, 2680, 3646, 1592, 349, 4314, 95, 3416, 3701, 4302, 1441, 1546, 1146, 1762, 3377, 4036, 4326, 3197, 4218, 336, 3343, 4074, 2422, 3649, 1783, 3754, 4039, 2925, 4198, 27, 81, 985, 3712, 153, 3727, 3859, 1663, 
3262, 4352, 4423, 865, 1153, 199, 1731, 3710, 2772, 4307, 3967, 654, 2933, 1723, 757, 3864, 3124, 4310, 2328, 3744, 2089, 3321, 2708, 1529, 2513, 2536, 1184, 1069, 880, 494, 2778, 116, 4437, 1768, 2696, 2726, 3565, 2588, 3557, 4261, 4335, 4370, 2702, 2511, 3463, 3243, 1975, 1824, 4341, 3206, 2381, 821, 4157, 905, 
1560, 968, 220, 1401, 3934, 4381, 1714, 103, 1518, 221, 2882, 521, 1426, 1355, 957, 3616, 459, 807, 2143, 300, 250, 4295, 3008, 2313, 2434, 1801, 2142, 4376, 2988, 4142, 3573, 999, 1446, 1390, 1574, 159, 3102, 
2077, 4288, 3785, 2799, 2127, 1818, 378, 1231, 3164, 4026, 3702, 1812, 789, 4375, 2876, 2405, 3994, 406, 
3765, 4467, 3580, 2402, 3842, 561, 997, 287, 3806, 1642, 929, 2296, 4006, 329, 93, 2793, 3984, 2560, 192, 3821, 784, 1207, 4205, 2283, 3965, 188, 897, 859, 2754, 3717, 3491, 709, 1224, 545, 461, 4271, 3661, 3022, 2863, 3912, 1943, 3639, 3139, 3346, 4244, 3707, 1885, 1465, 4113, 1524, 2783, 3238, 2440, 902, 2292, 228, 18, 1995, 1659, 1395, 3544, 1, 3794, 4110, 2881, 3068, 1270, 2516, 696, 4000, 2865, 2418, 2564, 688, 
3349, 1444, 744, 2213, 2250, 1709, 371, 3833, 4380, 2070, 664, 1209, 186, 708, 3670, 2967, 2717, 1452, 2889, 205, 4266, 1993, 1512, 526, 592, 1485, 3162, 927, 3836, 3479, 4366, 3266, 3694, 2962, 768, 1289, 786, 3752, 989, 3380, 3607, 2406, 321, 3075, 2269, 2697, 1090, 1876, 3363, 1912, 567, 1169, 1280, 1013, 4417, 1870, 1403, 255, 1399, 2079, 1060, 1286, 1549, 518, 904, 2981, 224, 1145, 1992, 323, 4223, 2469, 2138, 1519, 2809, 1255, 844, 2409, 3425, 3341, 3884, 1970, 1391, 1174, 4200, 2947, 4489, 3893, 1691, 3854, 2581, 1511, 3618, 945, 2164, 2036, 3187, 896, 4108, 3325, 285, 3535, 1035, 2309, 3549, 2911, 2347, 485, 3290, 
1602, 2655, 3973, 3178, 1755, 1902, 809, 101, 2404, 1905, 3459, 4136, 2454, 3938, 3502, 1431, 2172, 1706, 4276, 3201, 409, 764, 4279, 1655, 1418, 2742, 1832, 4042, 2384, 3223, 1779, 2255, 2821, 2229, 2415, 2649, 1983, 3850, 4117, 2992, 1699, 894, 3733, 536, 225, 714, 3655, 4311, 2753, 2370, 1031, 725, 1320, 3382, 
1923, 3351, 4029, 156, 4083, 304, 2786, 1028, 1124, 4484, 2477, 1702, 2614, 3135, 717, 3316, 2953, 3529, 
3080, 1558, 36, 3764, 319, 4169, 3929, 1584, 3925, 4162, 2651, 3874, 364, 2528, 3870, 2499, 3553, 814, 4037, 2256, 3665, 2999, 1525, 2382, 2249, 151, 3913, 2512, 4333, 2842, 2976, 1354, 2971, 4193, 604, 675, 2624, 1963, 650, 3834, 655, 2830, 3270, 2056, 4325, 857, 2493, 3158, 4442, 2024, 467, 2728, 991, 2755, 4210, 305, 1048, 3228, 4085, 2211, 2401, 4354, 4171, 1242, 1417, 3234, 2272, 4103, 4010, 3498, 3484, 3802, 2768, 1628, 259, 1348, 273, 2246, 3626, 3953, 3543, 3963, 464, 216, 4412, 3516, 2584, 2603, 3524, 1533, 1621, 1903, 3232, 1170, 3536, 3431, 4088, 2091, 2320, 918, 301, 89, 691, 912, 2377, 1811, 4176, 2098, 693, 1005, 3010, 1128, 2100, 3028, 2677, 1262, 3629, 1410, 1942, 2710, 3215, 2630, 496, 1900, 52, 2562, 1790, 3851, 1599, 4102, 1775, 2330, 1284, 2577, 559, 1930, 280, 1314, 575, 4140, 455, 150, 1384, 1101, 252, 437, 4212, 482, 2691, 3824, 4299, 587, 4465, 1218, 2860, 3563, 1651, 1096, 1552, 1550, 2131, 3690, 4095, 3055, 339, 3905, 668, 1078, 3194, 1757, 2579, 148, 2438, 624, 2875, 1278, 1503, 3672, 4487, 3740, 3410, 1623, 2087, 1587, 3782, 1051, 75, 4207, 2818, 1294, 607, 2185, 3652, 138, 2601, 2804, 1412, 303, 4055, 2276, 2675, 2173, 2891, 2387, 3587, 1181, 728, 2003, 2553, 1872, 2934, 3855, 2197, 1887, 2715, 2054, 3809, 108, 
2329, 1247, 551, 674, 3207, 3723, 3972, 2679, 353, 4147, 1273, 359, 415, 1998, 1411, 3732, 2270, 76, 2937, 930, 2771, 284, 667, 1343, 2802, 3311, 2663, 1680, 1175, 2520, 2476, 3473, 2662, 616, 2096, 1613, 2150, 3922, 2892, 3312, 842, 3195, 1689, 2831, 3658, 3602, 3129, 1879, 2373, 1573, 72, 1311, 3518, 1585, 2718, 3017, 3813, 2144, 2471, 1650, 636, 1049, 2711, 1243, 3344, 2685, 340, 649, 830, 125, 2005, 154, 1911, 2638, 2987, 971, 30, 2278, 2833, 4360, 1717, 2105, 1502, 3180, 2852, 574, 1299, 3442, 2220, 3948, 3704, 2569, 3507, 3374, 2090, 4004, 3061, 1798, 2028, 1871, 2874, 3202, 1180, 1018, 1359, 3352, 1974, 2616, 2431, 
1693, 2721, 519, 3651, 3521, 2846, 2763, 1357, 2437, 3718, 3906, 3558, 1611, 3108, 4114, 4192, 1309, 1948, 3742, 1409, 373, 3960, 386, 2110, 2805, 1389, 3147, 2994, 760, 3767, 2071, 1364, 1281, 338, 2129, 1082, 1810, 2731, 2654, 68, 2810, 3974, 1356, 1091, 243, 477, 314, 2639, 4156, 3673, 3716, 430, 3561, 405, 3949, 3990, 1817, 2064, 2747, 3758, 3136, 2872, 2612, 2416, 3976, 4133, 3632, 1454, 1402, 828, 3448, 2253, 565, 3079, 3975, 2456, 2533, 3049, 2922, 2439, 792, 2841, 1606, 3176, 3724, 1432, 3725, 2019, 2018, 1063, 
1740, 2928, 1032, 915, 3098, 3274, 578, 1769, 2188, 58, 2095, 296, 623, 3376, 2394, 3861, 3184, 3691, 774, 86, 1204, 3226, 1728, 2484, 3257, 1213, 491, 3054, 1378, 17, 2195, 3678, 1594, 2938, 1509, 2043, 1675, 
858, 4124, 555, 3308, 4290, 2623, 3434, 1260, 2537, 1784, 2664, 1326, 3402, 901, 4432, 128, 4321, 4174, 1726, 827, 85, 145, 4260, 2159, 3326, 1054, 4239, 1862, 276, 1896, 1888, 2703, 1795, 3889, 3541, 2757, 2817, 109, 7, 3515, 1331, 3095, 1201, 1177, 331, 1629, 2749, 1760, 2985, 1025, 4451, 1657, 1904, 3659, 1598, 992, 1329, 984, 4267, 112, 3269, 3799, 2952, 3327, 3405, 1929, 761, 3115, 1239, 3110, 4357, 4003, 3093, 
1507, 1704, 1510, 1415, 2720, 543, 3514, 2465, 3181, 2199, 2812, 2191, 308, 2323, 1969, 3946, 2458, 1268, 4253, 3790, 1151, 1918, 1214, 3191, 1382, 1774, 3390, 404, 4068, 1261, 4021, 1131, 1951, 2539, 355, 3018, 3424, 778, 796, 2573, 3294, 639, 2492, 731, 3811, 589, 1089, 2650, 2430, 1162, 4387, 2538, 111, 2151, 1763, 181, 1957, 3038, 1249, 3069, 3977, 1526, 1591, 63, 1250, 689, 2441, 3213, 979, 2413, 277, 752, 729, 
3244, 1925, 1335, 643, 2137, 3466, 713, 3840, 1617, 781, 2055, 4297, 978, 1134, 2291, 410, 3239, 4459, 3170, 3878, 4054, 84, 3120, 3051, 1011, 1168, 3942, 3034, 3058, 585, 3328, 2975, 3542, 39, 3877, 2136, 3621, 3362, 4287, 299, 212, 57, 1939, 206, 1483, 2608, 3216, 2130, 936, 177, 4402, 2627, 1523, 247, 2968, 4234, 3486, 3375, 4312, 3571, 1954, 173, 1960, 853, 1310, 3467, 1183, 1036, 2732, 13, 4396, 4391, 3519, 1494, 3387, 3989, 2645, 3404, 4016, 1345, 3615, 3155, 1246, 1339, 4350, 242, 2034, 3980, 823, 2509, 1909, 2145, 1635, 2517, 1119, 3254, 4180, 3140, 1834, 3511, 4379, 2683, 1369, 2870, 2325, 1588, 4183, 3513, 3199, 
3035, 1581, 354, 3807, 4473, 347, 146, 2724, 4158, 4283, 1920, 3229, 328, 3753, 288, 2977, 121, 1461, 1462, 2546, 1683, 2582, 33, 4424, 4364, 2162, 3127, 780, 3256, 900, 1159, 4275, 3249, 1616, 469, 1962, 3275, 3418, 687, 4249, 3107, 384, 1487, 135, 327, 361, 632, 3273, 1370, 1778, 4377, 2442, 2042, 1475, 2792, 3332, 4292, 1644, 3050, 2047, 3993, 4048, 1139, 2334, 955, 4448, 898, 3452, 1333, 1497, 2336, 3869, 1665, 3040, 1106, 634, 3857, 1805, 1928, 2730, 3927, 3671, 605, 1794, 3847, 4450, 3419, 1125, 293, 2791, 3208, 1654, 2189, 3598, 2832, 4461, 3781, 4480, 3041, 465, 3130, 1786, 2637, 2222, 3480, 92, 1919, 2049, 3700, 926, 25, 4087, 1656, 4416, 1425, 3248, 1293, 2050, 2762, 204, 4413, 4206, 507, 2408, 1559, 3662, 3302, 4179, 2449, 3356, 2470, 51, 4091, 4072, 681, 1535, 3384, 403, 2237, 2699, 3020, 937, 1102, 162, 1541, 1636, 
2428, 43, 4389, 2545, 4044, 4008, 2498, 4365, 4159, 1894, 3235, 157, 53, 1440, 215, 754, 4153, 2941, 861, 860, 3780, 1469, 1544, 313, 1338, 3339, 219, 651, 1188, 356, 1407, 2365, 4458, 332, 4491, 2861, 2111, 411, 3428, 1135, 4129, 1984, 2128, 1259, 2779, 399, 342, 3222, 1620, 4362, 3835, 2954, 3259, 1999, 4137, 3791, 3798, 2148, 3121, 1471, 4152, 610, 2450, 4270, 2119, 202, 3015, 2599, 2290, 671, 3190, 2906, 3822, 322, 1211, 745, 3300, 4435, 724, 1366, 743, 3997, 2194, 1443, 3092, 379, 1729, 3645, 3047, 3439, 1317, 1791, 31, 286, 2806, 385, 2094, 3456, 19, 3804, 3706, 698, 3077, 1227, 1132, 1424, 3495, 104, 3664, 124, 1116, 1376, 1880, 1413, 3372, 4438, 1563, 2839, 1386, 2506, 1967, 1997, 3940, 1913, 4146, 1197, 3926, 2494, 1804, 673, 2504, 3709, 1155, 4038, 1488, 2241, 2420, 352, 2122, 2885, 680, 2767, 2688, 1107, 168, 54, 1569, 345, 1649, 4404, 3078, 3611, 3070, 4440, 3413, 892, 3808, 3233, 2794, 4082, 444, 3333, 2856, 3796, 1671, 1508, 4109, 2563, 2011, 1193, 702, 3470, 3303, 4217, 1958, 234, 3159, 2466, 1719, 3171, 3539, 1084, 3336, 3065, 3584, 2160, 2940, 2561, 2848, 4355, 2072, 614, 819, 2082, 2790, 2260, 117, 2915, 3801, 848, 2590, 1375, 1315, 1057, 4226, 1701, 3144, 2388, 3141, 534, 553, 1491, 1908, 899, 193, 493, 2631, 750, 3335, 3297, 3578, 2481, 1860, 387, 3574, 1601, 4334, 2073, 3730, 1748, 1889, 3628, 1179, 4189, 2176, 1645, 4047, 1282, 2766, 672, 4070, 948, 2819, 1205, 3264, 1094, 311, 2358, 666, 527, 4407, 4343, 113, 295, 1216, 1754, 4428, 2964, 2580, 4049, 833, 4468, 2575, 4430, 3613, 1861, 3237, 2026, 1493, 365, 1161, 3711, 4363, 829, 3151, 4115, 98, 4086, 3722, 4258, 769, 3599, 1713, 1672, 4220, 845, 2615, 4441, 705, 1745, 2785, 3880, 367, 3037, 457, 2549, 3595, 3620, 2170, 2235, 3682, 2411, 1618, 1053, 1679, 3988, 508, 3361, 1147, 1551, 2154, 80, 1123, 4023, 1144, 3338, 316, 1625, 1398, 1624, 343, 1316, 4181, 2345, 2636, 3025, 2705, 2383, 
2008, 909, 1977, 4293, 1381, 2307, 1750, 4284, 2262, 4097, 389, 1194, 3021, 2571, 4216, 1109, 2254, 143, 
1127, 4027, 2414, 763, 1886, 3968, 2315, 1566, 1825, 3369, 1966, 3059, 2554, 3768, 2803, 4190, 1225, 158, 2360, 4094, 3064, 1138, 381, 1199, 4127, 2460, 2760, 811, 506, 1489, 3337, 190, 3901, 3318, 782, 1961, 2824, 1202, 1737, 3027, 2459, 1652, 3019, 4214, 1767, 79, 2902, 189, 3286, 4096, 1556, 1158, 3812, 3031, 254, 3769, 4203, 2116, 397, 3378, 21, 815, 3250, 1451, 233, 1989, 2233, 3581, 3909, 4431, 1597, 2335, 1042, 1554, 599, 2327, 4373, 4197, 2412, 3819, 1821, 783, 3172, 1547, 775, 662, 44, 767, 1751, 260, 2372, 2660, 1931, 531, 1142, 1658, 2543, 895, 422, 4243, 1172, 172, 1477, 3488, 3653, 1296, 1567, 1092, 3331, 2374, 4163, 4371, 3241, 2917, 1100, 377, 3745, 3957, 3962, 110, 3849, 3345, 2525, 3959, 1484, 1459, 3679, 1228, 4411, 986, 994, 3698, 2349, 1251, 1865, 3487, 4057, 867, 488, 2242, 3897, 279, 1265, 960, 1937, 3320, 
4265, 1789, 1152, 1470, 3527, 1039, 1283, 3089, 424, 595, 1575, 3760, 3899, 1829, 4368, 456, 2192, 1868, 
981, 817, 1895, 1752, 1394, 3848, 2462, 2632, 2340, 2503, 4281, 2167, 137, 1695, 317, 2058, 1724, 471, 2226, 613, 3007, 4131, 951, 1044, 3211, 2815, 2918, 2407, 3373, 2530, 133, 463, 1026, 2843, 2367, 2587, 4186, 4078, 1081, 2287, 3280, 412, 2339, 596, 1496, 4469, 3367, 2658, 2681, 625, 1777, 594, 2849, 2692, 2555, 2567, 618, 3846, 949, 2751, 677, 2029, 4052, 3306, 4075, 2485, 2097, 127, 4359, 1633, 663, 1223, 2644, 
2421, 1406, 368, 3067, 1877, 3145, 3342, 3443, 428, 2946, 1420, 3762, 676, 2618, 3247, 542, 3396, 3052, 2248, 3591, 2761, 218, 8, 1823, 556, 1363, 3309, 746, 1883, 1792, 4128, 3307, 1303, 2273, 3872, 3636, 4301, 26, 1330, 2433, 2216, 4447, 4269, 2880, 4456, 2558, 1501, 2733, 566, 302, 3693, 1302, 683, 4476, 934, 2795, 4471, 4015, 1347, 3188, 3548, 474, 669, 4449, 3177, 2607, 1732, 3933, 3006, 2227, 2359, 1160, 1433, 
2108, 4182, 315, 341, 3317, 4401, 766, 818, 2321, 2301, 2965, 4030, 1756, 1543, 1548, 3853, 3046, 2139, 1047, 711, 3726, 431, 2835, 4041, 1019, 2357, 2371, 176, 2989, 1300, 2251, 335, 1230, 1308, 2725, 3193, 1530, 1397, 3763, 1788, 3444, 4477, 1351, 2687, 3160, 1848, 4178, 330, 3265, 3750, 1677, 1480, 1610, 4322, 
690, 808, 3814, 2781, 3839, 3951, 832, 1108, 1203, 1572, 3354, 3105, 231, 62, 641, 248, 1712, 1730, 4111, 2284, 2045, 3430, 719, 970, 4121, 3831, 2298, 2672, 2201, 269, 1292, 185, 266, 436, 588, 2158, 1965, 1527, 2920, 100, 3458, 414, 1741, 2271, 3612, 2544, 3606, 2044, 851, 3393, 4408, 975, 1468, 122, 2894, 512, 
942, 2355, 1949, 383, 147, 1716, 3400, 739, 2455, 2959, 3890, 2068, 740, 4345, 855, 1978, 438, 3888, 239, 3505, 3165, 2380, 1764, 2508, 1068, 3455, 538, 3731, 4392, 2209, 4410, 4045, 3161, 4369, 2279, 2595, 3490, 1742, 1015, 4475, 3932, 4313, 1416, 2541, 2306, 1176, 1050, 70, 866, 91, 597, 648, 509, 3550, 3370, 3481, 3532, 758, 3609, 573, 3635, 4238, 3227, 1681, 2190, 56, 487, 2602, 4063, 4386, 3896, 1809, 2445, 2996, 1836, 237, 4184, 2592, 4209, 1423, 2707, 2236, 1807, 4305, 1336, 3492, 1072, 2391, 1568, 1001, 3279, 3432, 877, 3117, 3939, 2123, 1793, 2230, 1434, 2288, 3895, 478, 2635, 638, 2390, 2300, 1235, 6, 2163, 560, 
3689, 453, 1668, 1653, 3001, 2180, 3292, 4433, 196, 4304, 164, 3261, 3675, 2478, 1392, 3560, 816, 1009, 326, 3582, 925, 2510, 3251, 3883, 2001, 90, 2427, 1976, 617, 2084, 1733, 2085, 2326, 1952, 622, 1353, 194, 3204, 3520, 3293, 1457, 3163, 4119, 1436, 1578, 3004, 1220, 10, 3076, 1463, 369, 2826, 1690, 2884, 139, 
468, 2175, 1973, 2088, 3624, 1638, 208, 2457, 2125, 1715, 1687, 2878, 4351, 3952, 2432, 67, 3887, 3245, 1046, 4470, 3011, 1449, 1166, 1615, 2259, 1103, 3168, 2514, 4478, 3588, 1842, 772, 47, 1479, 3640, 959, 3828, 876, 73, 982, 1893, 1367, 988, 1630, 4043, 2926, 3882, 3800, 1583, 1154, 2224, 2266, 3371, 3429, 2206, 2304, 916, 3941, 2453, 3534, 131, 1287, 3761, 2869, 4046, 182, 1271, 1374, 1173, 2596, 4342, 201, 1400, 4080, 3623, 601, 3084, 50, 1739, 2775, 834, 953, 1595, 3793, 3150, 2867, 3446, 2342, 3263, 1782, 2955, 2787, 3858, 1074, 3457, 390, 2521, 2356, 2115, 3496] 
Cs = [99670, 4220, 41683, -57324, -99352, 10658, -15604, -65115, -113, -52175, 79812, 41063, -92293, 78739, 69061, -93800, 67181, -85649, -77810, -3133, 13436, 71421, 16836, 13305, 82842, 94708, -28566, 76984, 51617, -61975, 25093, -57279, 86963, 92603, 24711, -26293, -7921, 19266, -43633, 82710, 97061, 43802, 54264, 4867, 70071, -76036, -47744, 52346, 52449, 25359, -93590, -96307, -12572, 17840, -45280, -12820, -75776, 98173, -79556, -71167, -53562, -59261, -49578, 57107, 
67094, 70130, 65070, 24493, -21845, 83900, 46363, 54649, 86947, -68791, -95074, -86998, -66622, -67055, 4633, 814, 46967, -24265, -9082, 19735, -46035, 26901, -23247, 740, -13000, -82045, -27963, 60886, -45176, 30454, -89649, 13838, -29784, 50172, 2732, -63145, 66910, 19691, 8147, -47308, 94293, 28247, 6697, 66345, -77471, -32860, 23738, 18864, -60610, 9349, 3534, -11160, 26448, -12196, 1474, -77972, 44337, -47517, 7230, 56009, -69800, -15156, 75757, -96423, -66531, -96278, -11223, 33570, -75682, -53066, 67233, -60668, 
81105, -18374, -51438, 45808, 56901, 25729, 89582, -85583, 52280, -28012, 15703, -69426, 4076, 51436, -39430, 9271, -68302, -37945, -78111, -65331, -29309, -42574, 18697, -3878, 11469, 57043, 21323, -30194, 47442, 99849, 87751, 98153, 68488, 21993, -70778, 43701, -98089, -79157, 31773, 38085, -95027, -31070, 86593, 97355, 43977, 95920, 56075, 74664, -91932, 23615, 49653, 30528, 26622, -48864, 39496, 49020, -94875, -71906, 19584, -72141, -37226, -88703, 72892, -81306, 31685, -53737, 18930, -5729, 99737, -85775, -59254, -48045, -82991, -99086, -93955, 58435, -86022, -45328, 55659, -45563, 57342, 31710, -6849, 80301, -91261, 
44873, -38443, -87796, 95167, 19531, -54329, 19555, -26254, 81587, 63173, -75620, 79455, 95145, -67010, -73590, 37445, 77096, -72472, 40978, -21340, 7080, -13345, -85436, 83308, 13434, 69982, -75201, -22246, 56900, 41060, -386, 97595, 49634, -98431, -43558, 44606, 92208, 40960, 31925, 5929, 3224, 33777, -14375, 54605, 58598, -92094, 17814, 22007, -83511, 77482, -13517, 77349, 82861, 33278, -98758, -95275, 53880, -75770, -66062, -35495, -7332, 53746, -25805, 9658, -42021, -60290, 8768, 47900, 15402, 82518, 9216, -34508, 
-21637, 8378, -59071, 92262, -24461, 38430, 49673, 36209, -16147, 28238, 69386, 67419, -61454, 48490, 98161, 42609, 2733, -89004, -5713, 26059, 35856, -61426, 37490, -66468, -55685, -76410, -21660, -42417, 4820, -84565, 29549, 53834, 49273, -68333, -62786, -97575, -66639, 37963, 14690, 10585, -81477, 28858, -32476, 44838, 49310, -42549, 5181, 16701, 81937, 2766, -68433, 78273, -71202, -19221, 64797, -64806, 52609, -54585, 47450, 68567, -7642, 68134, 71862, 852, 38138, -46943, 64105, 2151, -64332, 15467, -77378, 66162, -68054, 35936, 92104, 58681, -95777, -51293, 65563, -6391, 96379, -26236, -72920, -28989, 62933, -88127, 85624, -60596, -94701, -78647, 19726, -8183, 78991, -12993, -31741, 74253, 11324, -15644, 40863, 69980, -37807, -9687, 62293, 74679, -43783, -59097, 44564, -52654, 79191, -6285, -10494, -6270, -89531, 64157, 16738, -56109, 40555, 368, -51896, 84683, -67229, -39617, -85058, 58687, -71990, 10209, 59734, -65390, 1866, 6365, -228, 79334, 48375, 51517, -58418, 17077, -67186, -68447, 56052, -4238, -50846, 55447, 9243, -99526, 99933, 74604, 83365, -4050, 26930, -24279, 86421, 84073, 66169, -3004, 99436, 15185, 25988, 60047, -421, 66118, 70596, -61589, -72961, 89391, -56691, -78491, 16370, -91002, 41999, -82020, -5517, 81526, 42306, 65435, 73257, -62703, 78415, -20886, -67047, -56541, -72797, 71572, 76387, -67417, 41353, -52975, 25588, 50977, -60920, 82681, -37162, -3098, 66058, 72615, -82812, -42300, 39632, 22425, -8552, -71375, 82175, 
-27068, -24079, 18106, -92631, -15490, -1301, 4254, -83358, 57913, -94608, 53376, 34454, 41227, -43704, 99992, -52491, 55490, -92539, 59001, -84021, 15574, 65802, -84702, 29374, -11685, -27348, 25055, 71201, -79079, 66676, 86944, -79621, -35179, -30670, 84723, 28655, 5979, 56193, 44137, 64925, 69441, -88383, -68606, -35152, 32225, -78846, -45610, 37043, -52993, -64190, -96421, -14077, -9343, -69091, -34634, 84710, -27270, -89657, -72743, 58707, 63223, -23389, -86390, -54274, 39955, 30602, 64152, 67211, 14878, -11050, 11574, -45509, -4071, -4535, 79023, 39045, -66501, -65274, -78549, -45047, -99901, -74192, -96660, -46344, 
-50209, 72774, 5033, 23646, -3313, -52570, 22879, -33111, 88916, -35189, 62836, 74882, 19473, 45925, 90200, 44301, -62749, -66104, 76638, 8936, 38553, 68754, 77629, -65314, 47279, 72426, 93929, 84864, 33306, 96565, -41791, 51350, 81462, 81485, -96013, -178, 14276, -53146, 36451, -64579, 19615, -70396, 8018, 35989, 83707, 74393, -82381, 55968, -38322, 9120, -70068, 88142, 81697, -9628, -4577, -23796, -74729, -90265, -53838, -14813, 15809, 81168, 44630, -49550, 24215, -12413, 6621, -90633, -83947, -25845, 16638, -47399, -69185, 15563, -16540, 35513, -51682, -66209, 34226, 72368, 95244, 99983, -88522, 82567, 69552, 41100, -29340, 18487, 26183, -90851, 74285, 92872, 2580, 57154, 85471, -33647, -16464, -86530, -75286, 37692, 60833, -35142, 58042, 64238, 89947, -38410, 85329, -74882, 24430, 75799, -4196, 11263, -94604, -3781, -40792, 
46262, -91332, -66202, 89890, 69999, 47149, 13682, 55009, 51662, -84296, -49023, -60713, 44057, -4866, 57540, -70257, -47104, 30941, 76374, 38927, -22731, 92569, -4507, -9140, -285, -82713, -52964, -28387, 75699, -9220, 96809, 20898, -32950, 65076, 92021, -46133, -93638, 45674, 62151, 58466, -14804, 86740, 58284, 
58720, 38166, 39091, -79511, 32602, 77012, 56692, 75411, -47984, -56913, -89790, -86947, 25293, 53914, 81490, 34246, 86569, -78904, -20956, -40382, -26634, 88716, 25808, -61585, 24509, -6739, 81660, 13835, 65569, -82308, -46264, 60335, 12545, -36181, -65949, -40564, 14057, 11468, 61235, -43736, 32139, 11006, -56479, 54225, -72038, 65210, -77902, -2915, -21044, 29514, 53602, -99920, 19327, 43459, -5912, 10646, -35506, 98494, 32150, -62050, -99938, -9563, 99564, -35436, 65457, 74027, 14763, -92245, -16851, 39545, -42710, 
37983, -93532, 9950, -54188, 41156, 67053, 15965, -3965, -15914, 13175, 93915, -991, -52092, 70408, 75431, 77937, -19869, 88018, -58366, -19049, 62454, -15427, -11596, -6114, -29340, -50867, -21155, 91239, 31903, 27554, -55191, -42312, 78210, -42875, 2051, 2859, 31339, -68438, 65379, 56548, -98393, 79747, -63767, 
-44730, 7873, 73145, -6533, -91853, 72867, 57497, 66362, -5865, -95110, 69830, 95489, -30876, 79810, -17809, -91173, -73884, -31279, -47549, 32209, -11506, 7506, -2058, -16293, -88938, -25795, -56280, -45443, 84219, -51228, 36908, 52466, 95110, 18827, 54391, -46274, 78090, 66664, 52323, -81469, -80860, 70821, -13911, -38582, 33498, -83195, 86551, -63481, 67063, 46420, -18594, -78798, -33618, 1654, 44337, -81714, 67705, 18485, -48849, 19419, -89449, -19212, -32486, 30093, 71546, -37018, 24194, 20836, -72403, 71983, -67496, -53499, -63499, 73347, 30969, -47598, -88938, -69284, 46207, 87257, 20463, 10785, 39717, -99425, 44225, 98205, 59585, 85035, -36794, 93925, 35374, -44257, 50073, -17740, 37309, 82670, 41829, -69995, -33191, 
-10426, 56728, 42613, -15641, 82729, -21083, -4532, 58511, -19128, -74764, -40481, -93986, -45813, 94258, 78687, 25025, -53009, -92958, -31286, -42210, -13315, -14213, 66637, 82158, 68540, 79510, 81024, -90176, 16631, 61012, -52946, -67008, -40034, -74880, -21638, -99128, -75584, -21352, -73494, -27288, -325, -68776, 44562, -61732, -23368, 52929, -55909, -25402, 40319, 73140, 16006, -76240, 64334, -37778, 15950, 95562, 50453, -44442, -80706, 84052, -21067, -98748, 72669, -36820, -24647, 44824, -12626, -74571, -5682, -68779, 20186, -20792, -18806, 93329, -84480, 95099, -5516, -60850, -1617, -30766, 25726, -17030, -4279, -61487, -61546, 53407, -74079, -3468, 80407, 34224, -21140, -83756, 76954, -23882, 37546, -22130, -44122, -32483, 53828, 20884, -28138, 15194, 22795, 96934, 86023, 73332, -41201, -18377, 48944, -31098, 76364, 64500, 89657, 2782, 12277, 923, -9216, 88278, 11692, -59819, -56949, 30072, -84035, 46032, -98730, -75183, 55890, 34635, -8901, 40737, 88682, 84273, -63691, 33901, 1701, 94727, -29491, -52439, 39159, -45135, -94825, -58661, 80029, 68217, -53907, -11607, -15913, 10996, 63946, 1325, -52150, 35205, -65561, 30774, 92807, 
22039, 55685, -74745, -22053, -66978, 73517, -19959, 57640, -59323, -14326, -81862, 12598, 76532, -97625, 62642, -18975, 35511, -87935, -95165, 49252, -26143, 66371, 29911, 46119, 51920, -40515, -95530, 71108, 
-10250, 39145, 23831, -62306, 8188, -17679, -92264, -54800, 3731, 19186, -99669, -13495, 29246, 29924, -82160, -23926, 45700, -66026, -57427, 50562, -54681, 97483, 1703, -46567, -24533, -78234, 14684, -2191, -90149, 86898, -1336, 51589, -80574, -88994, -29343, -21132, -28461, 32411, 50953, 17222, -38628, 67186, -81779, 58186, 27413, 65085, 44729, 35550, -14057, 82346, -34303, -79630, -15295, -96211, -9387, -84263, 52250, 32458, -51009, -80245, 19452, 42471, 13798, -98377, -59237, -21263, -20916, -12190, -3421, 89182, 22772, -58425, -25225, 69363, -69307, 6413, 88507, 69060, -2818, 98, 82281, 57395, 29910, -95873, 42397, -44389, 35832, 68044, 18657, -67336, 5555, 5113, -46369, -47183, 95864, -53522, -44079, 91223, -85917, 8678, -2143, -68083, 72131, 31086, 63323, 89670, -66491, 86325, -40152, -97501, 83929, -59082, -53367, 24203, 21021, -83562, 79450, 30705, 63497, -29434, -58157, 24251, 58693, -64597, -52173, 24795, 3424, -93161, -44301, 49162, 43936, -99958, 70610, -43042, -96446, -66833, 70295, 97856, -30209, -48186, 51433, 7371, 34131, -69916, 872, -68837, 65421, 32579, 48001, 6797, -87633, -15027, 9212, -94860, 28699, -47429, -90683, 83564, -11889, -28949, 19377, -3036, 37677, -20618, -50465, 42733, -94021, -62533, -56891, 9061, -37183, -91075, 24514, -6518, 47287, 60848, 50609, 15239, 45397, 6705, -71106, -5025, -63389, 51576, 58607, 9841, 6805, -54595, -38283, -48619, 37365, -79312, -75495, 6666, 11612, -13915, 34366, 99903, 236, 94177, 46396, -790, -87161, 86210, -16471, -27076, -89017, 73017, -18015, 55093, 16076, -64674, -29100, 72352, -17543, 27039, -39684, 32033, 21634, 94323, -75817, 73295, -90253, -45532, -61656, -73186, 5310, -76885, -38333, 36205, -20613, 23020, 70965, -67640, 23833, 44920, -79809, 98619, -8851, 22200, 78867, 69729, 6118, 64370, -80531, 19593, 46655, -4173, -95808, 89416, 11362, -18969, -26233, 3287, -67375, -44225, 60554, 8831, -43998, -63256, -50620, 46980, -99181, -87057, 20703, 98332, -32701, -59714, 76287, -81457, 14569, 70838, -82469, -73201, -50290, -53278, -16453, -88116, 32208, 77539, 54124, -72834, 9846, 80490, -50979, 89031, 82248, -51647, 82000, 74901, -92755, 85411, 5123, 27691, -40376, 59345, -92970, -74798, 39981, -68984, 63412, 63013, -87736, 14877, 2233, -45272, -67367, -76044, 53238, 14245, 63637, -4578, 87617, 87532, 53116, -37584, -92867, 59099, 43453, -64324, 47617, 8378, 54130, 15080, -73934, 8516, -94626, 12028, 32257, -68150, -46286, 17753, 70629, 68737, -58363, 74704, 44393, -13095, -82763, 49789, -48137, 93841, 59075, 
51441, -34708, -84638, 13542, -24675, 68046, 86278, 32673, 20103, 28791, -90081, -27790, -26128, 95507, -60889, 56980, -84423, -24131, -58328, -4934, 99630, -4486, 55881, -19463, 31056, -39273, -36986, 33271, -1988, 51950, 94805, -50612, -63059, 1086, 60731, 41169, 30872, -33516, -45183, 87050, 67852, -51435, -85560, -6174, 82995, 93660, -31103, -14115, 52061, -99687, -24615, 11856, -73999, -87455, -75146, -21286, -89212, -9317, 99138, 1936, 64694, -84053, -13034, 70175, -19921, 1155, -21023, -12262, -54607, 88156, -58721, 58867, -15356, 74639, -79539, -42463, -20630, -92192, 21705, 90189, 53930, 91663, -92619, -90854, 63642, 89331, 97726, -82108, 74947, -84803, 77908, -32503, -43526, 93981, -20086, 95395, 7823, 78757, -41837, 30976, 8999, -9595, 25260, -79612, -55706, -45289, -33676, 47718, -12277, 90995, 50400, -72303, 81381, 
-8987, 55, -8410, -37672, 22296, 59309, 85575, -37818, 49243, -80868, 70175, -60124, 63541, 68023, -67768, -12859, -27767, 36484, -87294, 74264, 74942, -61207, -31567, -46556, 70171, 3061, 84194, 96477, -40139, 43470, -73897, -86558, -42260, -89019, -94473, 75517, 20747, 78032, 9307, -44169, 93888, 75268, 96592, -94720, -99976, -9127, 8298, 88081, 62029, -58083, 72449, -19184, -14325, 24293, -97467, -28381, -89518, 84099, -61819, 94869, 31926, -37774, 54464, -59664, 95349, -6812, -27732, 65891, 67858, 34915, -94913, -23814, -24825, 11508, 30532, -28983, 64506, -44307, 53510, 6333, -55287, 73192, 87859, -36213, -57854, -61110, 51428, -74791, 10240, 25546, -46488, 39405, 85251, -76698, -36983, 82616, 36148, -42679, 37566, 73346, -77110, -57476, 13292, -26490, -75584, -21472, 10605, -7098, -85519, -28651, -74764, -44303, -73872, -7362, -28076, -330, 36707, -45943, -14265, 86888, 94117, -92293, 4188, -74010, -68865, 88967, -62512, 60492, -62832, -90844, -80584, -69864, -59960, -93721, 69874, -97328, -89871, 32579, 59299, 57475, 37589, 67620, -89680, 83961, -71928, 70531, 82060, 13470, -28361, -36768, 10180, 58504, -26546, 80221, 75648, -72683, -39558, -51878, 75894, 58378, 7409, -29008, 82282, 3661, -82714, 35994, -33455, -36064, -59337, -41599, -12889, 98961, -20690, -48363, 5449, 88298, -7433, -27623, 15607, -68302, -84500, -1556, 15402, 3936, 11233, 51754, -46460, 64556, -98527, -44292, -99632, -88316, -99233, -57832, 14084, -3431, -28293, 41947, 
58051, 62249, 90391, -90654, -33110, 50749, -54193, 52067, -38660, 72308, -13985, -50332, 73264, 63477, 66216, 73919, 30347, -21848, 14429, -49314, 47573, -17811, 92778, -59936, -33729, 88939, -57151, -61259, -26206, -22646, 52760, 53055, 43825, 13862, -51180, -34755, -59896, -94050, -8762, -39079, -49317, -5732, 
-60467, -16047, -13570, 29975, 70857, -36566, -75745, 53197, -35811, 97559, -53848, 67437, 61515, 66802, 
-31491, -1109, -99341, -91699, 47928, 59526, -64171, -10517, -72584, 86842, 44385, 70504, 23234, -70560, 
42126, -5016, 33685, -45027, 83482, -81534, 7021, -78441, 34481, -66365, -46018, 15272, 33621, 52590, -21191, 83667, 43027, 98578, 71171, 29419, 91866, 80129, 72763, 61538, -25090, -22637, 33271, -53274, 3716, 
-83415, 42103, 67431, 95418, 73094, -61650, -42871, 21278, -10484, 54369, 50785, -60838, 59634, 81702, -97340, 842, -13460, -77139, -20771, 34216, 26220, -96430, -89498, 69723, 36399, -88847, 23314, -53124, 61950, 73167, -35194, 74004, -40282, -69641, 28334, -47398, 5953, 91097, -30060, 72120, -82945, -75791, 44704, 36698, -25190, -25303, -25427, -82770, 53887, 75471, -22115, 22968, -51591, 58836, -13658, 16156, 69047, -24044, -49371, 44188, -63462, 71230, -89391, 57017, 55910, -39884, -12062, -27966, -62973, 11331, 42362, -32511, 1272, 11675, 30374, -33950, -91506, -7696, 46786, -15347, -51443, 68983, 33545, 61581, 51960, -65228, 42444, -28083, -65018, -10731, 74171, 59588, -26542, -12762, 2995, -20457, 64125, 72178, -99652, -34685, 22551, 2798, -24382, 50291, -89328, 86277, 21304, 69945, 32619, -80336, -57238, -59932, -92357, 
3522, 39653, 76934, 13506, -33949, 85253, -43145, -82513, 82391, -60342, -57416, 15773, 7092, 45862, 41345, 52174, -32470, 42118, -22443, -3638, 90225, 47614, -78860, 72417, 50292, 52374, 58616, -12414, -55318, 71859, -73106, 14003, 43576, -40596, 39942, -91743, -27934, -88394, 69771, 34738, -78446, -70788, 74078, -20851, -14804, 85974, -80908, 56451, -76273, -15116, 48380, 56857, -9205, -93734, -23312, -43116, 71416, -49327, -64055, -81289, -69448, -73188, -57686, 73324, 17134, 67209, -61336, 81285, -72721, 74963, -53870, 61884, 59208, 85493, -85619, -74379, 95072, 5576, 39081, -12615, -70342, 14012, 52628, -5101, -43457, -27621, -15758, 63890, -79882, -42904, -99504, 56920, 77327, 75708, -33321, -10690, 92027, -27513, 39951, 98557, -26503, 54072, -1197, 1947, 65901, -19668, 90901, 82162, -97221, -99980, 44754, -29710, -43515, 
10828, 68218, 58852, 87491, 25002, -92667, -40397, 15205, -89208, -74055, 49868, 22698, -69583, -49983, -39726, -45175, 4457, 44433, -62042, 65050, -87224, 69744, 75244, 20518, -6174, 33638, 97549, 21061, -89611, -92320, 27704, 17271, 55636, 99928, -81829, 36433, 65716, -85412, -49533, 96574, 12214, -31546, 75619, 28840, 35723, 57547, -81939, -70613, 7781, -83202, 94244, -22695, 95725, 6141, 63791, 473, 41577, -72400, -31756, 81960, -62415, -58097, 99368, -71103, -79381, 38733, -57775, -76840, -41541, 26116, -10042, -29760, 61435, -14108, 66191, -93674, -64059, -49239, 6104, -19092, -33266, 82354, 29069, -98656, -95334, -22353, -17545, -36986, -54814, 79797, -4204, -19572, 92095, -30867, -80849, -16920, -70223, -48214, 41580, -46053, -53493, -53540, -34511, 96641, -47419, -52664, 2941, -38383, -76555, -41187, -57744, 11696, -55598, -50032, 97603, 66571, -12504, 46075, 96791, 20319, -61241, 22221, -32337, -54269, -2593, -46749, -77961, -35613, -47425, 97780, -35877, 43389, 99435, 60393, -88318, -57407, 1327, 11869, 21260, 8122, -14001, -39021, 96474, -44285, -38906, 26086, 36730, 72249, 6538, 11101, 600, -80517, -8949, -68550, -64068, 99439, -59430, 36638, -48386, -73315, 45917, 44790, -61496, 68274, 95955, -49427, 93651, 79183, 17488, -77596, 36134, -5801, 567, 9106, -90063, 35674, 24588, 12743, -92732, -83013, -96397, -78746, 43126, -84113, -82507, 4729, -40837, 89187, 64167, -92089, -10302, 67196, -39874, 43160, 55972, -12077, -10492, 95294, 78157, -95278, 98242, 54916, 90769, -61981, 53644, 1697, 39468, 78784, -85795, 11571, -56194, -30389, -60572, -57359, 27096, 43255, -30686, 31621, -50436, 19064, -10358, 37541, -13425, -39734, -99852, 65145, 47388, 57597, -39682, -32949, 97282, 69197, -4338, 94361, 94715, 56439, -49858, 63520, 75152, -26333, 4724, -80169, 73993, -42125, 34023, -91048, -60556, -8250, 26570, -86320, -25005, -51914, 72780, 53664, 57363, -34569, 58026, 54254, 10701, -80096, 9956, -70860, -37081, 95088, 20770, -59967, 16919, 65145, -84408, 7467, 25853, -42531, -90025, -6159, -1865, 18758, -59770, 67988, 23658, 71305, -385, -9935, -47789, -39884, 
-28586, -78783, 38826, -96740, 71624, 36600, -17771, 44984, 10231, -50968, -93361, -52270, -50891, -77329, 50975, 33725, -72169, -60973, 91189, 53094, -67708, 44144, 41846, -73008, 78662, 45048, 67001, -73514, 
29741, -23604, 537, 45722, -49710, -3718, 79914, -20691, -29182, 45094, -26650, 78331, -75153, 48961, -16215, 20406, -94379, -80456, 44368, 64914, -81002, -20067, -20701, 6160, 97296, 50178, -436, -60357, -40054, -66607, -7990, 30559, 65451, 45733, 67214, 73411, -6064, 25493, -47240, -79918, 23631, 80942, -93315, 
8292, -39086, -45787, -10749, 57621, 54272, -45800, -55593, -59591, -7056, -53160, 68853, 61336, 43982, 23007, 81870, -61865, -51776, 5907, -37805, -11358, -37771, 72069, 66591, -9539, 86872, -77660, -83741, 36516, -35999, -16499, 51052, 16864, -72357, -93772, -31226, -53251, 70242, 85572, -14400, -58574, 54447, 36858, 81043, 11365, 33722, -72356, -71177, 12110, 46228, 59958, 90146, 25184, -90644, -92508, 80881, 80833, -18024, 27034, -57638, -41612, -73023, -48551, -80030, 31429, -91279, -6190, -87625, -32038, 16607, -23204, -22046, -66546, 97088, -2444, -57773, 7857, -19395, 70488, -68893, -11686, -49277, 20009, 54286, -1018, 66383, -32487, -74418, 42021, 30430, -43372, -83644, 80545, 67092, -94279, -73588, 92717, 23609, -89190, 61637, -60863, -54691, -71502, -22432, -1954, -45923, -99463, 61409, -13860, -82720, 25229, 92489, -75183, -91334, -88799, 9202, -35868, 51324, -83999, -94144, -91683, 53461, 66931, 67448, 66245, -48511, 7660, -77692, -56674, -88411, 61004, -24484, 95500, -81835, -96917, -18639, 39068, -93296, 20022, 90686, 11312, -36395, -48964, 31385, -25276, 15534, -37866, 48850, 23069, 81574, 66357, 96534, -46517, -73031, -49960, -2804, 31665, 76269, 12097, 67176, 99038, -60410, 62384, 36183, 16944, -71601, -91430, 44396, -80450, 70583, 37377, 76818, -18792, 32880, 82014, 37, 95575, -9897, 39606, 4049, 25752, 25085, 70190, 14691, 
52598, 34640, 93599, 38916, 57821, -77469, -80633, 82141, 43760, 77705, -31613, -22259, 91529, -17137, 64067, -3862, 76656, 92506, -10154, -71664, -18971, -28335, -29275, 34659, -79683, 79037, 71629, -32829, 35424, -58875, 7099, -52724, -74606, -10351, 95282, -57269, 9975, 24879, -47312, -3038, 66164, -1335, -37626, 43867, -510, 80723, 68438, 3018, -31616, -54074, 9772, 76679, 35455, -28963, 12558, 80157, -75920, -77747, 6516, -62528, 53395, -98946, -13058, 27537, -67710, 33878, 98581, 64251, -98379, 89049, 49344, -70149, -77989, -73684, 89837, 41104, -59555, -92218, 34897, -39883, 22345, -74695, 22028, -87340, 72304, -41968, -91867, 71696, 3292, -33119, 94653, -92521, 28328, -57516, 18143, 18434, -29388, 33999, 72143, -46289, 72610, 40282, -3091, 3140, 60340, -99022, 27123, -84663, 54040, -84883, -14895, -51469, 29279, -85798, 
-6400, 27785, -38947, -12029, 31054, -83351, -78062, -20189, -77977, -72787, -57399, 43679, -21770, 88988, -78161, -73962, 83906, 27802, -36071, 78522, -73910, -95401, -54704, 99157, 58497, -29159, 33059, -15985, 57251, 31131, -18957, -61994, -44312, 56397, -2239, 65642, -94992, -85111, 80009, 33490, 28517, 20094, 2753, 35757, -82906, 15708, -13448, -10266, -59251, 20906, 27922, 22615, -75294, 62162, 3311, 23452, -39609, 79574, 27329, 74721, -15621, -79411, -44339, -41750, -21069, 60233, 94590, 78687, 22602, -87508, -86861, 22849, -65883, -15755, -37486, 11673, -60652, 17106, -45099, 31472, -86735, 90235, -96868, -38390, 44408, -9864, -73380, -92328, 98259, 86180, -4462, -94780, -1038, 60909, -60486, 58598, 31373, -19368, 4791, 25200, 77119, -37520, -29683, -65883, 88658, 5077, 36020, -80077, 54181, 47249, -41693, -41293, 94706, 9093, 1620, -60264, -98400, 39181, -96172, 47010, -25729, 91262, 1100, -88179, -15121, -1610, -92954, -3819, -10540, -62604, 82175, 53326, -64170, 33075, -36021, 61461, 20933, -46567, -81578, -6165, 24321, 43310, -87934, -31598, 60589, -96593, -85470, -31559, -1073, -56797, -55517, -37540, -39206, -53301, 47929, 
78022, 35644, 32349, -73796, 54311, -57877, 95398, 97239, 28233, 93508, 81235, 39841, -80721, -82526, 64330, 35902, -30587, -64903, -30573, 56111, -69707, -29781, -4063, 69557, -56657, -17079, -70783, 40932, -15962, -13482, 12420, -42500, 10742, -58302, 11974, 72478, -64040, -1117, -16595, 1872, 44412, -88675, 49186, 71800, 90482, -36767, -28502, -77687, 20440, 33320, 48920, 60579, -67160, -41839, 5680, -90838, -78098, 93291, -19263, -64293, 13313, -40204, -7334, -73262, -67975, 78893, -52261, -85409, -16920, 18044, -51850, 40344, -38693, 62218, 37113, -60622, -79521, 54007, -82850, 31862, -52408, 33997, 43517, -87053, -53484, 98087, -17957, -41464, -50452, 84355, 2819, 65395, 99523, 31772, 16113, 14964, 62660, -26256, 69722, 44981, -51195, 55083, -1604, 76547, 22618, -28773, 26241, 53077, 76704, -31645, 42233, -2661, 49705, 68208, 32252, 66233, 93615, 97600, 45101, 87390, 62373, -52115, -26327, -17904, 93133, 51885, 5678, -85628, 
64356, 77248, -79268, -33993, 3740, -62267, -42010, 62325, 83468, -46085, 41125, -16800, 2726, 72894, -57189, -73895, 98341, 31229, 51758, 33316, -80978, 6096, 95437, 73692, -2359, 36016, -72434, 63050, -40163, 99765, -78040, -40948, -4595, 60004, -25317, 38313, -99309, -22278, -61295, 52639, 33586, 17110, 49946, 
-61520, -72217, 75626, -2928, -64926, -90284, 2698, -89328, 58029, 44104, 70348, -32933, -47740, 54037, -90658, 64739, -19269, 22438, 99130, -8256, 72731, 5048, -44261, 26053, 95521, 52073, 38509, 4166, -98220, -82626, 97708, -44794, 16823, -70812, -17547, 90152, -92549, 18399, -23731, -78460, -35256, -98087, -38992, 99370, -47616, -29500, -80547, 69657, -93637, 62562, -50007, -94960, -86132, -26647, -6580, 49675, -32300, -55486, 56345, 35978, -36523, -39297, -14898, -49669, -40744, -1075, -94314, 76145, -70616, 949, 6376, 43877, 71277, 50254, 20106, 95302, -43587, -75452, -75431, -52076, 75275, -98091, -70928, -583, 56515, -50091, 77760, 96531, 25893, 41102, 84081, 32362, -98638, -20541, -75644, 52639, 97147, -69410, 63058, 
83861, 61098, -48766, 133, 72977, -78727, 42009, 50180, 86613, 49961, -16632, -77629, -18375, 80348, 59991, -66023, 79410, -61693, -87473, 90904, -95899, -4307, -61551, 23223, 97385, -67031, -65559, 86721, -27299, -36642, -37174, 14813, -32635, 89399, 83566, -37491, 99400, -68703, -34839, -51732, 48405, -52941, 71603, 66159, -1769, -31724, -61091, 37008, -91745, -87328, 86006, 85426, -76120, 71623, -35204, 62694, -5303, -6684, -79314, -9025, -87131, 78568, -4868, 90348, 65793, -34946, 52140, -22224, 21121, -8407, -30693, 81520, -71224, 74039, 74851, -14219, 73836, -49155, -29615, 60111, -47403, -51772, -32191, 65472, -25529, -43632, -36357, -75896, -50472, 19934, -21179, 44879, -35164, -27156, 22463, -25383, -7321, 39685, -38993, -5333, -89351, 45162, -98524, 82102, 73963, 72487, 81332, -44304, 48016, 82816, -12923, 90622, -76351, 61629, 67745, 11414, 52612, 59634, -16340, 40743, -6370, -89837, 82949, -26902, -71833, -22828, 4924, 
-1738, -25836, 31562, 95692, -67245, 31127, 76357, 21789, 4158, -96389, -51803, 9841, -34695, -47773, 71577, -22859, 80137, 12687, 65862, -46115, -93921, -92235, 65850, 63892, -59751, 44165, 84234, 16653, 73371, 98369, -70049, -37152, -64706, 62646, 74353, -4330, 37494, 59283, -54745, -24367, -70314, 15269, -88769, -84803, -10109, -42875, 22722, 6889, 74433, 84396, -26070, -76699, -59125, -55105, -7364, 98945, -10699, -99414, 79463, -88636, 91228, -86274, 26354, 93282, -99686, 739, 91514, -54458, 48405, 96409, -88817, 92933, -12723, 8491, 31090, 79065, 38308, -97365, 17322, -30259, -92606, 31481, 10602, -42645, -45153, -92486, 6954, -22199, 17021, -98465, -84649, -16051, -21416, -79757, -82097, -85182, 78785, 65184, 79312, -89183, -17266, -75682, 32759, 84997, -94676, -97752, 62650, 63293, 99520, 51674, 97358, -42954, 17043, -86816, 72979, -86988, 68591, 18746, 2781, 23738, -49296, 24340, 26751, 46644, -29, 87134, -36652, 12298, -35873, -82661, -12837, 14608, -85503, 81661, -47709, 19157, 3077, 33050, 12455, 14817, -46285, 53851, -63299, -36479, -63294, -34581, -91935, -50077, -19423, -38885, 79944, -887, -91470, -55135, 71130, -78708, -2765, 20900, -23964, -16425, -55820, -48834, 21925, -89922, 56849, -86275, 24499, 14575, -71516, 55188, -11854, -46361, -89677, -80616, -35862, 91890, -24211, -47581, -4119, 80007, 34544, 67585, -62860, -91228, -19693, 6143, -56916, -59417, 55413, -95189, -45968, 2086, 69873, -34707, -36368, -3906, -77460, -66796, 68264, 4941, 32336, 33567, -15470, 77511, 86035, 32242, -34396, -12274, 93637, 52141, -84498, -12074, -23311, 27336, -34469, 48217, 75781, 4560, 89718, -58966, 17929, -74502, 86097, 57255, -26723, -85708, -57309, 37690, 77148, -24232, 65670, -98355, -25216, 83604, -12406, 87639, -28336, 65803, 11304, 78153, -71784, 73198, -6401, 28722, 37503, -97175, 80629, -57819, -8055, -81960, 45510, -85355, 95268, -75713, -69624, 27195, 82676, -5809, 32231, 36153, 10953, 69352, 39480, -39596, 35678, 33238, 80754, 13158, 79276, 57722, 97606, 89815, 58804, -8360, 31475, -82152, 41758, -3445, 29776, -57919, 10915, 46471, -21528, -79068, 
-79073, -48290, 48007, -50756, 34912, 56107, 12541, -85279, -71112, 19013, 32288, 18024, -98227, 18993, -66435, -38502, 69612, -33209, 16455, -17880, 6520, 85060, 7954, 4341, -93704, -7099, -80507, -64046, -24623, 44160, 83532, 12814, -55076, 45406, 65905, 32270, 67932, 73913, -62368, 16021, 13775, 26132, 88470, -16571, 88055, 82714, 50324, -37370, -95609, -84290, -29780, -85588, 53839, -52554, -76012, 75882, 62316, 
-65158, -13970, 29919, -28787, 54129, 88366, 90003, 69437, 47860, -51561, 40002, 93430, 91336, 15466, -80552, 31196, -6199, -8725, 12205, -72233, -79453, 89291, -17095, -76107, 2755, 16868, -42903, -83220, -8029, -46421, -33608, -17389, -55263, 83501, -75460, 3885, 86764, -15377, 72499, 68728, 9570, -2227, -23643, -89748, 63316, 80384, 51527, -54587, -45082, 88968, 88559, -68560, -15989, 83057, -53809, 4931, 23507, -4653, 66602, -44106, -8493, -3262, -26932, -36689, 89091, -89550, 34336, -16025, -17347, 78498, -33768, 20656, 78240, 47201, -67276, -54248, 25136, 53407, -92596, 10530, -74187, -45108, 73421, 86974, 19102, 76820, 2258, 84926, 21390, -50614, -89905, 54983, 91517, 87459, 64427, 84178, -96310, 47525, -52337, -40673, -10541, 23676, -61854, 8709, -35664, -56707, -58678, -42830, 21949, -66597, 66599, -41166, 15459, 89243, -95860, -766, 97483, 63219, -19487, -98252, 50294, 85079, 84416, 63258, 9373, 33072, -49691, -918, 76831, 32505, 57498, 20716, 78163, -38100, -13058, 27601, 53392, -12483, 38285, 95860, 33908, 31426, -20906, 32294, 34442, -19052, -68211, 4448, 27887, 40514, -93717, 53142, -55193, -96320, 62812, 86829, 37709, 42884, 76249, -47007, -32701, -88187, 61281, -93513, 96983, 87654, -3784, -33010, -25582, 66141, -82495, 89515, -97004, 35797, -52898, 90315, -27483, -54932, -76877, 93699, -37684, -74731, 6489, -52442, -40274, 39732, -73906, -92204, -83173, -36289, 43835, -46255, -89329, 59101, 30419, 73798, -10621, 78495, -18682, 39200, 63742, 38083, -48663, -14182, 70949, 77740, -37420, -3421, -39800, 61269, -14860, 93823, -35085, 8584, 13811, 79656, 57048, 39211, -49476, 59607, 76621, 38493, 67996, 78503, -18649, 11854, 40253, -8192, -83767, 48097, -35476, 42345, -5506, 92336, -20576, -65706, -96574, -58544, 81398, -94510, -32087, -54586, 
89988, 7005, -10205, 84554, -55707, 82808, -34096, 7749, 28416, 93146, -89436, -33832, -45838, -7815, -90479, 93538, -98222, -42224, -15124, -54165, -82440, -91597, 78369, -64753, -87457, 76312, 10961, 88605, -23371, 21155, -23916, -41075, 6876, 81883, -8895, -16795, 88528, -43544, 87795, 31245, 97418, -59992, -16319, -6590, 16611, 8972, 28316, 599, -69906, 95192, -27244, -10811, -75644, 16078, 38278, 37477, -98715, 
52922, -37858, -54342, 88607, 55924, 17840, 48488, -65426, 38682, -14777, 41675, -92595, 93351, 97863, -87126, 50040, -2456, -73078, 78625, -94130, 7621, 41430, -33054, -93933, -67240, 97374, -20270, 58291, -93674, -62626, 68661, 22763, 8479, -90379, 60046, 40377, -34547, -77554, -69556, -25987, 95418, -43737, -23098, 16363, 19729, -50024, 70959, 52112, 90084, 56610, -85508, -39828, -9627, 2690, -8206, -29515, 64156, 63365, -30614, 56054, 9418, -77748, 55857, 17505, -27794, 12307, 71153, 21374, -75309, -44646, 95536, -466, -79530, -492, 64619, -90115, -82046, -32874, -78042, 88132, 44258, 82255, -83689, 29895, 69727, -16373, 40782, 50605, 88466, -15802, 26350, 96754, 56088, -2714, -96618, 3739, -51759, 27185, -77028, 58684, -90578, 84844, 43409, 78128, -79554, 74700, -16786, 57875, -79652, -5289, -54110, 61640, 78866, -1957, 27426, 47338, -38091, 67897, 51609, -70614, 34481, -33929, 36861, -86543, -1736, -16904, -47029, 5314, -74733, -32973, 91973, -78778, -93165, 73303, 83150, 54029, 99892, -3981, -53970, -12741, -6476, 59876, 83587, -11154, 96047, -95429, 72009, -781, 84378, -97504, -26818, -60297, -66129, -73337, 62733, 46832, 4988, 85164, -9852, -33931, 5875, 26954, 28062, -19165, -93025, 17802, 90769, 97595, -50833, 11985, -35530, 14741, 65689, 23995, 95878, 72517, 88026, 27865, 5025, -44219, 49244, 98426, 92893, -15029, -88198, 43774, 88542, 45803, 22931, -4794, 291, 5354, -16047, 59794, -29338, -66331, -49689, 24185, -26175, 76638, -42510, -4632, -65364, -73484, 11589, -26700, -10994, 74339, 82607, -25483, -52709, -53103, -19209, 56108, 46674, -82701, -1601, 91063, -12234, -51753, 14984, 19638, 54307, -38466, -7718, -95633, -37392, -79127, 98583, -30400, 34148, -27952, -61349, 42733, -23215, -32629, -781, 35223, 94543, 84377, 97376, -49166, -63689, 31355, -54729, -20703, 19964, 2961, 7750, -6596, 60619, 54898, -68092, 4139, 91325, 10443, 75741, 92409, 45378, 96248, -82161, 67828, 34845, -58039, -30729, -47636, -61973, -22048, -10065, 86012, -71088, -21079, 91849, -43867, 53261, -93209, 31051, -45272, -96287, -12350, 38596, 86270, -29196, -37554, 27440, -6579, 16960, 36490, -65212, -5464, -29481, -3951, 32130, 37300, 96913, 80103, 66120, -52935, 60568, -28878, 
-42284, 91668, -62484, 34299, -18243, 94029, 60317, -54702, -6005, -41870, -36968, 5767, -93414, -11550, 
-61176, 6688, -35925, 54776, -45129, -12176, 68675, 69593, -85543, -26177, 86417, 7154, -67888, -80882, -30714, -33890, -55528, 80123, 36705, 74775, -97915, -22112, 94674, 23786, -25617, -89842, -40045, -67761, 66195, 98088, 6477, 15651, 96683, -49145, 99219, 42899, 77341, -87905, 28238, -90622, -95710, -52816, 24048, 24170, 29931, -23108, 57683, -63303, -78766, 40611, 51012, -55450, 64109, 6430, 14037, -96848, -20173, -85600, 12442, -57658, -88256, -88226, -30840, -32161, 66209, -73384, -52103, -37709, -14100, 11830, -59510, 17522, -7018, -50814, 71453, 25769, -81347, 51881, 43014, -82108, -9253, -52836, -2234, -76116, 11119, -33134, -29364, 87358, -14428, 11691, 93050, -61885, 18937, -30528, -24735, 81525, 91009, -93049, -2815, -61229, -64847, 38204, -33679, -95486, -29202, 53125, 38451, -68754, 47517, 29083, 756, -88705, -34695, -47260, 19435, -14830, -22294, -4131, -73006, 10731, -36183, 44954, -21213, -92219, 16589, -57093, 56032, 83484, 70404, 25308, -5817, 63543, -72830, 97278, -34179, -90286, 7700, 15552, -46131, 81813, -56930, 75969, -10062, 5986, 42411, -91043, 2438, -56147, 54941, -73139, 22108, 57496, 22622, -83878, -30929, -33704, -7947, 38012, 67696, 99592, 78229, -12826, 86420, -8149, 94786, 68947, -30176, -43316, 18394, -73993, -19397, -47244, -16454, 3751, -36817, 89698, 15122, 84829, 15772, 59035, -19292, -37979, 21514, 29060, 58397, -94842, -98658, 5708, 45932, -64708, -36805, -20323, -475, -28680, -51209, 95345, 22001, -2101, 
41440, 8293, 96146, 63374, 77074, 52674, 25001, 8540, -65316, 39717, -7730, -92556, -3538, -31004, -53528, 94498, -45299, -42797, 66288, -20294, -26658, 43120, 14661, -77969, 90519, -82673, -17335, -93845] 
#"""
group = [-1] * N
grouped_Cs = []
next_num = 0
for i in range(N):
    if group[i] == -1:
        g = []
        while group[i] == -1:
            group[i] = next_num
            g.append(Cs[i])
            i = Ps[i]
        grouped_Cs.append(g)
        next_num += 1

max_score = -(10 ** 18 + 10 ** 9)
for g in grouped_Cs:
    l = len(g)
    score_per_cycle = max(sum(g), 0)
    for k in range(1, min(l, K)+1):    
        q = (K - k) // l
        cycle_score = score_per_cycle * q
        score = sum(g[:k]) + cycle_score
        max_score = max(score, max_score)
        for i in range(l):
            score -= g[i]
            score += g[(i+k)%l]
            max_score = max(score, max_score)

print(max_score)