input

{
"b" : [9962,6864,248,8860,3276,9467,7222,7843,480,2254,9562,708,8716,5523,6677,7566,1529,4593,9782,4296,2104,9664,8571,1065,2585,5204,1531,4861,8054,8682,3086,2132,8579,3024,6999,9413,6572,6257,5165,4765,3485,7946,5809,5004,9087,4148,1147,4831,4029,1595,7865,9271,1951,8802,3146,9354,6584,1801,3393,607,5533,3862,5305,5431,569,2667,1013,4896,4585,5993,9677,8248,9118,1603,9275,3871,7457,1865,1292,1320,6339,2996,7815,4879,6696,7829,5751,8689,8267,7017,2353,8604,3084,1256,2191,9276,1920,676,6977,5698,6406,7574,2933,7384,2191,5636,3139,7545,7124,1,4049,4574,1468,5200,4365,1684,9453,6397,8699,980,6068,2501,4130,7480,8100,9428,4056,122,28,4494,5184,5312,1155,7276,9835,3871,7350,1838,8287,2334,8079,1001,4002,2753,4562,9679,6878,6553,2913,4004,4472,5866,3804,6957,643,7491,788,5174,4669,1851,3890,9203,6491,8536,375,8631,4983,9722,8468,1536,1405,9949,8432,9243,9680,3638,4181,1366,6224,1119,9175,9821,8837,1178,8535,3307,5147,2640,9876,2520,706,3764,7641,1042,4469,9190,6349,8656,2398,8009,1004,6253,248,5010,1057,3545,6365,523,1486,1281,8706,7123,3903,6143,226,1461,3133,9858,269,6851,7400,1330,6137,7493,339,7110,9252,1429,3833,1769,4261,4608,5107,8321,1063,824,7977,7312,3918,6914,6646,7970,4913,1853,7475,2872,7047,1199,5870,9874,3234,9409,2082,4568,4053,9423,4290,7449,4226,3627,4167,6291,9802,816,4818,4975,5700,4512,1972,8911,4116,8355,1034,2545,6321,1127,289,5986,6467,3212,1481,1762,9475,102,5130,2939,5530,1677,3249,8009,8397,8830,7324,1484,3934,6758,8629,4155,1587,2196,1832,8964,2159,2669,236,320,2755,8114,7156,5548,1420,3610,3699,3163,7645,2438,9655,5185,17,6855,4034,3835,6319,9034,3697,8800,6882,9718,6970,2262,7615,3178,2662,1823,933,7993,9832,9995,1089,5453,8899,6691,1432,2281,6058,7470,2906,5634,7523,5570,3890,1340,7102,7846,5879,1867,1349,4349,3728,3455,1128,9526,4552,9383,5960,7460,6625,7613,6920,4184,3329,9793,542,2454,9048,4858,3913,5494,762,1711,6710,3581,3428,8182,4066,7613,3208,3284,4432,1450,6840,9919,3192,3744,7037,2665,8924,492,7018,8490,1428,4896,2385,4220,400,4834,6467,8949,5931,7218,7981,8162,4556,7234,8446,4306,4220,3646,6947,4899,4207,4818,2734,142,1455,1367,413,4510,1963,9062,8938,1949,5642,252,9979,4651,3651,8467,7774,9317,2357,7096,4269,7512,5447,7963,2189,1096,3336,7810,1404,5469,6554,7943,2980,4845,4494,219,7124,1015,5403,2440,6585,8503,2577,2823,4561,9795,9235,2235,4961,4094,7546,8616,5244,2805,9340,9995,9318,9600,8227,7319,66,22,4145,117,9160,4853,5439,3011,6943,1401,2689,7972,1058,1945,1941,289,9799,6022,3621,3401,5983,7677,3017,6060,5244,1852,3445,1599,4905,8665,182,5253,4947,7765,8824,3135,4552,9201,7425,9657,1476,2016,5334,4400,7162,8586,4912,2576,1965,7716,6754,4145,3045,2019,8350,4797,5962,2190,3355,6626,7240,7098,7360,4580,9804,5231,1074,1335,6291,2531,9315,5269,7924,9885,441,9882,8625,3874,90,9444,5833,937,3118,5130,4682,3108,7566,5443,7523,766,2580,3587,6116,3517,7986,3264,2807,7513,2162,3810,3471,177,7962,7247,6624,5751,6519,5710,6184,5528,167,6825,7459,7270,9113,4399,7854,7233,6335,4375,6810,4663,2155,288,7839,9164,4263,632,1026,9366,5049,3567,5994,3480,2435,2003,3919,7789,8312,5287,1674,8061,8307,9598,5122,3989,8683,1439,7702,4123,5739,4435,1556,8273,322,7374,6964,8403,8652,3523,9788,2913,8099,5763,3527,5104,6273,5095,362,4583,7159,9407,8581,114,5617,1514,2818,7375,3049,4095,1656,3386,122,819,5105,7871,1686,7671,2904,828,853,3440,7941,1589,6299,5431,9055,6570,4849,7567,8600,6346,7160,8028,3372,3501,7913,1226,6512,2839,4587,7920,359,936,867,5400,2359,3591,4610,5823,3297,3638,9378,706,2822,3251,783,8515,9844,3690,6645,3474,8332,3870,1069,625,7361,7092,5502,8001,2070,7040,1061,7517,9861,5832,46,119,9365,3627,910,1281,5054,1167,312,6723,9460,2903,9931,630,8885,2552,204,5065,5958,5863,2296,2816,5705,5505,8231,9842,5299,6617,7623,6384,7212,4999,1164,7978,2604,4134,3718,8010,2468,7904,3533,3461,3492,6474,8734,4367,8771,7168,3473,5545,4984,7201,5971,4754,3825,4000,8993,6767,4622,7364,1741,3220,7008,3711,1311,9841,3636,5069,7883,7385,1021,5472,5852,2160,4775,3446,1333,4925,2984,6495,494,4374,5663,7561,5712,8969,2491,6810,9337,5969,7949,8918,145,9574,5682,6729,2963,2404,4765,1488,7823,2964,1869,5871,6207,6855,6108,9736,9830,4165,8307,56,1930,9509,8056,5342,2816,4835,4288,7639,1958,48,2634,9566,7676,6728,9640,1050,812,250,4294,1856,9985,5849,7231,4407,8654,5090,5991,2356,9084,5844,273,4216,1842,9674,2402,9600,3749,890,5679,2021,6326,7671,8806,5038,7322,9125,89,9199,2336,4479,9172,9046,1705,4829,1921,3893,2932,4407,4932,5530,2449,6908,7580,7333,4763,4474,3126,4205,5239,3195,7931,534,5691,9578,2045,7797,2432,3906,7169,5667,2296,4680,8263,2422,379,1441,1548,3052,7587,3824,1981,6920,3340,627,6041,8664,5324,3668,2077,7504,2617,9845,244,4920,2652,1275,1099,9579,7168,354,6963,417,2330,9859,9090,3102,5507,98,6276,7130,6778,8136,7303,7698,2613,2247,9817,5239,7335,7833,7008,7176,9929,2445,5271,3711,3851,7946,7665,8584,7366,4406,5662,9271,1302,1873,477,1672,1118,2173,1114,5347,9627,6975,8367,2219,7073,3252,3655,7319,9620,1238,4914,5956,4215,4145,2718,9833,9472,6145,8395,6763,5287,4963,3588,6604,4138,3476,1561,5640,1631,3572,3210,8651,691,4007,3792,6730,4031,2812,1598,1987,7542,8972,949,6524,1071,58,2167,8173,3553,5417,951,4951,6652,1904,245,8678,4510,4003,2065,5791,9993,3733,2410,70,9383,1104,5274,3391,8343,390,4283,6919,7415,9785,5637,4395,1871,2715,1563,6796,863,2099,1034,1305,1234,6604,8176,1840,8780,2855,9510,8942,8957,8435,432,8806,2533,5252,7689,9251,9307,7476,5514,1702,1881,2275,6068,1007,3629,7758,9671,2223,9682,8893,8257,8389,8300,6500,9228,4511,1840,563,2709,3804,8896,8167,5819,1571,5868,5391,7505,450,3411,180,7092,9892,5176,7264,6887,2047,2097,320,2111,6683,5196,1655,2495,9985,8306,2730,1546,6343,6487,232,8954,7000,2956,1746,4427,6716,4354,2144,7992,7802,7663,3095,5241,8755,4286,2143,8129,2018,5528,7977,4661,7705,3671,627,1829,6040,8434,4677,5867,4885,9098,4309,2638,3030,4911,132,2287,2249,8226,5126,4076,9853,9195,9592,5478,746,1504,3118,2734,6970,7806,6542,2360,4945,4996,403,1675,2325,2046,603,4809,9013,9285,898,1630,8714,3742,9353,4133,3584,97,748,2304,8098,7173,577,5355,9794,6870,6578,2979,2878,6367,1594,7422,7632,4912,1065,8094,1251,4640,7670,8310,4364,5119,9815,9466,9055,7188,6369,5554,5550,1692,8868,4154,2369,3013,4778,1958,4327,548,8756,5824,1546,1354,3884,7238,6016,3791,1216,6051,5963,1422,7164,4993,7853,6092,9685,1414,5570,8824,6331,1927,9382,7466,8438,6538,4565,8887,1565,5530,9373,1016,3175,160,2865,8149,643,2322,3321,7931,1208,3828,1867,712,8743,338,3511,7642,2870,2221,3388,5395,6697,6343,153,1312,3373,9982,1341,3288,6111,2426,6103,7952,4480,9635,4547,9117,6498,4359,8617,6318,7229,5648,7185,3188,6722,4600,4710,2933,4832,2112,8319,4120,5317,6729,2700,9725,6989,1195,3491,2120,4171,1877,537,251,1466,6514,7381,6928,1538,7507,4729,1248,5943,2862,3698,7771,957,5234,390,4443,9756,3997,9616,3766,1814,153,6507,8510,9423,4145,9777,9314,4386,9270,2518,6953,5586,1900,7219,3460,9277,955,9176,9744,6572,8864,980,5430,6368,1912,5662,7024,2962,4466,7315,4600,2649,4374,1193,9613,9614,3923,2192,928,3839,8920,9791,9012,9581,7705,377,8970,7534,726,1776,9908,1165,2515,4861,9551,5803,1867,522,2277,5799,4858,7722,4223,1077,7515,2636,4551,8659,9506,9760,6341,178,5081,8211,5897,3968,9962,9827,8320,6299,6586,5947,2769,4653,8102,440,4468,1571,6435,3257,3821,343,669,1573,742,7926,4975,638,8053,8619,4806,3604,9098,6051,7234,5078,3526,1611,1484,1590,9992,4864,235,6889,2673,7379,2771,4001,461,6607,1726,7100,9397,347,1097,6064,2243,7992,4566,5040,6238,2072,7412,6125,1433,1797,1144,7173,5158,9591,9812,5141,885,75,1431,6020,624,3224,3814,9489,9375,3806,5956,223,55,3550,8,2254,6275,8517,5126,6823,1469,66,2939,1772,6827,4577,8932,6260,4040,9314,6617,1340,3977,5885,5034,6719,6307,7709,7218,6059,3422,7217,6369,974,1497,4850,588,8332,2485,684,5149,4572,4816,3624,9377,3264,7271,7934,732,5687,8109,1009,7494,3673,2007,6227,9049,5126,5972,2014,6354,8367,4995,3173,9128,9150,3122,4547,5880,409,5244,6478,7398,5084,7114,9502,9520,2742,3184,8865,2670,3545,5946,4217,6566,2649,7287,7135,6915,7568,6338,8648,1454,2972,1212,8354,4954,3972,8411,1725,5325,7653,312,942,9987,4844,8642,5343,8868,6891,4931,8394,8098,5206,7760,8797,2262,2428,6299,3552,4888,3954,9191,2836,6767,7652,8959,7686,461,7595,4524,1766,2592,3847,5330,8412,2476,8107,8914,4806,550,333,6795,2631,3004,8690,4207,9757,9094,1160,9987,42,7954,5503,1834,111,8758,6827,6042,6674,4389,8359,844,1060,8404,7993,6675,4043,2221,4029,2190,1900,9615,6706,4552,4833,2432,7587,6989,7333,5445,7305,7229,8439,6188,9785,1786,1510,9450,5390,6179,8480,9240,4548,4104,5790,6275,2737,4623,1718,6057,7219,7763,4433,1426,3653,3743,2261,5078,2717,252,379,3766,9303,1919,2232,1966,4766,4427,1686,3610,5175,1889,2481,9604,6549,1521,3558,1456,142,2671,3864,5693,8986,9336,6147,5390,6683,1871,58,9690,197,8429,6595,2513,1895,4289,5037,5559,4816,848,3041,7549,1498,4445,4368,3056,6054,2415,2795,4717,6711,9619,1078,364,9985,3163,7258,1973,1412,9124,9990,1802,3111,3772,4362,5408,3006,6693,4358,8428,8098,338,615,1471,8859,4590,3448,776,5520,3538,1856,8792,8746,2088,5607,5720,1172,2064,4496,279,8400,9928,6479,3791,1475,8668,2691,5055,3000,5702,3902,7078,6339,3592,6149,8295,1342,583,4528,3431,2166,2688,5897,1077,3141,1242,339,2205,5557,4920,8332,6231,4110,2488,1917,3038,4383,9406,8059,5026,256,210,7335,8377,7881,7376,4692,7748,757,3511,9394,7294,5760,8156,7330,8857,7086,1493,9172,6611,5158,2506,9982,8067,1050,4792,8323,1493,2658,8043,9540,9164,1884,2531,6025,6706,979,3597,3821,8824,8583,2286,8095,4512,4337,1051,6469,788,4129,824,6751,9953,1310,9859,175,6654,2806,6357,1069,263,7699,6604,6193,5339,5401,2869,2118,4560,5727,4977,694,3692,8321,2943,7329,3917,8104,1131,4783,6955,6141,1360,1834,3641,4779,5342,4441,5070,4098,6189,272,5159,419,7649,8005,9199,9898,825,3463,4806,9080,8401,9902,1630,1698,8758,4944,1335,6506,3138,5977,9946,6067,653,650,8131,5742,3896,9081,3446,8755,9735,6050,3105,6923,4630,3927,9767,7142,2797,8053,4877,1869,9458,3509,6524,2980,3592,6742,8132,3694,4639,8143,513,8856,8068,9346,4898,1370,160,6877,3474,793,7286,5328,1042,8524,5607,2150,7668,841,1428,8694,3621,1813,2962,159,1185,2398,51,2455,6086,2804,4495,7282,7142,904,1410,2153,1473,1580,9954,843,3477,1087,6767,8091,8163,2919,5127,411,7429,1552,3549,7225,9735,1851,8639,2087,4092,4324,2954,3268,5977,7216,5060,4127,3784,9392,6082,6773,2570,2356,313,8544,6020,3297,5466,8536,9824,4646,2970,7752,1814,8951,9081,1824,3208,1392,8297,5022,7981,9126,9146,3532,3321,4870,5702,3373,5967,2393,6376,2822,7807,6934,9243,9005,5739,6325,8136,8594,6521,349,6251,3232,6782,5941,1871,5584,4427,1520,6608,426,2813,8785,5861,3558,2642,8788,3413,3723,7627,5455,1912,8441,3211,176,5032,3542,8745,4481,950,1047,6285,9187,7919,7604,134,6136,8367,6268,7516,4647,7563,6346,6148,5758,5887,9108,854,3142,4419,6529,2812,5023,37,475,7751,9431,5509,5784,6984,7327,781,6699,9224,1088,9536,4319,841,3118,9585,4703,9841,5025,3395,1859,6955,4772,1818,2326,629,2266,11,2718,4916,1169,7145,350,5602,4738,5335,8296,3246,6576,9793,7486,5849,903,7607,5396,4185,9672,5167,3933,8136,1001,7337,7213,867,8300,9574,3253,2280,6810,5976,9267,1545,7007,5582,8177,7863,4067,8547,854,4322,7513,929,9748,992,2007,5550,7049,8347,5448,5769,8556,675,2983,9084,3103,1235,811,1492,268,234,1696,3460,4793,6912,1166,1778,3414,8962,3972,1174,7383,8400,6985,6406,83,6822,9747,2618,315,7486,4161,3021,8630,1604,1969,5081,5020,7339,3425,6752,9221,9234,9075,388,1734,9360,4255,1173,3010,5078,3445,9562,3613,1875,2764,2387,3619,7613,6195,8375,9576,7370,8580,917,9239,2097,7212,3856,3076,1155,1120,3177,792,3190,3277,388,1044,7100,7347,6113,5287,3562,8945,4081,2159,5252,1062,8079,129,7469,6121,2987,6904,7542,1825,9188,7152,6993,9070,9531,3949,3302,1425,1684,8465,4072,3636,902,2089,4333,6029,9134,1671,1917,7610,5746,1345,9569,921,4793,8486,8420,7862,8665,5508,8850,7054,3236,8812,8651,8126,8023,8204,611,3084,1922,2007,2424,6294,6214,4395,2024,4357,5774,7556,6335,5288,1523,4486,1143,1994,2296,6559,7217,9150,5748,1302,1520,3857,2677,9716,6133,7433,2116,6701,9142,7454,6231,9569,6462,4702,8939,7619,886,9625,4299,9324,8746,6295,6811,8287,124,838,290,221,7804,9544,3878,6087,4463,1383,2580,3775,4588,98,7643,2272,3822,3905,4266,7245,2377,8681,1683,7339,4063,1309,9256,1874,2415,8911,6145,6493,8970,412,5903,3698,723,1581,3577,5165,9091,167,3664,2521,4172,4761,3870,7214,611,5072,3167,4965,3152,4440,8744,4077,6565,6138,1674,6365,2760,3429,2663,4276,7829,1510,5997,1064,3191,4040,3500,5590,1490,5076,8944,6023,7113,1454,4716,1281,5594,1464,5141,6336,9454,5609,2770,2478,2233,6214,7921,6297,6122,3818,3243,4486,3618,4691,1801,7361,451,7576,966,8045,3793,9422,9540,9178,8834,7707,3539,9147,446,3192,3778,9033,6173,6777,9106,3593,4843,6379,8632,814,9346,2280,6094,4700,9264,3149,4282,4734,6965,9586,8596,9999,9716,159,8838,9992,2478,3685,3402,1926,9524,2486,8769,5997,9068,4857,4445,3803,6270,8011,2670,3206,1559,8738,9769,109,1089,5824,1245,3327,2070,9981,8597,7032,2125,6310,9137,7715,9698,2629,1123,408,6913,413,4682,1780,7768,4227,4058,2775,6086,729,7398,9186,4540,8462,4276,5949,3018,3865,9238,74,3542,9832,5636,4078,4030,9946,1974,5388,203,3636,2281,2768,5176,2150,3429,5566,1526,819,3115,7708,3126,7602,330,5526,9228,2919,7638,6326,474,7579,7073,1868,2617,8269,6091,5705,7922,1502,7630,209,9138,9345,5135,4806,8557,2240,9271,8639,9114,664,9687,5588,7802,6403,7618,2120,3404,9690,6860,7252,4153,5950,9531,7059,8910,9330,6685,5848,7610,9141,5194,1656,4693,9814,6836,6002,9332,4350,2982,2855,1488,8256,6509,4265,9366,5309,8249,3595,6365,7412,4140,5783,9405,5536,1623,4296,7075,5494,191,4142,1607,3098,7661,6044,3399,5319,3769,4388,441,6953,7336,1038,8652,3027,757,3824,2873,4894,2320,786,9422,6107,5276,2120,9636,3391,236,2445,4717,9875,5988,1228,7055,6150,3287,9012,132,1561,6039,1095,3968,8443,7467,9977,7231,5581,737,7248,3059,1906,830,4219,1150,7638,361,708,2203,5295,994,1450,1864,8024,4782,1578,4441,2353,9223,916,4912,1193,4605,8698,1251,9933,1753,2263,4983,3047,8165,1402,4771,9183,837,8492,7845,4451,733,2884,579,5196,8171,9486,8862,3821,4813,795,6125,9987,2238,6453,5370,9640,3349,2392,708,3032,3633,9106,6762,2259,1053,7172,1895,3882,1437,6605,6328,2801,1833,3505,7335,7969,6607,5549,6742,8094,9022,7560,5934,7955,1576,820,5477,9952,1916,5750,4792,5858,7628,136,641,8851,2704,7827,8183,3661,4521,3854,8767,9111,970,8896,273,8090,2044,466,3636,2401,3168,5936,8176,2865,7187,1738,6020,291,4,5307,4732,1593,3125,614,6766,4798,7659,5593,6343,8628,7518,9316,9251,5528,9977,3174,9146,4358,9889,1899,4925,2317,5472,5482,1145,1584,9927,3168,4067,2848,1559,4184,4768,408,2242,9909,1692,8105,1189,782,528,2918,6325,8065,3425,6368,6489,8168,9785,9303,2780,2746,3043,7858,7861,4813,6140,8217,7034,414,6484,7196,3332,5914,6337,588,6724,6768,1235,7810,5178,6474,472,3610,1796,42,1746,9979,5840,8882,6293,2204,4601,6176,4294,6599,6358,6433,5176,1568,7360,9075,1076,460,1853,139,109,8644,9270,4136,6388,5249],
"a" : [9565,1179,1140,7009,4753,5936,5909,5213,7538,436,8421,3318,3705,817,3056,579,5583,1079,142,3929,9264,2230,4898,5759,8660,1050,3834,8856,5930,9074,2408,4460,252,5695,7887,927,4952,1514,5854,720,2913,553,4154,2783,4252,3179,1768,2256,6647,6717,6091,2565,1436,1896,5855,6816,2193,8754,4153,7236,6060,4636,105,492,4246,9909,8927,7592,874,8219,7205,1652,8121,2492,7584,6889,9865,7281,3621,2063,3144,8268,1761,8438,5131,9559,8283,8004,6325,9179,3636,3798,7304,861,3367,5378,6730,8448,7039,465,1142,300,83,3511,7241,2942,827,5774,5001,4455,9717,6979,1578,1395,7220,3669,8287,4802,8409,1472,2416,1406,2560,9557,4000,9669,1525,3601,2900,3111,1469,8206,3709,6670,4013,796,2844,7049,4015,5105,3727,5325,5770,7345,5180,7032,9943,5663,6610,8337,6743,7454,9230,9495,508,2584,4169,3592,1997,3907,6194,7232,5662,2016,4984,7386,5917,5652,9239,8587,8001,3173,6963,1717,1530,1809,5567,1695,5849,2109,6869,8517,4941,9219,5061,3813,4112,1542,801,1640,1480,3623,9797,5368,2965,1232,4788,997,5425,360,7811,3092,8061,9843,5621,1245,4804,9853,7498,6821,6134,5618,5415,121,7831,9721,3021,8053,7735,448,5365,7884,7409,1305,7157,580,427,6490,4738,8462,7251,9613,6027,7383,484,2197,411,8901,1260,56,3118,125,2129,4986,6978,8464,8921,6748,81,6097,9212,7983,8721,3506,9572,2600,2734,520,2612,8310,2449,6558,7679,3584,2459,4696,4388,1143,7544,9396,6633,7868,3866,6413,1,3986,5666,3059,7772,1720,2133,9530,846,8627,7044,3101,8797,1528,8830,7065,8526,2307,5981,6371,7344,5477,7686,4646,5272,9658,291,191,3877,3039,3139,8794,6047,2488,8247,7,2799,801,5469,1071,9976,3401,3809,3821,3856,2600,1794,4938,9787,3424,500,2655,9026,9228,191,5772,3857,8027,3481,4023,7950,4862,9852,956,5332,8456,8215,6877,902,3985,2731,779,1355,5250,5650,2247,9564,8255,4327,3270,808,2826,148,85,6907,8039,6237,1341,6296,5641,8330,4701,721,5673,7264,906,1795,4791,6164,5040,4926,8342,8491,7641,7423,9854,4255,75,6105,6413,9349,8141,9248,3626,6388,2173,4788,9728,5682,2736,1049,3735,7220,1575,4253,150,8717,2471,1130,9525,6135,9251,5970,1716,108,5510,3106,5060,973,3055,113,5449,3523,1733,2326,8984,5229,9293,7589,8650,3936,4254,7068,4209,4500,9652,9849,7644,3851,6614,5111,6985,3812,8598,244,4617,9082,7400,6029,3970,4593,9224,4251,5524,6096,4437,5432,6065,6518,9116,2922,4513,4303,1340,8490,8780,4027,6511,8552,5869,6313,6831,1995,87,4688,9818,672,4614,9811,9642,9710,3337,8518,1283,8023,1033,8748,7695,7031,5914,7779,831,3996,4308,8574,3307,9281,992,4604,9085,247,6043,9770,4569,8182,6302,1011,8003,8772,5264,9603,4952,7419,3548,4881,3608,3472,7379,6862,9798,3221,5312,2983,6,7435,2143,8733,8424,8417,2162,3444,880,3561,8128,3450,8524,1588,1160,6850,6244,30,5167,3970,6109,9517,462,5242,9244,5085,5256,534,2706,7796,502,5850,2078,4881,3041,2705,8464,3466,5936,4610,1431,8124,9609,7771,8805,8138,6630,551,9226,1749,5911,9911,1797,2849,8870,1375,117,4816,3912,363,8023,1198,4834,3978,5108,3372,2007,1929,7110,8538,8541,9544,5564,5119,5577,5031,2150,3883,3446,1886,6942,166,478,9215,9408,9233,3428,4763,6738,9328,5660,7387,1503,2443,3112,9535,1587,7256,8102,2186,9989,8431,1977,6619,1755,8621,6854,9782,3139,9584,9780,8953,2607,3188,7092,6142,4844,9579,6052,8911,9527,6245,9325,4559,5317,7994,9060,1329,8308,9076,9158,6690,8842,7482,7132,2480,9212,3328,1927,4511,8180,6869,1117,3830,9592,1843,7266,6301,1706,3331,3884,390,9047,9480,5514,9093,4965,3541,5424,1334,1891,1803,6302,1848,3084,8049,6124,9808,4493,9654,8083,9974,23,9162,9397,297,6256,1490,1415,8724,8385,1081,7450,3701,5461,1250,1375,7404,1530,4229,1583,7534,8395,7255,1129,1164,6042,1108,7393,4223,712,8438,29,5814,6177,6134,9693,8924,983,1465,6864,5257,4068,7002,8928,1646,3367,1479,3666,6104,994,3358,4686,4328,8365,8839,6733,7512,7347,1555,5048,2448,8065,5861,5489,8024,2820,9435,5011,5166,446,2428,8711,9792,3145,1420,5264,3660,2437,7218,8748,7828,7174,7641,6566,1282,3156,6344,5091,8642,3705,4436,7162,1762,9783,3829,9692,243,4340,8619,4025,272,8878,6711,1107,2813,8780,1107,7956,6560,8264,2012,4616,9400,1795,4647,9694,2591,6336,7169,6645,64,8731,9269,66,2662,2709,5377,9995,7479,1957,7949,4586,4440,1759,8839,1343,3713,6521,5976,4777,6466,3063,2724,9887,3793,2100,255,1967,1784,4189,5504,1425,8452,5531,3677,9537,3290,6305,7933,9133,1799,5275,5718,9312,6697,954,5574,12,3736,7937,2838,4311,7149,5696,4213,2316,7416,3384,4725,7258,6740,2790,801,736,9808,1006,4236,7177,2347,9927,9379,4337,2267,7639,778,4307,5422,408,1718,2999,6662,6023,458,1762,841,2155,691,1270,2494,4585,6774,1932,9956,6144,211,7411,6871,7348,7579,1755,326,8801,2035,5220,5899,3840,8182,7290,1585,4978,9446,2117,8027,3693,6682,1631,7910,6213,2175,5538,7403,4485,208,3490,1675,3569,8240,414,190,4594,4617,3782,4585,6789,5135,2609,4737,9907,6939,3764,7516,8448,7334,7980,8073,1472,2438,3418,4689,8589,3114,9762,7526,2730,911,5036,6736,6031,7979,8543,8687,4562,9206,6505,6572,6482,1840,5762,4208,4036,2614,9057,3507,857,988,9231,5919,2778,3846,1003,4635,7712,5459,9424,1251,6862,8008,7515,6674,8007,3208,3756,6131,2765,320,4226,4920,6798,2438,6164,2347,3388,6221,6782,7327,4073,4690,2132,115,1621,3033,5540,8514,8810,7775,3217,8923,4741,8116,731,9579,8404,3971,7203,8919,5307,5591,2328,76,1107,9010,405,9143,4802,5911,3004,9726,3056,209,5330,9433,7978,6884,9839,7887,4114,2701,9184,8446,8386,9952,4644,1083,1249,3327,5401,935,8529,5938,6724,1913,685,3663,8044,2456,1931,3191,7676,8173,562,3374,4863,1113,4058,6947,7821,8744,1571,347,9480,1972,6588,1457,6571,5039,1052,5715,5891,6327,4421,7665,7461,5220,9828,1527,9372,4258,8176,5585,3269,3694,7656,6332,1409,6297,9281,936,2225,8212,4609,6401,9890,4360,15,3383,8577,4146,9872,4025,4513,4490,8348,7072,5437,2281,8432,5511,931,6341,621,4223,6383,9101,4807,6215,3161,2940,6330,1512,6009,4229,637,6139,6804,8132,788,6348,8408,155,7761,4213,9237,7150,6586,7405,1324,2774,4159,2911,5660,4464,1442,4336,9612,3391,1573,7436,6362,6552,1745,2117,9523,8472,2373,3339,3039,9648,8406,1520,1712,6897,2051,8332,1159,7138,6649,3950,4930,4298,9334,6206,7554,3416,2169,8309,6497,5515,5467,3184,9242,5063,2274,4850,7612,7050,7867,6706,9749,36,295,8449,4226,5035,2543,2041,3113,9570,7644,4338,1034,4870,8411,6714,5140,8672,6798,7225,9314,418,6863,5670,2409,4803,3615,520,3077,7768,950,7157,4388,7618,4810,7833,2666,9786,8676,9411,4456,4849,6108,9955,5672,290,8704,2696,6040,5162,9452,547,947,8702,3154,210,6595,8759,2143,7024,7902,3269,3944,1380,9165,6920,3998,693,5889,1021,4858,6345,4012,38,7565,9607,1296,6179,6294,1065,2347,1159,3197,4833,3910,1943,3002,6351,9741,5854,8621,9405,6885,2624,1847,4107,3152,7968,3193,8401,1657,8082,9127,2394,4603,3357,4052,2311,269,4911,6921,5100,4446,4725,9563,7302,3987,7396,1437,890,3276,1187,1769,4390,3941,9545,8033,2010,5527,489,6179,9103,4342,9634,3237,3637,6743,6643,7625,1420,9093,36,8270,1968,4216,7240,94,4733,8484,8731,9154,4432,8240,6575,2877,4806,3638,2196,4502,7404,8861,3674,2425,5836,8211,4863,8821,2859,3394,7304,9186,9038,5226,9881,2491,6531,6029,6863,6281,100,1691,5710,7206,8268,7375,3968,7341,7308,549,973,6408,1394,7897,9097,3298,646,1768,7559,6593,2132,8188,5913,1381,3855,1560,836,7924,4499,2780,6431,8642,1536,1524,31,5461,6358,2624,9290,8452,8593,4028,2677,927,4114,8341,6051,7745,6682,1528,3775,6648,2187,9247,436,2562,8559,2683,9716,4164,4698,876,9684,9404,8806,7997,7089,1421,4002,6094,8248,6560,1526,711,2694,4845,9995,5979,5574,9686,1643,5897,2944,701,9545,9894,8672,715,8334,4190,491,7581,9244,1153,5080,9698,6122,1088,2915,5325,4602,3833,7848,2647,2390,8035,9701,758,2177,7648,5225,5522,9485,4830,9349,4419,4882,1357,8178,4997,1146,5185,1354,2774,1106,1566,8266,8346,4356,7602,3292,1828,1380,598,6823,967,6752,6437,2720,6890,5425,6829,5610,4711,6605,4489,3306,9219,9759,1034,8166,6147,8339,9416,3441,6148,7060,1813,2587,4128,7690,2897,3665,5898,4938,7595,1620,5548,7657,5492,5926,5603,6166,7975,1516,5979,6651,4805,6197,7576,2907,4130,7359,8898,6641,4963,2564,520,515,6113,4077,7055,189,1688,334,9886,7743,9226,3973,5563,8280,6007,7366,5713,8227,5327,9177,5187,9224,346,1655,683,2821,5561,4020,2964,9619,5688,688,8325,4044,2521,2896,2894,7759,2668,5339,4390,1299,3412,8010,5016,3261,4978,7485,2854,1551,2525,7935,20,2723,8740,9816,5629,8288,8686,1301,9778,3878,453,3722,1060,5172,3806,7313,4620,9512,2814,9259,2154,5738,1485,38,9566,6257,5232,9569,2661,6701,8125,4018,2392,5327,1501,6194,3688,4345,8211,5313,4325,2671,472,796,265,3496,8233,3135,961,7794,8744,13,9285,1419,2776,8971,6850,5802,9731,8207,4692,2356,6233,2255,350,3883,4866,9701,7266,4631,843,8947,2260,6025,1407,3349,9422,6896,2611,6077,6326,3432,816,3713,4157,9940,6729,1131,5009,8825,8335,6989,7999,7481,386,9897,3569,2229,3886,8401,1651,1159,7006,1036,183,2247,2456,4730,5513,6452,8920,2341,3133,6166,5156,813,6215,1409,5352,473,1278,8189,5061,5546,3744,3789,3654,5585,840,1876,9176,4103,6915,6249,9984,3270,78,1570,3259,2944,5685,8065,8157,8102,8679,3142,8897,8241,1701,7470,7928,1549,7591,8647,5244,401,6899,7319,9603,6903,4519,9986,9557,6422,5272,6232,4956,3186,5068,4050,2258,2206,6922,4710,7763,24,8905,926,4041,2722,4035,5867,1279,978,4097,4801,759,9856,6752,6524,1971,9648,9129,986,9172,3647,7314,442,3699,6779,752,4291,440,9687,4763,4108,7678,2747,2103,5937,9141,8533,2731,4202,5682,8310,9561,3694,5350,3182,5627,341,7301,3971,7014,3513,7030,2054,8863,9361,2582,1431,7923,7412,8692,2237,2671,402,4914,2220,8833,2882,384,8986,9766,9988,9576,7510,6082,1087,6287,2480,1177,4323,949,5180,309,8748,4274,8285,9813,4669,349,6376,5421,2609,3843,1044,5214,7910,4378,8919,5881,7447,7887,3493,7090,8717,6196,7913,6978,2100,2743,2875,5388,4723,5138,7000,7395,1323,8444,1018,8458,8658,4771,3029,7547,217,1057,6625,3347,2835,609,7221,239,517,9792,4822,324,6563,7559,4015,2194,3249,4742,9761,3295,9589,5984,4493,5996,7291,2211,2135,3947,5665,9948,6157,6314,58,137,9307,3446,861,5677,1267,6336,1475,5129,9771,2660,7052,918,1022,8948,1111,9394,2949,9780,5524,2402,4401,7277,4646,535,422,1871,342,8867,2825,4030,3168,410,305,7690,2023,3038,7994,697,6644,6013,6750,6513,3811,8824,9985,9064,9801,3021,892,5093,2628,5170,6681,4700,4079,6260,3188,4361,9570,9839,7188,2410,7403,8246,1911,5016,273,7632,6072,8156,1661,2208,665,7523,3310,6015,8176,9369,8707,3778,1691,9746,7006,6431,2616,9934,4061,171,1040,8785,7351,3761,1449,8506,4189,3830,2345,4919,8171,3548,2272,1515,1020,6589,8078,3418,1268,1471,6316,9914,7117,3832,2939,7157,6967,5532,2775,5626,3243,4716,5305,363,5054,46,7580,3625,9485,1495,7840,1839,3873,784,1020,4565,8745,9801,6886,8212,821,4834,9373,211,6625,9726,7991,6776,3076,6475,7722,6435,6198,8846,6750,9367,771,8088,8058,7279,4809,4443,6095,5996,4654,7500,6429,4964,1171,9523,3073,2194,9401,8760,7512,5858,8872,7407,5389,8652,9535,1220,8006,3029,6617,8506,6878,6094,6233,3368,1539,1763,5737,3967,3375,9534,1899,9416,2262,6110,263,1983,6137,7398,9003,5404,1236,8637,9670,9932,1655,3005,5453,6987,2730,5133,4493,3793,1096,3337,8224,9041,4730,9679,3293,7252,5868,9093,8011,5853,4774,4020,8638,3791,7757,1458,3919,17,348,4284,565,1250,5137,9901,3086,3047,5975,2292,651,8362,1680,7917,9713,3138,8174,3481,278,3107,3191,4068,5765,1541,5771,3030,7156,7568,4862,7220,3191,8097,4090,235,1335,341,1351,5737,5860,8312,2799,8637,3392,892,1317,6015,1876,9708,1740,9158,3456,4423,2653,1385,6385,8995,8619,1263,6229,5376,1738,8678,8533,5427,6641,3651,9425,3262,9145,6084,1515,4560,8557,9092,6597,754,1429,2906,6315,9502,5826,4192,7156,6308,1391,2890,5012,3874,8989,3316,8174,2533,3995,1330,2141,8766,3916,3058,1414,7045,2147,3615,9475,4373,2157,1069,1974,9539,7498,2268,1010,2203,2002,8753,7462,9923,6177,1888,5408,8546,358,4532,304,1248,6480,2865,1994,6791,4381,2007,1738,9184,1415,7421,5246,5586,942,490,8834,3322,5776,8250,7795,994,6438,4768,2058,9561,4332,9222,8178,2732,3162,274,4066,4168,4337,8210,7034,2189,1578,1796,5872,5468,7641,4809,9903,6064,2756,8714,4453,3483,8467,3536,1370,1907,3593,9977,4052,6885,4191,7526,9354,7425,6552,6058,9681,5703,6309,3069,9163,1033,7382,5018,2422,9841,4749,4574,1934,7548,5310,1959,2454,286,4951,6339,8957,1609,8441,6134,3828,3330,5040,8584,3557,2774,4613,8242,5999,3096,3622,4320,5414,1518,921,7298,9792,9945,1924,8433,6191,3565,8490,204,1344,222,766,8505,7226,4327,8470,7741,8032,8593,2220,9898,6735,1298,8473,8586,3102,749,6216,5600,615,4253,4192,7440,7932,5770,9430,5133,245,5759,2192,7400,4948,1830,5904,2212,2554,2525,9476,7467,1058,33,3750,9692,9637,9618,4061,8583,3472,3869,584,274,6926,8860,8950,3459,4889,243,8829,7910,3524,9134,423,9548,3728,7449,4529,7285,3874,809,633,1159,3029,9052,2871,612,7481,1011,3000,2692,6698,3980,2,6886,1224,2443,9570,6493,9770,9488,3340,753,5275,5695,5212,7211,5867,793,6438,4045,3532,9924,8169,9077,8806,9801,8931,2993,7244,6830,6062,2458,9299,2038,1337,7464,1356,4643,2936,2390,6193,3385,2511,8808,8455,2975,3824,779,7053,2312,2772,4883,5724,3796,9682,1880,5381,6292,6053,9546,1463,6649,6544,9110,5192,5157,2416,3605,6646,4942,1564,7702,3857,5462,1277,7055,5521,16,1378,5548,6817,3867,6469,6519,9706,9777,64,7269,6079,3103,448,3931,9982,3727,4819,7700,4872,315,4078,7176,4658,4176,9316,4594,8519,5491,7028,1325,9770,8324,2522,9120,3040,6031,5491,5753,6251,5674,2638,7290,9365,8744,146,4629,3017,5277,3187,3147,6310,5134,3242,8045,9429,4808,7240,7271,1901,7193,1223,5728,156,8450,7425,3179,3402,3575,9297,5490,2509,7596,190,4530,6067,2811,93,6934,9478,9449,3513,9811,776,9799,1876,5247,4980,683,6769,1846,7719,7089,9088,5933,7413,7572,6097,8552,6574,9651,4532,985,1260,2403,1951,582,8921,3140,2900,5764,3049,1704,7090,1326,127,9206,9592,8937,5957,6000,251,166,4864,1091,9426,5439,3482,449,1785,9825,9853,7978,9039,2167,1201,9802,9449,925,1827,7504,614,8052,1915,936,5215,8824,8477,2175,6152,8870,9091,4795,2244,8793,4912,3562,5264,1043,7180,9984,846,4561,938,3023,98,9968,5956,8348,9683,7170,4851,8598,785,9119,4983,8438,8431,9166,7635,9695,2895,5666,7119,6382,3127,376,7457,408,7468,7694,7013,2600,8730,1607,295,6116,5706,3815,2040,7207,837,3435,2978,2800,5778,1092,533,9894,8186,9125,5828,4434,4814,4404,2488,5064,5536,7030,5816,7636,9616,6625,5212,2872,6308,4750,6051,4515,8741,1166,9336,310,937,9507,4908,6283,2795,7863,3504,5900,5396,299,6896,7284,6806,9178,1738,1179,1902,8179,6240,2261,9081,9110,213,9690,732,3991,5341,1101,1326,7629,7484,5999,2424,6978,4545,742,2195,1883,2649,909,655,3058,7154,3390,2599,1898,2094,2657,8919,6921,5531,5398,7459,1167,7439,8956,348,3432,2879,5886,5675,5701,7465,368,2645,5459,962,1806,7038,6401,7407,564,2207,9096,3311,9869,7459,1694,2721,681,8182,5296,385,929,2138,3479,3111,4651,7150,244,3361,6949,7728,3366,3575,3993,9771,9145,5558,2115,6344,4728,9728,6838,8904,2059,433,3598,3988,6883,4351,1049,3149,9467,3569,1918,6180,8346,166,6555,1265,8933,3362,5143,1221,6325,4676,9351,6727,7621,9385,5934,6753,3800,619,6848,2627,3736,1212,1318,2636,962,2590,3253,8922,3781,8098,5716,1951,1826,619,1771,2184,1206,6292,1042,5416,1786,2333,861,5300,5811,2762,7124,3787,6306,3535,7961,9885,8359,2500,6383,8922,8847,4438,2607]
}