D. Сонсож байгаагүй үг

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

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

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

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

Дэд-тэмдэгт мөр гэдэг нь тэмдэгт мөрийн дараалсан хэсэг тэмдэгтүүд юм. Жишээ нь "bca" бол "abcabc" тэмдэгт мөрийн дэд-тэмдэгт мөр болж чадна, харин "cc" бол чадахгүй.

Давхар-тэмдэгт мөр гэдэг нь тэмдэгт мөрийг өөрийнх нь араас залгаж бичсэнийг хэлнэ. Жишээ нь "abcabc" бол давхар-тэмдэгт мөр байж чадна, харин "abcabd" ба "ababab" нь чадахгүй.

Танд тэмдэгт мөр байгаа ба алхам бүрд та давхар-тэмдэгт мөр болж чадах хамгийн богино дэд-тэмдэгт мөрийг хайж олно. Ийм дэд-тэмдэгт мөр олон байвал хамгийн эхнийхийг нь сонгоно. Одоо сонгосон $XX$ ($X$ нь давхар-тэмдэг мөрийг бүрдүүлэгч тэмдэгт мөр) дэд-тэмдэгт мөрөө $X$-ээр солино.

Гэх мэтчилэн энэ алхмуудыг давхар-тэмдэгт мөр олдохгүй болтол давтана. Тийм бол хамгийн сүүлд ямар тэмдэгт мөр үлдэх вэ?

Оролт

Латин цагаан толгойн жижиг үсгүүдээс тогтсон тэмдэгт мөр өгөгдөх ба $1$-ээс $50000$ хүртэл урттай байж болно.

Гаралт

Хамгийн сүүлд үлдсэн тэмдэгт мөр.

Орчуулсан: gmunkhbaatarmn

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

Оролт
abccabc
Гаралт
abc
Оролт
aaaabaaab
Гаралт
ab
Оролт
birdbirdbirdistheword
Гаралт
birdistheword

Тэмдэглэл

At the first sample the string transforms as follows: abccabc$ $ -> $ abcabc$ $ -> $ abc$.

At the second sample the string transforms as follows: aaaabaaab$ $ -> $ aaabaaab$ $ -> $ aabaaab$ $ -> $ abaaab$ $ -> $ abaab$ $ -> $ abab$ $ -> $ ab$.

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