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

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

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

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

Оролт

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

Гаралт

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

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$.