[Bug] Space is incorrectly removed from start of generated text for /v1/completion endpoint

[josephrocca]

Checklist

• 1. I have searched related issues but cannot get the expected help.
• 2. The bug has not been fixed in the latest version.

Describe the bug

I'm using /v1/completion endpoint, and if the first token begins with a space, it is incorrectly removed. The point of the completion endpoint is to be able to complete text, so we could send something like this to the model:

### Instruction:
Write a story

### Response:
Once upon a

Notice that we constrain the AI's output by forcing the AI to start its response with Once upon a. And for LMDeploy, the choices[0].text of the first message in the EventStream is time instead of time. The bug exists for streaming and non-streaming.

I've tested vLLM and TGI using the same AWQ model, and they both correctly return time.

Reproduction

Start server:

docker run -p 23333:23333 --gpus all --rm -it openmmlab/lmdeploy:v0.4.2 bash

lmdeploy serve api_server lmdeploy/llama2-chat-7b-w4 --model-name lmdeploy/llama2-chat-7b-w4

Send request "Once upon a":

await fetch("http://0.0.0.0:23333/v1/completions", {
  method: "POST",
  headers: { "Content-Type": "application/json" },
  body: JSON.stringify({
    model: "lmdeploy/llama2-chat-7b-w4",
    prompt: "Once upon a",
  }),
}).then(r => r.text());

It should generate an output that starts with time but instead it starts with time.

Note that the bug exists for all models Llama 2 models at least (maybe others - I have only tested Llama 2 models). I've tested multiple models, and ensured I was using the correct prompt template (unlike in this example where left out the special tokens/template, for simplicity).

Environment

Latest official Docker image: openmmlab/lmdeploy:v0.4.2

[josephrocca]

In case others are in need of a workaround here, a very hacky temporary fix is to find the token ids that start with a space - e.g. for Llama 2 they are:

token_ids_that_start_with_space = set([259,260,263,266,268,269,270,274,278,281,282,285,286,288,289,297,298,301,302,304,306,308,310,313,315,316,317,318,319,320,321,322,323,325,330,334,337,338,341,343,349,350,353,360,363,364,365,366,367,372,373,376,377,378,379,380,382,383,385,390,393,394,395,396,399,402,405,408,409,410,411,413,418,419,421,422,425,426,427,429,432,435,437,438,439,443,444,445,447,448,450,451,452,454,461,462,469,470,471,472,474,476,478,480,490,491,498,500,501,502,503,505,508,512,515,518,521,525,526,527,528,529,530,531,534,539,540,541,544,553,560,563,564,565,577,584,589,590,591,592,594,596,599,604,606,607,610,611,612,614,619,620,623,624,626,628,632,633,634,639,640,652,658,659,660,662,664,665,669,670,671,673,674,678,679,694,696,697,701,704,707,712,714,715,716,718,722,723,724,727,731,732,733,734,736,738,739,740,746,748,750,751,752,754,756,757,758,760,762,763,766,767,769,770,772,773,775,777,779,782,784,785,788,795,796,805,806,813,817,818,822,825,826,830,831,832,835,836,838,844,847,848,849,851,853,857,859,863,864,867,868,869,871,872,875,878,881,883,884,885,887,889,891,892,894,896,897,899,900,901,902,903,904,907,910,916,917,920,921,922,923,925,926,931,934,937,938,939,940,946,947,951,953,954,958,960,961,963,964,965,966,967,970,971,972,975,977,980,982,988,992,995,997,1002,1005,1006,1009,1010,1011,1014,1015,1016,1018,1019,1020,1021,1023,1024,1027,1029,1033,1034,1035,1040,1044,1045,1046,1047,1048,1051,1053,1055,1058,1059,1060,1063,1065,1067,1069,1072,1073,1074,1075,1077,1081,1083,1084,1085,1090,1094,1095,1097,1098,1101,1102,1104,1105,1106,1108,1109,1120,1121,1122,1126,1128,1134,1135,1136,1139,1142,1143,1146,1147,1149,1152,1153,1156,1158,1162,1163,1172,1174,1176,1178,1180,1183,1185,1186,1190,1192,1196,1197,1203,1205,1206,1207,1208,1209,1214,1222,1223,1224,1226,1232,1234,1235,1236,1238,1243,1244,1246,1248,1250,1258,1260,1261,1269,1273,1274,1275,1277,1281,1283,1284,1286,1291,1294,1298,1301,1302,1303,1304,1316,1317,1320,1321,1326,1334,1339,1342,1343,1345,1346,1347,1348,1350,1352,1353,1354,1361,1363,1364,1369,1370,1371,1373,1374,1375,1380,1383,1386,1391,1392,1394,1395,1399,1400,1401,1404,1405,1407,1409,1410,1411,1418,1422,1423,1424,1425,1426,1432,1434,1436,1437,1438,1439,1442,1444,1447,1449,1453,1459,1462,1465,1468,1471,1472,1473,1476,1480,1483,1487,1492,1494,1497,1506,1510,1513,1517,1518,1522,1528,1530,1532,1533,1538,1539,1543,1544,1546,1549,1550,1551,1554,1556,1559,1560,1561,1565,1568,1570,1571,1574,1577,1580,1583,1584,1586,1588,1589,1591,1592,1596,1597,1599,1601,1602,1603,1604,1605,1606,1612,1614,1616,1618,1619,1620,1622,1623,1629,1632,1634,1637,1638,1640,1641,1644,1650,1651,1652,1653,1661,1663,1667,1669,1670,1671,1677,1678,1681,1683,1685,1694,1695,1697,1700,1701,1702,1703,1704,1706,1708,1710,1712,1714,1716,1720,1721,1722,1723,1724,1728,1729,1732,1734,1735,1736,1737,1738,1739,1741,1746,1749,1750,1751,1752,1754,1757,1763,1766,1768,1770,1771,1773,1775,1776,1778,1780,1781,1784,1786,1787,1788,1790,1791,1795,1797,1798,1801,1804,1809,1811,1812,1813,1815,1816,1818,1819,1820,1824,1826,1827,1828,1831,1832,1833,1834,1835,1838,1840,1841,1842,1850,1852,1854,1855,1856,1857,1858,1861,1863,1865,1866,1869,1870,1871,1872,1873,1874,1876,1879,1880,1881,1886,1887,1889,1894,1895,1897,1898,1899,1900,1903,1904,1905,1906,1909,1913,1914,1919,1920,1921,1922,1923,1925,1931,1932,1933,1935,1936,1937,1938,1939,1944,1948,1950,1951,1952,1954,1957,1959,1962,1963,1967,1970,1976,1985,1986,1987,1993,1996,1998,1999,2000,2005,2009,2011,2012,2014,2020,2022,2023,2024,2025,2030,2032,2038,2041,2043,2044,2045,2046,2047,2048,2050,2056,2058,2060,2062,2066,2069,2070,2071,2077,2078,2081,2085,2086,2087,2088,2089,2090,2091,2094,2099,2102,2106,2107,2113,2114,2115,2116,2117,2123,2125,2128,2130,2134,2136,2138,2143,2145,2148,2149,2150,2155,2159,2160,2163,2166,2169,2171,2174,2175,2178,2179,2180,2181,2183,2184,2186,2188,2189,2191,2193,2195,2196,2198,2201,2203,2206,2210,2211,2215,2216,2217,2221,2224,2225,2228,2233,2240,2243,2244,2245,2246,2250,2253,2254,2257,2258,2259,2261,2263,2266,2268,2274,2278,2279,2280,2281,2282,2284,2286,2289,2292,2293,2294,2295,2296,2298,2299,2301,2302,2304,2305,2306,2307,2309,2313,2315,2316,2317,2318,2319,2320,2322,2323,2326,2329,2331,2334,2336,2337,2338,2342,2343,2346,2348,2351,2352,2355,2358,2360,2362,2367,2372,2373,2377,2379,2380,2381,2383,2391,2393,2394,2398,2399,2400,2401,2407,2411,2413,2414,2419,2420,2422,2424,2425,2427,2428,2431,2432,2436,2437,2439,2440,2441,2443,2444,2446,2448,2452,2453,2462,2465,2466,2471,2472,2473,2474,2479,2485,2489,2493,2498,2501,2504,2505,2507,2508,2511,2514,2515,2522,2524,2529,2531,2532,2533,2534,2535,2537,2538,2545,2551,2553,2560,2562,2563,2566,2567,2569,2578,2581,2582,2586,2591,2594,2595,2598,2599,2600,2601,2602,2604,2607,2609,2610,2613,2614,2615,2621,2623,2625,2626,2627,2629,2630,2635,2637,2643,2644,2645,2646,2648,2649,2652,2653,2654,2655,2656,2661,2664,2665,2669,2672,2675,2678,2684,2686,2688,2691,2693,2694,2698,2702,2703,2706,2712,2714,2715,2718,2721,2723,2726,2729,2730,2731,2734,2737,2739,2740,2743,2745,2748,2750,2752,2755,2756,2757,2758,2761,2767,2768,2769,2771,2773,2775,2777,2778,2779,2787,2788,2791,2793,2794,2796,2799,2802,2803,2804,2805,2808,2811,2812,2814,2819,2820,2821,2822,2823,2825,2826,2828,2832,2833,2834,2836,2840,2845,2846,2847,2852,2854,2858,2860,2861,2862,2864,2866,2867,2869,2874,2875,2880,2888,2889,2893,2894,2895,2896,2897,2898,2900,2902,2903,2906,2907,2908,2910,2912,2913,2916,2919,2920,2921,2923,2924,2927,2930,2931,2933,2939,2942,2943,2944,2947,2948,2949,2950,2958,2959,2961,2964,2967,2969,2970,2971,2973,2977,2978,2979,2980,2981,2982,2983,2984,2988,2989,2990,2991,2992,2994,2996,2998,2999,3001,3004,3005,3006,3008,3012,3013,3014,3017,3022,3023,3025,3030,3031,3033,3036,3037,3038,3041,3046,3050,3052,3053,3056,3058,3060,3061,3063,3064,3067,3070,3072,3077,3078,3079,3080,3081,3082,3086,3087,3088,3091,3093,3095,3099,3104,3105,3107,3109,3111,3113,3114,3115,3117,3118,3119,3122,3132,3133,3138,3139,3142,3143,3144,3147,3148,3151,3152,3153,3154,3158,3159,3160,3161,3164,3165,3168,3171,3172,3180,3181,3182,3183,3184,3185,3186,3189,3190,3191,3196,3201,3203,3209,3211,3212,3216,3218,3219,3229,3230,3233,3234,3236,3237,3239,3240,3244,3248,3251,3252,3255,3256,3261,3265,3268,3269,3271,3273,3275,3279,3282,3287,3288,3290,3291,3294,3295,3300,3303,3307,3309,3315,3323,3329,3330,3336,3337,3339,3340,3342,3344,3345,3347,3348,3349,3351,3353,3354,3355,3356,3362,3367,3370,3371,3374,3375,3380,3382,3384,3386,3387,3390,3394,3397,3402,3404,3405,3407,3408,3412,3413,3414,3415,3419,3420,3422,3423,3428,3430,3431,3435,3436,3438,3439,3440,3441,3443,3444,3446,3447,3448,3449,3450,3454,3455,3457,3458,3461,3462,3464,3467,3468,3472,3474,3477,3479,3480,3482,3483,3484,3485,3489,3490,3494,3495,3497,3500,3503,3507,3508,3509,3512,3513,3514,3515,3516,3517,3519,3520,3523,3526,3528,3529,3532,3533,3534,3536,3544,3546,3548,3550,3551,3553,3561,3564,3566,3572,3573,3574,3575,3576,3577,3578,3579,3581,3584,3585,3587,3588,3589,3593,3595,3599,3600,3602,3603,3604,3607,3611,3612,3614,3617,3618,3619,3620,3621,3622,3623,3625,3627,3630,3632,3633,3635,3638,3639,3641,3643,3645,3646,3649,3650,3651,3652,3653,3654,3655,3657,3659,3661,3662,3667,3669,3671,3672,3674,3677,3678,3681,3682,3683,3684,3685,3686,3691,3692,3693,3694,3695,3697,3699,3700,3701,3704,3705,3708,3710,3711,3713,3715,3716,3719,3720,3721,3724,3725,3731,3732,3734,3736,3737,3739,3740,3741,3743,3748,3750,3755,3756,3758,3760,3762,3763,3764,3765,3767,3769,3770,3771,3772,3773,3776,3777,3778,3785,3786,3787,3789,3792,3793,3796,3799,3800,3802,3803,3804,3805,3806,3807,3810,3812,3813,3814,3815,3817,3824,3826,3829,3830,3831,3833,3834,3836,3838,3839,3840,3841,3847,3852,3855,3856,3858,3861,3862,3863,3865,3866,3867,3869,3872,3876,3878,3879,3882,3883,3884,3887,3889,3894,3895,3896,3897,3900,3902,3907,3908,3911,3913,3917,3918,3920,3925,3926,3928,3929,3933,3935,3937,3938,3939,3940,3942,3948,3949,3951,3956,3957,3961,3963,3964,3965,3966,3967,3969,3971,3974,3975,3976,3978,3979,3980,3982,3983,3984,3985,3986,3987,3988,3989,3990,3992,3994,3996,3999,4001,4004,4005,4007,4010,4016,4017,4021,4022,4023,4024,4028,4029,4030,4031,4033,4036,4038,4041,4042,4045,4046,4047,4048,4049,4050,4052,4053,4055,4059,4060,4066,4067,4069,4071,4072,4073,4075,4076,4078,4079,4082,4083,4084,4086,4088,4091,4092,4093,4094,4095,4098,4100,4103,4104,4105,4107,4111,4113,4114,4116,4118,4119,4120,4121,4122,4123,4124,4128,4129,4133,4134,4137,4138,4139,4140,4145,4147,4148,4152,4153,4157,4158,4160,4163,4166,4168,4169,4171,4175,4177,4179,4180,4185,4186,4188,4191,4192,4195,4203,4206,4207,4208,4209,4213,4216,4218,4221,4223,4224,4225,4226,4228,4231,4232,4234,4235,4236,4239,4240,4241,4242,4248,4249,4250,4251,4256,4257,4259,4263,4265,4266,4269,4272,4274,4275,4280,4281,4284,4292,4296,4303,4306,4307,4309,4312,4313,4315,4318,4319,4320,4321,4322,4323,4325,4326,4327,4328,4329,4331,4332,4333,4335,4337,4340,4341,4342,4343,4344,4348,4354,4355,4356,4358,4359,4360,4363,4365,4367,4368,4370,4377,4380,4382,4383,4385,4386,4390,4392,4398,4402,4404,4406,4407,4408,4412,4413,4414,4417,4418,4423,4426,4432,4433,4434,4436,4438,4439,4441,4443,4444,4445,4446,4450,4451,4452,4454,4457,4459,4460,4461,4464,4465,4469,4472,4473,4475,4477,4480,4482,4485,4486,4489,4491,4493,4497,4500,4502,4503,4505,4508,4509,4511,4513,4514,4516,4517,4520,4522,4523,4525,4526,4527,4529,4531,4533,4538,4544,4546,4547,4549,4550,4552,4553,4554,4555,4556,4558,4559,4560,4562,4565,4567,4570,4573,4575,4576,4577,4581,4583,4586,4587,4588,4589,4593,4595,4596,4601,4602,4603,4606,4607,4608,4609,4610,4612,4613,4619,4623,4624,4625,4628,4629,4631,4634,4635,4636,4639,4642,4643,4644,4646,4648,4649,4651,4653,4654,4655,4656,4658,4660,4662,4663,4665,4667,4669,4670,4671,4673,4674,4677,4679,4682,4683,4685,4686,4687,4688,4689,4693,4694,4696,4697,4698,4699,4700,4701,4702,4706,4707,4709,4711,4712,4714,4719,4720,4721,4723,4724,4725,4726,4728,4731,4732,4733,4737,4740,4742,4744,4748,4750,4753,4755,4756,4759,4760,4761,4764,4765,4766,4767,4768,4770,4771,4772,4779,4780,4783,4784,4785,4786,4788,4792,4794,4795,4796,4797,4799,4800,4802,4803,4805,4808,4810,4811,4813,4815,4817,4818,4822,4823,4824,4825,4827,4828,4829,4831,4832,4833,4834,4837,4839,4840,4842,4843,4844,4845,4846,4847,4849,4852,4853,4856,4857,4860,4863,4864,4866,4867,4868,4870,4874,4875,4876,4879,4880,4883,4884,4886,4889,4890,4891,4892,4893,4902,4903,4908,4910,4911,4918,4922,4929,4930,4931,4932,4933,4934,4940,4942,4943,4944,4946,4947,4948,4949,4952,4953,4954,4955,4956,4957,4958,4959,4963,4964,4966,4967,4969,4970,4971,4972,4973,4974,4976,4978,4982,4988,4989,4991,4996,4997,5001,5004,5007,5009,5011,5012,5013,5016,5017,5018,5019,5020,5023,5024,5025,5027,5032,5034,5036,5039,5040,5043,5045,5046,5048,5050,5051,5052,5053,5054,5055,5057,5061,5065,5067,5068,5069,5073,5075,5076,5077,5078,5087,5088,5089,5092,5094,5096,5097,5099,5100,5101,5102,5104,5106,5107,5108,5110,5111,5112,5115,5119,5120,5121,5122,5123,5124,5125,5127,5129,5130,5131,5132,5133,5134,5135,5136,5139,5141,5142,5144,5146,5147,5148,5149,5151,5152,5153,5155,5157,5158,5159,5161,5162,5163,5164,5165,5166,5167,5169,5172,5174,5176,5177,5178,5181,5183,5186,5187,5188,5189,5190,5191,5192,5193,5195,5196,5198,5199,5201,5202,5204,5207,5208,5212,5214,5216,5217,5220,5221,5222,5224,5225,5226,5227,5229,5232,5233,5235,5236,5237,5238,5239,5240,5241,5243,5244,5245,5246,5247,5250,5251,5253,5254,5256,5257,5260,5263,5264,5266,5272,5273,5276,5277,5278,5279,5282,5285,5290,5291,5293,5294,5296,5297,5298,5300,5302,5304,5305,5306,5307,5310,5312,5314,5316,5318,5320,5321,5322,5324,5329,5330,5331,5332,5334,5335,5337,5339,5342,5343,5345,5347,5351,5352,5353,5354,5356,5360,5366,5368,5373,5374,5375,5376,5377,5381,5382,5383,5384,5386,5390,5394,5399,5400,5401,5406,5407,5408,5412,5413,5417,5418,5419,5424,5429,5430,5432,5434,5439,5440,5443,5445,5446,5447,5448,5449,5455,5456,5457,5459,5462,5466,5468,5469,5470,5473,5476,5478,5480,5482,5484,5486,5488,5490,5491,5492,5493,5496,5497,5500,5502,5503,5505,5511,5516,5517,5518,5519,5520,5522,5524,5528,5530,5532,5533,5534,5535,5536,5537,5538,5539,5541,5544,5545,5546,5549,5556,5557,5565,5566,5569,5571,5573,5578,5579,5583,5587,5591,5593,5595,5599,5602,5608,5609,5613,5614,5615,5619,5622,5624,5625,5626,5629,5633,5636,5637,5639,5641,5642,5643,5644,5645,5646,5648,5649,5650,5654,5655,5656,5660,5662,5663,5664,5665,5669,5670,5671,5674,5677,5678,5680,5681,5682,5683,5684,5685,5686,5687,5692,5694,5695,5697,5700,5701,5702,5703,5704,5706,5712,5713,5714,5716,5717,5718,5720,5722,5724,5725,5726,5728,5730,5731,5732,5733,5734,5735,5737,5739,5741,5742,5745,5748,5749,5751,5754,5757,5758,5759,5763,5764,5765,5766,5768,5769,5771,5772,5774,5775,5777,5778,5780,5782,5785,5786,5787,5791,5792,5796,5797,5798,5799,5802,5804,5806,5807,5808,5810,5811,5812,5814,5820,5821,5823,5825,5826,5827,5828,5829,5833,5835,5837,5839,5840,5844,5845,5846,5849,5852,5853,5855,5857,5858,5862,5864,5865,5866,5868,5870,5874,5875,5877,5879,5881,5882,5883,5884,5885,5886,5895,5898,5899,5900,5901,5902,5905,5906,5912,5913,5915,5917,5918,5920,5922,5923,5925,5928,5929,5930,5932,5934,5936,5937,5939,5941,5947,5948,5950,5951,5952,5953,5954,5957,5960,5962,5967,5969,5970,5972,5974,5976,5977,5978,5982,5984,5988,5993,5994,5995,5997,5998,5999,6000,6003,6005,6010,6012,6013,6015,6017,6019,6023,6024,6025,6029,6030,6031,6032,6033,6035,6036,6041,6042,6043,6044,6047,6049,6053,6054,6055,6056,6057,6058,6060,6061,6062,6063,6065,6068,6070,6077,6079,6081,6083,6084,6087,6088,6089,6091,6093,6094,6095,6097,6101,6105,6106,6107,6109,6111,6114,6118,6120,6121,6123,6124,6125,6126,6128,6130,6131,6133,6136,6137,6139,6140,6142,6143,6145,6148,6153,6155,6158,6159,6161,6162,6163,6164,6166,6167,6171,6175,6176,6178,6179,6182,6183,6189,6190,6192,6193,6196,6198,6199,6200,6204,6206,6209,6210,6211,6212,6213,6216,6217,6218,6219,6220,6221,6222,6225,6226,6228,6230,6232,6233,6237,6238,6242,6245,6251,6253,6254,6257,6258,6260,6261,6262,6263,6265,6266,6267,6273,6274,6276,6280,6281,6282,6283,6284,6285,6286,6287,6290,6291,6296,6297,6298,6299,6300,6303,6305,6306,6308,6309,6313,6314,6315,6316,6317,6319,6320,6323,6324,6325,6328,6331,6336,6337,6339,6340,6342,6343,6345,6346,6350,6351,6354,6355,6356,6361,6363,6364,6365,6366,6367,6368,6369,6371,6372,6374,6375,6376,6379,6380,6382,6385,6389,6397,6398,6401,6403,6407,6408,6410,6411,6412,6413,6414,6416,6417,6418,6421,6423,6425,6426,6427,6431,6432,6433,6434,6435,6437,6438,6439,6440,6441,6445,6446,6449,6450,6452,6454,6455,6456,6457,6458,6459,6460,6461,6462,6464,6467,6470,6471,6473,6474,6475,6476,6479,6480,6483,6492,6493,6494,6495,6496,6497,6498,6499,6501,6502,6503,6505,6507,6509,6511,6514,6515,6516,6517,6518,6520,6521,6523,6524,6527,6528,6529,6532,6534,6535,6536,6540,6546,6548,6549,6551,6554,6555,6556,6559,6560,6561,6562,6564,6567,6568,6569,6570,6571,6573,6575,6576,6577,6579,6580,6581,6583,6584,6586,6588,6589,6590,6592,6593,6597,6599,6600,6601,6602,6603,6606,6607,6608,6610,6611,6612,6613,6615,6623,6624,6625,6628,6629,6630,6631,6633,6634,6635,6639,6640,6641,6643,6645,6650,6651,6652,6655,6657,6659,6660,6662,6663,6664,6666,6667,6668,6673,6674,6675,6676,6679,6680,6681,6682,6683,6684,6686,6692,6694,6695,6697,6699,6700,6701,6702,6704,6706,6709,6712,6714,6715,6719,6721,6722,6723,6724,6725,6726,6728,6731,6732,6736,6738,6743,6745,6746,6749,6752,6754,6755,6756,6757,6760,6761,6763,6766,6769,6770,6771,6773,6775,6776,6780,6781,6782,6783,6784,6785,6787,6788,6789,6790,6791,6795,6796,6803,6804,6805,6806,6807,6808,6809,6810,6811,6813,6815,6819,6820,6826,6828,6829,6835,6836,6837,6838,6839,6841,6849,6850,6851,6852,6853,6855,6856,6858,6860,6862,6863,6864,6865,6866,6867,6868,6869,6870,6872,6873,6874,6876,6879,6881,6882,6885,6888,6890,6892,6893,6894,6896,6898,6900,6901,6907,6908,6909,6910,6911,6912,6919,6920,6923,6924,6927,6928,6931,6932,6934,6936,6938,6939,6940,6942,6943,6944,6952,6953,6956,6957,6958,6960,6961,6963,6964,6965,6966,6968,6969,6971,6973,6974,6975,6976,6977,6978,6981,6985,6987,6989,6991,6993,6996,6999,7001,7005,7006,7007,7013,7014,7015,7017,7019,7021,7023,7025,7027,7028,7029,7034,7035,7037,7038,7046,7047,7048,7049,7051,7053,7055,7057,7059,7062,7063,7064,7065,7067,7073,7074,7075,7079,7080,7082,7084,7087,7088,7089,7090,7091,7095,7096,7098,7101,7102,7103,7105,7106,7107,7109,7111,7112,7113,7115,7116,7117,7120,7123,7124,7126,7127,7128,7130,7132,7133,7134,7135,7136,7137,7138,7139,7140,7142,7145,7146,7148,7149,7150,7152,7155,7156,7159,7160,7162,7164,7167,7169,7171,7172,7174,7175,7178,7179,7180,7182,7186,7188,7189,7190,7191,7195,7197,7198,7199,7200,7203,7205,7206,7208,7209,7212,7213,7215,7216,7222,7223,7225,7227,7229,7232,7233,7234,7236,7242,7243,7245,7246,7248,7250,7251,7252,7254,7255,7256,7258,7259,7260,7265,7266,7269,7271,7272,7274,7275,7276,7280,7282,7284,7286,7287,7291,7292,7294,7296,7298,7300,7303,7304,7306,7307,7309,7311,7314,7315,7318,7319,7322,7325,7326,7329,7330,7331,7332,7333,7335,7336,7338,7339,7343,7344,7347,7348,7349,7351,7353,7356,7357,7359,7360,7361,7362,7363,7365,7370,7371,7372,7374,7375,7376,7378,7379,7380,7383,7385,7388,7389,7391,7392,7395,7396,7397,7398,7399,7400,7403,7404,7405,7407,7408,7412,7413,7415,7417,7418,7419,7421,7423,7424,7426,7429,7431,7432,7434,7436,7437,7438,7440,7441,7442,7444,7446,7448,7450,7452,7455,7456,7457,7458,7460,7462,7463,7465,7468,7470,7471,7472,7473,7475,7477,7480,7481,7482,7483,7484,7487,7488,7493,7494,7495,7498,7499,7500,7502,7505,7509,7510,7512,7513,7518,7519,7521,7522,7523,7525,7526,7527,7531,7533,7535,7536,7537,7539,7540,7542,7546,7548,7550,7551,7552,7553,7555,7556,7557,7559,7560,7561,7562,7563,7567,7568,7569,7571,7572,7573,7575,7578,7579,7580,7581,7587,7591,7592,7594,7595,7596,7599,7600,7601,7602,7603,7604,7605,7609,7613,7618,7619,7621,7622,7623,7624,7625,7628,7629,7631,7632,7633,7634,7636,7637,7639,7641,7646,7649,7651,7654,7655,7656,7657,7660,7663,7664,7666,7668,7669,7670,7672,7673,7676,7679,7683,7684,7687,7688,7689,7691,7693,7695,7696,7697,7699,7700,7702,7704,7705,7706,7709,7714,7718,7722,7725,7726,7732,7733,7736,7737,7738,7739,7740,7743,7744,7745,7747,7748,7750,7751,7752,7753,7755,7756,7758,7761,7762,7763,7764,7765,7766,7769,7770,7773,7774,7776,7777,7779,7780,7782,7783,7784,7786,7787,7788,7791,7793,7794,7795,7797,7800,7801,7802,7803,7805,7806,7809,7812,7813,7814,7817,7819,7821,7824,7825,7826,7828,7829,7831,7834,7835,7840,7841,7842,7845,7846,7847,7848,7849,7852,7853,7855,7857,7860,7861,7863,7865,7866,7867,7868,7870,7871,7874,7875,7876,7877,7878,7881,7882,7885,7890,7899,7901,7902,7903,7904,7905,7906,7907,7908,7910,7911,7913,7916,7917,7919,7923,7927,7928,7929,7930,7931,7933,7934,7935,7936,7942,7945,7946,7948,7952,7953,7954,7955,7956,7957,7960,7962,7963,7965,7968,7970,7972,7973,7975,7977,7980,7983,7984,7985,7987,7990,7991,7992,7993,7995,7996,7997,8002,8004,8005,8006,8007,8010,8011,8012,8014,8018,8019,8020,8022,8023,8024,8025,8026,8027,8031,8033,8034,8037,8038,8039,8040,8041,8042,8043,8045,8046,8047,8049,8051,8052,8053,8056,8059,8060,8061,8062,8063,8064,8067,8068,8072,8073,8074,8075,8078,8079,8080,8081,8082,8084,8086,8087,8090,8092,8093,8094,8095,8099,8102,8104,8108,8112,8114,8115,8116,8118,8119,8121,8125,8126,8128,8129,8130,8131,8133,8134,8135,8138,8142,8145,8147,8151,8152,8153,8155,8158,8161,8162,8164,8167,8168,8170,8171,8174,8175,8177,8178,8182,8183,8184,8188,8195,8196,8198,8201,8203,8206,8207,8210,8211,8213,8214,8215,8218,8220,8221,8224,8225,8227,8229,8230,8234,8236,8237,8239,8242,8248,8249,8251,8252,8258,8260,8261,8265,8267,8271,8273,8275,8277,8278,8280,8281,8282,8283,8286,8287,8288,8289,8291,8292,8293,8294,8296,8297,8300,8301,8303,8304,8307,8310,8313,8314,8316,8317,8320,8321,8323,8324,8327,8329,8334,8335,8338,8340,8341,8343,8344,8347,8348,8350,8351,8354,8359,8360,8363,8364,8365,8367,8368,8369,8370,8371,8372,8373,8378,8379,8380,8383,8386,8388,8389,8390,8393,8396,8398,8401,8402,8405,8406,8407,8408,8409,8410,8413,8414,8416,8421,8422,8424,8425,8427,8429,8430,8432,8433,8436,8437,8440,8441,8442,8444,8445,8446,8448,8449,8450,8451,8453,8454,8455,8457,8459,8460,8461,8465,8466,8467,8468,8469,8470,8471,8472,8473,8474,8475,8478,8481,8482,8483,8486,8487,8490,8492,8494,8496,8500,8502,8503,8506,8507,8509,8512,8515,8518,8519,8521,8524,8525,8526,8527,8528,8529,8531,8532,8533,8534,8536,8540,8541,8542,8543,8544,8545,8548,8550,8554,8556,8557,8560,8561,8562,8564,8565,8569,8570,8571,8572,8573,8574,8575,8576,8578,8579,8580,8581,8583,8585,8589,8591,8594,8595,8597,8598,8599,8600,8601,8602,8604,8607,8608,8611,8612,8615,8616,8617,8619,8620,8622,8626,8629,8630,8632,8633,8635,8636,8638,8640,8642,8644,8646,8648,8649,8651,8653,8656,8660,8661,8662,8665,8666,8669,8671,8672,8674,8676,8677,8679,8680,8681,8682,8686,8688,8689,8691,8692,8693,8694,8695,8699,8701,8702,8703,8707,8709,8713,8714,8716,8717,8718,8720,8721,8722,8724,8725,8727,8731,8735,8736,8740,8741,8742,8743,8744,8745,8746,8748,8750,8753,8756,8759,8760,8761,8762,8763,8764,8772,8774,8775,8778,8780,8781,8783,8786,8788,8790,8792,8793,8794,8795,8796,8797,8799,8804,8805,8806,8811,8812,8814,8815,8816,8818,8820,8823,8825,8826,8828,8829,8830,8831,8833,8836,8838,8839,8843,8845,8847,8852,8853,8855,8856,8857,8858,8859,8861,8866,8867,8868,8869,8870,8871,8872,8877,8878,8879,8880,8881,8882,8886,8889,8891,8892,8898,8900,8901,8905,8906,8907,8908,8911,8912,8913,8914,8918,8919,8920,8922,8928,8930,8933,8935,8936,8937,8938,8939,8943,8950,8951,8952,8954,8955,8956,8957,8959,8960,8965,8967,8970,8972,8973,8974,8976,8978,8980,8981,8982,8984,8986,8988,8989,8991,8992,8996,8997,8998,9000,9002,9004,9007,9008,9013,9014,9015,9016,9017,9019,9023,9024,9025,9027,9028,9031,9032,9033,9034,9036,9038,9041,9042,9045,9049,9050,9051,9055,9056,9060,9063,9066,9068,9070,9071,9073,9074,9076,9078,9079,9080,9082,9083,9087,9088,9090,9091,9098,9101,9104,9105,9108,9109,9110,9111,9115,9116,9117,9119,9120,9121,9122,9123,9124,9126,9127,9128,9129,9132,9133,9134,9138,9141,9143,9145,9146,9148,9149,9150,9151,9156,9159,9160,9162,9164,9167,9172,9173,9174,9177,9178,9179,9180,9181,9184,9185,9186,9189,9193,9194,9196,9199,9200,9201,9204,9205,9206,9208,9209,9210,9211,9212,9213,9218,9220,9221,9224,9225,9226,9227,9228,9232,9234,9235,9236,9237,9238,9241,9242,9243,9245,9248,9249,9250,9251,9253,9254,9257,9259,9261,9262,9263,9266,9267,9269,9272,9273,9275,9277,9279,9280,9281,9282,9284,9285,9286,9287,9291,9293,9299,9300,9301,9305,9307,9308,9310,9311,9316,9317,9320,9321,9322,9324,9326,9327,9328,9330,9332,9333,9335,9336,9338,9343,9348,9349,9350,9352,9353,9355,9358,9360,9362,9364,9365,9366,9367,9368,9369,9370,9371,9372,9376,9377,9378,9379,9380,9385,9388,9391,9399,9400,9401,9405,9406,9408,9410,9411,9412,9413,9414,9416,9417,9418,9419,9423,9425,9426,9427,9428,9432,9433,9434,9436,9437,9439,9443,9444,9445,9448,9449,9451,9452,9453,9455,9459,9460,9461,9463,9467,9471,9475,9476,9478,9479,9481,9483,9484,9487,9488,9489,9491,9493,9495,9500,9501,9503,9505,9506,9508,9511,9512,9515,9521,9522,9523,9528,9529,9531,9535,9537,9538,9540,9541,9542,9543,9545,9546,9548,9550,9551,9554,9556,9557,9558,9559,9560,9561,9562,9563,9565,9566,9570,9576,9577,9579,9580,9581,9582,9583,9586,9587,9589,9590,9591,9595,9596,9597,9602,9603,9604,9607,9608,9609,9612,9613,9615,9619,9620,9622,9623,9624,9626,9628,9630,9631,9635,9636,9637,9638,9640,9642,9644,9646,9647,9648,9649,9651,9654,9655,9656,9657,9659,9660,9664,9665,9667,9668,9669,9670,9673,9674,9677,9678,9679,9681,9682,9683,9685,9686,9687,9690,9691,9697,9698,9699,9701,9702,9703,9704,9705,9707,9709,9712,9717,9719,9720,9723,9724,9725,9726,9727,9728,9731,9732,9734,9736,9741,9742,9744,9746,9747,9750,9752,9753,9755,9757,9758,9762,9763,9764,9766,9768,9769,9771,9773,9775,9779,9788,9790,9791,9792,9793,9796,9798,9801,9805,9807,9809,9810,9811,9814,9815,9817,9819,9820,9821,9825,9826,9827,9828,9830,9831,9833,9834,9836,9839,9846,9848,9849,9850,9853,9856,9859,9862,9863,9865,9866,9867,9869,9870,9871,9872,9873,9875,9878,9879,9881,9883,9885,9886,9887,9892,9897,9899,9900,9901,9904,9905,9906,9909,9911,9913,9914,9920,9922,9923,9924,9925,9926,9927,9932,9935,9937,9939,9941,9942,9943,9946,9949,9950,9953,9954,9955,9956,9958,9959,9960,9962,9963,9964,9969,9971,9973,9976,9978,9982,9985,9987,9991,9995,9999,10004,10005,10007,10008,10009,10012,10013,10014,10015,10016,10017,10018,10019,10021,10022,10023,10026,10029,10032,10033,10034,10035,10038,10039,10040,10042,10043,10049,10050,10053,10056,10057,10059,10061,10067,10073,10075,10076,10078,10079,10081,10082,10083,10087,10088,10089,10090,10092,10097,10098,10099,10103,10104,10105,10106,10107,10110,10111,10112,10113,10115,10116,10117,10121,10122,10124,10127,10128,10130,10133,10134,10135,10136,10138,10143,10144,10146,10150,10151,10152,10153,10155,10156,10158,10159,10160,10161,10163,10166,10167,10168,10169,10171,10173,10174,10180,10182,10186,10188,10191,10193,10195,10197,10200,10201,10203,10205,10208,10210,10211,10212,10213,10215,10216,10217,10218,10219,10223,10224,10225,10227,10228,10229,10230,10231,10235,10239,10240,10241,10244,10245,10247,10248,10252,10253,10255,10256,10257,10258,10259,10261,10263,10266,10267,10269,10272,10273,10275,10276,10277,10279,10282,10283,10284,10288,10290,10292,10293,10294,10295,10296,10297,10298,10306,10307,10309,10311,10315,10316,10317,10318,10319,10320,10321,10322,10324,10325,10329,10331,10332,10338,10340,10341,10342,10343,10345,10346,10347,10348,10350,10352,10353,10354,10355,10357,10359,10361,10362,10364,10365,10366,10368,10369,10371,10372,10375,10377,10379,10383,10387,10393,10395,10397,10398,10400,10402,10404,10405,10406,10409,10410,10413,10415,10416,10417,10418,10419,10420,10421,10422,10423,10425,10426,10428,10429,10430,10431,10432,10433,10434,10435,10437,10439,10440,10441,10442,10443,10445,10446,10447,10450,10451,10452,10453,10458,10459,10462,10464,10465,10466,10468,10469,10470,10476,10477,10478,10480,10481,10483,10484,10487,10488,10489,10494,10502,10503,10504,10505,10506,10508,10509,10513,10515,10516,10517,10518,10522,10523,10524,10528,10529,10534,10535,10537,10538,10539,10541,10542,10545,10548,10550,10551,10554,10555,10557,10558,10559,10561,10563,10564,10565,10567,10569,10570,10571,10575,10576,10579,10580,10583,10584,10585,10586,10589,10591,10592,10594,10595,10596,10597,10600,10603,10604,10606,10608,10609,10613,10614,10615,10616,10618,10619,10621,10623,10624,10625,10626,10627,10628,10629,10630,10631,10632,10634,10635,10636,10637,10638,10640,10641,10642,10643,10645,10650,10655,10656,10657,10658,10659,10663,10664,10667,10668,10670,10671,10672,10674,10675,10676,10677,10679,10680,10682,10683,10684,10686,10688,10689,10692,10693,10694,10695,10696,10697,10698,10701,10703,10705,10707,10708,10710,10711,10712,10713,10714,10715,10719,10720,10722,10723,10726,10727,10728,10729,10731,10733,10734,10741,10742,10744,10747,10748,10750,10751,10752,10753,10754,10755,10756,10757,10760,10761,10762,10765,10766,10767,10768,10769,10771,10772,10775,10776,10777,10781,10782,10783,10784,10785,10787,10788,10790,10791,10793,10801,10802,10803,10804,10805,10808,10809,10811,10812,10813,10814,10815,10816,10819,10821,10822,10823,10824,10825,10828,10829,10830,10831,10832,10833,10837,10838,10839,10841,10842,10843,10845,10847,10849,10850,10852,10854,10856,10860,10863,10864,10865,10866,10868,10871,10872,10875,10876,10878,10879,10882,10884,10886,10887,10888,10890,10891,10894,10895,10897,10898,10899,10901,10902,10906,10907,10908,10911,10914,10915,10916,10917,10918,10919,10920,10924,10926,10927,10928,10929,10930,10932,10933,10937,10938,10940,10943,10944,10949,10951,10952,10953,10955,10959,10961,10966,10968,10969,10970,10972,10974,10975,10976,10977,10979,10980,10981,10982,10984,10985,10986,10987,10988,10990,10992,10995,10996,10999,11000,11001,11004,11005,11006,11009,11012,11013,11015,11016,11018,11019,11020,11021,11025,11028,11029,11032,11033,11034,11039,11043,11044,11045,11046,11050,11051,11053,11056,11060,11061,11062,11063,11066,11069,11070,11071,11073,11075,11076,11077,11080,11084,11086,11090,11091,11092,11094,11095,11097,11098,11099,11100,11101,11103,11104,11105,11107,11109,11111,11112,11113,11114,11117,11118,11119,11122,11126,11127,11131,11132,11133,11134,11137,11138,11141,11143,11148,11149,11151,11155,11157,11158,11159,11161,11162,11164,11166,11169,11170,11171,11172,11174,11176,11179,11180,11181,11182,11183,11185,11187,11188,11189,11190,11192,11193,11196,11198,11199,11200,11201,11202,11203,11205,11208,11210,11211,11212,11213,11215,11217,11220,11221,11223,11229,11230,11231,11232,11233,11239,11240,11243,11244,11247,11252,11254,11258,11260,11261,11262,11263,11264,11265,11266,11270,11273,11274,11275,11278,11281,11286,11289,11293,11297,11299,11301,11302,11304,11305,11306,11307,11308,11312,11313,11314,11315,11317,11319,11322,11323,11324,11325,11328,11329,11334,11336,11339,11340,11343,11346,11352,11354,11359,11361,11364,11365,11366,11367,11368,11369,11374,11378,11379,11380,11382,11386,11387,11388,11389,11390,11391,11393,11394,11395,11397,11398,11399,11400,11401,11402,11404,11405,11406,11408,11409,11412,11413,11415,11417,11418,11420,11421,11423,11424,11425,11429,11430,11431,11437,11438,11443,11444,11446,11447,11448,11449,11450,11451,11453,11454,11455,11456,11459,11460,11462,11463,11465,11467,11468,11469,11470,11471,11472,11473,11474,11475,11478,11479,11480,11482,11483,11484,11486,11488,11492,11493,11498,11502,11504,11509,11510,11511,11515,11518,11520,11524,11525,11527,11529,11531,11532,11533,11534,11535,11539,11543,11544,11545,11546,11547,11549,11551,11552,11553,11554,11557,11558,11559,11561,11562,11563,11564,11565,11566,11568,11570,11571,11573,11575,11580,11581,11582,11583,11584,11585,11587,11588,11589,11592,11593,11594,11595,11597,11598,11599,11605,11608,11610,11611,11612,11613,11619,11621,11623,11624,11628,11629,11630,11633,11635,11636,11637,11638,11640,11643,11644,11646,11647,11648,11649,11650,11652,11653,11654,11655,11657,11658,11660,11661,11662,11663,11664,11668,11672,11677,11678,11679,11680,11681,11682,11683,11684,11688,11694,11695,11698,11699,11701,11705,11706,11708,11711,11712,11714,11715,11717,11719,11720,11721,11722,11723,11731,11732,11733,11735,11736,11738,11740,11743,11747,11748,11749,11751,11755,11756,11757,11758,11761,11764,11765,11769,11772,11773,11774,11775,11777,11779,11780,11781,11782,11783,11784,11785,11786,11788,11790,11791,11792,11796,11797,11798,11799,11801,11803,11805,11806,11807,11809,11810,11812,11813,11814,11815,11817,11819,11821,11822,11823,11824,11825,11826,11827,11828,11829,11830,11833,11834,11835,11837,11839,11840,11842,11844,11845,11846,11847,11848,11849,11855,11856,11858,11859,11860,11865,11870,11871,11872,11873,11874,11875,11876,11878,11879,11880,11883,11886,11888,11890,11892,11893,11894,11896,11898,11899,11901,11902,11904,11905,11906,11909,11910,11914,11915,11916,11917,11919,11920,11923,11924,11926,11928,11929,11931,11934,11935,11938,11939,11942,11943,11946,11948,11949,11951,11952,11955,11959,11961,11962,11963,11966,11968,11969,11970,11971,11972,11975,11976,11977,11978,11979,11981,11982,11984,11985,11986,11988,11990,11994,11995,11996,11998,11999,12000,12001,12002,12003,12004,12005,12006,12009,12010,12012,12013,12016,12017,12019,12020,12021,12022,12023,12026,12027,12028,12029,12030,12032,12033,12034,12036,12037,12039,12041,12042,12043,12045,12046,12047,12048,12049,12051,12052,12057,12059,12060,12061,12065,12066,12067,12069,12070,12074,12077,12078,12080,12081,12082,12084,12086,12088,12089,12091,12092,12093,12098,12101,12103,12104,12105,12106,12108,12109,12110,12111,12113,12115,12118,12124,12125,12126,12127,12128,12129,12131,12132,12134,12136,12138,12139,12140,12141,12142,12145,12146,12149,12151,12152,12155,12157,12158,12159,12162,12164,12166,12167,12169,12173,12176,12178,12179,12180,12183,12185,12186,12187,12196,12200,12201,12203,12205,12206,12208,12209,12211,12212,12214,12216,12217,12218,12219,12220,12221,12224,12225,12226,12227,12228,12230,12231,12233,12234,12235,12237,12238,12241,12242,12243,12244,12245,12246,12247,12249,12250,12251,12252,12255,12264,12265,12266,12267,12270,12271,12272,12273,12278,12279,12280,12281,12286,12287,12289,12291,12294,12297,12298,12299,12301,12302,12303,12305,12306,12307,12309,12311,12312,12314,12315,12317,12318,12319,12320,12321,12325,12326,12327,12331,12335,12337,12338,12340,12341,12342,12345,12349,12351,12354,12355,12359,12362,12363,12365,12367,12368,12369,12370,12372,12374,12377,12379,12380,12381,12383,12384,12386,12388,12389,12390,12391,12397,12399,12400,12402,12406,12407,12408,12409,12411,12417,12420,12421,12422,12423,12424,12428,12430,12433,12435,12437,12438,12439,12440,12441,12442,12444,12447,12448,12450,12452,12453,12455,12456,12457,12458,12459,12461,12462,12463,12464,12466,12467,12468,12469,12471,12474,12475,12476,12477,12479,12480,12481,12482,12485,12487,12488,12489,12490,12493,12494,12497,12500,12501,12502,12503,12505,12507,12509,12511,12512,12515,12516,12517,12518,12519,12520,12522,12524,12525,12526,12527,12528,12529,12530,12534,12536,12537,12538,12540,12541,12544,12545,12546,12547,12549,12550,12551,12553,12555,12558,12560,12561,12563,12564,12565,12566,12567,12568,12569,12570,12573,12577,12579,12580,12583,12584,12585,12586,12589,12590,12591,12592,12594,12595,12599,12601,12603,12604,12606,12607,12608,12610,12611,12612,12615,12616,12618,12623,12624,12625,12626,12630,12633,12634,12635,12639,12640,12641,12642,12646,12647,12651,12655,12656,12658,12660,12662,12666,12668,12670,12672,12677,12678,12680,12684,12688,12689,12693,12694,12695,12699,12700,12704,12705,12707,12708,12709,12710,12713,12714,12718,12720,12721,12722,12723,12725,12726,12727,12728,12729,12730,12736,12738,12740,12741,12745,12747,12749,12753,12755,12758,12760,12762,12766,12767,12768,12770,12773,12777,12778,12780,12781,12782,12783,12784,12785,12786,12788,12789,12790,12793,12795,12796,12797,12798,12799,12801,12802,12804,12807,12808,12812,12813,12814,12815,12816,12819,12821,12823,12824,12826,12827,12828,12829,12830,12831,12833,12834,12835,12837,12838,12842,12843,12844,12845,12848,12849,12850,12852,12853,12855,12856,12862,12865,12866,12868,12871,12874,12875,12876,12878,12879,12884,12885,12886,12887,12891,12892,12893,12894,12895,12899,12900,12902,12904,12905,12909,12912,12915,12917,12919,12920,12923,12926,12929,12930,12931,12934,12936,12939,12940,12941,12942,12944,12945,12946,12949,12950,12951,12952,12953,12954,12955,12956,12959,12960,12962,12965,12967,12968,12969,12970,12971,12976,12977,12978,12979,12983,12986,12987,12988,12990,12991,12992,12994,12995,12997,12998,12999,13001,13003,13004,13005,13006,13008,13013,13014,13015,13016,13019,13023,13024,13030,13031,13033,13034,13035,13037,13038,13040,13041,13042,13047,13049,13051,13052,13055,13056,13059,13061,13062,13064,13066,13068,13069,13070,13071,13074,13078,13081,13085,13088,13089,13091,13093,13100,13101,13102,13103,13104,13105,13106,13107,13108,13109,13110,13112,13113,13114,13121,13122,13124,13125,13126,13127,13128,13132,13133,13135,13136,13137,13138,13142,13143,13144,13146,13149,13151,13153,13154,13156,13159,13160,13162,13164,13166,13172,13173,13175,13179,13180,13181,13182,13184,13185,13187,13189,13195,13201,13202,13205,13206,13209,13211,13212,13213,13214,13215,13216,13218,13219,13220,13222,13223,13224,13225,13226,13227,13229,13230,13232,13235,13240,13243,13246,13249,13250,13252,13253,13254,13258,13259,13260,13261,13263,13265,13266,13267,13268,13271,13272,13275,13276,13277,13279,13280,13283,13284,13285,13286,13290,13291,13293,13294,13298,13299,13301,13302,13303,13304,13306,13307,13310,13312,13315,13316,13319,13320,13324,13327,13328,13329,13330,13331,13332,13333,13336,13337,13340,13341,13343,13345,13348,13349,13350,13351,13352,13354,13355,13358,13360,13361,13362,13368,13370,13373,13374,13377,13378,13380,13382,13384,13386,13387,13388,13389,13391,13392,13394,13395,13397,13402,13406,13407,13408,13412,13413,13414,13417,13420,13421,13422,13423,13426,13430,13432,13433,13435,13436,13439,13442,13444,13446,13449,13450,13451,13452,13455,13456,13457,13458,13460,13461,13465,13466,13472,13473,13474,13475,13476,13477,13482,13483,13484,13485,13486,13487,13488,13489,13490,13491,13494,13497,13499,13500,13501,13502,13503,13511,13512,13515,13516,13521,13522,13524,13526,13527,13528,13530,13534,13540,13542,13543,13545,13547,13548,13552,13553,13557,13559,13560,13563,13564,13568,13569,13570,13572,13575,13577,13582,13585,13586,13587,13588,13589,13590,13592,13594,13597,13598,13600,13601,13602,13607,13610,13611,13612,13615,13616,13617,13618,13619,13620,13622,13623,13625,13626,13627,13630,13631,13632,13633,13638,13641,13642,13644,13645,13649,13652,13654,13656,13659,13661,13663,13665,13669,13672,13673,13674,13675,13676,13677,13679,13680,13681,13682,13686,13689,13693,13694,13698,13700,13701,13702,13704,13705,13706,13708,13709,13710,13714,13718,13721,13722,13725,13726,13727,13728,13729,13730,13731,13733,13734,13736,13737,13739,13740,13741,13742,13743,13745,13746,13747,13748,13749,13750,13751,13752,13754,13755,13756,13758,13760,13761,13763,13764,13765,13766,13767,13768,13769,13771,13772,13773,13774,13777,13781,13783,13784,13786,13787,13790,13791,13792,13793,13797,13798,13803,13806,13807,13810,13811,13812,13813,13814,13815,13817,13818,13819,13822,13824,13825,13830,13831,13832,13834,13838,13840,13843,13848,13849,13850,13851,13852,13853,13855,13856,13858,13859,13860,13861,13862,13863,13864,13866,13867,13870,13872,13874,13877,13878,13879,13880,13882,13883,13886,13888,13889,13890,13893,13894,13896,13897,13898,13899,13900,13901,13905,13907,13911,13912,13913,13914,13915,13916,13917,13918,13920,13923,13924,13925,13926,13927,13928,13930,13931,13932,13933,13934,13935,13936,13939,13940,13942,13943,13944,13945,13947,13949,13950,13952,13955,13957,13958,13959,13960,13962,13963,13964,13965,13966,13968,13969,13973,13976,13977,13978,13979,13981,13982,13986,13987,13988,13993,13994,13995,13997,13999,14000,14002,14007,14008,14009,14010,14012,14013,14014,14015,14019,14020,14021,14024,14025,14028,14031,14033,14034,14038,14040,14041,14049,14050,14051,14053,14055,14059,14060,14061,14062,14064,14070,14071,14072,14074,14077,14079,14088,14089,14092,14097,14099,14100,14102,14104,14106,14109,14110,14111,14113,14115,14117,14120,14121,14122,14123,14124,14127,14129,14134,14137,14140,14141,14152,14154,14156,14157,14159,14160,14161,14163,14164,14165,14169,14171,14172,14173,14175,14176,14177,14179,14180,14183,14184,14187,14188,14189,14192,14195,14197,14198,14200,14202,14204,14205,14209,14210,14211,14212,14213,14215,14216,14217,14218,14219,14221,14222,14223,14225,14227,14230,14231,14233,14234,14235,14238,14240,14241,14243,14244,14245,14249,14250,14251,14253,14255,14257,14259,14260,14261,14262,14263,14264,14265,14267,14269,14270,14271,14276,14277,14278,14279,14280,14281,14282,14283,14284,14288,14291,14292,14293,14294,14295,14296,14297,14298,14299,14302,14303,14304,14305,14307,14309,14310,14311,14312,14313,14314,14317,14319,14320,14321,14322,14323,14325,14326,14328,14329,14330,14332,14333,14334,14335,14336,14338,14341,14342,14344,14347,14348,14350,14351,14354,14355,14363,14364,14367,14368,14371,14372,14374,14376,14377,14378,14379,14382,14383,14385,14387,14390,14391,14393,14396,14397,14401,14402,14403,14405,14406,14407,14409,14412,14413,14414,14415,14416,14418,14419,14422,14423,14425,14426,14427,14428,14429,14430,14431,14432,14433,14434,14435,14436,14439,14440,14445,14446,14447,14450,14451,14452,14453,14455,14457,14458,14461,14464,14467,14468,14472,14475,14476,14477,14478,14482,14488,14490,14491,14492,14495,14496,14497,14499,14500,14501,14502,14503,14505,14507,14509,14511,14512,14514,14515,14517,14519,14521,14523,14525,14528,14529,14530,14533,14534,14539,14542,14543,14544,14546,14547,14548,14550,14552,14557,14558,14560,14562,14563,14566,14567,14568,14570,14574,14575,14576,14578,14580,14581,14582,14583,14585,14586,14589,14591,14595,14597,14598,14601,14602,14603,14604,14610,14612,14614,14615,14616,14617,14619,14621,14622,14624,14629,14631,14635,14636,14637,14638,14639,14645,14646,14647,14649,14650,14652,14653,14655,14656,14657,14660,14661,14662,14666,14667,14670,14671,14673,14675,14677,14678,14679,14680,14681,14682,14686,14687,14690,14691,14692,14693,14696,14698,14700,14704,14705,14706,14707,14709,14710,14711,14712,14713,14714,14715,14717,14718,14720,14721,14724,14725,14726,14728,14729,14731,14733,14734,14735,14737,14738,14741,14743,14744,14746,14750,14751,14752,14753,14756,14757,14758,14761,14765,14767,14768,14770,14771,14775,14781,14783,14784,14787,14788,14792,14794,14795,14796,14798,14801,14802,14806,14808,14809,14813,14818,14821,14823,14825,14826,14827,14828,14831,14832,14835,14837,14839,14841,14842,14845,14846,14847,14848,14852,14853,14854,14855,14857,14858,14859,14861,14864,14865,14866,14869,14870,14871,14872,14874,14875,14877,14879,14880,14881,14882,14883,14884,14887,14888,14890,14891,14892,14893,14896,14897,14898,14902,14904,14905,14908,14909,14911,14913,14914,14915,14919,14920,14921,14922,14923,14924,14926,14928,14929,14931,14933,14935,14937,14938,14942,14944,14945,14946,14950,14951,14953,14954,14955,14956,14957,14960,14961,14962,14964,14965,14966,14970,14971,14973,14974,14976,14978,14979,14982,14983,14984,14985,14988,14990,14993,14998,15000,15001,15002,15004,15006,15007,15010,15011,15012,15014,15015,15016,15017,15018,15020,15021,15022,15023,15025,15027,15028,15029,15030,15031,15034,15037,15038,15040,15041,15043,15045,15046,15047,15049,15050,15051,15053,15055,15056,15057,15058,15059,15061,15062,15065,15066,15068,15069,15072,15074,15075,15076,15087,15089,15090,15093,15096,15098,15100,15101,15103,15106,15111,15113,15115,15116,15117,15121,15125,15128,15129,15130,15131,15134,15141,15142,15143,15144,15145,15146,15147,15148,15149,15150,15151,15153,15154,15155,15158,15159,15160,15162,15163,15169,15170,15171,15174,15175,15178,15179,15180,15181,15182,15183,15185,15186,15187,15188,15191,15192,15194,15195,15196,15197,15198,15199,15200,15201,15202,15205,15207,15210,15212,15215,15217,15220,15221,15222,15223,15225,15226,15228,15230,15232,15233,15234,15236,15237,15239,15240,15241,15242,15243,15245,15246,15247,15248,15251,15252,15253,15254,15256,15258,15259,15261,15262,15265,15267,15268,15270,15271,15276,15278,15279,15281,15283,15284,15285,15286,15288,15293,15294,15295,15296,15299,15300,15301,15302,15303,15304,15305,15306,15308,15309,15310,15311,15312,15313,15315,15316,15317,15318,15319,15326,15327,15331,15332,15336,15337,15338,15341,15345,15347,15350,15351,15352,15354,15355,15358,15359,15365,15366,15367,15371,15373,15376,15377,15378,15381,15382,15385,15390,15393,15397,15399,15400,15401,15402,15405,15407,15408,15409,15411,15412,15413,15414,15416,15419,15422,15426,15428,15430,15431,15433,15434,15435,15442,15443,15446,15447,15448,15453,15454,15455,15456,15460,15463,15465,15468,15469,15472,15473,15474,15476,15477,15478,15481,15482,15483,15484,15486,15489,15492,15493,15496,15497,15498,15499,15500,15502,15504,15505,15509,15511,15512,15515,15516,15517,15518,15521,15522,15523,15525,15526,15528,15531,15533,15534,15536,15538,15540,15542,15544,15545,15548,15549,15552,15553,15557,15558,15560,15561,15562,15567,15568,15569,15570,15571,15572,15573,15574,15576,15577,15579,15582,15584,15585,15586,15587,15588,15589,15590,15591,15592,15593,15594,15595,15599,15600,15602,15605,15606,15610,15611,15612,15613,15615,15617,15620,15621,15624,15626,15629,15630,15636,15639,15640,15642,15643,15645,15648,15649,15650,15651,15652,15655,15658,15659,15661,15662,15665,15668,15671,15672,15673,15674,15676,15678,15680,15681,15682,15683,15685,15687,15688,15690,15691,15694,15696,15698,15699,15703,15706,15707,15709,15710,15712,15717,15718,15720,15721,15722,15723,15724,15725,15727,15729,15731,15732,15733,15739,15740,15741,15743,15744,15745,15747,15751,15754,15756,15758,15759,15761,15763,15772,15774,15777,15779,15780,15781,15782,15783,15785,15786,15787,15793,15795,15796,15798,15799,15800,15804,15808,15811,15821,15822,15823,15824,15825,15829,15830,15832,15833,15834,15835,15837,15839,15842,15846,15847,15848,15849,15850,15853,15854,15855,15856,15857,15859,15861,15862,15864,15867,15869,15871,15872,15873,15874,15875,15876,15877,15878,15880,15882,15883,15885,15886,15887,15888,15889,15891,15893,15894,15895,15897,15898,15899,15904,15905,15908,15910,15911,15913,15915,15918,15919,15921,15923,15924,15925,15927,15928,15929,15935,15937,15939,15940,15944,15946,15949,15950,15957,15958,15960,15963,15964,15967,15968,15969,15971,15974,15976,15977,15978,15979,15980,15981,15982,15983,15984,15985,15990,15991,15992,15993,15996,15997,15998,15999,16000,16003,16005,16008,16010,16012,16014,16018,16019,16020,16021,16025,16028,16030,16032,16034,16035,16038,16042,16045,16049,16050,16051,16052,16053,16054,16058,16060,16064,16067,16069,16071,16073,16075,16077,16078,16079,16080,16081,16082,16083,16085,16087,16088,16089,16092,16096,16101,16104,16106,16108,16110,16111,16112,16114,16116,16117,16119,16120,16124,16125,16126,16127,16131,16133,16134,16140,16144,16146,16147,16148,16150,16151,16154,16155,16156,16157,16158,16160,16161,16162,16165,16167,16169,16171,16172,16177,16178,16180,16184,16185,16186,16187,16188,16189,16193,16194,16197,16198,16199,16200,16201,16204,16205,16206,16208,16209,16210,16212,16216,16218,16219,16221,16222,16223,16224,16225,16226,16229,16230,16231,16232,16235,16236,16238,16245,16246,16247,16248,16250,16251,16253,16254,16255,16256,16257,16258,16259,16262,16263,16267,16269,16273,16274,16275,16277,16278,16280,16281,16283,16285,16286,16287,16289,16291,16294,16295,16296,16297,16298,16303,16306,16308,16312,16313,16314,16316,16317,16318,16319,16321,16322,16324,16326,16330,16331,16332,16333,16335,16336,16338,16339,16340,16342,16345,16346,16350,16351,16353,16354,16355,16356,16357,16362,16366,16367,16369,16370,16371,16372,16373,16374,16375,16377,16379,16380,16384,16385,16386,16387,16388,16389,16391,16392,16393,16396,16402,16403,16404,16407,16408,16410,16411,16413,16415,16417,16419,16420,16421,16423,16424,16425,16427,16428,16429,16430,16435,16436,16437,16438,16439,16441,16445,16446,16448,16449,16450,16451,16452,16454,16455,16456,16457,16458,16459,16460,16462,16463,16464,16466,16467,16471,16474,16477,16478,16480,16481,16482,16483,16486,16487,16493,16494,16495,16497,16498,16499,16500,16501,16502,16503,16504,16505,16507,16508,16510,16511,16512,16516,16517,16521,16523,16525,16526,16528,16530,16531,16532,16534,16535,16536,16537,16538,16539,16540,16541,16543,16545,16547,16548,16549,16550,16551,16552,16557,16558,16559,16560,16562,16563,16564,16567,16568,16569,16571,16572,16573,16578,16579,16585,16587,16588,16591,16597,16600,16601,16605,16607,16608,16610,16611,16612,16614,16615,16620,16621,16623,16624,16625,16629,16630,16631,16632,16633,16634,16636,16640,16641,16642,16646,16650,16651,16653,16657,16659,16661,16662,16663,16667,16669,16671,16679,16682,16683,16684,16685,16688,16689,16690,16692,16693,16694,16696,16698,16699,16701,16703,16704,16705,16706,16709,16710,16712,16714,16715,16716,16717,16721,16723,16724,16725,16726,16728,16729,16730,16731,16732,16734,16735,16738,16740,16741,16742,16743,16749,16752,16753,16755,16756,16758,16759,16760,16762,16763,16766,16767,16768,16772,16775,16777,16778,16779,16780,16781,16782,16784,16785,16788,16790,16791,16793,16794,16795,16797,16798,16800,16805,16809,16810,16811,16812,16813,16814,16816,16818,16819,16822,16823,16824,16825,16827,16828,16829,16830,16831,16832,16833,16834,16835,16836,16840,16841,16842,16843,16844,16845,16847,16849,16850,16851,16852,16855,16856,16864,16866,16867,16868,16869,16872,16873,16874,16875,16876,16878,16879,16880,16882,16883,16884,16886,16889,16891,16892,16893,16895,16896,16897,16899,16901,16902,16904,16905,16910,16913,16914,16915,16916,16918,16919,16920,16921,16922,16923,16924,16925,16928,16930,16931,16932,16933,16934,16935,16936,16937,16938,16939,16943,16944,16947,16949,16951,16952,16954,16955,16956,16959,16960,16962,16964,16965,16967,16968,16969,16972,16974,16977,16978,16980,16981,16982,16983,16984,16985,16987,16988,16989,16991,16992,16993,16994,16995,16999,17002,17003,17004,17005,17007,17009,17012,17014,17015,17018,17021,17023,17026,17030,17031,17032,17036,17039,17040,17041,17042,17043,17044,17045,17048,17049,17052,17054,17055,17058,17065,17066,17067,17069,17071,17072,17074,17075,17076,17078,17081,17086,17088,17089,17090,17091,17093,17096,17097,17098,17099,17100,17102,17103,17105,17110,17114,17116,17117,17119,17121,17122,17123,17124,17126,17127,17128,17129,17131,17132,17134,17135,17136,17137,17138,17140,17141,17145,17146,17148,17149,17150,17151,17152,17153,17154,17155,17157,17159,17161,17162,17163,17164,17166,17167,17168,17169,17172,17173,17175,17176,17181,17182,17183,17184,17186,17187,17188,17189,17190,17193,17194,17195,17197,17198,17202,17203,17205,17207,17208,17209,17212,17213,17214,17215,17217,17218,17221,17222,17224,17228,17229,17231,17232,17233,17235,17236,17237,17238,17240,17244,17246,17248,17250,17251,17253,17254,17256,17257,17261,17262,17265,17266,17268,17270,17274,17275,17276,17277,17278,17279,17282,17284,17285,17286,17288,17289,17291,17292,17294,17295,17296,17299,17300,17302,17304,17305,17306,17309,17311,17313,17315,17318,17319,17320,17322,17323,17325,17326,17327,17328,17329,17331,17332,17333,17335,17336,17337,17340,17341,17343,17346,17352,17354,17355,17356,17358,17360,17362,17363,17364,17366,17368,17369,17371,17372,17373,17374,17375,17377,17378,17379,17380,17381,17383,17384,17385,17386,17390,17391,17394,17399,17402,17403,17404,17407,17410,17411,17412,17415,17420,17421,17422,17424,17425,17429,17430,17432,17434,17436,17439,17440,17441,17442,17443,17444,17446,17448,17450,17451,17452,17453,17454,17455,17456,17457,17459,17461,17463,17465,17467,17468,17473,17475,17476,17477,17478,17479,17480,17483,17484,17485,17486,17487,17488,17489,17490,17498,17501,17503,17504,17508,17509,17511,17512,17513,17515,17517,17520,17522,17523,17524,17525,17526,17534,17535,17541,17543,17545,17546,17549,17550,17551,17555,17558,17560,17561,17562,17563,17564,17567,17568,17570,17571,17573,17574,17575,17577,17581,17582,17583,17585,17586,17587,17589,17594,17596,17597,17598,17601,17602,17603,17604,17610,17611,17612,17614,17616,17617,17620,17621,17622,17623,17626,17629,17631,17636,17643,17644,17645,17646,17647,17649,17650,17651,17654,17655,17656,17659,17660,17661,17665,17666,17667,17668,17670,17672,17674,17676,17677,17680,17684,17686,17687,17689,17690,17691,17692,17694,17700,17702,17704,17705,17711,17714,17715,17716,17717,17719,17721,17723,17724,17726,17727,17730,17731,17732,17733,17735,17736,17737,17739,17740,17742,17745,17746,17747,17748,17749,17750,17751,17752,17753,17756,17757,17758,17759,17761,17762,17763,17766,17767,17768,17769,17770,17772,17773,17774,17775,17777,17778,17780,17782,17784,17785,17786,17787,17788,17789,17791,17792,17793,17796,17798,17799,17800,17802,17803,17805,17806,17808,17809,17812,17814,17818,17819,17820,17824,17826,17828,17832,17835,17837,17838,17839,17841,17842,17845,17846,17847,17848,17849,17852,17853,17855,17857,17860,17861,17865,17866,17867,17869,17871,17872,17873,17874,17876,17878,17880,17881,17882,17887,17888,17889,17890,17895,17898,17899,17900,17902,17903,17905,17906,17908,17910,17912,17913,17919,17920,17922,17924,17926,17927,17928,17931,17932,17934,17935,17937,17939,17940,17942,17943,17944,17945,17947,17948,17949,17950,17952,17953,17956,17957,17960,17962,17963,17964,17965,17966,17967,17968,17971,17972,17973,17977,17980,17981,17982,17983,17984,17985,17986,17988,17989,17992,17993,17994,17995,17997,17998,17999,18002,18003,18004,18007,18008,18011,18012,18014,18016,18018,18024,18025,18026,18028,18030,18031,18032,18033,18034,18036,18042,18043,18044,18046,18047,18048,18051,18052,18055,18057,18058,18060,18061,18062,18063,18064,18066,18067,18068,18070,18073,18074,18075,18076,18077,18080,18081,18083,18084,18085,18086,18088,18089,18090,18093,18094,18095,18096,18097,18100,18102,18107,18108,18109,18110,18111,18112,18113,18115,18116,18117,18120,18122,18124,18129,18130,18131,18134,18135,18136,18138,18139,18142,18143,18144,18145,18147,18148,18151,18154,18156,18158,18160,18161,18164,18165,18167,18168,18169,18172,18173,18175,18176,18177,18178,18179,18180,18183,18185,18187,18188,18189,18190,18194,18195,18196,18197,18198,18199,18200,18203,18204,18205,18208,18209,18215,18216,18218,18224,18225,18227,18229,18230,18231,18232,18233,18234,18236,18239,18240,18242,18243,18246,18247,18249,18251,18252,18254,18256,18259,18260,18261,18262,18264,18265,18266,18268,18269,18270,18272,18273,18274,18281,18283,18284,18285,18286,18287,18290,18292,18293,18294,18296,18297,18298,18299,18300,18302,18304,18305,18308,18311,18312,18315,18316,18318,18319,18320,18322,18325,18328,18331,18332,18334,18335,18338,18339,18340,18341,18342,18345,18346,18347,18348,18349,18350,18351,18352,18356,18357,18359,18363,18364,18365,18371,18372,18373,18374,18375,18378,18379,18384,18385,18387,18389,18390,18392,18395,18396,18397,18399,18400,18402,18403,18404,18406,18407,18408,18409,18410,18412,18413,18414,18416,18418,18421,18422,18423,18424,18425,18427,18428,18430,18431,18432,18433,18435,18436,18438,18439,18440,18442,18443,18444,18445,18446,18449,18451,18459,18460,18462,18465,18466,18469,18470,18472,18473,18475,18480,18481,18483,18484,18486,18488,18490,18492,18493,18496,18497,18500,18501,18502,18503,18504,18506,18509,18511,18512,18514,18515,18517,18520,18523,18527,18530,18531,18532,18533,18534,18536,18539,18540,18546,18550,18551,18553,18554,18555,18557,18558,18559,18561,18563,18566,18568,18570,18573,18574,18577,18578,18579,18580,18581,18583,18585,18586,18587,18588,18589,18593,18599,18600,18601,18604,18606,18607,18608,18610,18611,18613,18615,18617,18618,18619,18620,18621,18623,18624,18625,18626,18627,18629,18631,18632,18633,18635,18636,18637,18640,18643,18645,18646,18647,18648,18651,18652,18655,18656,18657,18658,18659,18661,18662,18664,18665,18666,18668,18669,18670,18671,18672,18674,18675,18677,18678,18679,18681,18682,18683,18685,18686,18690,18691,18694,18695,18696,18697,18698,18699,18701,18702,18705,18707,18708,18709,18710,18715,18716,18719,18720,18722,18726,18727,18728,18729,18730,18733,18737,18738,18740,18741,18742,18744,18747,18748,18750,18751,18752,18755,18756,18757,18758,18760,18761,18764,18765,18766,18768,18770,18776,18777,18778,18779,18780,18781,18782,18786,18787,18788,18791,18793,18795,18796,18803,18804,18806,18811,18812,18815,18817,18818,18819,18822,18824,18826,18827,18830,18831,18832,18834,18835,18836,18838,18841,18842,18843,18845,18846,18847,18848,18851,18853,18858,18859,18860,18862,18863,18864,18865,18866,18867,18870,18871,18872,18873,18874,18875,18876,18878,18879,18880,18881,18883,18884,18885,18886,18888,18890,18891,18892,18893,18895,18896,18897,18898,18900,18903,18906,18909,18910,18911,18912,18913,18914,18915,18916,18917,18918,18920,18922,18923,18924,18926,18927,18931,18932,18934,18935,18936,18937,18938,18940,18941,18942,18946,18947,18948,18950,18951,18952,18955,18956,18957,18960,18969,18971,18972,18973,18978,18979,18981,18982,18983,18987,18988,18989,18990,18991,18993,18994,18995,18998,18999,19001,19002,19004,19005,19006,19007,19009,19010,19012,19013,19014,19015,19017,19018,19019,19020,19022,19023,19025,19026,19027,19028,19030,19034,19035,19037,19039,19040,19042,19044,19045,19049,19050,19053,19054,19055,19056,19060,19061,19062,19063,19064,19065,19066,19067,19068,19069,19075,19076,19078,19079,19082,19083,19084,19086,19087,19088,19089,19090,19092,19093,19097,19098,19100,19102,19104,19105,19107,19108,19109,19110,19115,19116,19117,19118,19119,19120,19121,19122,19126,19130,19133,19135,19136,19137,19138,19139,19141,19148,19152,19153,19154,19155,19157,19160,19161,19163,19164,19166,19171,19172,19173,19174,19176,19178,19179,19180,19181,19182,19183,19184,19185,19186,19189,19191,19192,19194,19195,19196,19198,19200,19201,19205,19208,19209,19214,19215,19219,19220,19221,19223,19224,19225,19228,19229,19231,19232,19234,19235,19236,19237,19239,19240,19245,19246,19247,19249,19251,19253,19255,19256,19257,19259,19260,19262,19269,19270,19275,19276,19277,19278,19281,19282,19283,19285,19286,19287,19288,19289,19291,19293,19295,19298,19299,19301,19306,19307,19308,19309,19310,19311,19312,19313,19314,19315,19317,19318,19319,19320,19323,19325,19326,19328,19329,19330,19332,19333,19338,19339,19340,19341,19342,19343,19344,19345,19348,19349,19350,19353,19354,19355,19356,19358,19359,19361,19364,19366,19367,19368,19372,19373,19374,19375,19376,19378,19379,19383,19384,19387,19389,19390,19391,19392,19395,19396,19397,19398,19399,19401,19403,19404,19405,19406,19408,19410,19412,19413,19417,19418,19419,19421,19429,19430,19431,19432,19434,19435,19436,19437,19439,19441,19444,19445,19446,19449,19450,19452,19454,19459,19462,19463,19464,19468,19469,19471,19472,19473,19474,19475,19476,19477,19479,19480,19481,19484,19487,19489,19490,19491,19492,19493,19494,19495,19500,19506,19507,19508,19509,19510,19512,19513,19514,19516,19517,19518,19519,19520,19523,19525,19526,19528,19530,19531,19532,19533,19537,19538,19539,19540,19542,19543,19545,19546,19548,19549,19551,19552,19554,19555,19556,19559,19561,19565,19566,19568,19571,19572,19573,19575,19576,19578,19580,19584,19587,19588,19589,19590,19591,19592,19595,19597,19599,19600,19601,19604,19606,19607,19609,19611,19612,19614,19615,19616,19618,19620,19623,19624,19626,19628,19632,19633,19638,19640,19643,19649,19650,19656,19659,19662,19663,19664,19665,19666,19670,19671,19673,19674,19677,19679,19681,19683,19684,19685,19687,19688,19691,19692,19693,19694,19695,19696,19697,19700,19702,19703,19706,19707,19709,19710,19714,19716,19717,19719,19722,19723,19724,19725,19726,19727,19728,19731,19732,19734,19735,19736,19739,19741,19742,19743,19744,19745,19746,19747,19748,19749,19750,19752,19753,19754,19756,19757,19759,19760,19761,19762,19763,19764,19766,19767,19768,19769,19774,19777,19778,19779,19780,19781,19782,19784,19785,19786,19787,19789,19792,19793,19794,19796,19797,19798,19799,19802,19803,19804,19805,19806,19808,19810,19813,19814,19815,19816,19817,19818,19821,19823,19824,19825,19827,19828,19830,19831,19833,19835,19836,19837,19838,19840,19841,19842,19843,19845,19848,19849,19850,19853,19854,19857,19859,19860,19861,19863,19864,19866,19869,19870,19871,19872,19875,19876,19877,19879,19883,19884,19885,19886,19887,19888,19895,19896,19897,19899,19901,19904,19905,19906,19909,19911,19912,19916,19917,19918,19919,19921,19922,19923,19927,19928,19929,19931,19932,19937,19938,19939,19940,19941,19945,19946,19947,19948,19949,19950,19951,19952,19955,19956,19957,19963,19964,19965,19966,19967,19974,19975,19976,19979,19980,19981,19983,19987,19989,19991,19993,19995,19997,19998,19999,20000,20003,20004,20005,20007,20010,20016,20017,20018,20019,20020,20021,20022,20023,20024,20025,20026,20028,20029,20031,20033,20035,20036,20037,20039,20040,20042,20043,20044,20045,20046,20049,20050,20051,20052,20053,20057,20058,20059,20061,20063,20064,20065,20066,20067,20070,20071,20074,20075,20076,20077,20080,20081,20084,20085,20086,20088,20089,20090,20092,20096,20099,20100,20102,20103,20104,20105,20107,20108,20109,20110,20111,20112,20113,20114,20115,20116,20118,20121,20123,20129,20132,20133,20134,20136,20139,20140,20145,20147,20148,20150,20151,20152,20153,20159,20160,20162,20164,20167,20169,20172,20173,20174,20175,20177,20178,20179,20180,20183,20185,20186,20187,20190,20194,20195,20196,20197,20199,20201,20202,20203,20204,20206,20207,20208,20209,20212,20215,20218,20220,20221,20223,20226,20228,20229,20231,20234,20236,20238,20239,20240,20241,20243,20244,20246,20247,20248,20250,20251,20254,20255,20258,20259,20260,20262,20264,20265,20266,20268,20269,20270,20271,20274,20278,20279,20280,20281,20282,20283,20285,20286,20287,20288,20289,20290,20292,20293,20295,20297,20298,20299,20301,20302,20303,20305,20307,20308,20311,20312,20314,20315,20316,20319,20320,20327,20328,20329,20330,20331,20332,20337,20339,20340,20341,20343,20345,20346,20347,20349,20351,20352,20353,20354,20355,20356,20358,20359,20360,20364,20365,20366,20367,20368,20370,20371,20373,20374,20375,20376,20377,20379,20380,20382,20383,20384,20389,20391,20393,20394,20395,20396,20398,20403,20406,20407,20408,20410,20413,20414,20416,20417,20419,20423,20425,20427,20428,20429,20430,20431,20432,20436,20437,20438,20441,20443,20444,20445,20446,20447,20448,20450,20453,20454,20456,20458,20459,20462,20467,20468,20469,20470,20471,20473,20474,20476,20478,20479,20480,20482,20487,20489,20490,20491,20492,20493,20496,20498,20499,20500,20501,20502,20504,20505,20506,20507,20509,20511,20512,20513,20514,20516,20520,20522,20528,20530,20531,20532,20533,20534,20535,20536,20537,20538,20540,20542,20545,20549,20550,20552,20553,20554,20558,20559,20561,20562,20563,20565,20568,20569,20572,20573,20574,20577,20579,20582,20583,20586,20589,20590,20591,20592,20594,20596,20597,20599,20601,20602,20603,20604,20607,20609,20610,20611,20612,20613,20615,20616,20618,20619,20623,20626,20627,20628,20629,20630,20635,20636,20637,20639,20642,20643,20645,20646,20649,20650,20651,20653,20654,20655,20658,20660,20661,20662,20668,20669,20670,20672,20674,20676,20677,20679,20680,20681,20685,20686,20687,20688,20689,20692,20693,20694,20695,20697,20699,20700,20702,20704,20706,20708,20709,20710,20712,20715,20716,20720,20721,20722,20723,20724,20727,20729,20730,20732,20733,20734,20735,20737,20739,20740,20741,20742,20743,20744,20745,20747,20748,20749,20750,20751,20753,20757,20758,20759,20760,20763,20765,20766,20767,20768,20770,20771,20773,20775,20776,20780,20781,20782,20783,20786,20789,20790,20793,20794,20795,20796,20797,20798,20799,20801,20802,20803,20804,20805,20807,20810,20811,20813,20814,20815,20820,20823,20826,20827,20829,20830,20831,20835,20837,20839,20840,20842,20844,20846,20847,20848,20851,20852,20853,20854,20857,20859,20861,20863,20866,20868,20871,20872,20873,20875,20877,20878,20879,20880,20881,20883,20885,20886,20887,20888,20890,20891,20892,20893,20894,20898,20902,20913,20916,20917,20918,20920,20922,20923,20924,20928,20929,20931,20932,20935,20939,20942,20946,20947,20948,20949,20951,20952,20953,20954,20955,20956,20957,20961,20962,20963,20964,20968,20969,20972,20974,20975,20976,20978,20981,20982,20983,20986,20990,20991,20992,20993,20994,20996,20997,20998,20999,21000,21003,21005,21006,21008,21010,21013,21014,21016,21018,21020,21021,21022,21023,21028,21029,21030,21031,21033,21034,21035,21036,21037,21038,21039,21041,21044,21045,21046,21049,21050,21052,21054,21061,21062,21065,21069,21070,21072,21073,21078,21080,21082,21083,21086,21087,21089,21090,21091,21092,21093,21095,21097,21099,21100,21102,21103,21104,21105,21107,21109,21110,21113,21114,21116,21117,21118,21119,21120,21121,21122,21126,21129,21130,21131,21132,21135,21136,21137,21138,21139,21141,21142,21149,21151,21152,21153,21156,21157,21159,21162,21163,21164,21165,21166,21168,21169,21170,21171,21172,21173,21178,21179,21180,21181,21182,21184,21185,21186,21188,21189,21190,21191,21192,21193,21195,21196,21197,21200,21201,21202,21204,21206,21209,21210,21213,21214,21215,21217,21218,21220,21221,21223,21224,21225,21226,21227,21228,21230,21232,21235,21236,21239,21241,21242,21243,21244,21246,21247,21248,21249,21250,21251,21253,21255,21256,21258,21259,21261,21262,21265,21266,21267,21268,21270,21271,21272,21274,21277,21279,21282,21283,21284,21285,21286,21288,21291,21292,21293,21295,21296,21297,21301,21302,21303,21306,21308,21309,21311,21313,21315,21316,21320,21324,21325,21326,21327,21329,21330,21332,21333,21334,21340,21342,21343,21344,21349,21350,21351,21352,21353,21356,21357,21359,21362,21363,21364,21370,21373,21374,21375,21376,21377,21378,21379,21380,21383,21384,21385,21386,21387,21388,21389,21390,21391,21393,21394,21395,21396,21397,21398,21400,21401,21403,21404,21405,21406,21407,21411,21414,21415,21417,21418,21420,21421,21423,21424,21426,21427,21428,21429,21431,21432,21433,21436,21438,21439,21440,21442,21443,21444,21445,21447,21448,21451,21455,21458,21460,21463,21464,21465,21467,21468,21470,21480,21481,21484,21485,21486,21488,21489,21490,21491,21493,21497,21498,21499,21500,21501,21502,21503,21504,21505,21508,21510,21511,21512,21516,21517,21519,21521,21524,21526,21527,21530,21531,21534,21535,21536,21538,21541,21542,21544,21551,21556,21557,21559,21560,21561,21562,21564,21565,21567,21568,21569,21572,21573,21577,21578,21580,21581,21582,21584,21585,21586,21588,21589,21590,21592,21595,21597,21598,21600,21601,21605,21606,21608,21609,21610,21612,21614,21615,21617,21620,21622,21623,21624,21625,21626,21629,21631,21633,21634,21635,21636,21637,21638,21639,21640,21643,21649,21650,21651,21653,21654,21655,21656,21657,21658,21665,21666,21668,21669,21670,21671,21672,21673,21674,21676,21677,21678,21679,21680,21681,21682,21683,21684,21687,21688,21689,21691,21692,21696,21697,21698,21699,21700,21701,21702,21703,21704,21710,21712,21714,21718,21719,21723,21724,21726,21727,21730,21732,21733,21734,21736,21737,21739,21742,21743,21746,21747,21748,21749,21750,21751,21753,21755,21756,21757,21758,21759,21760,21762,21763,21764,21765,21767,21768,21769,21770,21771,21772,21773,21774,21775,21776,21777,21778,21779,21782,21783,21784,21787,21790,21793,21794,21796,21798,21799,21800,21801,21802,21804,21805,21806,21807,21808,21809,21810,21811,21814,21815,21817,21820,21822,21824,21826,21827,21828,21829,21830,21832,21833,21834,21836,21837,21838,21839,21840,21842,21844,21846,21848,21849,21850,21851,21855,21856,21857,21861,21862,21863,21864,21865,21869,21872,21874,21875,21877,21879,21880,21881,21882,21884,21886,21887,21888,21892,21893,21894,21896,21901,21903,21904,21905,21906,21907,21910,21911,21912,21914,21915,21919,21921,21923,21924,21927,21929,21930,21931,21932,21933,21934,21937,21940,21944,21945,21946,21947,21948,21949,21950,21951,21952,21953,21954,21955,21957,21958,21959,21967,21971,21973,21974,21975,21981,21983,21984,21985,21986,21987,21988,21989,21990,21991,21992,21994,21995,21996,22001,22002,22003,22004,22006,22007,22009,22010,22011,22012,22013,22014,22015,22018,22019,22020,22021,22024,22025,22028,22029,22030,22035,22036,22037,22038,22039,22040,22041,22044,22045,22047,22049,22053,22055,22056,22057,22059,22060,22063,22065,22066,22069,22071,22074,22076,22078,22079,22080,22081,22082,22085,22086,22087,22088,22089,22090,22091,22092,22095,22096,22101,22102,22103,22104,22105,22106,22108,22109,22111,22112,22113,22114,22118,22121,22123,22124,22125,22126,22127,22128,22133,22134,22135,22139,22140,22144,22145,22146,22147,22148,22151,22152,22157,22159,22160,22161,22162,22163,22165,22167,22169,22170,22172,22174,22176,22179,22181,22182,22183,22184,22186,22188,22191,22193,22194,22195,22196,22200,22201,22202,22203,22204,22206,22207,22209,22213,22215,22216,22217,22219,22220,22221,22222,22224,22225,22226,22227,22228,22229,22233,22235,22236,22237,22238,22239,22242,22243,22244,22247,22248,22249,22250,22252,22253,22254,22257,22259,22261,22263,22264,22265,22267,22268,22270,22271,22272,22273,22274,22275,22276,22277,22278,22280,22281,22285,22286,22287,22288,22289,22291,22292,22294,22295,22296,22299,22300,22301,22303,22305,22306,22307,22308,22309,22310,22312,22313,22314,22316,22317,22318,22320,22321,22323,22325,22326,22327,22329,22330,22332,22333,22335,22336,22337,22338,22340,22341,22343,22345,22347,22348,22351,22354,22355,22356,22357,22358,22360,22361,22362,22363,22365,22366,22369,22370,22372,22374,22378,22380,22383,22384,22386,22387,22388,22389,22390,22392,22395,22397,22398,22399,22401,22402,22403,22404,22405,22407,22411,22415,22417,22418,22419,22420,22421,22422,22424,22426,22427,22433,22434,22435,22440,22441,22442,22443,22444,22446,22447,22448,22453,22454,22456,22458,22464,22465,22467,22468,22469,22470,22471,22473,22474,22475,22476,22477,22478,22483,22485,22486,22487,22488,22491,22493,22494,22497,22499,22500,22504,22505,22506,22507,22510,22511,22512,22513,22514,22517,22518,22520,22521,22522,22523,22524,22525,22526,22528,22533,22535,22538,22540,22542,22544,22545,22546,22547,22549,22551,22552,22554,22556,22557,22558,22559,22560,22561,22562,22564,22566,22567,22568,22569,22570,22572,22573,22575,22576,22577,22578,22581,22582,22583,22586,22588,22589,22591,22592,22593,22595,22596,22597,22598,22599,22600,22601,22602,22607,22608,22609,22610,22611,22612,22615,22616,22618,22619,22621,22622,22623,22624,22629,22630,22632,22635,22637,22639,22641,22642,22645,22647,22648,22649,22650,22652,22654,22656,22658,22659,22660,22661,22663,22664,22665,22666,22667,22669,22675,22679,22680,22682,22683,22684,22685,22688,22691,22695,22696,22699,22700,22703,22704,22706,22707,22710,22711,22712,22713,22717,22718,22719,22720,22721,22722,22723,22725,22727,22728,22729,22732,22737,22738,22739,22740,22743,22744,22746,22747,22750,22753,22754,22758,22759,22760,22761,22763,22764,22765,22767,22768,22769,22770,22773,22775,22777,22778,22780,22782,22784,22785,22786,22787,22790,22792,22794,22796,22799,22804,22805,22806,22808,22809,22810,22813,22815,22816,22819,22820,22821,22822,22827,22828,22829,22830,22831,22832,22834,22835,22836,22838,22839,22843,22844,22845,22846,22847,22850,22851,22852,22853,22855,22856,22857,22859,22862,22864,22865,22866,22868,22869,22871,22873,22874,22876,22879,22883,22884,22885,22886,22887,22888,22889,22890,22894,22895,22898,22900,22901,22902,22903,22904,22905,22906,22907,22909,22910,22912,22913,22914,22915,22916,22917,22920,22921,22922,22924,22927,22931,22932,22936,22937,22938,22939,22941,22943,22944,22945,22948,22949,22950,22951,22956,22957,22958,22959,22960,22961,22962,22963,22964,22965,22968,22973,22974,22975,22977,22979,22980,22981,22982,22983,22985,22986,22987,22989,22990,22994,22998,23001,23004,23005,23009,23010,23011,23012,23013,23015,23016,23020,23022,23023,23025,23026,23028,23030,23032,23033,23035,23037,23038,23040,23041,23046,23047,23049,23050,23051,23052,23056,23058,23060,23061,23063,23064,23068,23069,23070,23072,23073,23077,23082,23085,23086,23089,23092,23093,23094,23099,23101,23103,23104,23105,23107,23109,23110,23112,23114,23115,23116,23118,23119,23120,23123,23124,23125,23130,23131,23132,23133,23134,23136,23138,23139,23140,23146,23150,23151,23153,23154,23155,23158,23159,23160,23161,23163,23164,23166,23168,23171,23172,23175,23178,23180,23181,23183,23185,23186,23187,23188,23191,23194,23196,23197,23198,23199,23200,23202,23203,23204,23205,23206,23212,23214,23216,23217,23218,23220,23222,23223,23225,23226,23227,23228,23229,23230,23231,23233,23234,23235,23236,23238,23241,23242,23246,23247,23248,23250,23251,23253,23254,23255,23259,23260,23263,23266,23267,23268,23272,23273,23274,23277,23278,23279,23281,23283,23287,23289,23290,23291,23292,23295,23297,23299,23300,23303,23304,23305,23306,23309,23311,23312,23315,23316,23317,23320,23321,23324,23326,23329,23330,23331,23332,23334,23336,23340,23342,23344,23346,23347,23349,23350,23351,23353,23354,23355,23359,23363,23366,23371,23375,23376,23380,23381,23382,23383,23385,23386,23387,23388,23389,23390,23393,23394,23396,23399,23400,23403,23404,23406,23407,23408,23409,23411,23412,23413,23414,23415,23416,23421,23422,23423,23425,23428,23429,23430,23431,23432,23434,23436,23437,23438,23440,23446,23449,23451,23452,23454,23455,23457,23459,23460,23461,23463,23464,23465,23466,23467,23468,23470,23471,23473,23474,23476,23477,23478,23480,23481,23483,23484,23486,23488,23489,23490,23491,23492,23494,23496,23499,23500,23502,23503,23504,23505,23506,23507,23511,23512,23513,23514,23520,23522,23526,23528,23529,23530,23531,23532,23533,23539,23541,23542,23543,23546,23547,23549,23550,23551,23553,23554,23555,23556,23557,23561,23562,23563,23564,23566,23567,23568,23570,23571,23580,23582,23585,23588,23590,23591,23593,23594,23595,23597,23599,23601,23602,23603,23606,23608,23609,23610,23611,23613,23614,23615,23616,23618,23619,23622,23623,23624,23627,23628,23629,23630,23631,23632,23633,23634,23638,23643,23644,23645,23646,23647,23649,23650,23653,23654,23655,23657,23658,23659,23660,23662,23663,23666,23667,23671,23673,23674,23678,23680,23682,23683,23685,23688,23689,23690,23691,23695,23697,23698,23701,23703,23704,23706,23707,23708,23710,23713,23715,23716,23719,23720,23722,23723,23725,23726,23729,23730,23732,23734,23735,23736,23737,23738,23739,23740,23741,23743,23744,23746,23748,23750,23751,23752,23753,23754,23755,23757,23759,23761,23762,23763,23764,23768,23771,23772,23774,23775,23777,23778,23779,23782,23783,23784,23786,23788,23789,23790,23791,23792,23793,23794,23795,23796,23797,23800,23801,23803,23804,23806,23807,23808,23809,23810,23812,23814,23815,23816,23817,23819,23820,23821,23822,23826,23829,23831,23832,23833,23835,23836,23837,23839,23840,23841,23842,23844,23847,23849,23851,23852,23856,23857,23858,23861,23862,23863,23864,23865,23866,23868,23870,23871,23872,23873,23874,23875,23876,23877,23878,23879,23880,23882,23885,23887,23888,23889,23892,23895,23896,23897,23899,23900,23903,23904,23906,23907,23911,23912,23913,23914,23915,23918,23919,23920,23921,23924,23925,23926,23927,23928,23930,23931,23932,23933,23937,23939,23940,23941,23942,23943,23946,23947,23948,23949,23950,23952,23953,23955,23957,23958,23960,23961,23962,23964,23966,23967,23968,23969,23974,23976,23977,23982,23983,23985,23986,23988,23989,23990,23991,23992,23993,23994,23995,23996,23997,23998,23999,24000,24002,24003,24004,24006,24007,24009,24011,24012,24013,24014,24016,24017,24019,24027,24029,24032,24034,24037,24041,24042,24043,24045,24046,24047,24048,24052,24053,24054,24055,24056,24060,24062,24063,24064,24066,24067,24069,24072,24073,24074,24076,24080,24081,24082,24084,24086,24089,24090,24092,24093,24094,24097,24099,24100,24101,24103,24106,24107,24108,24109,24112,24113,24114,24116,24117,24118,24119,24122,24123,24124,24127,24128,24132,24133,24134,24137,24138,24143,24144,24145,24146,24147,24148,24149,24151,24152,24153,24158,24159,24160,24161,24162,24164,24165,24166,24167,24169,24170,24171,24172,24173,24174,24176,24177,24179,24180,24181,24185,24187,24188,24189,24190,24191,24193,24194,24196,24198,24199,24200,24201,24202,24205,24206,24207,24211,24215,24218,24221,24222,24226,24228,24229,24230,24231,24232,24233,24234,24235,24236,24237,24238,24239,24240,24241,24242,24243,24245,24246,24248,24249,24250,24252,24253,24256,24257,24260,24261,24262,24263,24265,24268,24269,24270,24271,24272,24273,24274,24276,24277,24278,24279,24280,24282,24284,24286,24287,24292,24293,24295,24296,24297,24298,24300,24302,24303,24304,24305,24307,24309,24311,24312,24314,24315,24316,24318,24319,24320,24321,24322,24323,24324,24327,24328,24329,24331,24332,24333,24334,24335,24337,24339,24342,24343,24344,24345,24346,24347,24350,24351,24352,24353,24354,24355,24356,24358,24362,24363,24364,24366,24367,24368,24369,24370,24371,24372,24373,24374,24375,24378,24379,24380,24382,24383,24384,24385,24386,24388,24390,24391,24392,24393,24395,24396,24400,24401,24407,24409,24410,24411,24412,24413,24415,24417,24418,24419,24420,24421,24423,24424,24426,24427,24428,24429,24431,24432,24435,24438,24439,24440,24441,24443,24444,24449,24450,24451,24452,24454,24457,24459,24462,24464,24466,24469,24470,24471,24472,24473,24474,24475,24478,24479,24481,24482,24486,24488,24489,24490,24492,24493,24496,24497,24499,24500,24501,24502,24505,24506,24507,24508,24509,24510,24511,24512,24513,24517,24518,24519,24520,24521,24526,24527,24531,24532,24533,24534,24536,24537,24543,24544,24548,24550,24553,24554,24555,24557,24559,24562,24567,24569,24571,24575,24576,24577,24578,24580,24583,24586,24587,24589,24590,24591,24592,24593,24596,24600,24604,24605,24606,24607,24608,24609,24610,24611,24612,24613,24614,24615,24617,24618,24620,24621,24626,24627,24628,24631,24632,24634,24635,24637,24638,24639,24640,24641,24643,24644,24646,24649,24650,24652,24653,24654,24655,24656,24657,24662,24663,24664,24670,24672,24673,24674,24675,24677,24678,24682,24684,24685,24687,24690,24692,24694,24696,24698,24699,24703,24706,24707,24708,24710,24711,24712,24715,24716,24717,24718,24719,24720,24721,24722,24723,24724,24725,24726,24727,24728,24730,24731,24732,24734,24738,24740,24741,24742,24743,24745,24750,24752,24753,24754,24755,24757,24760,24761,24762,24763,24764,24765,24770,24771,24774,24775,24776,24777,24778,24779,24781,24783,24785,24786,24787,24788,24790,24791,24792,24794,24795,24796,24797,24799,24800,24801,24802,24803,24804,24805,24806,24808,24809,24810,24813,24814,24816,24817,24818,24819,24820,24824,24825,24828,24829,24831,24833,24834,24835,24836,24837,24838,24839,24841,24842,24843,24844,24848,24850,24852,24853,24854,24856,24857,24859,24860,24864,24866,24867,24869,24870,24874,24875,24876,24877,24878,24879,24881,24882,24883,24884,24886,24888,24889,24890,24891,24894,24897,24899,24904,24905,24906,24907,24908,24909,24913,24915,24917,24918,24919,24921,24922,24925,24928,24929,24930,24931,24934,24935,24936,24937,24940,24941,24944,24945,24948,24951,24952,24953,24955,24959,24961,24962,24963,24964,24965,24966,24967,24968,24971,24972,24973,24977,24978,24979,24980,24981,24984,24986,24987,24988,24989,24991,24992,24993,24994,24998,24999,25000,25001,25002,25003,25004,25005,25007,25008,25010,25011,25012,25013,25015,25016,25017,25020,25022,25023,25026,25032,25033,25034,25036,25037,25040,25042,25043,25045,25052,25053,25055,25056,25057,25061,25063,25065,25067,25068,25070,25074,25075,25077,25078,25079,25080,25081,25082,25083,25085,25086,25088,25090,25091,25092,25094,25095,25097,25100,25106,25109,25110,25111,25112,25114,25115,25116,25121,25122,25124,25126,25130,25131,25132,25133,25135,25136,25137,25141,25142,25145,25147,25148,25149,25156,25157,25158,25159,25160,25161,25166,25167,25169,25170,25172,25173,25174,25176,25177,25178,25179,25181,25182,25184,25185,25186,25187,25188,25189,25191,25192,25194,25195,25197,25198,25199,25200,25202,25203,25204,25205,25209,25211,25212,25214,25215,25219,25220,25222,25223,25224,25225,25226,25227,25228,25230,25234,25235,25236,25238,25239,25242,25243,25246,25247,25249,25256,25257,25259,25260,25262,25264,25266,25267,25269,25272,25273,25274,25275,25276,25277,25278,25279,25280,25281,25283,25286,25287,25289,25291,25292,25294,25296,25297,25298,25300,25301,25302,25304,25305,25306,25307,25309,25311,25312,25314,25315,25316,25320,25323,25324,25325,25326,25327,25329,25331,25334,25335,25336,25338,25340,25341,25342,25343,25345,25346,25348,25349,25351,25352,25354,25355,25357,25358,25361,25362,25364,25368,25370,25371,25373,25374,25377,25383,25384,25386,25387,25388,25391,25399,25401,25405,25406,25407,25408,25409,25410,25412,25413,25415,25417,25419,25420,25421,25422,25423,25424,25425,25427,25435,25437,25438,25439,25440,25441,25444,25445,25447,25448,25450,25451,25452,25453,25454,25455,25456,25457,25458,25459,25460,25462,25464,25465,25466,25468,25470,25472,25477,25478,25479,25480,25481,25482,25483,25484,25485,25486,25488,25491,25492,25493,25494,25495,25497,25499,25501,25502,25504,25505,25506,25507,25508,25509,25511,25513,25514,25515,25517,25519,25520,25522,25523,25524,25527,25528,25529,25530,25531,25532,25533,25535,25538,25539,25540,25541,25542,25545,25546,25549,25550,25551,25552,25553,25554,25556,25557,25560,25561,25562,25563,25564,25565,25568,25569,25570,25571,25573,25574,25576,25577,25579,25581,25585,25586,25589,25591,25595,25596,25601,25605,25606,25607,25610,25615,25616,25617,25618,25619,25620,25622,25623,25625,25626,25630,25631,25633,25635,25638,25640,25642,25645,25647,25650,25651,25652,25653,25657,25658,25659,25660,25661,25662,25663,25665,25668,25669,25670,25671,25672,25673,25676,25677,25678,25679,25681,25683,25684,25685,25686,25687,25688,25689,25690,25691,25693,25695,25696,25698,25700,25701,25702,25703,25704,25706,25710,25712,25713,25718,25720,25722,25723,25725,25726,25727,25728,25731,25732,25734,25735,25737,25738,25740,25741,25742,25745,25746,25748,25749,25750,25753,25754,25755,25757,25761,25763,25764,25765,25766,25769,25773,25774,25775,25777,25778,25779,25780,25781,25782,25783,25785,25786,25787,25789,25791,25792,25793,25794,25795,25796,25798,25799,25800,25801,25803,25805,25806,25808,25810,25811,25812,25814,25815,25816,25817,25818,25820,25823,25824,25827,25828,25829,25830,25831,25834,25836,25837,25839,25840,25841,25843,25844,25846,25849,25850,25853,25857,25858,25859,25860,25861,25862,25863,25869,25870,25871,25872,25875,25876,25877,25878,25879,25881,25884,25886,25887,25888,25889,25890,25897,25899,25900,25902,25904,25906,25907,25909,25910,25911,25912,25913,25914,25915,25916,25917,25918,25919,25920,25921,25922,25924,25926,25927,25928,25933,25937,25940,25941,25944,25945,25946,25947,25948,25953,25954,25955,25956,25957,25959,25960,25962,25963,25964,25966,25967,25970,25972,25973,25974,25975,25976,25979,25980,25981,25984,25985,25989,25992,25993,25994,25995,25997,25999,26000,26001,26002,26003,26005,26007,26008,26009,26011,26014,26015,26018,26024,26028,26030,26032,26033,26034,26035,26038,26040,26042,26043,26044,26046,26048,26049,26051,26053,26054,26055,26060,26064,26068,26069,26070,26071,26072,26077,26078,26079,26080,26083,26085,26086,26087,26089,26091,26094,26096,26099,26101,26104,26105,26106,26107,26108,26109,26110,26111,26113,26114,26116,26117,26118,26121,26125,26128,26130,26132,26133,26134,26135,26136,26137,26138,26141,26142,26144,26147,26148,26149,26150,26154,26157,26158,26159,26160,26161,26162,26163,26164,26168,26170,26171,26173,26174,26176,26178,26181,26182,26183,26184,26185,26186,26187,26188,26190,26192,26194,26195,26198,26199,26201,26202,26203,26205,26206,26209,26211,26212,26217,26219,26220,26221,26223,26224,26226,26227,26228,26229,26230,26232,26233,26234,26236,26239,26240,26241,26245,26246,26248,26250,26251,26256,26257,26259,26260,26263,26266,26267,26269,26271,26272,26273,26274,26275,26277,26278,26279,26280,26285,26286,26287,26295,26297,26298,26299,26301,26302,26303,26304,26305,26307,26309,26313,26314,26315,26317,26318,26319,26320,26321,26324,26325,26327,26328,26329,26331,26332,26333,26334,26336,26337,26338,26339,26343,26345,26346,26348,26351,26354,26356,26360,26361,26363,26364,26365,26367,26368,26370,26371,26373,26377,26379,26380,26383,26384,26385,26386,26387,26388,26389,26390,26391,26392,26393,26394,26396,26397,26399,26400,26401,26402,26403,26406,26407,26408,26410,26411,26412,26413,26414,26416,26417,26418,26421,26422,26424,26425,26426,26427,26428,26429,26430,26431,26432,26435,26436,26437,26438,26439,26440,26442,26444,26445,26446,26447,26448,26449,26450,26451,26452,26455,26457,26459,26460,26462,26463,26467,26468,26469,26470,26472,26474,26475,26478,26479,26480,26483,26484,26485,26487,26488,26489,26490,26491,26494,26497,26502,26503,26504,26505,26506,26507,26508,26511,26515,26518,26519,26520,26522,26523,26524,26527,26528,26529,26530,26531,26532,26534,26535,26540,26541,26543,26544,26546,26548,26550,26551,26552,26553,26554,26556,26558,26559,26561,26562,26563,26565,26566,26569,26571,26572,26573,26574,26576,26577,26579,26580,26581,26582,26583,26585,26587,26590,26591,26592,26593,26595,26596,26597,26598,26602,26603,26605,26606,26610,26611,26616,26617,26618,26619,26622,26623,26624,26627,26630,26631,26633,26634,26635,26636,26637,26639,26640,26641,26642,26643,26644,26645,26646,26647,26649,26650,26652,26653,26654,26656,26657,26661,26662,26663,26667,26669,26670,26671,26672,26673,26675,26676,26677,26678,26681,26685,26688,26691,26692,26693,26694,26695,26696,26697,26698,26699,26700,26702,26703,26708,26710,26713,26714,26718,26720,26721,26722,26727,26728,26730,26731,26733,26734,26736,26742,26743,26744,26745,26748,26749,26750,26751,26755,26756,26757,26758,26760,26761,26764,26767,26769,26773,26774,26777,26778,26780,26782,26783,26784,26786,26787,26789,26790,26795,26797,26798,26799,26800,26801,26802,26804,26805,26808,26809,26811,26812,26814,26815,26816,26817,26818,26820,26821,26823,26824,26829,26830,26831,26832,26833,26834,26835,26836,26838,26839,26842,26843,26845,26848,26849,26850,26851,26853,26855,26858,26863,26864,26867,26869,26871,26872,26873,26874,26875,26876,26877,26878,26879,26882,26883,26884,26885,26886,26890,26893,26895,26898,26899,26900,26901,26903,26904,26905,26907,26908,26911,26916,26919,26921,26922,26924,26926,26929,26931,26932,26933,26935,26937,26939,26943,26946,26948,26949,26950,26951,26952,26953,26954,26957,26958,26959,26960,26962,26963,26964,26965,26967,26969,26971,26974,26975,26977,26978,26979,26980,26981,26985,26986,26987,26989,26990,26991,26992,26993,26995,26996,26997,26998,26999,27000,27001,27003,27005,27007,27008,27009,27010,27011,27012,27016,27017,27020,27021,27023,27025,27028,27030,27032,27035,27036,27037,27038,27039,27040,27042,27043,27044,27046,27050,27051,27052,27053,27054,27055,27056,27057,27058,27059,27060,27061,27063,27066,27068,27070,27071,27073,27076,27079,27080,27081,27085,27086,27087,27088,27089,27091,27092,27093,27094,27096,27098,27099,27100,27105,27108,27110,27111,27113,27114,27116,27119,27120,27121,27122,27124,27125,27127,27128,27130,27131,27134,27135,27138,27140,27141,27142,27143,27144,27146,27147,27149,27150,27151,27156,27158,27161,27162,27163,27165,27167,27168,27169,27170,27172,27173,27174,27176,27178,27179,27180,27181,27183,27187,27188,27189,27191,27194,27196,27197,27200,27201,27207,27208,27209,27210,27211,27213,27214,27216,27217,27219,27220,27221,27222,27223,27226,27227,27228,27229,27230,27231,27232,27234,27236,27237,27239,27241,27244,27245,27246,27249,27252,27253,27254,27255,27256,27257,27261,27262,27263,27264,27265,27270,27274,27277,27278,27281,27282,27285,27287,27288,27289,27291,27292,27295,27296,27299,27300,27301,27302,27303,27304,27306,27307,27308,27310,27313,27314,27315,27316,27317,27318,27319,27320,27321,27322,27323,27324,27326,27329,27335,27337,27339,27340,27341,27343,27344,27347,27348,27350,27351,27353,27355,27357,27365,27366,27367,27368,27370,27372,27377,27378,27379,27383,27386,27387,27390,27391,27396,27397,27398,27399,27401,27402,27405,27408,27409,27410,27411,27412,27413,27415,27416,27417,27428,27430,27431,27435,27436,27437,27438,27439,27440,27441,27442,27443,27444,27446,27447,27448,27449,27450,27452,27454,27455,27458,27460,27461,27462,27466,27467,27468,27470,27471,27472,27474,27476,27477,27481,27482,27485,27486,27497,27498,27500,27503,27504,27506,27509,27510,27513,27515,27516,27518,27520,27523,27524,27526,27527,27529,27530,27534,27536,27538,27541,27543,27544,27545,27546,27549,27550,27553,27555,27556,27558,27561,27562,27564,27565,27567,27568,27569,27571,27572,27576,27577,27581,27583,27584,27585,27586,27588,27589,27591,27592,27593,27594,27595,27596,27597,27598,27599,27605,27606,27607,27608,27610,27611,27612,27614,27615,27618,27619,27620,27622,27623,27624,27627,27628,27629,27630,27632,27633,27637,27638,27639,27640,27641,27643,27645,27646,27647,27650,27651,27653,27654,27655,27656,27658,27661,27662,27663,27664,27665,27666,27668,27669,27670,27671,27672,27673,27675,27676,27677,27678,27682,27683,27684,27686,27687,27688,27689,27690,27692,27693,27694,27697,27698,27699,27701,27702,27704,27705,27707,27708,27709,27710,27712,27713,27714,27715,27716,27717,27718,27719,27721,27723,27724,27725,27727,27729,27733,27735,27738,27739,27741,27742,27743,27745,27746,27747,27752,27754,27757,27758,27759,27760,27764,27767,27768,27769,27770,27771,27772,27773,27777,27778,27780,27781,27782,27783,27784,27785,27786,27788,27791,27792,27793,27794,27799,27802,27803,27804,27807,27808,27809,27810,27811,27812,27813,27814,27815,27816,27818,27819,27822,27826,27827,27829,27830,27831,27832,27833,27834,27836,27837,27841,27842,27843,27847,27848,27849,27850,27851,27853,27856,27858,27859,27860,27861,27862,27863,27866,27869,27871,27873,27874,27876,27877,27878,27879,27880,27881,27883,27884,27886,27887,27889,27892,27895,27898,27899,27900,27903,27904,27905,27907,27908,27911,27912,27914,27917,27918,27921,27922,27923,27924,27927,27929,27930,27931,27935,27937,27938,27940,27941,27942,27943,27945,27948,27949,27951,27952,27953,27954,27955,27956,27957,27960,27961,27962,27963,27965,27966,27968,27970,27971,27972,27973,27974,27977,27978,27980,27981,27985,27986,27989,27990,27994,27997,27999,28001,28004,28005,28006,28007,28008,28009,28011,28014,28015,28017,28018,28019,28020,28022,28025,28028,28029,28032,28033,28038,28042,28043,28044,28047,28048,28050,28051,28052,28053,28055,28056,28057,28058,28061,28064,28070,28072,28073,28074,28075,28076,28078,28079,28081,28083,28085,28086,28087,28088,28090,28091,28092,28093,28094,28095,28096,28097,28098,28099,28103,28105,28108,28113,28117,28118,28121,28122,28124,28125,28126,28127,28128,28130,28131,28132,28134,28138,28143,28144,28145,28146,28147,28149,28151,28152,28153,28156,28158,28159,28162,28163,28164,28167,28169,28171,28172,28174,28175,28176,28177,28178,28180,28182,28184,28185,28186,28187,28188,28189,28190,28191,28194,28195,28197,28199,28201,28202,28203,28205,28206,28207,28208,28209,28215,28217,28218,28220,28221,28224,28226,28227,28228,28231,28232,28233,28234,28235,28236,28237,28238,28239,28240,28241,28243,28244,28245,28246,28247,28248,28250,28251,28254,28255,28256,28258,28261,28262,28263,28264,28265,28266,28267,28268,28269,28271,28272,28273,28274,28275,28276,28277,28278,28280,28281,28282,28284,28285,28288,28289,28291,28292,28293,28295,28297,28298,28299,28300,28301,28302,28305,28306,28308,28310,28313,28316,28317,28318,28320,28321,28325,28326,28330,28331,28332,28333,28336,28337,28339,28340,28343,28344,28346,28347,28348,28349,28353,28354,28355,28356,28357,28361,28364,28365,28366,28367,28368,28370,28371,28372,28373,28374,28376,28379,28380,28381,28382,28384,28386,28388,28389,28390,28394,28395,28396,28398,28399,28403,28405,28406,28410,28412,28414,28415,28416,28417,28418,28420,28421,28422,28423,28424,28425,28428,28430,28431,28432,28433,28434,28435,28439,28441,28442,28444,28447,28448,28453,28454,28456,28458,28460,28461,28465,28468,28469,28472,28473,28475,28476,28477,28482,28484,28485,28488,28489,28492,28495,28496,28498,28499,28500,28503,28504,28505,28507,28511,28512,28518,28519,28520,28521,28523,28526,28528,28529,28531,28532,28533,28534,28535,28536,28537,28539,28540,28542,28543,28545,28546,28547,28548,28550,28551,28552,28553,28554,28555,28557,28559,28561,28563,28564,28565,28566,28568,28569,28571,28572,28573,28574,28576,28578,28579,28580,28585,28587,28588,28589,28590,28597,28598,28601,28602,28603,28606,28608,28609,28610,28612,28613,28614,28615,28617,28618,28620,28621,28622,28623,28624,28625,28626,28635,28636,28637,28638,28639,28640,28642,28643,28644,28645,28646,28647,28648,28649,28650,28652,28653,28654,28655,28656,28657,28659,28660,28662,28663,28664,28668,28669,28670,28672,28673,28674,28675,28676,28678,28679,28681,28682,28683,28684,28686,28687,28688,28689,28692,28694,28697,28698,28701,28702,28703,28704,28705,28706,28709,28710,28711,28714,28715,28718,28719,28720,28721,28722,28723,28724,28725,28728,28729,28730,28731,28732,28733,28734,28735,28736,28738,28740,28741,28742,28743,28744,28745,28747,28748,28749,28750,28755,28756,28757,28761,28763,28766,28768,28769,28770,28771,28773,28774,28776,28777,28780,28781,28782,28785,28786,28788,28791,28792,28794,28796,28797,28800,28801,28803,28804,28806,28808,28810,28811,28812,28816,28817,28823,28824,28825,28827,28828,28829,28830,28832,28834,28837,28838,28839,28840,28841,28844,28845,28846,28847,28848,28850,28851,28853,28854,28855,28856,28858,28859,28860,28861,28865,28866,28868,28869,28873,28875,28876,28877,28880,28883,28884,28885,28886,28888,28889,28890,28892,28893,28896,28900,28901,28905,28906,28907,28908,28911,28912,28914,28915,28918,28919,28920,28922,28923,28924,28925,28928,28929,28930,28931,28932,28933,28934,28936,28937,28942,28943,28944,28947,28948,28949,28950,28953,28960,28962,28965,28966,28967,28968,28969,28972,28973,28974,28975,28976,28977,28979,28981,28982,28984,28985,28987,28991,28994,28995,28996,28998,28999,29003,29004,29005,29006,29007,29008,29010,29011,29016,29021,29022,29023,29024,29025,29026,29030,29034,29035,29036,29037,29039,29040,29041,29042,29043,29046,29047,29051,29052,29053,29054,29055,29057,29058,29060,29061,29063,29067,29068,29070,29071,29072,29073,29074,29075,29078,29079,29081,29082,29084,29085,29086,29088,29091,29092,29093,29094,29095,29098,29099,29100,29101,29102,29103,29104,29105,29106,29108,29110,29111,29112,29115,29116,29117,29119,29120,29124,29125,29126,29128,29129,29130,29132,29133,29134,29138,29139,29140,29141,29142,29143,29146,29150,29151,29152,29154,29156,29158,29159,29161,29162,29163,29166,29167,29168,29170,29174,29175,29178,29180,29181,29183,29184,29185,29186,29188,29189,29190,29191,29192,29194,29195,29196,29197,29198,29199,29200,29201,29202,29203,29206,29207,29208,29210,29211,29213,29214,29215,29220,29223,29224,29225,29226,29227,29229,29230,29231,29232,29233,29234,29235,29236,29237,29239,29240,29242,29243,29244,29245,29246,29247,29249,29250,29252,29253,29255,29257,29258,29260,29262,29263,29268,29271,29273,29275,29276,29278,29279,29281,29283,29285,29287,29289,29290,29297,29298,29299,29301,29303,29304,29307,29309,29310,29311,29313,29314,29318,29319,29320,29321,29323,29325,29329,29330,29331,29334,29335,29336,29337,29338,29340,29341,29342,29343,29344,29345,29346,29349,29350,29351,29353,29355,29356,29358,29360,29361,29363,29364,29365,29370,29371,29378,29380,29382,29383,29384,29385,29386,29387,29389,29393,29395,29396,29398,29402,29403,29404,29405,29406,29407,29408,29409,29411,29413,29416,29417,29418,29420,29421,29422,29424,29425,29427,29429,29430,29431,29432,29433,29434,29435,29436,29441,29442,29443,29444,29445,29446,29447,29449,29451,29452,29453,29455,29457,29459,29460,29461,29462,29465,29466,29468,29469,29472,29474,29476,29477,29479,29480,29481,29482,29483,29484,29485,29486,29487,29489,29490,29491,29493,29494,29496,29497,29498,29499,29501,29502,29504,29505,29506,29507,29508,29509,29511,29513,29515,29516,29518,29520,29521,29522,29524,29526,29527,29528,29529,29532,29534,29535,29536,29537,29538,29540,29542,29543,29544,29545,29547,29548,29549,29550,29553,29554,29555,29559,29561,29563,29564,29566,29571,29572,29573,29574,29577,29578,29579,29580,29584,29585,29586,29587,29588,29589,29591,29593,29595,29596,29597,29598,29599,29601,29604,29607,29608,29609,29610,29611,29612,29614,29616,29621,29624,29626,29627,29630,29631,29633,29634,29635,29639,29640,29642,29643,29645,29650,29651,29652,29655,29661,29662,29663,29665,29666,29668,29671,29672,29673,29675,29676,29677,29678,29679,29681,29682,29684,29685,29687,29688,29689,29691,29692,29693,29694,29695,29696,29699,29701,29702,29703,29704,29706,29707,29708,29709,29710,29712,29714,29715,29717,29718,29722,29723,29724,29726,29727,29728,29729,29732,29735,29736,29738,29739,29740,29743,29746,29748,29749,29750,29751,29753,29754,29755,29756,29757,29758,29759,29760,29762,29763,29766,29767,29768,29769,29770,29772,29773,29774,29775,29776,29778,29779,29780,29782,29783,29784,29786,29788,29790,29793,29794,29797,29799,29801,29803,29804,29805,29806,29807,29808,29811,29814,29815,29817,29818,29820,29821,29822,29825,29826,29827,29828,29830,29832,29833,29835,29836,29837,29839,29840,29843,29845,29846,29847,29848,29849,29850,29851,29855,29856,29859,29860,29863,29864,29865,29867,29868,29869,29871])

And then, just above this line:

lmdeploy/lmdeploy/serve/async_engine.py

Lines 649 to 650 in 8cc7f43

	yield GenOut(response, self.id2step[str(session_id)],
	len(input_ids), tokens, finish_reason)

you can add this code:

if is_first_output and outputs.token_ids[0] in token_ids_that_start_with_space:
    response = " " + response
is_first_output = False

and init is_first_output to True outside of the loop.

And that fixes it.

[AllentDan]

I am not sure if we should fix it as it produces the same result as AutoTokenizer.decode(gen_token_ids). Let's say, a token_id 1018 refers to _time. No matter whether your question is "once upon a" or "once upon a " (please notice there is a space in the latter one), it generates the same result 1018. But we should append a prefix space for the former question, not the latter one.

[AllentDan]

However, the engine does not care about the question. It cares only about the generation result.

[josephrocca]

I am not sure if we should fix it

I might not be understanding you correctly. LMDeploy's current behavior is not how an OpenAI-compatible API works.

E.g you can try:

curl https://api.openai.com/v1/completions \
  -H "Content-Type: application/json" \
  -H "Authorization: Bearer $OPENAI_API_KEY" \
  -d '{
  "model": "gpt-3.5-turbo-instruct",
  "prompt": "Once upon a",
  "max_tokens": 32
}'

And you will get a time [...].

You can also try vLLM and TGI (including /generate and /v1/completions). They all add the space when there should be a space. It's not just for compatibility with OpenAI - it makes sense from the developer experience perspective. I.e. it's what developers who use these APIs naturally expect.

(Note that the behavior of /v1/completions is different to /v1/chat/completions. I believe the current behavior [i.e. removing prefix space] is correct for /v1/chat/completions, because in that case the LLM is always starting generation in a new message, and never half-way though some text. The AutoTokenizer.decode default behavior is probably designed for chat use case, but I don't have much experience on that so I'm just guessing here.)

[AllentDan]

It should be resolved by PR #1753.

[josephrocca]

I haven't tested that PR yet, but I think since it's merged this can be closed. I'll re-open after testing if there are any issues.

Thanks very much!