C. Хаммын зай

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

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

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

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

$a$, $b$ ижил урттай тэмдэгт мөрүүдийн $Хаммын зай$ нь ($h(a, b)$ гэж тэмдэглэнэ) $(1 ≤ i ≤ |a|)$, $a_{i} ≠ b_{i}$ байх ялгаатай $i$ тоонуудын тоог хэлнэ, энд $a_{i}$ нь $a$ тэмдэгт мөрийн $i$-р тэмдэгт, $b_{i}$ нь $b$ тэмдэгт мөрийн $i$-р тэмдэгт. Жишээлбэл, "aba", "bba" тэмдэгт мөрүүдийн Хаммын зай нь $1$, эдний эхний тэмдэгт ялгаатай байна. "bbba", "aaab" тэмдэгт мөрүүдийн хувьд Хаммын зай нь $4$.

Жон До ижил урттай $s_{1}$, $s_{2}$, $s_{3}$, $s_{4}$ тэмдэгт мөрүүд бичигдсэн цаастай байв. $s_{i}$ тэмдэгт мөр бүр "a", "b" үсгүүдээс л бүрднэ. Жон эдгээр дөрвөн тэмдэгт мөрийн бүх хослолуудын Хаммын зайг олсон байлаа. Тэгээд тэр тэмдэгт мөр бичсэн цаасаа алга болгсон ч Хаммын зайнууд нь үлдсэн байв.

Жонд $s'_{1}$, $s'_{2}$, $s'_{3}, s'_{4}$ гэсэн ижил урттай, "a$", "b$" үсгүүдээс бүрдсэн, хослолуудын хоорондох Хаммын зай нь түүнд байгаатай тохирох тэмдэгт мөрүүдийг нөхөж олоход нь тусална уу. Илүү тодорхой томъёолбол $s'_{i}$ тэмдэгт мөрүүд нөхцлийг хангах ёстой.

Цаасан дээр бичихдээ илүү амар байхын тулд аль болох бага урттай байхаар тэмдэгт мөрүүдийг олно уу.

Оролт

Эхний мөрөнд $h(s_{1}, s_{2})$, $h(s_{1}, s_{3})$, $h(s_{1}, s_{4})$ бүхэл тоонууд зайгаар тусгаарлан өгөгднө. Хоёрдугаар мөрөнд $h(s_{2}, s_{3})$, $h(s_{2}, s_{4})$ тоонууд зайгаар тусгаарлагдан өгөгднө. Гуравдугаар мөрөнд $h(s_{3}, s_{4})$ гэсэн ганц тоо байрлана.

Бүх $h(s_{i}, s_{j})$ тоонууд сөрөг биш, $10^{5}$ тооноос хэтрэхгүй байна. $h(s_{i}, s_{j})$ тоонуудын ядаж нэг нь эерэг тоо байна.

Гаралт

Бодлогын нөхцөл хангах тэмдэгт мөрүүд олдохгүй бол -1 гэж хэвлэ.

Олддош бол тэмдэгт мөрүүдийн урт болох $len$ тоог хэвлэ. Дараагийн дөрвөн мөрний $i$-р мөрөнд $s'_{i}$ тэмдэгт мөрийг хэвлэ. Боломжит хамгийн бага урттай тэмдэгт мөрүүдийн хэд хэдэн шийд байвал дуртайгаа сонгоно уу.

Орчуулсан: Sugardorj

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

Оролт
4 4 4
4 4
4
Гаралт
6
aaaabb
aabbaa
bbaaaa
bbbbbb
Сэтгэгдлүүдийг ачааллаж байна...