C. Хэв

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

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

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

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

Хөгжүүлэгчид энгийн илэрхийллийн хэвүүдтэй (regex pattern) их нүүр тулдаг. Энэ хэв нь ихэвчлэн таны хайлтын дүрмийг тогтоодог тэмдэгтүүд болон тусгай тэмдэгтүүдээс бүрдсэн тэмдэгт мөр хэлбэрээр тодорхойлогддог. Эдгээр хэвүүд нь ихэвчлэн тэмдэгт мөрийг тодорхой дүрмүүдийг хангаж байгаа эсэхийг шалгахад ашиглагддаг.

Хэв нь Англи цагаан толгойн жижиг үсгүүд болон асуултын тэмдгээс ('$?$') бүрдэнэ. Хэв дахь асуултын тэмдэг нь Англи цагаан толгойн дурын нэг үсгийг заана. Бид хэрвээ тэмдэгт мөрийн тохиромжтой үсгүүдийг асуултын тэмдгээр солих замаар хэврүү хувиргаж чадаж байвал бид энэ тэмдэгт мөрийг хэвтэй таарч байна гэж үзнэ. Жишээлбэл $aba$ тэмдэгт мөр нь дараах хэвүүдтэй таарна: $???$, $??a$, $a?a$, $aba$.

R1 компаний ажилчид нэг нэгэнтэйгээ таавар таалцах дуртай. Таавар нь дараах байдалтай байна: танд ижил урттай $n$ хэвүүд өгөгдөх ба та боломжит хамгийн цөөхөн асуултын тэмдэгтэй хэвийг олох хэрэгтэй мөн таны олсон хэв өгөгдсөн хэв бүртэй огтлолцож байх ёстой. Хэрвээ эхний болон хоёр дахь хэвтэй хоёулантай нь таарах тэмдэгт мөр байвал энэ хоёр хэв огтлолцоно гэсэн үг. Та энэ тааврыг шийдэж чадах уу?

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 10^{5})$ байх буюу хэвүүдийн тоо юм. Дараагийн $n$ мөрөнд хэвүүд байна.

Хэвүүд зөвхөн Англи цагаан толгойн жижиг үсгүүд болон '$?$' тэмдгээс бүрдэнэ. Бүх хэвүүд хоосон биш байх ба ижил урттай байна. Бүх хэвийн нийт урт $10^{5}$ тэмдэгтээс хэтрэхгүй.

Гаралт

Асуултын хариулт болох өгөгдсөн бүх хэвтэй огтлолцох мөн хамгийн бага '$?$' агуулах хэвийг нэг мөрөнд хэвлэ. Хэрвээ хэд хэдэн хариулт байвал алийг нь ч хэвлэж болно.

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

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

Оролт
2
?ab
??b
Гаралт
xab
Оролт
2
a
b
Гаралт
?
Оролт
1
?a?b
Гаралт
cacb

Тэмдэглэл

Эхний жишээг авч үзье. $xab$ хэв нь өгөгдсөн хэв бүртэй огтлолцож байна. $???$ хэв ч мөн өгөгдсөн хэв бүртэй огтлолцоно гэвч энэ хэв нь олон асуултын тэмдэг агуулж байгаа учир хамгийн тохиромжтой хариулт биш юм. Илүү тодорхой хэлбэл $xab$ бол хамгийн тохиромжтой хариулт учир нь энэ хэв ямар ч асуултын тэмдэг агуулаагүй байна. Энэ жишээнд өөр олон хамгийн тохиромжтой хариултууд байна: $aab$, $bab$, $cab$, $dab$ гээд үргэлжилнэ.

Сэтгэгдлүүдийг ачааллаж байна...