יחד עם גורל מפותל, ל-Nadeko יש מחרוזת $s$ המורכבת מאותיות קטנות. משאלתה העליונה היא לבנות מחרוזת $t$ שעבורה מתקיימים התנאים הבאים:
- $t$ אינה מכילה את $s$ כתת-סדרה.
- כל תת-סדרה של $s$ שאינה מתלכדת עם $s$ מוכלת ב-$t$ כתת-סדרה.
עזרו לה למצוא מחרוזת $t$ באורך המינימלי האפשרי. אם קיימות מספר מחרוזות כאלה, מותר להדפיס כל אחת מהן.
קלט
שורה בודדת של הקלט מכילה את המחרוזת $s$ ($2 \le |s| \le 10^6$) — המחרוזת של Nadeko. מובטח כי $s$ מכילה רק אותיות קטנות.
פלט
בשורה בודדת, הדפיסו מחרוזת כלשהי $t$ באורך מינימלי המקיימת את תנאי הבעיה.
דוגמאות
קלט 1
aaaa
פלט 1
aaa
קלט 2
bba
פלט 2
bab
הערה
בדוגמה השנייה, המחרוזת bab מכילה את bb, ba, a, b כתתי-סדרות אך אינה מכילה את bba. כמו כן ברור שאי אפשר לבנות סדרה חוקית באורך $2$, ולכן bab היא תשובה אפשרית.