D. Нэр

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

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

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

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

Холоо орших Тау Цети гаригт бүх зүйл бидэнд тодорхой бус байлаа. Ялангуяа Тауцэтичүүд хүүхдүүддээ маш онцгой байдлаар нэр өгдөг.

Хоёр залуу эцэг, эх $abac, bbad$ нар эхлэн төрсөн хүүхэддээ ямар нэр өгөхийг бодож байлаа. Тэд нэр нь $s$ тэмдэгтэн цувааны үсгүүдийн сэлгэмэл байлгахаар шийдсэн. Тэд хөрш айлыгаа гүйцэхийн тулд хөршийнхөө хүүгийн нэр $t$-ээс цагаан толгойн дарааллаар эрс их байх нэрээр хүүхдээ дуудахаар шийдсэн.

Гэхдээ тэд нэрний татвар удахгүй хэрэгжүүлэгдэнэ гэж таамаглаж байгаа. Цагаан толгонй дарааллаар өндөр нэртэй хүмүүс их татвар төлөх юм. Тиймээс $abac, bbdad$ нар шинэ төрсөн хүүхдээ цагаан толгойн дарааллаар $t$ нэрээс эрс их, хамгийн бага нэрээр хүүхдээ дуудахыг хүссэн.

Тэмдэгтэн цувааны цагаан толгойн дараалал нь бидний дассан "толь"-н дараалал юм. Ийм харьцуулалт бүх орчин үеийн програмчлалын хэлд тэмдэгтэн цувааг харьцуулахад хэрэглэгддэг. Чухамдаа $n$ урттай $p$ тэмдэгтэн цуваа нь $m$ урттай $q$ тэмдэгтэн цуваанаас доорх нөхцөлүүд биелэж байвал цагаан толгойн дарааллаар бага гэсэн үг.

  • $n < m, p$ нь $q$ тэмдэгтэн цувааны угтвар (жишээ нь "aba" нь "abaa"-с бага).

  • $( 1 <= k <= min(n, m)$ байх $k$ тооны хувьд $p_1 = q_1, p_2 = q_2, ..., p_{k - 1} = q_{k - q}, p_k < q_k$ байх. Энд тэмдэгтэн цуваануудын тэмдэгтүүд 1-ээс хэлэн дугаарлагдсан.

Хөрш хүүгийн нэр $t$, болон $s$ тэмдэгтэн цуваанууд өгөгдөхөд $s$-ийн сэлгэмлийн дүнд үүсэх тэмдэгтэн цувааг тодорхойлох програм бич. Уг тэмдэгтэн цуваа нь цагаан толгойн дарааллаар $t$-ээс эрс их, хамгийн бага тэмдэгтэн цуваа байна.

Оролт

Эхний мөр хоосон биш тэмдэгтэн цуваа $s (1 <= |s| <= 5000)$-г агуулна, $|s|$ нь урт нь. Хоёр дугаар мөр хоосон биш тэмдэгтэн цуваа $t (1 <= |t| <= 5000$-г агуулна, $|t|$ нь урт нь. Тэмдэгтэн цуваанууд Латин цагаан толгойн жижиг үсгүүдээс бүтнэ.

Гаралт

Хайсан нэр эсвэл тийм нэр байхгүй бол -1-ийг гарга.

Орчуулсан: devman

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

Оролт
aad
aac
Гаралт
aad
Оролт
abad
bob
Гаралт
daab
Оролт
abc
defg
Гаралт
-1
Оролт
czaaab
abcdef
Гаралт
abczaa

Тэмдэглэл

Эхний жишээнд өгөгсөн тэмдэгтэн цуваа $s$ нь бидний хайсэн тэмдэгтэн цуваа, бид юу ч өөрчлөх шаардлага байхгүй.

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