239.滑动窗口最大值.js

var maxSlidingWindow = function (nums, k) {
  let currentWindow = nums.filter((_, index) => index < k);
  let currentWindowMaxIndex = currentWindow.findIndex(
    (i) => i === Math.max(...currentWindow)
  );
  let res = [currentWindow[currentWindowMaxIndex]];
  for (let i = k; i < nums.length; i++) {
    let item = nums[i];

    if (item >= currentWindow[currentWindowMaxIndex]) {
      currentWindowMaxIndex = k - 1;
      currentWindow.push(item);
      currentWindow.shift();
      res.push(item);
      continue;
    }

    if (currentWindowMaxIndex === -1) {
      currentWindow.push(item);
      currentWindow.shift();
      currentWindowMaxIndex = currentWindow.findIndex(
        (i) => i === Math.max(...currentWindow)
      );
      res.push(currentWindow[currentWindowMaxIndex]);
      continue;
    }
    if (currentWindowMaxIndex > 0) {
      res.push(currentWindow[currentWindowMaxIndex--]);
    } else {
      res.push(item);
    }
    currentWindow.push(item);
    currentWindow.shift();
  }

  return res;
};

console.log(maxSlidingWindow([-301,7825,3986,6586,4837,9414,8005,803,5827,-93,7789,2217,4263,3382,2158,7877,2616,3642,-371,-33,2420,5665,9379,6472,4642,9407,3543,9194,2930,979,972,2388,8031,4973,1987,6109,-863,4697,8852,6415,2413,1029,1927,3709,8115,2661,982,9091,2328,6507,1786,252,-394,8773,5514,4036,9037,3379,3677,3877,3907,9207,9847,3582,8360,8654,5541,5621,2117,7440,3851,6462,1548,7652,7005,329,6146,3890,8342,7518,1497,-124,7150,-631,1786,2786,-697,3791,-936,4801,1315,637,141,3018,5236,-789,1681,3144,2223,4088,9558,6806,2889,5380,3352,6259,4056,2184,5925,8329,3764,7871,4621,1062,-299,4586,9582,1878,6959,6679,7734,9915,8461,2243,588,9713,-306,-75,3562,3082,9669,4856,700,3388,3354,4503,-387,-787,6008,9764,111,6941,3992,4024,4515,41,4596,6967,4401,3593,5503,5842,6841,3473,7229,6038,3459,9641,6214,103,-42,4567,7508,-189,5283,-570,-772,7824,5708,3094,228,2439,7586,3611,3447,9185,7974,2712,9402,8514,5934,5079,3163,2499,9060,1751,707,8224,1189,3713,3042,8402,9651,-789,192,346,1739,-841,81,7877,2131,1647,3258,196,1640,8051,1761,5194,5601,-614,2266,857,4815,169,7533,717,2810,1831,2041,8658,5273,6607,9981,5263,8020,2949,6040,2890,6904,5038,6224,9458,9619,-231,3199,8134,9363,7695,9748,5410,3177,5034,1728,5371,6126,2136,4099,2045,7649,8591,-357,748,-762,2636,-492,3370,8720,5158,-849,3903,-534,705,6462,-245,6643,2503,5259,9091,-13,7210,2836,6584,8191,579,1055,6031,6621,2954,799,9980,-418,3941,194,937,6885,-203,9164,1009,1425,4368,555,3010,687,2789,6280,530,3441,9278,4019,8790,8835,9113,6841,-687,5012,2764,4509,2554,9826,-496,9926,4012,9765,2843,8015,6455,9053,3598,2271,1490,7872,2113,7523,5268,6793,7763,7902,167,9616,4122,7222,3239,3169,5464,422,7907,60,16,8997,5753,4263,3992,9157,487,1935,34,4666,2683,2905,4379,8309,-338,9438,3620,7391,8725,6145,3882,7707,1572,1061,1422,8491,-641,3396,7138,1193,5976,3236,-22,4250,7326,454,3447,2404,2990,6461,2049,4606,3178,8459,-791,7957,1233,5241,5296,8132,3536,5930,8141,9700,3540,4989,7362,561,2612,6402,-17,5574,2480,8838,8069,4011,-189,2241,5188,1299,1154,8762,7478,350,759,9950,832,2955,9375,551,4060,3855,3398,7462,7004,-835,7777,6031,8710,9668,7057,1290,9434,2348,5496,8220,5595,9022,5526,-746,9991,5760,1324,8454,4168,-351,9319,232,7612,388,7270,1613,1712,6119,1204,8974,3212,582,6009,7725,3206,-95,7236,1087,8793,6188,3410,550,887,-777,6335,-162,917,4624,7013,-783,4777,3534,2003,7275,5321,2562,8421,9356,762,1419,3044,1562,-586,2049,7191,156,1273,8417,2554,6869,6927,636,3822,6935,874,8592,8090,4879,6986,-982,1406,5068,8926,2255,280,9993,-151,-489,5233,1295,5656,1444,3928,3262,2265,4446,2075,7735,8584,3102,291,1194,356,9985,2061,3591,5478,3881,4618,4055,6133,5494,5950,4198,5561,8690,4358,-270,8188,-894,3528,6157,2053,1810,7054,7369,9100,4409,8715,2564,8270,8252,8338,970,269,1972,-723,8361,9694,7474,6678,809,-549,9744,1855,346,2098,194,415,9529,5875,1561,4090,2146,9974,3856,9822,5001,229,-795,4826,4614,-907,4131,4948,7748,2387,4042,1926,2090,7455,2397,2404,6787,2205,6161,3166,-620,8840,4096,3282,5335,6908,5934,6475,5265,2541,9437,8453,9986,3735,-405,376,4228,4767,-257,8723,5238,2177,8439,-814,8445,1797,2040,5102,9878,4530,8377,8049,6184,3068,4928,2899,1782,5704,9338,-988,5582,8482,6306,8592,8977,830,9204,7252,419,981,9772,953,6926,2664,9337,-187,800,7674,4584,-1,6984,5482,9075,5842,5403,397,569,5797,5070,-460,9807,-141,8447,11,627,-42,476,9074,3381,9522,2726,6040,-924,3687,1377,7679,3500,3267,5645,5701,4633,2052,3946,1093,821,879,4859,1872,6438,3854,5473,3172,7304,7684,7186,5103,4447,2377,620,7123,6419,7651,9122,9637,-269,9817,1426,2523,1032,253,2759,6418,9400,7889,1698,9150,8258,9531,3453,4328,5241,6801,2140,3503,3225,2189,686,3249,6141,2966,6923,1716,2389,3950,7565,6841,5697,1247,-311,7423,1054,1468,2699,420,5954,3350,9669,4626,6344,8712,-208,4903,5236,-528,1369,3680,5287,4090,3251,9094,-546,842,9758,3773,6702,2831,7324,4929,4812,8242,4218,9279,1557,7184,4779,1752,1960,1728,8407,9211,2557,9393,7017,9536,-639,7094,9742,1145,5168,217,830,3157,8087,1878,2305,4437,5734,6783,6655,190,5997,1655,7094,5053,6857,9779,8370,493,-398,9769,4658,3104,3292,5726,5466,7269,3322,6268,1528,146,1069,4602,1260,3377,9663,6752,4712,-427,2104,5612,4136,4049,8557,4671,7279,7586,2435,6596,7134,5069,5855,9415,8887,7676,2887,1832,759,1661,2301,2571,3566,8693,2845,1342,7276,9598,2047,8167,5910,8900,7912,1865,4061,-155,5975,3043,2899,4284,6940,-658,634,539,6873,7275,6672,9740,8598,34,5813,7949,1724,4126,8746,212,3047,7821,319,-279,-962,965,3321,3147,1499,1384,3258,6126,9179,9162,4454,9932,422,4602,4225,139,5680,5297,6969,3484,2385,585,7212,9981,9846,6445,9539,2765,-386,-10,9638,-652,8797,-95,2977,1885,9354,656,-802,4154,887,647,9039,446,3689,-687,7864,9260,9468,581,7948,1344,4913,2244,6878,-280,9976,4944,558,6697,-701,6886,1000,-368,3484,3670,4968,9886,2855,8888,4621,6822,8758,1048,2659,8846,288,8269,3243,2181,9208,9550,5146,6412,6085,694,3246,-856,1081,5906,8218,4031,-354,9010,9968,5979,4820,704,5312,-935,8446,7174,6735,1727,4896,8507,2515,837,2595,-428,5010,6031,3399,2141,3522,2237,3556,-130,4772,7680,878,9520,2236,7761,8743,1262,2590,3847,6879,1540,4410,2996,-400,824,8924,2882,4984,7209,7178,3093,3830,-145,4707,293,4136,2772,9816,9370,270,7991,6629,5899,1063,5930,8270,7276,877,8255,7592,5917,9308,5151,4433,4179,4920,9373,9054,4798,9454,8653,3342,2073,4351,8026,7261,4443,4735,933,6206,154,-925,2288,745,490,8671,1401,3846,4737,2599,4994,2905,2771,2527,6387,1227,6144,392,2289,4933,6475,5730,-619,678,6196,9095,5124,5386,8630,-245,763,-408,3130,3826,-367,7377,9120,8058,7370,7020,672,5273,9005,6191,9181,6893,-334,2575,404,7202,68,3507,4910,8258,7424,8172,881,9347,4126,9157,8947,1821,3226,4979,3582,4274,9134,2701,-688,3313,-308,1549,5821,2045,319,8982,4397,5355,9299,695,4269,5071,5913,3385,8948,4675,1233,795,7923,1057,7612,-378,2129,4790,3501,4283,2073,-753,3711,7044,8596,926,485,-506,3699,5512,6307,9488,7543,3026,-373,1345,8065,3093,3712,1485,4060,3510,2678,-835,4487,4446,4511,-67,4546,5858,4395,-157,4533,6209,8220,2731,6131,4683,844,-645,6316,6071,2169,8628,9229,7706,7785,885,3586,8070,1237,7477,-673,1227,3341,3738,5559,228,91,2221,-535,6019,-116,1662,4163,4276,4430,6188,3865,7268,3745,7258,2979,654,3966,5987,-354,-918,7644,5069,7050,7662,9708,5030,5707,4626,2390,6628,8271,1302,8515,5422,2572,4934,-885,5277,230,4434,8858,9608,9009,8510,9137,-898,9423,4512,8935,8005,1772,7894,5085,1563,-122,-673,6233,-389,9192,3895,747,5297,1031,890,761,3834,-422,7873,4145,7939,9944,6935,7730,8129,366,9335,2132,2131,1712,264,3857,1322,9545,6729,6403,6066,1637,6736,1489,8115,584,1513,-134,1484,4706,3622,2272,2880,2207,1256,6156,6243,6140,8303,389,5951,2778,-541,603,972,5307,4988,-763,3398,9528,9138,9085,552,6577,-678,3846,258,6598,4059,5513,7342,1864,11,2557,-480,6184,5877,3389,-599,8109,3778,9271,6336,6828,-50,7243,7773,6609,2948,3131,241,1582,7089,-999,375,7360,4600,2602,2345,5130,-101,-542,4281,9888,5793,1983,8971,2572,8305,1569,9921,4028,1388,1103,1582,2693,9986,5553,7053,2580,4681,1252,5593,8402,2487,7128,7695,4479,4048,5661,9309,826,847,7994,1250,6187,2820,9263,2591,403,4517,4968,7222,7774,7875,9518,2360,9472,9897,8565,3961,6158,9876,6851,1487,8821,4476,9078,2922,8102,5175,8885,7271,9145,9344,5096,8198,6469,3137,-944,9800,1159,5854,6165,2711,1756,-834,9982,-300,7571,4836,7641,-434,1096,596,1360,3926,6664,8836,3065,6972,431,3083,7031,231,5387,8543,6840,4957,7732,760,6194,3144,6930,613,437,683,-453,3017,6373,6933,-975,8660,-324,4904,-121,999,4747,7358,7175,6593,3953,7255,2206,3217,4899,6310,3021,2603,71,2760,3410,4768,5558,9338,6853,6652,1771,7946,1112,1018,9612,1036,8456,5143,4721,5291,7058,6712,199,-452,1980,315,-679,9952,8148,802,1427,1445,5407,1821,4617,8609,5968,4489,2239,180,-435,7744,4712,6861,500,6565,5183,6082,2073,8092,8920,-532,-848,2109,3157,6933,3551,330,9638,8672,8313,3682,5318,2219,8202,1998,5685,8099,7741,-570,9189,7935,9461,8805,1815,4235,6692,951,461,4026,2932,4171,6560,9308,531,4129,859,1915,2630,1483,-238,9109,8579,6830,9578,7218,2622,8712,1204,8409,5728,787,-307,2488,5473,5539,-100,8030,7182,3245,6671,8071,806,4039,6443,8276,5555,-754,4361,8442,9788,4097,945,1954,4712,2305,127,4368,2325,2908,7714,7722,6430,6920,7555,4580,5522,6572,1251,5042,7758,5494,2630,3298,9425,6712,493,5141,8426,4242,2587,6509,727,8713,4850,1370,903,9504,8581,7325,8287,6583,1914,1929,3181,284,8720,1964,5461,2893,5794,2010,1867,1980,1044,-683,7646,3136,6960,1665,3634,6215,5220,1772,1529,562,6716,5151,8711,35,2589,5748,5372,-11,1960,-86,8643,-359,6354,2026,6563,6478,3991,5199,8939,8398,8527,2177,1391,7115,1062,8900,8625,7742,6877,5116,-108,7191,8522,9811,1075,5616,5431,1351,7630,3095,3999,3556,2236,3076,1643,-834,5404,8136,8010,5564,7466,7170,6107,8554,8441,1383,5555,2027,6089,5213,9700,7135,9989,1057,3635,8451,2879,9578,7804,4999,2827,5962,5794,168,1757,497,143,-655,6303,3182,5970,5014,4525,8169,7897,3300,4952,4461,2296,3374,5128,-786,9937,7293,5351,7856,4055,3316,5435,-100,5265,7749,6385,7979,1001,3923,-928,-221,147,8919,8777,1921,3776,9438,7570,231,3557,8368,880,92,6993,3526,2256,-763,4569,5650,1621,5906,3370,1792,6767,1303,6587,2712,1293,1549,-234,5005,3577,8960,5998,7089,6698,8884,5214,1093,795,-35,212,7746,4298,762,4808,3252,9660,6678,7401,6702,7725,3929,1022,8557,1659,9405,7901,9507,-239,1174,380,4455,4852,7443,-564,1407,462,1825,9663,3718,5725,8242,8885,279,7379,8492,8903,4998,9836,-93,7719,6157,7781,649,19,5851,6422,5853,5747,4108,9320,6025,8521,4631,6587,7495,8845,8228,6663,8876,1855,5821,7477,8276,3735,9497,608,1835,351,8557,8938,3410,847,966,3411,8842,3072,988,9598,448,9109,1700,9239,7283,3036,7712,2580,-467,6894,6669,9593,5265,732,5482,3806,8589,6102,7266,1272,8068,4770,2118,9493,3805,5556,1799,610,4098,-126,9570,9887,4946,2928,4967,6584,5455,4728,9955,5184,9265,7935,9761,7999,7720,4657,1834,-885,7412,4548,4558,9810,5886,4018,4439,1818,7655,-711,-778,3097,4923,9252,9242,8870,5692,4143,7949,2883,5169,1069,928,284,9515,7825,8640,-677,3493,5011,2276,621,2780,9453,7307,3810,415,1874,4859,6595,3053,5735,6602,6334,6596,-460,6967,8773,3514,5636,7551,9023,8446,7339,7744,8684,1307,4107,3390,2764,7013,3934,312,6757,3150,1237,-84,8587,-958,1756,317,8444,1231,6309,840,3101,135,9015,767,6302,1360,6905,-374,106,8129,8319,8403,5023,9448,4068,2610,3162,6362,2639,777,8025,5376,434,2393,5804,677,1072,-15,-697,3212,4765,9873,5867,6668,3702,5777,1989,3087,248,5343,4753,5499,-81,1235,1913,9091,4352,8286,2524,5732,672,9365,7388,5867,4464,1914,92,4851,2899,-718,5734,2888,6842,8660,7972,3623,9390,3959,3584,5106,1820,9294,1937,7112,3329,1741,2519,7183,6470,2250,6886,-375,6702,3122,-279,693,4923,-636,4049,-433,1452,4526,1819,749,2351,1078,1925,9549,6921,4542,7185,8707,1193,4099,5635,8475,4142,5712,-627,913,8582,9512,1585,6424,2421,1096,2408,7715,6903,8418,-333,9091,3831,7227,4196,4712,23,418,4663,3773,9749,359,9589,6846,6516,1602,8533,4630,576,4321,7675,9984,5023,7779,1698,731,8877,7784,7095,2990,2038,8366,9160,2494,5542,2746,6864,1530,3229,-38,8332,9435,664,4975,1378,8854,4727,9542,5107,5936,-121,1476,4579,-55,-801,2670,4247,31,1956,5094,1655,2654,2582,1099,4738,6668,7896,3856,2406,8506,6783,5972,9852,1446,2767,8793,8990,2671,335,3234,-795,9991,2647,1764,-268,363,1538,8235,1446,1939,5078,-754,-539,1205,1944,2833,2072,7087,2264,8497,2090,7206,157,9669,4548,-964,1344,-62,9814,3287,2343,2444,471,2248,7554,7243,1458,4734,9953,4977,5975,7289,1765,4949,2570,4454,9587,6564,2593,5066,-588,7518,6986,5186,1339,363,6453,4360,-628,2243,6785,2551,-546,3723,7020,6087,5702,2679,6074,3923,6496,9753,-99,4706,-879,2998,5018,3596,8962,21,425,9798,1618,9181,-622,8183,555,7762,3599,8716,1276,4616,9033,6506,9042,7504,-715,9451,9078,6991,8784,-791,3295,7093,226,1476,9776,5060,6558,2525,5622,4125,4166,3339,595,3906,7450,6268,3150,8891,2693,9906,7314,2358,4052,7517,9878,7932,2886,7136,7011,-198,746,8633,600,4299,9409,6910,2205,9206,7201,2806,7451,7729,6489,7635,1432,4336,9255,5100,-463,4620,9857,350,8048,2125,8581,4216,2428,2768,7992,2316,500,5103,6475,9722,-516,7615,1687,4875,6137,2668,9353,8357,6262,-245,3762,9405,2814,2882,3306,9354,7837,8066,7489,-180,4399,4210,-148,9561,5635,4083,354,2166,832,2183,9485,9717,-973,7071,4694,6206,41,6206,6188,2657,5448,3655,-385,-503,1073,935,5035,4439,5352,3768,-764,4581,9932,5179,3279,5074,6996,-602,1884,1958,8353,6318,327,9913,363,3814,6034,5408,8532,-790,8064,9017,6957,4338,8592,475,1613,-888,5079,8318,149,8033,778,-361,1611,4932,1666,3652,4198,-131,2637,6474,6693,1100,3538,8280,7923,9181,5999,7480,1275,3990,408,3631,5560,5478,3297,4451,9037,8382,2583,297,870,8817,487,4839,5188,3807,4039,8755,5177,7406,4620,8057,1380,7412,8518,1746,2425,-514,80,9549,7889,-981,9271,6738,9917,9875,9049,6908,1704,5599,3941,5506,7660,6122,5223,9023,8384,1977,6692,8046,-232,371,6213,5523,4418,5025,1296,6104,1046,527,7147,6889,5424,9545,661,9596,7026,7045,4625,1001,9169,2124,-816,3675,238,7456,3193,2322,1452,4995,501,3106,4827,9009,7416,171,7088,6717,7938,9826,9933,9822,6173,-304,3684,3227,8132,4154,-406,9895,-70,4297,916,6905,4698,8383,8158,9088,9696,2784,2844,-778,8368,6574,-399,4053,-258,4509,449,2411,-178,6443,6010,8369,6871,4657,9981,-406,5023,9509,3891,5346,4090,6727,5793,5219,2987,9715,1297,5885,2953,2444,3193,-804,3124,2475,3049,3301,-240,5571,9560,-605,8147,-519,8091,3458,1260,2367,3578,4308,5415,3365,7096,6209,3577,8051,9497,5023,4817,1935,8211,2499,9093,2148,-920,9904,3206,1160,4799,5558,3653,7052,630,8309,4310,827,5942,1674,6871,4216,331,8563,7125,8658,6586,8454,6347,7300,6825,6319,2232,-102,2219,4253,8798,1645,-560,6250,666,1307,-612,6552,2890,8158,8720,9410,5046,8347,2784,-159,2946,2355,6301,-7,7946,5312,2076,4544,9597,9283,2998,6801,2700,-627,9074,639,4009,1646,-748,-441,9212,2605,3368,3072,7082,5615,404,4710,6668,2369,4766,9622,-90,5693,2453,6432,6842,3860,1104,4816,1369,6976,-214,5279,950,-535,2864,7183,5922,-985,5964,-202,9541,3039,4759,-15,-467,335,7248,5523,2103,8126,8074,7306,6082,7245,-934,7183,7981,7103,8049,715,9266,8375,6510,5633,4344,4946,7483,753,2021,1081,6561,2784,8492,1655,7313,9748,-211,977,2341,7500,5016,125,6220,5343,2631,2506,3668,-203,6121,2132,352,7034,256,9407,7675,1230,3372,510,2539,5242,8478,400,9196,2750,4390,959,-679,5845,5219,2073,4592,5934,5759,7650,9090,2756,5880,3114,5887,1611,6281,1140,4687,4511,9019,8282,4771,1450,839,8448,-839,9374,5188,5854,8747,2599,3318,2396,8040,6501,3162,4326,3167,-170,2590,2914,987,8979,307,5864,5408,2669,-108,7258,7595,2886,7922,4063,1361,4543,8169,7670,5292,8944,3082,7271,8758,7676,1146,-789,1854,5004,3345,9018,4189,8356,-72,817,4643,7046,425,6550,-929,104,5179,6937,2580,205,567,3473,2534,6241,1807,8765,407,1870,1035,6566,8543,1684,1570,5537,4397,-532,4961,-84,-490,2381,1524,489,-339,5524,2862,3884,4691,-733,9744,8834,3360,6137,2423,4555,2516,7805,1511,5626,8028,-825,2792,3845,2206,4890,6915,1250,4061,-383,3737,3871,1695,2786,6225,-466,5741,7918,-92,768,808,2906,3392,2014,7992,6973,1804,7093,9260,8978,192,6424,1308,2161,4202,9695,6630,4348,7430,9023,9585,7338,7102,-281,642,724,420,2063,4463,8735,2644,8146,5631,2067,-356,403,6834,3509,3644,4019,1268,516,7921,1482,3667,-539,8743,9082,-494,5130,2026,6573,6827,9048,9860,334,-835,7131,9879,8451,4980,4681,3003,5079,4384,4659,3650,748,5246,2722,-8,2950,2297,6197,4840,9233,8299,7160,7907,3880,2784,838,8186,9238,4314,2855,90,2253,6260,4179,6750,4012,9991,3702,7672,2640,2761,457,9884,1200,1871,6794,7546,8566,-837,-85,-955,6617,5408,1502,2954,77,1577,4066,9516,7379,3598,4217,9939,8060,5957,6116,689,600,8240,6599,8452,1889,1685,4565,3876,6944,9508,4537,9736,9356,4269,5026,2234,3615,2240,8269,2418,9895,8190,784,6821,2673,3955,-919,4713,4810,6671,9318,4239,5106,9667,3612,2418,7825,7796,1850,8594,5815,6783,8969,809,2145,-50,883,8791,8646,2711,-644,-191,8320,5495,9911,-86,1090,8598,5276,-836,9240,-179,-338,9993,2665,7252,9198,9202,6726,-451,681,-501,8244,8713,868,2674,6892,4150,2119,7859,-431,1102,-892,6908,985,1358,-439,8622,-985,9591,3878,4902,8789,-929,2774,7406,9020,-202,-911,3209,7347,4384,4085,7105,7782,5707,9120,9294,1931,-724,4402,2907,9258,8459,-169,3238,4917,6335,-409,997,-819,5492,1479,2850,4706,2710,4951,1015,7507,9878,9952,-26,3888,4702,2766,1956,4109,4623,943,2729,2643,745,6167,-29,4897,1144,2542,2939,2870,2276,1457,-572,6681,2325,3371,4780,7493,1556,5144,7237,7157,295,6718,-433,78,2532,9348,2942,3407,4348,4213,-61,2109,6434,9212,6690,5467,485,5113,4346,-787,1208,4795,4538,7779,4124,7852,8714,-170,9410,2795,-592,5803,6221,5903,2674,2533,2313,4687,6501,2042,8830,5763,7233,4230,760,1761,8786,9141,3928,5628,2636,2628,7422,991,3195,1660,-246,183,8826,3512,8367,347,6220,3282,255,9162,575,1061,2084,4480,4774,1518,5433,8850,9285,6801,2425,2519,2611,7098,1269,5077,7404,3812,3468,-910,5381,5019,5429,7025,4197,4964,1940,7538,8330,3546,5173,3703,8556,659,7352,9977,6409,4490,2451,7987,2003,6525,4195,7101,-845,1825,1977,4282,7253,9733,-660,-832,1815,401,3994,-146,4912,6403,493,7000,1814,5780,-431,5251,7093,5531,8542,9646,5388,7229,5538,8093,4332,7925,1101,5517,4375,6409,7726,8122,5336,8543,2031,8919,4472,1816,4571,6142,2149,5110,1522,7134,3743,7130,7854,862,493,-292,1453,5218,3909,2591,6010,3778,2610,358,3269,2387,4916,439,53,87,1806,1874,7148,2723,5040,-187,4059,4209,-416,5071,8916,7271,8087,4699,-43,7117,1007,9944,335,9973,-334,7473,8793,4630,-988,8210,4815,6033,3938,8610,7050,6095,9363,9392,4000,8964,4397,1417,1704,5249,-511,-292,4397,497,1865,9501,8914,414,229,4902,3576,6856,5112,4659,8947,3577,1946,54,1070,-253,8391,527,3608,4845,1627,7489,1027,2555,4652,6266,604,144,3135,3068,6109,2289,1513,7936,7980,6022,5185,1891,673,7058,1424,3752,-673,1239,2981,2587,4889,4657,-413,8782,2345,7052,8570,5677,5849,681,4340,1338,6432,7309,7384,5355,9122,4949,9094,8390,2801,1902,5325,7384,2795,4276,3212,5970,5196,9880,4539,4389,556,-565,8989,2110,765,6524,7873,9351,8898,2156,3264,405,2850,-81,5356,4487,1745,6088,-957,4673,4821,125,3428,8714,2421,6915,177,2982,453,1545,1050,6356,-713,3338,5959,9616,2018,156,4998,9855,9996,5883,8006,-533,2464,4131,8749,8388,1577,7391,5209,8819,9023,2905,7061,-87,8482,6927,4906,-705,1689,2731,-744,5983,15,1866,1903,-969,4578,9971,1336,1156,7736,1200,1715,5081,147,4270,5845,3073,3795,9156,3503,1943,9083,1343,9802,7385,8078,3225,6724,5434,8099,3255,8060,5934,4370,43,4911,2987,456,9694,9743,1927,4250,9041,44,5839,4019,478,2488,7317,1137,-517,7704,5199,6887,8253,1859,6198,5632,4618,610,9864,8882,9822,1841,9500,3707,1036,7193,1063,2092,6758,5543,9441,9348,2189,5648,1569,9601,-226,5765,6668,4661,2437,7147,-345,2456,5496,7936,7050,6028,1590,2819,4757,4630,401,2127,-44,8223,5206,8246,2505,6101,4737,9010,7922,3151,5098,9449,2751,2591,9154,8347,1662,606,-413,2536,-414,7527,3340,-178,-202,8146,4122,2021,7655,3210,8470,5995,1124,7248,5820,8970,6729,9242,2417,6379,8852,6500,8372,-649,5695,7434,-922,6447,9384,6842,8401,360,5264,314,727,1586,18,1612,146,2678,9561,6241,4630,-267,7701,1486,339,1710,162,-114,7431,1819,8333,8810,3300,1210,797,1769,2811,893,3637,1962,2075,-196,695,1104,1977,1078,159,205,6885,1775,805,6306,9906,2292,5622,6910,1310,5347,3751,3463,7163,904,5165,1844,9995,5342,7917,9521,6422,4960,5088,5912,6194,5884,3851,8878,7246,-966,6215,9901,9704,-316,7498,1323,-285,2093,4347,3861,2041,5137,4592,-559,6150,435,2018,5869,6993,3100,1831,8192,3407,816,-104,3500,9716,3636,7529,-349,1958,732,2320,6262,4211,-18,-330,8120,3163,188,-872,8212,3751,6658,-811,5511,9750,1719,-389,217,9194,5511,2898,3058,9205,3301,130,-758,2122,8541,3736,2772,9656,3022,2799,5054,6957,2047,5731,7986,-448,662,-939,9079,7153,1835,7364,8674,7322,7709,7319,5863,1751,-815,3899,4424,9749,4566,6922,4696,7916,8284,5415,-891,9172,5467,4656,2000,4968,1477,4842,3467,3902,4647,554,-601,4538,3820,8084,-70,695,8539,6864,7259,9608,6204,5845,2632,5751,2624,2992,9477,9723,8985,718,201,1599,-565,8692,5825,3745,7594,345,4950,3908,9969,2066,-180,-154,-440,8889,163,8060,1802,2532,-784,1335,8287,-952,3937,3182,8124,7805,7335,5642,7153,9793,2941,5001,-787,5376,730,8731,9408,1326,-386,8950,850,4637,8257,9092,8796,1231,-873,8489,3512,3685,9443,6542,4486,7922,854,7734,9762,5601,3214,2979,1582,-943,4642,6543,3671,4601,1256,3108,3835,3136,4217,3579,32,-393,8768,6120,3311,8712,5677,4209,2947,3528,9290,1826,5263,-627,5512,3946,6402,7754,526,7103,2871,9526,8333,5785,3645,7424,1105,960,-725,5964,1327,584,7851,2110,-868,7870,5195,7610,61,2106,9612,-534,2634,3692,1031,4562,-386,1532,3726,7294,6150,7184,361,6310,7854,1608,6589,8067,672,6519,8668,6729,6504,6423,3379,3268,7204,9359,4197,8876,3024,768,744,-882,98,8151,9583,5848,-992,5621,7305,97,2695,4693,-399,9182,4490,899,-399,9119,9573,2228,2899,7364,4518,7548,6609,6132,-886,2752,2643,6042,992,6191,2047,7432,556,5423,-588,970,7161,-523,7567,387,3361,9296,747,-912,2674,-725,1227,5649,1071,9882,8178,6638,4850,4763,7307,1034,8773,8780,3055,3456,666,5452,8494,8632,2632,8706,8171,4163,8145,7461,2078,5192,-913,7156,6894,3889,8136,3211,4614,5281,1069,6130,7346,7515,1547,8405,-598,421,3840,-628,9423,114,8100,6713,2885,-359,1417,6143,3776,907,9127,5026,6150,4363,436,3379,809,6728,8052,4083,1579,7507,4484,3383,2109,-612,3521,3288,4109,4141,1818,268,1760,479,5952,9310,5221,7191,8439,-3,1601,3210,7270,4746,2735,1147,-623,7239,3181,-82,4672,470,4191,1897,2421,8259,-959,6610,2411,1427,6694,7012,7251,1490,4916,6,4727,4215,7753,8721,5628,6858,9784,4679,1850,8494,9448,3333,2473,2045,4342,6775,6311,5271,-366,542,559,1172,7143,3719,4202,1376,4686,3269,6460,8937,2041,8405,1227,2345,4441,6499,5299,1950,8123,3077,-428,43,2818,1371,4141,4410,2463,3943,9223,2825,9058,-602,2535,8082,4116,9089,2200,1689,5786,5597,3551,1286,795,3447,4485,810,283,1777,2228,3438,1292,926,8994,6595,3657,3522,1214,6535,3430,5851,-370,2993,9513,3835,8942,5288,6175,947,-343,7807,8902,1352,5209,-895,547,3203,954,6215,1572,862,5881,9268,1487,8296,9387,2623,9737,602,8158,7373,7495,4348,420,2147,-375,492,8051,6465,7172,509,-446,213,8555,6921,4383,9889,8003,4140,7589,2742,8225,8396,5105,-653,407,5900,3000,9759,8433,-198,5205,6220,4309,2857,3207,-764,2483,4260,-587,3498,9455,3196,5271,-814,3749,5245,7648,8207,3504,5758,8614,7105,1720,3114,4352,-302,1886,328,3169,9478,4935,2604,9269,1524,6461,2373,2983,-748,7853,8847,748,9689,103,3447,5084,3217,8208,9980,2527,7448,3513,863,4960,1504,2587,3110,1730,4188,1882,8338,2880,3077,1030,-384,-903,5189,3061,5217,2816,2842,5827,4265,3091,5602,2204,2610,-5,8506,1489,6627,5251,2626,5599,1386,8175,4276,7743,9072,2927,6052,-44,6820,7919,2719,94,5203,8432,5894,6488,5784,2925,8275,3984,1184,6076,4385,-953,283,1206,5861,-117,2006,5311,5239,-502,2804,5322,8937,5687,9483,2803,4076,541,4645,9539,7662,2069,1738,1749,-346,9095,2630,6565,5614,9192,-337,3929,7062,992,6738,9229,578,-154,1403,2041,-948,9321,3072,8285,5298,1404,1280,8642,773,5561,3404,7123,6231,9490,6112,6292,3831,7656,2005,7303,1916,6450,-959,5931,4091,8051,-599,9478,3029,3035,8522,6206,1252,9966,-690,6710,4368,-401,2751,-877,5695,6282,2356,7559,9549,4215,2458,4568,8432,9467,4304,5289,1259,2089,8009,7234,-536,1797,6028,4140,3082,3978,2033,-236,5090,4887,5191,-715,6925,659,3485,4375,277,9745,8868,6343,5996,5380,3229,5301,6415,784,6590,-428,9518,2956,5843,-559,1726,4843,6407,6895,7257,8942,7843,1200,-625,-722,3647,2528,4259,-35,-708,3142,7,-589,-681,4056,7482,7576,1330,6127,1283,-278,2559,-866,642,1757,2243,7941,226,1659,681,8213,1090,3620,5564,-28,7612,7060,7291,5607,5501,-917,7362,5600,8211,4419,4300,1677,-579,3433,9721,7474,9795,5680,9291,-149,4694,2186,962,8361,7961,4238,4409,7028,2054,3703,3052,-99,1981,6780,822,3393,6787,1386,438,9683,10,8675,7428,2912,8344,2877,4643,4447,7106,2968,2800,1864,-378,7176,2920,2081,5462,2647,6459,-775,4910,2064,617,73,9593,9697,167,5085,7228,4193,5211,8669,189,7177,3616,4685,4764,6597,2306,5323,6849,5134,9921,8901,8430,2469,3742,6993,1359,484,2963,1561,3011,5052,8841,1870,9178,8477,3064,1704,4987,856,1937,8014,1369,5642,1555,5905,-100,4641,5398,3118,6821,701,9856,6979,7715,892,7990,3149,2880,-992,4517,8182,624,3619,1724,9686,9187,1947,4138,3732,8278,3745,1468,1257,7900,6643,939,-647,-637,8475,869,3499,1643,1698,-430,9410,8667,1722,6053,744,7408,9633,4225,7757,6682,2010,3044,4866,888,-832,9965,6761,-252,6983,8290,2698,545,3463,443,5141,9062,4497,4794,8525,8304,8619,2857,9997,7979,2566,8230,2735,5516,5620,6533,6578,5498,-767,-126,2413,6552,5237,3779,1447,634,1632,-363,2575,9435,5585,2920,253,3581,7900,5824,4329,8069,7926,5025,7620,-37,6916,3961,9944,2039,694,1259,6482,-331,3011,1342,3164,4518,-226,777,9861,9492,3098,1860,8098,5703,6795,-127,7733,1836,1304,4235,260,3326,7287,6617,2461,6839,298,69,8474,9548,5997,-761,932,167,9162,9909,544,3953,2605,4267,6559,6768,471,9656,8930,8085,6086,7838,6351,5263,6203,-203,3243,6132,3437,3142,7918,6384,6143,4998,-393,93,1829,5589,2082,623,1462,3200,3293,7581,3394,9283,6167,855,3401,3487,4473,2433,2715,4311,3503,8574,9426,3037,7194,7649,3759,6761,6543,4897,4495,4332,70,8862,376,-145,9782,1329,4920,5317,6724,4896,-243,4795,8416,1913,3838,286,8284,-799,9443,3286,8860,2351,1158,6496,-505,2892,-558,-48,5515,6950,7356,-432,517,6837,9988,-599,7358,5148,-160,2726,1959,515,-327,6300,-188,3902,6948,7062,2916,2482,5303,3629,9962,7990,3511,9750,2141,-955,-562,5929,1822,5041,7896,4591,-321,5536,3447,7911,8452,1500,2020,6111,3376,413,9588,6906,283,-511,-445,3810,6207,8308,3430,7555,-699,3176,3364,6430,7202,-592,6714,9956,3337,1293,5331,2142,8424,6627,790,2590,3450,4838,5495,8934,8525,8866,6844,-228,3675,7695,620,6412,7288,312,4649,-137,7517,-556,1672,1746,8636,5256,5299,6890,7440,1549,-191,628,5758,766,5349,9389,5010,5853,5607,4416,-311,4307,548,3384,2035,4693,6242,1438,8288,2445,8807,9198,5884,6568,455,8430,7861,6830,6938,1508,8568,4962,3139,8570,2937,2314,304,9131,876,4357,4948,9424,312,3032,2545,8951,1056,76,8574,-199,9302,5373,9372,207,6963,1344,7570,-225,2616,2808,3443,4266,6824,-93,6231,1414,4991,-872,5320,6363,5375,1641,9597,1758,5251,4546,-224,8651,9369,491,392,5716,6086,5516,5592,9563,8822,7052,1069,7472,590,5168,287,-39,8771,9667,3237,1329,-691,8615,5794,-689,6839,792,809,4295,7827,1799,9871,8858,1903,2773,-424,1192,3096,-737,2461,7028,5271,4149,9263,2076,900,1803,-15,9537,9793,5165,6472,-903,5054,3085,9115,1216,502,4529,275,5002,6537,6571,5735,5438,6129,5949,-146,-74,695,8880,16,-928,7657,5331,3218,7433,2794,3602,9137,-96,995,9641,8733,183,9820,6950,2754,6528,2909,5095,3549,801,-47,9614,9496,-338,7429,1155,8090,683,376,8802,7952,3388,841,6623,3797,1422,-845,3808,4893,-851,3283,4305,-414,1880,3636,4236,6471,6493,6207,56,7906,1817,4554,7178,8117,-602,9204,-256,728,802,2204,5961,7060,843,1498,1205,2095,8650,9311,5089,6423,7969,8623,547,6395,7270,6928,6948,3833,2353,6075,6238,6417,1800,6679,4393,7187,3044,6019,9286,1034,8415,1341,3844,968,6516,6761,4375,1692,4010,1211,3596,3442,1474,586,8189,6223,-917,2705,-997,-616,4172,6636,7587,3843,8688,4668,8047,5876,9527,8911,2365,-193,-809,9576,49,3987,5045,2255,-284,1535,9448,7058,7253,3767,9222,6793,3480,1975,6247,-215,9382,7546,6984,7188,4319,3517,8902,2808,2010,2965,8901,4921,8514,1203,9838,5908,7925,5429,89,8395,8473,8911,3137,-927,3415,7188,2865,5093,7835,4544,211,3563,8286,3389,8989,4526,6758,1349,7022,-213,2799,4828,1573,9749,8316,2781,419,4793,-475,8027,273,4549,3212,2958,3726,3657,7743,4444,3311,5614,2423,2890,3248,9353,-312,8239,8598,6211,-11,5634,5955,1774,7968,8921,8079,7611,1288,8298,4539,9986,-920,417,4585,34,-395,4759,9687,9372,-833,5493,387,7853,2829,2274,5233,-50,5805,7301,6495,6767,2071,5467,366,3427,2243,7730,9299,9113,536,5874,6466,353,2151,7112,3972,4891,6934,5638,8627,6676,2986,6935,6239,-289,5922,2295,2292,1762,1499,4758,8189,1778,2211,6342,-846,2727,4174,8236,8643,6989,3033,4097,5836,6563,2159,4162,2197,4294,2202,9665,8770,6098,1408,5205,-548,4520,7128,2242,9067,6742,9061,8156,8686,6480,4413,6748,5884,6076,2364,-983,6430,9745,2659,3406,7340,-942,4406,7093,2429,7044,2204,3351,1331,1752,4604,1587,1621,2338,4319,7928,7793,2917,5100,5141,7731,3207,-831,8559,110,1866,5270,1045,6073,5796,2907,936,7949,7173,3897,3793,-639,8267,-139,3883,9419,2876,8001,3402,1357,59,6820,3988,-375,6462,4489,9149,4562,-716,7186,7303,9423,6313,5600,1286,4259,5789,9055,7279,8631,-398,1217,8989,-870,1448,9684,6119,800,-733,5355,-92,4104,8551,6151,5735,1703,2242,5063,2131,4466,2915,7708,2311,2111,6943,5435,7112,-64,2694,5877,4640,157,2226,5606,7365,8534,4772,5515,2873,940,329,-552,3470,9070,1896,2030,-215,7034,9446,9415,3095,3993,3413,-307,6237,1225,3358,1626,7114,3482,3165,1875,7402,1457,1374,8770,9891,6091,5603,584,6613,5286,9265,7132,5606,7345,6411,2733,4313,8038,9448,1177,9492,4168,8659,5069,4473,195,5416,6129,2940,7971,4334,3766,4003,3384,2459,7520,5399,2669,4754,9547,3932,532,7482,9695,2221,3790,6743,-647,1319,9965,1979,9469,2838,9316,9159,5790,8231,9247,6264,8802,1050,-780,7830,9902,7737,7220,3176,3977,3550,1314,2790,8465,8116,8601,4883,3662,-272,4256,9087,6633,-190,2135,7633,5833,8823,5028,7493,6185,1139,4327,5654,1833,4093,1464,1015,5015,7589,8110,5123,3607,8732,3204,3891,3193,1965,6606,7380,4721,8867,2469,6494,5635,6731,7545,3366,5548,-586,5703,1761,-438,3060,1004,7631,5376,6330,458,-127,-428,3499,4180,6599,2975,6250,920,7515,9138,7977,7363,2042,8330,5387,5767,2518,-853,96,-892,3951,-375,8149,5491,9910,4405,1147,760,3739,8800,1176,890,8685,3473,9045,7090,3274,4590,1850,3236,5965,84,1686,1378,7300,3836,5747,2692,7253,-380,3358,3969,2235,6381,4293,8070,8845,3577,7577,6870,8338,6026,2656,2386,2441,7258,9949,1684,-211,9486,2249,4967,3207,9254,8046,5645,9581,1898,8028,3568,7024,7831,1895,7560,6517,7029,8357,2296,8987,2724,9170,5514,2099,-929,5951,8555,366,4136,1656,8854,2841,4670,2263,620,2264,9708,6870,5580,4315,1805,4897,8271,4085,-366,4044,3348,7225,3780,469,2479,1419,-326,-27,3322,7795,1664,604,1324,9275,3012,3086,6921,3147,7671,5892,2769,-168,8144,5333,3545,8472,-904,-361,5092,9469,-791,852,8864,2273,7964,6093,9586,2994,4705,729,5828,2259,6726,6673,5206,1202,1742,1170,428,1151,7813,8429,5282,7696,9193,5888,7509,9991,5764,6527,4999,6948,4616,6229,7668,4916,-150,3143,2023,2072,9999,2416,956,8406,7180,6893,9333,103,1966,-467,707,7383,745,5197,-249,3007,7410,1625,2111,8308,8802,6664,7578,1134,4367,9177,4765,4443,2141,309,7436,5455,4053,4124,5580,9860,-114,-726,7937,3900,1875,4796,-236,1196,9483,3586,2815,8246,8920,2796,9620,8451,1605,416,1882,1775,8680,1952,6626,7535,9484,593,4774,1680,8755,6591,3174,5341,6927,-365,7398,2587,8295,7454,3781,5077,1472,4480,8270,3434,9964,1967,-828,4360,5197,5448,9534,1445,389,3238,7748,3918,3491,2152,3146,5470,4638,-777,4070,1352,7503,8898,2707,2147,9035,2123,6211,5164,-17,3243,1301,5419,7461,6155,6495,9520,494,5165,8016,5124,504,8603,4406,6909,1935,4417,7554,9690,3918,9369,846,5456,5455,8984,799,5033,46,5817,2987,7269,1857,2457,4254,6457,2384,8137,3277,1746,2324,4892,-605,8376,-628,1284,7597,3429,7874,2851,8186,7776,8124,9659,8895,-81,7357,6159,-128,4751,9846,9939,1890,4205,7861,4806,2972,545,3632,3794,2908,1309,6898,4310,1777,3876,7654,8897,1296,3796,2172,2355,2253,3878,4511,2447,-228,5674,-612,8624,79,9711,-552,1898,9733,8556,6028,7228,3822,6309,7054,2977,-965,2766,-234,-498,8551,8866,988,-362,-354,7045,-952,4035,7925,1480,7186,4770,3365,2296,3419,6001,3481,9170,7873,5028,3174,-639,7087,6809,5029,-807,8324,6497,3027,686,3886,5604,6168,8617,9904,1729,8052,8452,9194,4247,6858,3388,9657,4477,8544,605,4280,7860,-308,5617,5060,4632,1264,3597,5808,8551,4629,5722,5166,8459,1964,3903,1147,4385,1247,8391,8114,4470,4388,4502,-489,5533,3309,1258,5358,8626,2643,794,4665,7570,3475,4668,7789,3943,2069,2490,5780,9410,2927,9499,8552,-244,7115,9993,690,6524,9238,9228,974,7240,2778,208,7740,2150,4990,3645,9114,1170,5441,8674,3741,4155,6302,-681,1891,3449,-882,6953,7002,1832,8561,9632,4528,3340,848,4112,-503,7637,2350,886,4026,2345,8374,1741,-143,8344,9678,5625,5752,2372,8252,252,-548,-282,5362,8950,2554,6803,-984,4158,1542,8260,2477,7923,-425,2335,1442,798,333,6176,109,-408,4300,2707,4915,3373,5833,3885,6190,9542,182,-117,1112,8814,3027,1803,8241,1143,6597,4983,5470,1186,2070,5036,8051,1791,2531,5660,7096,6593,2317,5855,4939,-587,-704,1613,5715,7386,4919,4757,6046,1860,8863,4096,100,8686,5956,4372,8929,3398,2982,5872,1689,1292,1881,-12,7111,6701,1675,1848,-476,298,3790,4807,298,-846,6579,5226,-518,3173,5513,3407,257,4151,7466,-577,1061,4585,4452,7031,5458,8996,7243,1720,7773,4998,3631,4960,3948,4361,6958,-155,8408,3347,2753,356,-85,5756,892,7147,9381,1505,7339,4255,9120,6962,4564,3263,7836,2419,2595,-511,7111,2331,-254,8371,3996,4263,7475,1784,4217,2122,6673,1881,8200,8970,2815,1079,518,-374,8119,7565,8149,6458,6415,5010,1968,8195,2106,8110,9846,4054,7524,9163,4448,8661,8125,-595,-316,5200,-263,9231,6954,5838,732,3167,7577,-976,5697,7765,5036,5431,8925,8074,2166,2842,6360,9985,5527,-257,2097,1678,4101,4573,6499,1278,2699,7641,6276,9669,-658,7053,5598,813,-190,9325,3543,3596,8707,2076,82,7148,2389,5842,-840,8844,9438,3317,3605,2841,4766,5200,7282,4680,6537,4281,5546,4065,3675,5684,9586,-501,9887,7280,3054,4295,2376,6242,4390,1376,4100,2168,-552,-256,3009,-615,6939,-762,5831,5410,-464,-342,40,2846,4900,1372,2547,1924,-326,767,-276,6600,6561,5806,3507,8193,8530,7176,2251,4567,5627,1845,8469,1498,7277,-682,-958,4005,4757,3744,9650,6089,2720,8232,2430,6607,8077,4794,5546,8352,6081,5847,2981,4682,3126,-337,1652,279,107,6383,5422,-33,4578,6705,5489,7110,1978,9944,9943,2141,7925,8960,2162,4568,3827,715,8197,2787,923,-477,7753,5969,4846,7239,1217,4222,9695,1547,5487,1964,7976,-558,1213,867,9023,9996,-915,1228,3606,7227,891,7344,5375,3984,797,3954,5369,719,2142,3825,5705,54,4797,1256,361,3138,4538,3561,327,-637,6335,2540,5719,32,4440,9430,4516,4049,9555,4191,934,9473,5943,2929,5368,2280,-163,5509,6601,4337,3720,7134,4039,-747,6230,1183,2531,6850,2022,-712,1238,1149,5388,1678,61,397,6413,-927,7842,5255,-243,-562,9220,-150,5398,7802,6042,3363,8954,-612,2569,1821,5292,7118,6424,3652,6242,8581,1136,2726,2481,4206,3589,1618,961,2482,1287,9754,4202,5368,304,9550,9811,8895,9519,2263,2342,7986,7195,4668,7862,3162,-365,933,8473,9645,2755,2819,2689,5828,7453,1777,5195,9949,8435,8777,8424,7315,3986,4129,3532,7252,5557,8703,9954,4925,2568,2121,1500,9255,3170,2124,586,7050,7287,8214,338,882,3853,4220,3971,2152,7728,7866,-553,7256,2873,6489,9580,3927,-399,1741,7514,4519,-419,912,5490,2677,5950,5797,4300,4464,197,5743,-585,111,3494,6,5899,253,8778,5056,8487,247,8117,3907,1383,9028,7378,3761,4816,9184,4121,2087,4962,8656,6307,7868,504,6186,2749,3384,1445,4744,3926,6740,7972,7327,4771,1657,4016,-348,6223,3814,5894,2435,4258,8789,5174,3332,1954,8463,9007,3441,4526,1762,4498,1480,5730,3904,3950,5375,1541,3342,6631,5891,433,6995,9184,-947,316,4014,2966,9460,8662,3376,774,-301,5714,4622,1588,7385,962,9706,3151,1204,9829,9641,4676,6294,3975,7428,8146,7377,8638,195,5075,4179,5425,8204,3599,8068,7701,823,1999,8553,9926,9818,2773,8574,9511,5173,2592,6191,-700,1990,7892,-353,7211,5369,3855,6282,4682,8249,3615,9347,6743,8657,5149,-752,8114,5176,3194,2501,-875,7898,2689,5365,2757,7507,160,1363,7465,6116,4895,8885,2534,8859,-242,7729,7173,8966,9996,3026,7984,1972,6622,22,-729,5664,4032,1237,9777,3533,8124,2622,1545,2268,2769,86,1962,8535,6728,5749,2716,9516,7947,9105,5528,7385,420,2817,1587,4167,9427,5284,1853,-409,3615,3055,6768,6496,9139,9340,3551,-151,1442,9976,5123,5870,4173,3618,2300,3643,5519,3677,430,1646,-865,3826,4747,2657,1846,3169,1999,8737,64,4067,7458,6883,9768,2151,-35,4412,1887,5559,950,3884,4189,-597,7498,5237,5481,6646,-544,9052,7598,7113,8148,5239,2645,8916,4082,3197,4164,-942,5708,724,2180,8972,-384,3581,1103,5544,9759,2620,-537,8882,1858,7557,6983,6447,2489,126,-714,6742,570,416,2750,-729,5571,9231,-657,7536,3760,5406,6826,-311,6255,3647,2170,9503,3211,5779,4054,6645,1182,4366,5263,2365,3958,1746,585,1493,5185,6117,1336,4973,8187,8576,4250,4325,551,3199,1311,4930,3823,1870,1469,-490,5847,6138,2414,343,8324,2590,2848,4447,2081,1552,5917,6942,9544,6777,8820,-528,7027,4324,6402,3766,927,604,9197,1336,799,4170,9816,4397,1685,7194,733,1993,930,576,4025,2697,5488,7775,1515,1607,1632,3858,1043,6649,-210,5581,-267,3399,6861,3383,5893,4788,7582,6492,4234,1503,1315,1689,7873,9638,8406,5110,-220,6111,59,67,2582,7163,2219,812,9578,5098,3360,4406,4416,3383,1107,95,8910,2118,1898,1261,3276,3362,4211,9905,5160,6550,-952,-632,3497,2007,-779,7717,879,-235,8521,4051,7800,5350,6700,2487,4416,9105,832,801,92,2526,-741,71,-581,-766,-433,3023,2920,3845,7363,2635,85,5218,3021,1299,7618,7636,3933,5345,3612,7706,3694,-228,5654,5348,366,8676,5271,481,5176,4118,1542,705,9839,8874,762,4053,3374,-382,8972,-655,1916,8378,7824,1640,4819,7008,5175,3800,830,9843,3155,5506,5386,7823,2951,69,-70,5453,8656,1556,2949,-578,1562,3492,8060,1807,6440,1561,6645,9740,2164,5826,881,2116,-400,8292,2244,3274,5153,4946,-949,7810,-598,5155,6372,3888,194,9900,6327,655,1555,447,3243,7884,276,2065,8443,8586,6692,3597,1060,-585,7798,-108,1486,1617,7649,9561,5381,6019,-599,4050,5577,291,2293,7627,4787,4902,4347,5284,7678,1131,3106,3326,2632,7409,8250,5069,1295,8889,7226,9417,7000,4941,1604,8868,4008,4983,7520,-153,7835,9251,6279,5763,5808,9854,9973,241,5016,5924,2457,1574,4576,1390,6885,3977,5904,7724,5697,9613,-259,5519,7965,1307,-182,3744,-503,9606,2436,2241,9546,1243,3362,4877,6695,9479,9311,2466,6562,6051,7311,2222,-10,8618,8720,2642,2481,9701,4150,5499,7676,6213,2625,6486,5657,661,6928,2807,5150,2510,3872,4256,1866,-107,9760,4909,7730,3226,5423,1207,-616,1282,8023,9904,5221,2965,332,7345,8845,6679,4406,7635,9311,-806,4532,9808,6533,3415,3429,255,6335,3645,-772,913,2039,901,9502,-708,-309,7719,4302,-837,7082,-596,8055,4855,2204,3567,522,3056,2804,6758,6638,1579,139,4589,9711,836,1861,7799,3054,1774,4999,1264,7648,163,6121,1971,5248,3019,348,2592,9241,9030,5956,2666,5162,-50,9680,9647,5125,1249,5733,1023,-741,160,-74,-70,-236,7165,3762,2255,4287,3177,4622,-973,5117,-803,6806,1183,4575,8863,6177,6004,2321,5123,2034,7876,3933,8766,9384,6245,6239,4675,1450,8154,-881,6319,2142,5480,6466,7706,6423,9278,4534,1423,5514,294,6913,8020,8116,4037,8371,3875,2792,5538,45,-127,4268,2431,9261,4155,5601,5177,3472,2122,1112,9043,792,9781,9562,9512,9124,1225,-344,9066,4952,5289,2737,6325,1808,1302,767,7094,6133,9440,5446,4152,7478,9532,1654,2576,5810,2886,2851,2705,-86,810,9113,8544,3478,7353,8365,879,3350,4751,996,9214,3794,5525,6390,6534,8034,7721,7701,3509,6276,820,7589,2447,-898,2114,4127,1711,-438,3238,1732,9929,-509,2431,7030,7174,801,8702,591,4372,-72,280,3893,5948,-391,9340,-201,7889,1785,2024,4332,4787,6121,7921,1641,9816,2541,9210,2397,4583,5198,6013,5100,2382,5247,3490,57,9345,152,343,8158,4078,-396,3215,1069,1311,8972,543,3708,8753,-742,7712,1284,1917,-525,6468,5423,6022,-473,6560,4747,1074,3862,7348,4326,7017,5313,3892,7496,106,2867,550,894,3783,6146,3524,6205,8042,5174,5321,7255,4302,4322,2311,2359,8072,8409,400,9062,9975,7752,8610,2163,6773,6842,930,9811,3550,3754,683,4090,1113,2449,7703,4749,9644,-236,7089,-443,1349,4435,4792,6869,1931,6912,1932,8213,9181,2526,1759,9974,4674,6142,6651,-362,111,5227,394,8211,1223,4469,-477,4273,8102,3815,2204,2810,7183,6142,3693,305,9059,3771,165,-724,2817,8748,8948,3823,3998,4871,6514,8635,2958,1304,116,8516,6074,-584,856,4386,-626,2828,9998,4919,6594,7641,6767,5634,4001,4138,4480,737,8450,6513,1554,3878,5513,1246,-534,-464,3661,4502,9014,-29,5288,9014,2783,1071,7879,634,4917,2472,5288,3824,8415,6638,2968,634,4807,5657,2856,3066,4059,516,9126,1019,5473,4462,9201,9039,4914,9392,6562,7978,1958,7021,6839,1269,6638,791,5028,7944,8996,5795,6826,2811,5506,7694,8753,-94,2464,1572,-801,2041,157,1841,5062,3732,2730,7708,8061,20,4063,9874,8672,2767,4861,2245,8760,7037,7128,945,7577,9079,9949,1991,188,7750,9631,4868,9356,9385,9215,5843,6022,4745,7405,7828,6230,2045,570,7515,804,9908,7555,2669,7345,7853,7985,1092,9840,9131,273,8528,5657,2848,6346,2859,4031,1262,7034,3001,5187,8441,8934,8915,353,472,7698,9098,5691,8984,2686,5880,2784,7494,6700,6991,-803,2646,5124,3911,5931,8914,3210,9720,7117,2939,6902,8159,2443,3635,2671,6911,243,5938,1734,2982,6320,6647,8133,8947,9264,2369,9195,3751,3396,7889,1170,6081,892,6175,2956,1582,9045,1951,4668,600,4305,6553,5139,1164,4291,4852,1446,4930,8817,9924,-40,-693,9405,8967,4439,4611,4681,7485,8262,8031,-271,5829,832,87,2146,8977,1309,9559,1266,486,6638,8709,5071,7431,3372,6982,-644,113,-747,3687,2347,1652,3443,8921,4693,5046,4153,5613,418,1543,6978,3015,1072,3851,2450,6492,6685,5279,5798,3600,-884,1496,9466,1214,5105,7864,9859,877,4557,1547,1235,1473,3971,3633,-703,3249,8041,1558,7196,5300,5419,3947,3900,5731,4001,-572,8080,9064,7812,4217,7981,5891,-7,7602,1007,7628,3984,5226,2188,5969,-535,1119,1313,328,1028,673,9161,3674,4236,9968,9649,2020,7228,5287,5822,1479,4390,8895,9578,8223,2806,5003,4977,1667,32,240,8822,2827,5992,7664,75,6016,6686,9090,6643,5514,7964,9978,4143,-724,1311,-662,6304,9411,4882,216,4975,3547,498,6744,9826,5273,6378,2387,-777,5449,6359,2329,5289,6640,6838,9067,4942,9375,2485,7992,2303,2990,1459,9520,6685,8925,7272,4751,2909,3174,1371,1672,2796,3993,481,-279,9761,6141,7108,4094,7642,4449,8207,6483,4795,674,5241,4747,4972,-23,4829,3687,1431,4869,4008,5322,7717,4492,6083,908,6053,7289,4625,4281,811,3423,590,8050,7025,7245,5501,3134,8925,9907,4999,6726,6140,2376,4278,938,140,3088,134,7434,7371,7877,3701,393,5564,3433,8015,8338,4864,4699,-492,6069,3866,135,7969,7414,2438,7717,7975,2698,3642,6169,8444,7771,9011,7314,740,6139,5631,5862,4725,-410,5725,7955,9972,2313,6864,2396,6574,9491,2972,906,3407,423,757,4315,1659,7604,172,1129,8383,2310,8566,7929,467,1733,2237,-622,5772,1887,2675,4034,5060,3278,6086,6484,5308,-842,4950,6260,-826,9690,-585,6938,7027,2996,163,2844,8807,417,3235,8774,409,1855,8516,7837,4714,-338,-759,7195,2100,-121,74,6633,4451,2670,6738,2232,2817,755,242,9990,8581,8493,3940,1367,5615,4081,9910,2310,3193,2567,5016,7753,805,-949,7825,2095,9680,8096,3905,-623,6052,7159,-155,9464,959,7756,2936,5462,2968,9520,9025,2531,7248,9370,3698,690,1626,9835,7783,2685,1012,1507,1996,5852,6998,3292,8113,4173,459,8485,4436,-577,746,4548,5857,-755,7385,188,4335,6351,7541,5232,6635,2596,4720,9610,2592,409,6840,6893,3294,8264,7163,1743,2454,-221,4703,668,4487,8778,2368,6566,4042,5023,283,8801,459,9968,9754,3372,7551,7586,3087,9722,-898,2914,-687,8058,632,1208,8241,8214,9916,9155,6723,4045,2904,5315,8967,4017,1202,92,-171,-609,-921,2963,4083,5684,6716,9539,-296,5844,3418,7250,5893,7025,-681,-153,-366,4047,3208,3138,8741,8662,6406,9812,611,8363,9615,632,7093,1327,7426,8312,3045,5883,5101,847,4662,4500,7529,6392,1028,1763,7026,5633,1625,-446,9078,9563,2241,5278,-236,2905,9858,1354,6443,9296,3892,8959,7027,4592,-899,8919,3285,9948,487,4427,761,7828,1713,3758,2453,3743,9411,3550,6045,3741,4913,2222,4757,5829,833,7181,-824,5825,3437,650,5468,1314,681,5270,2584,3504,5973,5692,7842,7382,8275,6995,9019,3708,2134,1491,507,-148,2696,4561,3474,1480,6277,9537,1240,5985,3668,9579,8688,9501,5150,2947,-787,5400,-687,9496,4543,6041,-772,4669,5021,-712,7371,4398,2969,8444,8819,-554,2919,2730,9726,4314,4925,-698,9061,6423,1100,2197,-922,7570,5102,5049,7290,3897,4470,4790,1707,9990,2473,-97,1229,6224,-421,2153,5537,3967,8954,1080,9807,964,6212,1431,385,626,701,3072,5116,7415,-250,339,4944,8600,7052,-23,7511,7043,2208,-642,524,3290,6018,1196,3705,6043,8844,4382,6578,6431,257,5325,2390,1271,3859,9449,9607,4683,7980,334,1513,908,8904,-990,891,1679,3216,8878,100,7531,5060,6392,4878,7570,1377,9922,8676,1425,-555,-317,4268,1562,9327,3961,9070,5323,3448,3323,6245,6787,4703,9165,1558,9227,-88,1491,7525,6888,5707,2608,8709,7865,488,8881,-844,8246,68,11,6800,5354,7986,-652,5219,426,4278,5326,5645,1303,7720,6012,6415,849,5230,-126,7453,9254,6765,2675,9253,7604,8552,3895,6577,-312,6462,9659,2494,3215,9688,6154,7565,6965,-327,142,-924,7854,1211,6980,8861,5501,2209,5966,9002,5874,3500,-367,5544,4144,4670,8706,1556,8722,3024,6622,6056,1776,5944,-819,9595,5266,8,1016,5081,7106,4201,5024,8910,7970,575,2582,7822,9499,-13,6361,-845,1622,630,7789,5445,7211,1828,4400,7722,2060,9873,4093,3437,5668,2381,5931,1442,3925,9850,7435,-780,9918,404,1008,8586,9530,7260,89,3298,7758,9513,9590,6903,4351,9877,-91,-642,-94,3541,7376,1564,6619,4236,7390,2268,7214,177,129,-431,9740,5302,5289,8918,4921,-137,889,6851,3061,6287,4708,-80,9884,947,4142,9672,5880,712,-600,-102,4365,1312,6651,1987,6141,5379,5806,8170,557,9893,7767,1600,-237,9843,788,2405,200,3689,2977,8013,4666,7315,6872,-610,609,983,-333,4800,1304,4771,7582,1193,889,9448,1756,4756,3415,1462,5498,6597,8368,304,4621,4673,1267,9396,1349,7064,4797,3496,6639,1707,3406,4322,3871,4436,1252,6932,-128,2308,4609,1348,1733,-242,5202,5360,4701,4840,6552,3212,484,-726,-843,2545,8974,6370,5009,3055,7554,4011,1772,3632,-965,65,5227,6061,7049,7921,9736,-638,6719,-935,3375,4929,2401,60,9350,-970,7869,5683,9663,7713,4117,2163,2272,-726,-949,2491,5302,4471,1522,8408,1867,9726,2760,-258,3410,5850,7790,4378,1890,2692,63,2098,5699,5718,6785,3649,-635,467,1404,8241,-783,5344,4014,5848,9894,7841,3351,7554,9957,5860,1709,8515,6938,-164,2622,2601,2750,9377,7863,2991,4637,-899,2614,4322,2252,6702,678,1795,-139,-950,103,7381,6723,9411,4544,6280,2047,5880,4450,8438,3400,1817,3709,2575,6481,8832,8945,6695,5116,988,4800,9404,1133,830,6041,9637,559,8093,2658,7417,9352,855,9497,3043,9827,4720,6068,3300,-156,643,1992,2212,5838,-633,3251,4515,8977,674,1980,5424,607,8319,5220,-860,5694,2221,3848,-415,7441,7051,-689,7516,4423,8279,8191,3570,6188,3857,2354,6831,5647,-383,6374,2847,3926,120,1242,3076,3039,-625,2156,3081,152,7419,-344,8404,4611,3033,9787,1654,5083,6027,413,5755,-944,9835,9666,-286,377,8298,6050,777,-628,9768,9167,6041,1742,7662,1627,7927,4262,6673,6414,8618,3456,3472,5406,5823,4458,6569,9278,9568,8923,6947,575,9184,5011,1580,4460,315,4650,8158,3670,5717,3314,8930,5995,4255,1708,4876,721,-922,-310,-88,6768,7253,8287,9031,1946,1664,2843,2916,5548,7428,-360,5279,4195,-954,6518,9737,-839,2704,4913,738,701,5767,5376,2822,618,5711,5523,5438,9012,5617,-728,6363,4399,5297,4774,3699,8935,1135,6348,3493,3072,6842,6422,5429,8722,6905,2886,17,7494,4473,9245,9698,4977,3227,9849,1192,9225,6010,3924,37,2476,85,4465,1879,2338,8244,-158,4446,1533,8859,6728,5092,8890,781,5010,8278,-462,4492,-378,7411,8679,5325,712,-21,8448,-299,483,6696,5821,9291,7030,4965,4601,8386,3081,3384,1383,1550,7294,6348,8156,-781,3278,764,-180,8289,2794,2249,3510,211,9756,3517,6755,3349,6701,4818,869,5530,7071,9070,9168,9249,6040,2243,1489,1768,9917,1156,5084,5866,9527,6309,2301,8344,-824,7152,6489,190,7123,6822,1009,906,-976,2310,1939,-833,5788,-175,1634,3400,9179,2940,-441,6668,9864,3269,7104,-223,-828,4589,4311,2809,8217,8132,7621,5981,-250,8277,2420,-308,2671,4815,4909,7813,3905,451,9864,7030,4279,949,2732,6781,7691,6573,4145,4860,9096,9671,2092,3677,7800,2159,4759,53,2527,3346,5150,6636,-164,9794,1054,2899,8487,9515,2268,9794,2606,5253,-845,4735,8306,3838,-627,9658,7444,1751,8097,2079,6753,6596,3030,7683,6747,4446,7719,8567,8887,5427,-714,5849,8336,608,5864,7265,5884,235,966,-588,4417,167,9702,1528,63,-873,8986,4159,6773,1599,2510,5120,8949,-496,9281,2133,7879,8759,254,7489,7728,442,3176,5317,2658,2594,7123,9838,9716,1472,5763,1245,3048,6877,-168,3305,3579,9312,4396,5540,6733,9877,6028,4373,1040,4700,9636,1059,9857,3763,4373,9028,6288,1051,2115,8851,2015,2114,81,3633,8357,1739,3109,2093,2576,1322,6818,7434,4963,5680,1953,5253,-100,3901,488,9344,2389,7502,2234,5767,3469,7711,6817,993,8121,9984,5148,3072,3890,-755,6298,4606,7898,7233,2045,2412,7453,8916,9812,602,940,1273,8616,6927,8075,580,-505,3718,2069,4832,-165,2388,5487,7766,9328,3513,7454,176,3795,750,8877,1930,7546,3885,5124,-336,7938,-760,8292,2131,3334,5976,-854,6592,-480,445,9117,9124,5810,3136,1937,682,135,7634,-962,4126,-808,-708,1019,-690,3755,9446,3806,-954,1598,5197,7038,8641,5463,2362,8729,6924,9383,1918,-877,4616,8805,367,905,7315,9781,8276,8712,9244,-203,1179,767,2078,4928,6562,9413,4831,9199,2277,358,4389,4952,6739,6900,462,819,5391,2318,1947,6101,2646,5654,8065,5232,3479,199,5641,4100,3830,9608,2394,4410,6209,8417,3574,6454,8355,3736,8425,-599,1182,-174,7669,2836,5340,1427,690,5097,9582,4565,4160,6176,1922,235,9070,8117,9027,5705,-586,5584,9256,3162,8454,5514,9313,4566,1281,9196,2270,7889,1190,-76,-551,4360,85,9031,568,8318,228,9555,890,9465,8058,1041,7710,-746,567,6490,8774,7507,7389,6195,309,1644,7350,4054,3487,1627,6542,8070,7662,9031,2497,6205,304,-232,1129,8553,-702,6171,5078,2440,6479,6220,1369,6597,3500,6796,8279,4728,4612,7542,7991,4781,3491,6237,8324,3116,3838,-401,6007,-663,1172,8032,23,3454,7639,3253,6483,2293,7161,4212,9034,4602,3070,-465,8651,2293,5150,5189,3408,5195,6456,6922,949,4920,9174,5960,3795,7989,5663,6437,238,6341,4771,-158,-580,9444,7804,33,7516,8241,3274,5498,-407,7024,6244,1655,2916,1781,2371,2266,3626,-694,7750,8074,-23,7115,-504,8533,3551,3272,8635,8332,4743,9432,2134,3992,3650,3768,4277,7567,6546,5757,2618,889,9275,6818,6848,8262,7863,3748,8978,2411,4801,4304,8226,-360,-833,1153,1101,6734,6204,9081,8231,9602,6826,-527,8781,582,6185,-464,5295,7890,7468,4772,5734,-801,-485,1904,9900,6216,622,5045,5312,2344,7776,1773,1111,12,4060,9291,3796,231,9544,8610,9718,-592,5822,5593,9881,7015,9982,1408,6924,259,6512,2463,6963,1819,6445,575,5964,9221,870,964,4430,3372,6989,8934,7612,7238,275,9287,4675,-57,6901,9299,8704,3130,6498,4188,-632,1001,-19,3213,6535,3119,1848,8749,-631,9940,-288,5075,5496,5927,4454,7583,3390,5646,-312,6124,1314,3699,3351,2076,6296,5530,3990,5958,3305,322,2963,2744,3407,2859,6920,7483,8887,129,5396,8962,4716,5242,4059,4978,7427,4150,8137,5494,5343,3221,3135,804,6302,9816,730,1330,6934,1782,7777,3975,30,1142,6812,9542,2833,1450,7183,2240,4056,7737,95,6888,132,7412,9879,9937,9440,-883,1939,214,6138], 5000
));