add reverse iconv mappings for JIS-based encodings

these encodings are still commonly used in messaging protocols and
such. the reverse mapping is implemented as a binary search of a list
of the jis 0208 characters in unicode order; the existing forward
table is used to perform the comparison in the search.

2 files changed, 612 insertions, 1 deletions

diff --git a/src/locale/iconv.c b/src/locale/iconv.c
index 01f1752..1784dc9 100644
--- a/src/locale/iconv.c
+++ b/src/locale/iconv.c
@@ -80,6 +80,10 @@ static const unsigned short ksc[93][94] = {
 #include "ksc.h"
 };
 
+static const unsigned short rev_jis[] = {
+#include "revjis.h"
+};
+
 static int fuzzycmp(const unsigned char *a, const unsigned char *b)
 {
 	for (; *a && *b; a++, b++) {
@@ -134,7 +138,7 @@ iconv_t iconv_open(const char *to, const char *from)
 
 	if ((t = find_charmap(to))==-1
 	 || (f = find_charmap(from))==-1
-	 || (charmaps[t] >= 0320)) {
+	 || (charmaps[t] >= 0330)) {
 		errno = EINVAL;
 		return (iconv_t)-1;
 	}
@@ -192,6 +196,25 @@ static unsigned legacy_map(const unsigned char *map, unsigned c)
 	return x < 256 ? x : legacy_chars[x-256];
 }
 
+static unsigned uni_to_jis(unsigned c)
+{
+	unsigned nel = sizeof rev_jis / sizeof *rev_jis;
+	unsigned d, j, i, b = 0;
+	for (;;) {
+		i = nel/2;
+		j = rev_jis[b+i];
+		d = jis0208[j/256][j%256];
+		if (d==c) return j + 0x2121;
+		else if (nel == 1) return 0;
+		else if (c < d)
+			nel /= 2;
+		else {
+			b += i;
+			nel -= nel/2;
+		}
+	}
+}
+
 size_t iconv(iconv_t cd, char **restrict in, size_t *restrict inb, char **restrict out, size_t *restrict outb)
 {
 	size_t x=0;
@@ -493,6 +516,79 @@ size_t iconv(iconv_t cd, char **restrict in, size_t *restrict inb, char **restri
 				}
 			}
 			goto subst;
+		case SHIFT_JIS:
+			if (c < 128) goto revout;
+			if (c == 0xa5) {
+				x++;
+				c = '\\';
+				goto revout;
+			}
+			if (c == 0x203e) {
+				x++;
+				c = '~';
+				goto revout;
+			}
+			if (c-0xff61 <= 0xdf-0xa1) {
+				c += 0xa1 - 0xff61;
+				goto revout;
+			}
+			c = uni_to_jis(c);
+			if (!c) goto subst;
+			if (*outb < 2) goto toobig;
+			d = c%256;
+			c = c/256;
+			*(*out)++ = (c+1)/2 + (c<95 ? 112 : 176);
+			*(*out)++ = c%2 ? d + 31 + d/96 : d + 126;
+			*outb -= 2;
+			break;
+		case EUC_JP:
+			if (c < 128) goto revout;
+			if (c-0xff61 <= 0xdf-0xa1) {
+				c += 0x0e00 + 0x21 - 0xff61;
+			} else {
+				c = uni_to_jis(c);
+			}
+			if (!c) goto subst;
+			if (*outb < 2) goto toobig;
+			*(*out)++ = c/256 + 0x80;
+			*(*out)++ = c%256 + 0x80;
+			*outb -= 2;
+			break;
+		case ISO2022_JP:
+			if (c < 128) goto revout;
+			if (c-0xff61 <= 0xdf-0xa1 || c==0xa5 || c==0x203e) {
+				if (*outb < 7) goto toobig;
+				*(*out)++ = '\033';
+				*(*out)++ = '(';
+				if (c==0xa5) {
+					*(*out)++ = 'J';
+					*(*out)++ = '\\';
+				} else if (c==0x203e) {
+					*(*out)++ = 'J';
+					*(*out)++ = '~';
+				} else {
+					*(*out)++ = 'I';
+					*(*out)++ = c-0xff61+0x21;
+				}
+				*(*out)++ = '\033';
+				*(*out)++ = '(';
+				*(*out)++ = 'B';
+				*outb -= 7;
+				break;
+			}
+			c = uni_to_jis(c);
+			if (!c) goto subst;
+			if (*outb < 8) goto toobig;
+			*(*out)++ = '\033';
+			*(*out)++ = '$';
+			*(*out)++ = 'B';
+			*(*out)++ = c/256;
+			*(*out)++ = c%256;
+			*(*out)++ = '\033';
+			*(*out)++ = '(';
+			*(*out)++ = 'B';
+			*outb -= 8;
+			break;
 		case UCS2BE:
 		case UCS2LE:
 		case UTF_16BE:
diff --git a/src/locale/revjis.h b/src/locale/revjis.h
new file mode 100644
index 0000000..3ab369f
--- /dev/null
+++ b/src/locale/revjis.h
@@ -0,0 +1,515 @@
+31,80,81,87,14,299,74,61,12,344,62,63,1280,1281,1282,1283,1284,1285,1286,1287,
+1288,1289,1290,1291,1292,1293,1294,1295,1296,1297,1298,1299,1300,1301,1302,
+1303,1312,1313,1314,1315,1316,1317,1318,1319,1320,1321,1322,1323,1324,1325,
+1326,1327,1328,1329,1330,1331,1332,1333,1334,1335,1542,1536,1537,1538,1539,
+1540,1541,1543,1544,1545,1546,1547,1548,1549,1550,1551,1552,1553,1554,1555,
+1556,1557,1558,1559,1560,1561,1562,1563,1564,1565,1566,1567,1568,1584,1585,
+1586,1587,1588,1589,1591,1592,1593,1594,1595,1596,1597,1598,1599,1600,1601,
+1602,1603,1604,1605,1606,1607,1608,1609,1610,1611,1612,1613,1614,1615,1616,
+1590,29,28,33,37,38,39,40,342,343,36,35,338,75,76,263,77,337,266,267,265,268,
+300,301,302,318,303,319,281,282,60,324,326,70,315,297,298,288,287,328,329,71,
+327,325,321,65,320,68,69,322,323,285,286,283,284,316,317,1792,1803,1793,1804,
+1794,1805,1795,1806,1797,1808,1796,1807,1798,1819,1814,1809,1800,1821,1816,
+1811,1799,1815,1820,1810,1801,1817,1822,1812,1802,1818,1823,1813,258,257,260,
+259,262,261,256,93,90,92,91,349,89,88,73,72,341,340,339,0,1,2,22,24,25,26,49,
+50,51,52,53,54,55,56,57,58,264,269,43,44,32,
+768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,
+787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,
+806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,
+825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,
+844,845,846,847,848,849,850,10,11,20,21,1024,1025,1026,1027,1028,1029,1030,
+1031,1032,1033,1034,1035,1036,1037,1038,1039,1040,1041,1042,1043,1044,1045,
+1046,1047,1048,1049,1050,1051,1052,1053,1054,1055,1056,1057,1058,1059,1060,
+1061,1062,1063,1064,1065,1066,1067,1068,1069,1070,1071,1072,1073,1074,1075,
+1076,1077,1078,1079,1080,1081,1082,1083,1084,1085,1086,1087,1088,1089,1090,
+1091,1092,1093,1094,1095,1096,1097,1098,1099,1100,1101,1102,1103,1104,1105,
+1106,1107,1108,1109,5,27,18,19,3915,8793,6934,10843,7493,6671,7492,4379,10291,
+11294,12033,4110,4685,12034,7939,12577,5173,10521,7494,11549,10529,12035,8773,
+12036,5465,12037,4924,8719,6982,12038,12039,12040,9748,5174,9750,9538,5922,
+10770,18472,12041,7495,12042,4372,5444,5967,11080,13573,11343,9564,4868,5140,
+12043,12044,11546,11292,8263,12046,6741,9554,12049,4125,5950,5949,3909,11818,
+11817,6418,3840,12050,12051,12052,10771,12053,5969,3910,10833,5211,5212,5213,
+9025,11547,12054,12055,12056,7724,7193,7725,12061,12059,12060,5175,6402,4431,
+12058,12057,10504,6693,6692,8477,12062,10292,8006,23,12063,12065,8516,11584,
+3881,12064,4381,5411,8774,5710,12066,9731,4938,12067,3882,5951,4939,10329,
+10001,5176,4432,12102,9248,9803,12069,10011,11585,7692,6694,6742,4383,9008,
+8705,12073,3883,9026,7194,6419,11267,8493,4382,12072,11293,12068,12070,6477,
+12071,13315,12079,12082,12080,4385,10522,12074,12078,5970,6695,4869,12083,
+12075,11586,6743,12076,12081,12084,12077,5376,3884,5377,4384,13316,10840,
+10317,5971,7694,11542,10551,5655,8452,4419,7218,12088,12093,12091,12086,8462,
+12089,12092,12090,10556,12087,7693,10834,12094,12095,7171,12108,9775,10261,
+12103,10575,4373,12107,12101,12110,8241,5923,9787,16166,12109,9276,12098,5973,
+5972,12096,6969,12104,10574,8748,12100,5712,12097,12105,12099,11568,12106,
+11808,5445,5711,12111,12112,12116,3885,10543,12115,12114,12118,12117,9027,
+5713,12119,6948,8453,9028,5461,12120,5141,12121,12123,10772,5701,6672,10070,
+12122,6436,11298,12125,12290,12124,6435,7260,5656,12291,5422,12288,12289,9486,
+8283,5378,10796,12292,11548,12293,12296,12294,8237,12295,12297,12299,12298,
+10535,5142,12301,12302,4366,12300,6995,12305,12304,12303,12085,12306,7261,
+12307,11268,11064,12309,12308,12311,12310,12312,12313,3923,5908,5658,7195,
+8794,5379,8007,5974,6221,12315,11047,9253,6744,12314,12316,9277,4692,12317,
+9565,8211,12319,12320,9995,5975,11802,12321,5381,10523,8469,5456,
+9236,5714,12322,12323,9537,4158,12326,6492,12325,6437,12327,17741,12328,10784,
+12329,12330,12331,7496,6955,4870,12334,12332,11036,12333,10297,12335,12336,
+12337,9278,12341,12339,12340,12338,6466,12342,11081,11587,12343,7943,12344,
+7225,12345,8795,11550,9279,12580,12346,21252,5412,12347,10813,7239,8539,12349,
+9539,12350,12351,4621,12352,5382,9515,4185,7215,9984,12353,9280,7726,12354,
+10507,7993,4865,4872,12355,12357,5657,12356,11602,7240,10012,10539,12358,
+11351,12359,12360,9309,12361,7944,6493,5715,12362,6696,6222,9029,12364,8454,
+6478,12365,12366,8207,12363,12368,10773,6211,12367,5716,6461,9804,12371,12369,
+10330,7497,12378,4675,12372,12370,8238,12374,12373,4643,5695,12379,11532,
+12375,12380,12377,12376,11566,5976,4386,11603,7252,9271,6212,12545,12546,
+11588,11786,12548,5977,12547,4622,12549,10805,8987,11269,10552,12550,20276,
+9487,12551,4873,11026,7424,12552,10566,12556,7945,12553,5423,12554,4874,5645,
+12557,12558,12559,12560,6970,5978,11069,11079,9558,10576,12561,12562,12564,
+12566,12565,12567,4380,10795,6491,12568,8248,7425,5384,12569,10042,12570,
+12571,12572,12573,10243,5447,3908,9502,12574,7196,8008,12576,12575,7426,5952,
+12578,10013,12579,10043,8467,8525,5383,9549,8720,9805,10797,12581,8009,5652,
+12582,12583,4107,3924,4940,8455,5168,11344,12586,4374,12585,5385,12587,11088,
+12588,11569,5979,5909,12589,12591,12590,7742,4120,4157,12592,12593,5910,12594,
+5197,6673,12595,10835,6420,5177,11270,8239,10014,7004,7206,6983,
+6996,7253,10015,12598,4130,8240,5980,5924,5446,12602,8704,8541,5386,7427,
+12603,12601,4387,8517,6935,6698,4101,4687,6213,6697,12604,12605,5160,4645,
+6214,5159,9022,4100,9488,11037,6144,11352,9254,5981,5646,12614,5442,10793,
+10044,12613,4925,12608,12609,12611,12612,5178,7744,10508,12610,12606,5954,
+12607,11779,10577,9031,5953,6223,12615,9532,12619,7005,6997,12622,12620,11010,
+12617,12626,12621,12624,5925,11038,12625,12627,12629,6479,11809,12618,12616,
+12628,12623,12631,12802,12633,12637,12800,12634,12829,6472,4624,12632,12804,
+3925,12803,3844,10281,12801,12635,12630,12636,6439,12805,3926,12814,12806,
+12807,7428,10824,12812,12811,9230,12813,12810,4115,6421,7695,12808,9281,12809,
+3841,12819,11266,7430,12825,12824,12815,8482,12816,8526,12821,7429,12818,
+11075,5659,12822,12823,12820,12826,12817,12832,12837,12833,12828,12838,8208,
+12840,6145,12830,8796,12834,12827,4876,4941,4676,12835,12831,5717,12841,12839,
+8242,5161,5387,12836,5459,4131,12845,12843,13062,12848,12842,12846,12844,6699,
+12847,12850,12855,12853,12852,8721,4388,12849,12851,7431,4114,12854,4413,
+12865,7515,12861,12859,12860,12862,4124,8216,12856,12857,4697,12864,4942,
+12867,12863,12866,10509,9524,10007,12869,12868,4644,12870,12873,12872,12871,
+9752,12874,12875,12877,12876,12879,12882,12880,12878,12881,12883,12884,12885,
+12886,12887,12324,7003,6700,4434,3927,8739,12888,6403,3886,7741,12889,5926,
+6224,12891,12890,10559,12892,13056,12893,13057,13058,5718,4159,13059,13061,
+13060,
+13063,9273,13064,3860,6462,5660,8750,13065,13066,13068,13069,6467,5424,10774,
+13067,13070,6432,6146,13074,6404,8722,13071,9017,13075,7745,13073,13076,5662,
+13077,13078,6147,4639,13080,13081,13082,13079,13072,13083,13084,10819,7498,
+13086,13087,13085,13089,9751,3911,10293,13090,7516,6936,9788,4943,6474,10808,
+9489,5719,8494,13088,13091,8483,13092,13093,13095,9032,4877,21248,4160,10578,
+7499,9255,6469,13101,10524,11580,4435,13097,8217,13100,9282,9256,9283,10008,
+9004,6440,13096,4181,9237,13098,13094,7727,13102,7213,5388,13103,10567,8284,
+8997,13105,10798,13106,13111,10510,13110,13104,13107,13109,6405,10536,13112,
+8740,4436,7500,13114,13113,6215,13115,13117,13116,13119,13108,13121,13120,
+13118,6701,7728,8243,13122,7963,3916,9795,9018,13124,13123,13125,13126,13127,
+13128,10544,13129,4389,13130,11291,4623,12584,7207,8478,13131,11082,11027,
+13133,8518,9238,8479,10294,13134,13135,4186,6937,13136,3887,13137,13138,4161,
+4944,9535,10579,13142,8244,13141,5663,10810,13140,9284,13144,13143,13146,
+13145,4187,13147,7432,13149,8708,13148,10514,7254,9274,13312,6148,13313,9728,
+10045,11056,9732,13322,5143,11300,11022,13579,13314,13317,8484,10775,9257,
+13318,10820,6441,7433,13319,6703,6702,3864,5927,7946,3888,13323,13324,13321,
+4119,4878,13320,11044,10256,3847,3928,6704,3889,3842,13329,13327,11035,13330,
+13328,13326,7696,13325,10553,5955,13334,13335,7434,13331,11787,9771,13333,
+6406,13336,10295,13337,13332,11034,9789,13338,10257,13339,13343,
+13340,4390,13342,6938,13341,5720,13355,13348,13345,8771,13344,13346,13347,
+13349,13350,4945,13352,13351,13353,7501,13356,9019,4132,13354,13357,13358,
+13361,13359,13360,6705,13362,6149,13363,6745,8471,13364,13365,6713,6150,11057,
+5127,5928,13366,4663,13367,8472,13368,13570,13369,13370,13371,13373,13374,
+13375,8527,4102,6984,3873,8246,4879,6932,6151,9285,7168,4880,8775,9033,3863,
+5144,10580,6945,5169,8010,6939,11271,13376,5179,6442,4625,4162,7435,4391,
+13377,11301,7208,6979,13378,4946,9521,11016,13379,13380,10296,13382,4871,5462,
+13381,4881,7697,13386,6656,4392,13385,13383,13387,13384,9738,15148,7698,13388,
+11551,13389,13391,8797,13390,7938,6746,8495,6998,10324,8011,6956,13392,7436,
+13393,13394,3890,8473,7729,13395,9490,7437,7438,13396,8012,7439,13397,13398,
+11071,13399,5413,7169,13400,13401,6971,7691,9555,7731,10071,9729,5416,13402,
+5198,13403,5469,9518,4367,6706,13404,13569,13568,5468,13405,9239,8463,9258,
+6951,8247,11353,13571,13572,9525,6674,13574,13575,13576,4947,13577,13578,4363,
+8218,4931,13580,11015,8497,4664,13582,13584,4926,13581,13583,13586,13585,
+13587,13588,9500,5389,4420,13589,13594,13592,10582,10581,9286,13591,7219,
+13590,7761,13595,6473,13601,13602,13596,4626,13597,13606,13605,13604,13600,
+13599,13603,10583,13610,13607,13609,11345,13608,13598,7762,13611,6422,13612,
+13613,13616,13615,13614,9287,13593,13622,13618,13617,13619,13620,13623,11589,
+13624,13621,13625,4927,13626,13628,13627,13629,13630,8013,7170,
+7235,8258,6152,6423,6153,5199,13631,6424,5929,13632,11013,9762,13633,6154,
+4875,8710,5425,6707,10298,10016,13634,4948,13637,8960,13636,13635,13638,9034,
+7746,6708,7977,8498,5121,8961,13639,13640,7502,10776,13643,13642,13641,10332,
+13650,10809,13644,13646,10826,13645,13647,9991,13648,10525,13649,4882,10526,
+9742,13651,13652,6155,4883,13653,5911,11299,11272,4949,13655,8962,6156,7440,
+10046,7441,7255,9035,10584,9240,6157,10299,13656,9272,6433,5930,9036,3874,
+7245,6158,11302,13657,13658,9776,13659,11606,11788,13661,13660,4646,13824,
+13827,13828,13826,10271,7442,13830,13829,13825,13831,13832,13833,13836,13834,
+13835,13837,4163,9037,13838,5721,4437,9749,13839,9562,10554,13840,11789,13841,
+10527,13844,12032,12048,6927,9556,13845,5180,8963,3929,13846,10501,6159,8751,
+9038,11086,5912,5931,13847,13848,13854,6980,8964,5390,13849,10250,8741,13850,
+13851,5391,13852,13853,13855,9301,13856,13857,13858,13843,13842,13859,5664,
+10246,6443,10262,8965,10282,13860,7443,4133,13861,13862,11089,10047,13865,
+4188,7947,13864,13863,5665,8499,13869,13867,13866,11526,5956,7256,13868,9259,
+7197,9503,13872,13871,13870,13873,5957,13874,10331,7226,13875,10072,9504,8966,
+9231,13876,5130,7699,10251,4950,9733,13877,6709,10777,10778,4189,13882,8776,
+13879,4438,14092,13881,9743,13880,13878,6233,13884,13890,13896,13888,9275,
+13893,10300,13887,13892,11590,6710,8500,13885,5181,13895,7948,4164,13889,4439,
+13894,5392,13891,13897,13899,13909,13907,13904,13903,11607,
+13905,5393,6160,7257,13912,13898,13902,13886,4441,13906,13908,8752,6407,4375,
+13900,13911,13910,5394,8456,4677,5666,13901,13913,13916,14080,6940,14086,9039,
+13914,14084,4440,14082,14083,13917,14081,5958,11273,4884,4152,14085,9753,3852,
+10048,13883,14091,14095,11076,14088,9288,14093,7503,14094,9526,11814,14090,
+14096,6234,7978,3891,14089,14087,8249,13915,6675,8485,14108,8250,14103,14100,
+14101,6981,14104,14107,14102,7172,14105,14099,11099,11098,14109,14110,3892,
+14098,5457,3845,4885,14106,14114,14113,14118,14119,14117,14120,14112,14116,
+14121,14122,14111,6747,14115,8501,6161,14097,7700,14135,10568,14125,14126,
+14127,14134,14133,10844,4886,14131,5668,4627,14128,11543,14130,3893,14132,
+14123,14129,14136,5667,14124,11324,11274,14139,14143,8285,11608,14144,14141,
+14138,14137,14142,10511,9491,5669,14145,14140,14146,5722,4368,14154,4887,
+14152,14153,6408,14151,14149,14148,14155,14147,14157,4442,14159,14158,8967,
+14162,14160,14150,5723,14161,14165,14164,14166,14163,14167,14168,14169,10569,
+14171,14170,7198,7949,4421,4443,14172,3870,7979,14173,19234,14336,5696,14337,
+8014,14338,14339,5145,14340,14341,14342,8502,5932,11072,10779,7241,14343,8015,
+19740,10049,6985,6444,14344,8486,10502,8528,14347,14345,14348,14346,14349,
+10512,3862,10301,10050,14350,14353,7444,5146,14351,14358,7445,14352,9763,
+11325,14354,14355,14359,9289,14356,6162,7997,14373,10003,8529,10051,14604,
+10585,9040,10836,14362,4352,8777,14371,8723,14365,14372,14367,14374,14370,
+14369,9806,14363,
+4444,14361,5200,8530,14357,14360,6163,7994,7446,14368,9777,5201,4647,4678,
+7680,14376,14381,14377,5724,14382,6657,6216,7173,14364,6748,14379,6711,14380,
+3875,14375,8968,5202,5395,14378,3846,6434,7701,9041,10035,14384,8253,8457,
+6666,14385,14387,14383,10560,8988,8251,10586,6957,14399,14398,7767,5725,14392,
+7448,9543,9744,14390,8252,6999,14395,7447,14389,14394,9778,14388,5632,4668,
+14396,11530,6445,8724,14393,7995,6164,7747,4165,8219,14391,5156,5670,9006,
+14397,8254,14400,14402,8470,14408,14403,14405,10272,9042,14406,11275,11303,
+4888,3853,14404,14401,4951,4166,14407,11304,14411,8474,14418,14412,14409,
+14416,14386,14413,14417,10017,9290,14410,14414,5671,6480,7996,14422,9221,
+14419,10815,14420,14421,11053,7937,5697,14428,6676,14425,14424,9745,9492,9232,
+14426,14427,10318,9764,6658,8016,10799,4648,14596,14429,11305,14598,14594,
+14595,8255,14593,14366,14597,14592,14602,14603,9222,14605,6659,14600,5147,
+14606,14599,14610,14609,14608,14611,14613,7504,14612,14616,14614,14615,14415,
+14618,14617,14423,14619,14607,6712,14620,14621,14623,14622,14624,4445,6165,
+10587,7950,5933,14626,14629,10289,5182,14628,14627,9779,14630,5396,14632,
+14631,4889,6677,9527,5672,7763,14633,7951,9223,10302,14634,14635,14636,10519,
+13372,7973,10283,6455,10052,10018,9260,11552,14638,6959,14639,3861,5427,7980,
+10303,14640,6689,8742,6714,7702,14641,10588,4182,6715,14644,14642,14645,11544,
+14643,8026,14646,8465,14647,4953,14649,14648,14650,14651,4954,9563,
+8725,5195,6716,8256,7227,3855,14652,4353,14656,6166,14655,6410,7449,14654,
+7450,11039,6409,3894,7981,14661,7952,4134,7220,10821,6481,7451,7942,14660,
+14658,14659,8778,14853,14665,6749,6167,14663,14664,7703,14662,6670,14667,
+14666,14671,14672,14668,4609,14669,14670,10036,10304,5673,14673,7953,7452,
+8753,5414,14674,14678,4394,14675,14677,14676,7242,8743,3876,14679,14680,8969,
+11600,6690,10570,10780,14849,14682,14685,14684,14681,14848,9533,14683,14850,
+7243,14851,11306,9815,14852,14854,14855,14856,5417,4135,6168,14857,14858,7248,
+8257,12599,8221,8220,8503,6438,12113,5709,11276,10589,10333,14859,6482,8990,
+14860,11790,10781,8970,14861,4955,14862,14863,11065,11011,10837,10811,6660,
+14865,6986,10800,14867,14870,14869,4952,5183,14866,14868,14871,7768,11354,
+3880,6463,8475,6972,7506,14874,9261,14872,8458,14873,7505,11068,14875,14876,
+11335,14881,6169,9780,14878,9291,14653,14657,5166,9766,14880,7453,10019,14886,
+10073,14877,14883,14882,7982,10828,11570,10822,4395,6717,11815,14885,7764,
+14884,14879,5934,14891,14889,4396,14887,14893,14899,8487,10528,14901,10241,
+14900,9807,10782,4890,8022,7199,9010,11277,14896,14895,14897,14894,14902,
+14892,14890,14898,14888,8779,11095,6949,6483,6425,10830,4640,9005,9513,4136,
+8017,7955,5641,14904,6170,4699,14906,4691,14912,14909,8018,4650,6411,4649,
+6446,14907,5700,5674,9292,14905,3877,14908,14910,5420,5643,4891,5162,14913,
+6488,10832,6678,14914,10255,14926,4370,14915,14932,14916,11553,14923,
+9790,14931,14918,3859,14920,6171,14922,14921,14917,14928,7454,13132,5959,
+11355,14919,9043,4610,6412,14911,14927,4672,14925,14929,9293,4957,15121,11048,
+14934,4956,14941,10783,15104,15106,15110,14936,8713,9294,15114,14939,15111,
+15105,7704,15115,7954,15113,4892,11823,14933,15109,3895,14935,11033,14940,
+7681,8998,14930,15108,7769,15118,4688,5888,15120,14937,15119,15112,14938,
+15116,15117,15134,9517,15107,15130,15132,9015,11307,10325,15127,8489,15133,
+8222,15124,15137,15136,9550,15135,9545,15139,15126,5415,15129,7228,9791,15131,
+5418,15123,15125,15122,11791,4665,15128,15138,4628,6470,4156,15155,11792,
+15158,7705,15157,15156,15153,15141,15170,15140,15159,15151,15146,15143,15144,
+15152,21249,15149,6172,8999,8259,15147,15142,15145,11308,10825,15150,15160,
+15168,15161,15174,15172,15167,15166,9007,8260,15164,15162,15169,15175,10068,
+15181,15176,15179,15173,8787,10263,15163,15171,7455,11054,15191,15178,5889,
+4354,4670,15154,7456,15183,15190,7000,4689,8717,15180,15185,15189,5397,5163,
+15187,5120,9514,15186,15188,15182,15184,4671,8744,15195,15193,5960,15192,
+15360,14903,15194,15196,15197,15371,15367,14924,15366,15365,15362,15177,15364,
+15363,15369,11781,15372,5466,15368,15370,9990,15373,15377,15374,11346,15375,
+15165,15378,15379,4116,15381,5702,6912,5428,4355,11326,15383,15382,15385,5148,
+5429,4893,15388,15387,15389,4397,8726,15390,4894,15392,15391,15393,15394,
+15395,6718,7956,6400,10319,10561,11811,6740,6447,11601,15396,15397,6719,15398,
+15399,15401,15400,10807,
+7229,6987,6691,15402,15404,7682,15403,15405,15406,15407,15408,15409,15411,
+15410,15412,4356,8745,15413,6661,4651,15414,9249,13099,5122,15415,15416,10571,
+10823,9510,15417,10053,10074,11058,15418,15420,15419,15422,15421,15424,6720,
+11024,15425,15426,5123,15427,15429,15428,7748,10264,4137,10020,9044,7200,5184,
+10021,6925,15431,4895,4183,9553,15430,6173,8754,15432,15440,15433,8480,5185,
+15441,5703,5124,15439,15437,15434,11327,8991,9528,15435,15443,15442,5634,4364,
+6426,15436,15438,10806,8531,10838,15451,15452,4398,10503,11100,15616,6914,
+7457,15447,15453,4167,5398,15444,15449,8019,9808,10054,15446,10752,15448,
+15619,15617,15450,10753,9767,5186,9220,8780,15620,15618,8504,15445,4138,11309,
+15631,15630,8021,15627,11339,9493,15621,8996,4139,6174,15624,7174,15629,15628,
+15623,15626,4679,15625,9768,11533,7507,8020,15637,15635,10284,15632,15634,
+4121,6175,11793,4636,10305,11328,4611,7706,15636,15641,7458,11279,15638,15633,
+15639,11581,9298,9505,4629,4148,15645,15648,11554,11331,15655,15649,15646,
+11571,15652,7209,15654,15659,9296,15657,15651,8727,15658,15647,15653,15660,
+3931,15650,15661,7707,7230,10500,6413,15642,15656,9241,7957,4680,6448,7459,
+15644,7201,5675,15643,15665,7244,5913,15680,15674,5203,9262,15669,15678,3854,
+4113,4376,15671,8459,15662,15664,6176,15681,15676,15668,15675,11018,15673,
+15677,5935,7460,8728,15667,11278,15670,15663,9297,15666,15672,11824,6941,
+10845,15682,9997,15694,5914,7231,15684,11534,6177,15697,3917,15695,15683,
+15689,15691,11310,15686,9229,15688,15696,15690,11046,15685,6913,15709,4681,
+15687,15692,15693,8523,8505,15701,15707,15705,9224,15874,15702,15703,15679,
+5208,10265,6942,6230,11794,15699,15873,4168,8261,9816,4896,11609,11008,9009,
+15706,15708,8209,15872,15704,15698,4898,5704,15886,15881,8023,4674,7232,15890,
+15883,8971,15880,9016,15915,15877,15876,15885,15879,15878,15884,7936,15875,
+15887,15888,4897,15893,15892,15894,15897,9250,15891,15895,5698,8536,15889,
+9754,15896,15901,15899,15902,15905,15898,6217,9735,15640,11347,15900,15904,
+8532,15903,15882,20040,15908,15912,15910,15906,15907,15911,15909,10285,15917,
+15914,15913,15916,9523,15918,8788,8524,7940,15919,15921,15920,15700,15922,
+9542,15923,4399,9299,4612,5187,6973,6449,11782,7749,4169,15925,15924,15928,
+8729,15931,15926,15930,15929,9247,3896,11604,15933,4103,15935,15934,15932,
+15927,10754,15937,15936,4170,15939,10513,15938,11028,7462,8210,7461,11610,
+15945,8024,15941,15946,4171,15944,9792,15940,15943,7463,10032,15947,6960,8025,
+15950,15942,5638,15948,11311,15951,21253,7214,15952,15953,9741,15955,15956,
+9746,9300,15958,15960,11572,15957,15959,4172,15954,12858,15961,8262,6679,
+15963,15962,7683,12600,15964,16128,15949,15965,16129,9817,16130,16131,16132,
+16133,9021,16135,16134,16136,16137,6974,10306,11083,16138,16139,8245,6915,
+16140,16141,16142,10545,10022,16143,9782,8972,16144,4422,5196,11045,11029,
+4371,11795,10801,10505,7958,16145,9506,5890,16146,6451,16148,16147,16149,
+16150,16151,5149,16152,16153,
+5891,10023,16155,7508,16154,5399,16156,16158,16157,16159,5936,16160,5448,8223,
+6236,16162,16163,16161,6988,9511,5400,16165,8715,16164,11796,9793,16168,16170,
+16167,11059,16169,16171,11555,16175,16174,8789,9740,5892,16173,16172,11280,
+11281,16176,4173,6229,6721,16177,16178,16180,7202,16182,16181,16183,4652,
+16185,16184,16187,16186,5915,11527,5419,4357,5449,4928,11591,16189,16191,
+16192,4400,16188,6680,8992,16190,16195,6989,16193,5661,10024,16194,16221,
+16200,5916,5188,16197,11356,11535,8533,16199,16201,11573,5430,10075,9769,
+16202,16204,16207,16203,16206,5961,4140,16208,7759,16205,11579,16211,21251,
+16209,16212,16198,16210,6427,16213,16214,11357,16215,16216,16196,16217,4899,
+6916,16218,16219,16220,4122,16384,10266,16385,4867,16386,16387,16388,16390,
+16391,16389,10290,16393,16392,16395,16394,16396,16397,16399,16398,6232,16401,
+16400,4900,7730,9243,16402,7959,6681,4184,16403,11312,10562,16404,9251,11282,
+6178,7708,8746,12563,8973,4423,16405,16406,16411,16409,16408,14625,4613,16407,
+3897,9993,10025,11536,16412,16410,8763,7941,9994,10252,16414,11531,5676,16415,
+16413,10037,16416,16417,3898,7509,16422,16419,9548,16418,5125,16425,16420,
+16421,16424,16423,10244,8225,8224,5150,16426,16427,16428,16430,16429,4149,
+16438,10055,16432,16434,16436,7709,16437,16435,6943,16431,16433,10273,7464,
+16440,16439,16441,6917,6414,9302,16442,9002,16444,11520,16443,8264,16449,
+16451,16452,8755,16450,16447,16445,16446,16448,16455,16453,16454,16456,16458,
+16459,16460,16461,16457,
+16463,16462,16464,11556,16467,16465,16466,4929,11101,10537,16469,16468,16470,
+16471,16475,16472,16473,16474,16476,16477,16640,16641,16642,9998,9263,16643,
+9809,10259,16644,16645,9225,4614,6179,16646,16647,16648,6664,16650,16649,
+16651,16652,10056,16653,16654,21064,16655,16656,16657,6669,16658,9781,10814,
+4141,4150,16659,16661,16660,9295,7960,15384,16662,11040,16663,4901,10038,
+16664,16665,16666,11067,11060,8989,8265,16668,7233,7465,16671,16670,16669,
+10076,4902,5896,16677,16674,7710,11025,16673,16675,16676,16672,16678,16679,
+8974,4930,8772,16680,16681,16684,7750,9507,16685,10802,16682,16683,16688,
+16687,16686,16690,16689,16691,16693,16692,10540,7221,11557,16694,9494,16695,
+16696,16700,16698,16699,16697,16701,16702,16703,16704,11030,16705,11087,16706,
+8749,9801,5450,8730,16707,5401,7983,16708,6428,16709,16710,5893,6452,16712,
+9269,6453,5165,10755,9770,9270,6203,16714,7466,11537,6180,5894,9986,16716,
+16718,5962,16717,9045,16720,4630,16715,10057,4111,6475,11825,16719,16721,
+10538,7992,16723,16724,16722,4653,16730,16729,6918,16731,16726,16732,16727,
+10039,16725,16728,16897,16896,10816,16733,3914,16899,16898,7467,16900,8226,
+16902,16901,16903,16711,16713,16905,16904,6919,11592,6961,16906,5654,5151,
+5126,6722,11283,16912,16911,8227,16908,16910,7210,7711,16909,16907,9737,7468,
+10267,6454,9303,16913,16914,16936,5431,11804,8212,16915,4401,9046,10496,16916,
+5209,16917,16919,16920,9736,16921,16922,16923,5432,4402,9508,7175,6723,16924,
+7176,4393,10274,16925,
+10058,8228,16928,16929,9800,7712,16926,8768,16927,7469,3899,5128,16930,9047,
+16931,7974,11020,10242,16932,16933,8756,11558,16935,16934,6990,16937,3919,
+16940,16938,4403,5677,16939,6181,6225,10565,16941,10803,16943,7984,4142,4377,
+3851,16942,16944,16945,7510,16946,4654,16948,5705,5189,16949,5460,16950,8027,
+9516,7999,6484,16951,8769,8266,16953,16955,16952,16954,5633,16956,5637,5190,
+11313,16958,16959,4109,16962,4693,16961,16960,16964,16957,16965,11528,16966,
+16967,13139,16969,16968,16970,16971,11540,16972,20302,7470,16973,16974,7222,
+9495,16975,8711,16976,8731,16977,5380,12318,8764,6930,4903,16978,17153,16981,
+5191,16980,17155,16979,7471,16983,16984,9226,16985,4669,7737,10307,16987,8519,
+16982,16986,16988,6490,17157,10253,9989,9304,5433,17156,17154,10004,16989,
+8765,9306,9305,6485,17175,17159,17161,17164,17165,17162,17163,17160,17158,
+17152,10542,4404,17172,17169,17174,17173,9810,11014,6682,17167,17176,17171,
+17170,17166,17168,4904,8732,8028,9985,17181,9987,8000,17178,10030,17182,10546,
+8762,17177,17179,17180,17183,6947,9509,17188,17187,17184,11797,17193,17197,
+17194,17190,17191,17196,17185,12596,17192,17186,17195,17201,4905,17198,17199,
+17200,17203,17202,10069,17204,11611,10572,17209,17206,17205,7985,17208,17210,
+17207,17214,17211,17212,17189,17213,17215,17216,10533,17217,11073,5421,5640,
+17218,10515,7751,11023,17219,11538,9811,8229,9747,7212,3871,17224,17222,17220,
+4864,7472,17225,17223,17221,17229,17228,17227,17226,17230,17231,7961,17232,
+17234,
+17233,5937,8215,17236,9307,17235,17237,10516,8267,6182,17238,11559,17240,
+17241,17242,17243,6724,17244,5678,5193,5129,17408,11090,6183,17245,17411,
+11077,9755,10258,7234,17410,6962,6184,6725,5192,10517,17409,8230,10785,6486,
+6726,9020,17414,11582,6456,17415,7713,17417,7473,6415,17416,7177,5917,8231,
+17412,17418,17413,5679,17421,17425,5706,17420,17429,6185,11340,3867,17426,
+5194,17423,17424,9308,17422,17419,4615,8003,5895,17431,17428,17430,17427,5680,
+8466,17432,8269,17445,17441,17435,17439,7001,3900,17434,17442,17446,6186,
+11061,9013,17436,17444,17433,8733,17438,3868,11049,17437,5434,10059,8268,
+11567,7246,17485,17447,8029,17443,17448,17450,9048,17453,17449,10547,4906,
+11050,3901,17452,11612,17451,4174,9547,17454,17461,17455,17462,17458,9818,
+6953,17460,17457,17463,17456,7203,10756,7211,17459,17471,17467,17470,17468,
+17472,17466,17440,7986,10026,17469,17464,8192,5681,7178,7684,8213,17475,17477,
+17478,17474,17476,17465,17473,17481,17480,10841,5642,17479,17483,17482,17486,
+17488,6683,17484,17489,17490,17491,17497,9242,17493,17492,17494,17495,17496,
+17498,17499,4907,17500,17501,17664,17665,17666,17667,17668,17669,17671,17670,
+17672,17673,17674,17677,17675,17676,6464,5682,8757,10002,7247,9772,10060,
+17678,14156,17679,17681,11332,17680,17683,17682,11314,17684,10077,17685,17688,
+17687,17686,17689,5649,8193,5152,17693,17690,17691,17694,17695,17692,4104,
+4358,17697,17698,17699,11329,7179,17701,17700,7752,17702,17703,17704,4932,
+4908,17705,17706,10812,11330,
+11315,11798,6188,17709,6963,17708,17710,6920,8496,17711,6187,11062,17712,
+17713,17714,17715,17716,6921,11084,17718,8734,17717,17720,17719,17721,7962,
+17722,17723,10520,17724,8270,17725,17726,11613,17729,17728,17727,8975,17730,
+7685,17731,17732,11799,17733,17734,17736,17735,9988,9560,11805,9992,17738,
+7474,10249,17739,17737,4909,5939,6727,10061,5897,10786,17742,17740,6189,6190,
+3912,6471,9784,3902,17747,8735,9783,8506,17749,17745,17748,17743,17746,10757,
+5940,3932,17744,17751,17752,9496,5402,17925,9756,6728,5403,7975,11813,11021,
+17750,7987,5170,17753,17755,17754,17756,8709,9757,8976,17922,17921,17757,7732,
+10308,17924,17923,6191,11826,17940,17928,17929,6991,17927,6231,17926,17930,
+8977,10497,8194,8507,17934,17935,17931,17932,17933,6192,17941,17937,10309,
+10827,10247,17936,17939,17938,10787,17942,17943,8214,17944,17946,17950,17947,
+17945,9758,17948,17949,4369,17956,17951,17952,17953,8448,17955,17954,17957,
+17958,17959,7714,4424,17960,11574,6922,7180,6729,8758,17961,17962,4112,17963,
+17964,17965,17966,17967,5404,14601,17968,8004,17969,6954,17970,12047,17971,
+10557,4923,8195,7223,10320,7181,17972,6193,17973,10027,17987,17975,8488,9812,
+5918,17974,8196,17976,9049,17978,17977,17980,17979,17981,17983,17982,4910,
+17984,17985,17986,6416,11560,17988,7686,4175,17989,17990,17991,3921,17992,
+17993,10310,6950,17995,4616,3857,17994,17997,9773,7715,4405,10758,5692,5435,
+17996,4425,4866,4176,18001,11593,8508,10275,18013,4406,18011,18009,18000,
+17998,17999,
+6978,5451,8790,9520,4144,18003,18002,18008,18004,18007,11055,18006,4407,4700,
+18010,18012,5683,18178,18187,18188,3850,18195,3920,18186,18185,18180,18179,
+18177,18176,8770,8538,18182,18181,18184,8271,5684,4128,18183,6194,8272,18201,
+18202,4408,4365,18199,18189,18197,18204,18198,18196,18005,18194,18190,4911,
+18192,18203,18193,18205,18191,9819,11336,18200,18222,18214,7770,5157,5436,
+18209,4410,7475,18212,6457,9264,18217,10573,18208,4409,5941,10248,18218,18206,
+18215,18225,18210,18211,9497,18216,18213,10759,18219,3903,18207,18221,18220,
+9802,18227,18238,4701,18241,18223,18228,11341,18237,11316,11529,8791,4682,
+10321,18243,9472,3856,18236,18232,8273,18226,18234,18239,9739,3849,18231,
+18240,10327,18235,18230,7476,7182,6923,11063,10278,18246,18255,18233,4694,
+7511,18244,18249,8274,18245,18252,8766,18253,11317,18242,4631,18248,18251,
+11019,18254,18247,18250,10760,11776,18258,18265,18257,6946,18224,10541,11009,
+18264,18263,18259,18260,4117,18262,18256,9012,18261,3933,8449,10530,18266,
+18432,10040,18269,7477,6952,18434,5405,18435,10328,18268,18229,18267,11822,
+9473,10322,18442,18448,18449,18436,9813,18446,18438,18440,18450,18439,18443,
+4177,9540,18444,18447,18437,8197,18441,6662,7716,5647,11091,11096,7249,18454,
+18452,11821,18451,11348,18453,18455,18456,18459,18457,9474,18458,10028,18445,
+7250,18460,18465,8275,18464,18433,18466,8232,18461,18463,18462,15376,15361,
+18468,18467,11349,16667,18469,18470,18471,5942,5171,18473,12348,5204,11545,
+5458,18474,18475,8781,18476,
+9561,3865,4418,18481,18482,18477,6684,18478,9761,18479,18480,18490,18484,
+18487,18483,18485,18486,6967,18488,8736,5685,4641,18491,4638,18496,18492,
+18495,10009,18493,18494,10279,10041,18497,8540,18507,18503,4426,18501,10761,
+18502,18499,18500,18505,18508,18506,18504,18498,8759,18515,11017,18513,18514,
+18509,18511,18512,18510,8005,11800,18519,18520,18688,7689,18522,18525,18517,
+18516,18689,4411,18523,18690,18524,18521,8978,18518,9799,18694,11290,18693,
+18692,18701,18695,18703,11333,18706,18697,18698,18702,18705,18704,18696,18699,
+18716,18709,18707,18708,18713,18714,4617,5153,18712,18691,18711,18715,18710,
+18717,18719,18718,18721,18720,18489,18725,18722,18723,18724,18726,5707,18728,
+18727,7183,6195,15622,18729,7216,4632,18730,4145,7478,18731,6196,18732,3904,
+10268,18733,7753,18740,18737,8782,18738,18735,5437,18734,18741,5653,8509,
+18747,18743,8468,18742,18745,18736,18746,18748,10062,18744,18749,18751,5938,
+18739,3872,18750,6458,11605,18752,18753,8276,11521,18754,11284,18755,18756,
+10563,18757,6431,11522,18762,18763,7479,18761,11334,18758,18760,7964,7773,
+18759,18764,10498,18766,18765,4683,10762,18767,18779,18769,18770,18771,18772,
+18776,18777,18775,18773,18768,18774,18778,20246,4359,18781,5438,18780,18945,
+18944,18947,18946,18948,7184,18949,18950,18951,7965,11318,18952,10499,9765,
+18953,18954,5898,5131,18955,6730,9760,18956,4655,18957,18959,11350,18958,7717,
+18960,18961,18962,4912,18963,18964,18965,18966,4656,18967,18968,18969,4433,
+7687,18970,18971,18972,5919,9050,18973,
+5686,7733,18976,9475,18975,5648,18974,8534,5132,18977,18978,7480,5708,18979,
+10763,7998,5205,11092,8233,18980,7718,8783,7481,18981,18984,18985,6429,8481,
+18983,7482,10269,18982,6731,4146,18989,5687,6733,6732,11820,18988,18987,8198,
+5164,11810,4633,7483,18986,18991,18992,18990,5943,11295,6734,9734,18995,7967,
+8737,11285,18998,5963,7966,18994,18999,5964,18996,18997,18993,8001,9512,8718,
+4412,10063,5154,8979,19002,19000,8747,7968,4913,19001,7738,11561,11807,19003,
+19014,8980,19013,19010,19018,19011,19007,9051,19006,19004,11264,6735,19008,
+19005,19012,7251,5920,8537,10788,4153,3905,9476,19016,19015,9541,19020,19009,
+19019,19021,5899,19017,6197,6964,19022,11319,19025,19028,19026,10260,19023,
+5439,19027,19029,19033,19030,19032,19031,19034,6928,19036,19035,10311,19200,
+5688,19037,19201,19202,5155,17696,7512,19203,5965,19204,19205,6685,14637,
+19206,19207,7185,19208,19209,19210,19211,19212,8714,19213,19215,19214,9477,
+19216,10764,19217,19218,19219,19220,9529,7484,19221,6218,12045,19222,19223,
+10270,19224,19232,19225,19227,19226,19228,10789,19229,19230,19231,19233,4620,
+9030,10312,6465,6198,10286,4414,10029,19236,4914,7988,19235,19240,8792,11074,
+19238,19239,5133,19241,9794,8510,10064,9244,19237,10790,4427,19243,11783,8993,
+11812,6736,19242,8464,19259,8199,9559,10287,19246,6686,6737,7485,9796,5900,
+19245,19244,10313,6944,9265,19248,19249,6199,19247,19250,19251,19253,8450,
+19252,4933,19255,19254,19256,19258,19260,19261,7989,6958,19262,4657,
+19263,8277,19264,19265,10314,5134,19266,8981,4154,19267,6992,7765,8460,19270,
+19269,19268,19276,19274,19271,19273,19272,19275,5206,19279,7990,19280,5944,
+19277,19278,11784,8982,8200,19281,19284,19282,19283,11320,9478,19287,19285,
+19286,19288,19464,19291,19292,19290,19289,9052,19456,19460,19457,19293,19458,
+19459,19466,19461,7991,19463,19465,19462,19468,7186,19467,19469,19470,19473,
+19472,19471,19475,19474,11093,19477,19476,19478,19479,19481,19480,7719,19482,
+5452,19483,19485,19486,19487,19484,19488,6965,19489,5135,5650,5901,19490,9551,
+9245,19491,19494,6931,19493,19492,5689,19495,4658,19497,6459,19496,19505,
+19499,19501,10564,19498,19500,19504,19502,5136,19503,19506,9785,11575,7187,
+19507,11265,19509,19508,19512,11296,19511,4684,19510,19515,19514,19513,9233,
+19516,19517,19518,6219,5636,19519,19520,19521,7720,19522,6924,19523,19524,
+12544,12381,19525,17487,19526,8707,7690,9759,19527,10548,9011,6237,8712,4105,
+10839,7734,5693,5440,10549,19528,19530,19529,4415,9557,19531,9814,9234,19532,
+7217,19534,11041,19549,19536,19537,9000,8511,8278,9479,19535,5172,19544,19541,
+19716,9480,8767,19538,9053,9266,19539,19543,7743,9798,9003,7969,19542,8461,
+8451,19540,3848,11777,19545,8512,7188,7721,19547,19546,3918,19548,10254,19718,
+9530,7754,8760,5463,19717,11286,4126,10550,4416,19712,19713,19714,19715,9498,
+8706,3906,19719,19720,21250,8476,19721,4178,8235,5902,11321,19722,9227,8279,
+6966,19723,19726,7236,19724,8202,8201,3907,11562,19728,10065,19730,19729,
+19727,16963,4915,19533,19732,19731,19733,11287,9536,10765,19734,6968,19735,
+19736,19737,9216,3913,6200,11801,19741,5651,19738,19739,10323,4659,11288,5406,
+9267,19742,19743,19744,9217,19746,19745,9522,19747,7189,6975,9786,8784,6993,
+7755,19748,19749,7740,19750,19751,19752,11342,7190,19754,19753,6201,6226,6687,
+19757,7237,19756,19755,8520,5966,7970,9999,7192,19758,7486,19761,19759,19760,
+19763,19762,7513,19764,19765,19766,10031,6450,6976,19767,19768,11523,7204,
+11085,11563,19769,5441,19770,9218,19773,4695,7722,19771,19772,9023,10804,5467,
+19775,19776,19774,19778,9534,4642,19782,19779,19781,19777,20014,19780,11594,
+5945,19790,9235,19785,19788,19786,19791,19792,19784,19797,4179,19783,9996,
+19787,7487,6202,10791,5443,7205,9499,8204,19795,19789,19794,11042,8983,19796,
+19793,8203,19800,19799,19798,10766,7258,19801,10558,4147,10277,8785,5207,
+19803,6204,6667,19802,7756,7757,19968,19970,7514,19969,19971,5426,10276,6977,
+11778,19805,6487,11806,19973,19972,19974,19804,9544,9268,9014,19979,8738,
+19975,19976,5644,19978,5903,19977,7488,4696,19983,6430,8280,9001,4634,19981,
+19982,8994,19980,19984,19990,19993,19992,9228,19985,19986,19989,19991,5407,
+19994,19988,19987,19998,19999,20000,19997,19996,7489,9481,19995,20004,20002,
+20003,20001,8535,20005,20006,20008,4916,20007,11097,20019,20009,20012,20010,
+20011,20013,20015,20016,20017,20020,20018,20021,20023,20022,8984,11078,20024,
+8205,20025,10531,20026,4618,4123,4918,4917,20027,20028,20029,20030,20031,4919,
+4660,6205,10005,20033,20032,20034,4155,20037,20036,20035,20038,20041,3878,
+20039,20043,20042,20045,20044,20046,9485,20047,20048,20050,20049,10315,20051,
+20052,6468,20053,20054,10792,8234,3843,8490,20055,10316,20058,20056,6206,
+20057,5921,10532,20060,20224,20061,20225,4096,7735,7259,4920,20226,9797,20228,
+4097,20227,8995,11564,9482,20059,11525,5904,11322,5464,11539,5639,8513,17920,
+20229,4619,7758,4661,20231,20232,20230,5699,6460,7490,4098,11576,20234,19725,
+20233,20237,20235,20236,20238,20239,11595,20240,20241,7976,10010,7772,4934,
+11289,4428,7191,5946,20244,20243,6738,20245,20242,6663,20249,18700,12597,7766,
+20247,11524,9552,4106,8002,6933,10518,4127,11596,11338,20250,9252,7002,20251,
+20252,7723,20253,11597,20248,20255,20257,20256,20254,20258,20259,8281,4417,
+20260,11031,20261,20262,11785,14864,20263,20264,20265,20269,20266,20267,20268,
+20270,7971,11094,7972,20271,10066,20272,21042,11051,20273,20274,20275,4662,
+20277,7736,20278,5635,20279,20283,20281,20282,4690,20280,20284,20285,3879,
+20286,20287,7491,20288,5158,20291,20290,20289,19024,10555,20292,20293,20294,
+20295,20296,20297,4921,20298,20299,9730,20301,4378,20304,20303,4099,5408,
+10534,8985,6401,6207,7238,7739,20306,20305,11297,4935,10033,9531,7771,11565,
+5690,20309,20308,10794,9483,4143,20310,20307,10288,11337,20311,20312,20314,
+8521,4666,4667,20313,4936,5905,4937,9246,11583,5947,20315,20316,20317,20480,
+20482,20481,10326,20483,20484,20485,20486,20488,20487,20489,10067,17707,7688,
+5137,20490,
+20491,12555,15386,10034,3930,3866,6739,10767,7517,20492,11070,20493,11323,
+4129,6688,20494,4429,20495,20496,20498,20499,20501,20497,20500,4922,20502,
+20503,20504,20505,20506,20508,20507,20510,20513,20509,20511,20512,20514,5409,
+6994,20515,20516,6208,20517,4637,9774,20518,20519,8761,9546,20520,9820,8491,
+4151,5453,5454,8786,20525,5455,4430,20524,20522,20523,20521,20535,20526,20527,
+20528,20529,20531,20530,7224,20532,20534,5138,20533,8282,5906,20536,8492,
+20537,9484,20538,20543,20541,20540,20542,20539,20545,20544,20547,5410,20546,
+20548,20549,20551,20550,20552,20554,20553,6235,20555,20556,4635,20557,20558,
+7760,20559,20560,20561,20562,6209,20563,20564,20565,20566,20567,10000,20569,
+10245,20570,20568,20572,20571,20573,20736,20737,20738,20739,20740,20741,20742,
+20743,20744,20745,20746,20747,20748,20749,15380,20750,17239,5139,4608,6417,
+20752,20751,11012,20754,20755,20753,20756,10817,20757,5210,11780,20758,20760,
+3869,20761,10506,20759,20762,20763,20764,20765,20766,10829,6668,6489,8206,
+20767,20770,20768,20771,5968,20769,20772,20773,20774,20778,6665,8515,20779,
+20776,20775,20777,5694,20783,20782,20781,3858,20793,20789,20790,20786,20792,
+20788,4673,11819,20791,20787,20785,20784,20795,20798,20797,20796,10280,20794,
+3922,20799,20801,4686,20780,4118,20803,20802,20800,8716,10831,11577,20804,
+20805,20806,20807,20808,8986,20809,10006,20814,20810,20811,10768,11043,9519,
+20815,20816,9501,20813,20812,4361,20824,20823,4180,20821,20820,20818,4698,
+20817,6929,4360,6210,20827,20826,20825,
+20822,20828,20829,20996,20995,20997,4108,20992,20993,6227,11032,20994,10769,
+21002,20998,21003,21000,20999,5691,21004,21005,21006,21001,20819,21007,9024,
+21011,21012,21010,21009,21015,21008,21013,21014,21017,21016,21019,21020,21021,
+11816,21018,8522,6476,21022,21023,21024,21025,21026,5907,21027,21028,6926,
+21029,21030,21031,21032,21035,21033,11803,21034,11598,21036,11578,21037,9821,
+21038,21040,21041,21039,6220,11052,10818,13654,15423,10842,4362,21043,5167,
+21044,21045,21046,6228,21047,16179,11066,8514,21048,21050,21049,21051,21052,
+21053,21054,21055,21056,21057,21058,21059,21060,21061,21062,21063,9219,5948,
+21065,8236,21066,21067,10240,21068,21069,16918,19257,20300,21070,21071,21073,
+21074,21075,11599,21072,21076,21077,21079,21078,21081,21082,21080,11541,21083,
+21084,16947,21085,9,83,79,82,84,41,42,85,59,3,4,30,527,528,529,530,531,532,
+533,534,535,536,6,7,66,64,67,8,86,544,545,546,547,548,549,550,551,552,553,554,
+555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,45,46,15,17,13,
+576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,
+595,596,597,598,599,600,601,47,34,48,16,78,