Muallif: __thecrash__
D. Marjon shodasi
Vaqt limiti: 1000 ms Xotira limiti: 128 mb
Zargar usta marjonlardan shoda tizadi. U avval bir nechta rangli marjondan iborat naqsh tanlaydi, keyin shu naqshni ipga qayta-qayta, ketma-ket tizib chiqadi. Ip tugab qolsa, oxirgi naqsh chala qolishi ham mumkin.
Bir kuni ustaxonada boshlanishi buzilmagan, lekin oxiri uzilgan shoda topildi. Har bir marjon rangi bitta kichik lotin harfi bilan belgilangan, shuning uchun shoda \(s\) satri ko'rinishida yozildi. Usta tanlagan naqshni tiklash kerak. Bir nechta naqsh mos kelishi mumkin, shuning uchun eng qisqasini toping.
Boshqacha aytganda, shunday eng qisqa \(p\) satrni topingki, \(s\) satri \(ppp\ldots p\) satrning boshlanishi bo'lsin.
Kiruvchi ma'lumotlar
Bitta qatorda \(s\) satri berilgan (\(1 \le |s| \le 10^6\)). U faqat kichik lotin harflaridan iborat.
Chiquvchi ma'lumotlar
Eng qisqa naqshni chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
abcabcab |
abc |
| 2 |
aaaa |
a |
| 3 |
abcd |
abcd |
Izoh
Birinchi misolda shoda 'abc' naqshidan tizilgan, ya'ni 'abc' 'abc' 'ab', oxirgi naqsh chala qolgan.
Ikkinchi misolda shoda bitta rangdagi marjonlardan iborat.
Uchinchi misolda hech qanday qisqaroq naqsh mos kelmaydi, shuning uchun naqsh butun shodaning o'zi.