C. Шифрийг тайлах

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг өдөр Мария Ивановна Сашагийн Оляд зориулсан мэссэжтэй цаасны хэлтэрхийг олсон. Мария Ивановна уг мэссэжид юу байгааг мэдэхийг хүссэн боловч харамсалтай нь энэ мэссэж шифрлэгдсэн байсан. Мария Ивановна түүний оюутнууд ихэвчлэн анхны мэссэжийн үсэг бүрийг өөр нэг үсгээр сольж мэссэжүүдээ шифрлэдэг гэдгийг мэднэ. Үсэг солих үйл явц нь ижил үсгүүд үргэлж тогтмол нэг үсгээр солигддог ба ялгаатай үсгүүд үргэлж ялгаатай үсгүүдээр солигдох замаар явагддаг.

Мария Ивановна мэссэж эцсийн шалгалтын хариуг агуулж байна гэж бодсон (мэссэжийн урт нь эцсийн шалгалтын асуултуудын тоотой тэнцүү байгаа учир). Нөгөө талаас тэр Сашагийн хариулт зөв байх албагүй гэдгийг мэднэ. Энд асуулт бүрийн хувьд боломжит $K$ хариултууд байгаа. Мэдээж Мария Ивановна зөв хариултуудыг мэдэж байгаа.

Мария Ивановна Сашагийн зөв хариултын тоог хамгийн их байлгахаар мэссэжийг тайлахаар шийдсэн. Тэр одоо маш завгүй байгаа учир таны ажил бол түүнд туслах юм.

Оролт

Эхний мөрөнд хоёр тэмдэгт мөрийн урт $N$ ($1 ≤ N ≤ 2 000 000$) ба бүхэл тоон утга $K$ байх ба энэ нь ($1 ≤ K ≤ 52$) асуултууд бүрийн боломжит хариултууд юм. Асуултуудын хариултууд нь дараах дараалалтай $abcde...xyzABCDE...XYZ$ зэрэг Латин үсгүүдээр тэмдэглэгдсэн. Жишээлбэл $K = 6$ үед боломжит хариултууд нь $abcdef$ бол $K = 30$ үед боломжит хариултууд нь $abcde...xyzABCD$.

Хоёр дахь мөрөнд Латин үсэгнүүдээс тогтсон тэмдэгт мөр буюу шифрлэгдсэн мэссэж байна.

Гурав дахь мөрөнд Латин үсэгнүүдээс тогтох тэмдэгт мөр буюу асуултуудын зөв хариултууд байна.

Гаралт

Эхний мөрөнд Сашагийн боломжит зөв хариултуудын хамгийн их тоог хэвлэ.

Хоёр дахь мөрөнд шифрийн дүрмийг оюутнуудын шифрийн ($'a'$-с эхлээд дээр дурдсан шиг) үсэг бүрийн хувьд харгалзах тодорхойлсон үсгийг агуулсан хариултыг $K$ урттай тэмдэгт мөр хэлбэрээр хэвлэнэ үү.

Хэрвээ хамгийн их хариултыг гаргах хэд хэдэн зам байвал тэдгээрийн алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
10 2
aaabbbaaab
bbbbabbbbb
Гаралт
7
ba
Оролт
10 2
aaaaaaabbb
bbbbaaabbb
Гаралт
6
ab
Оролт
9 4
dacbdacbd
acbdacbda
Гаралт
9
cdba
Сэтгэгдлүүдийг ачааллаж байна...