+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک رشته از حروف کوچک انگلیسی به نام $s = s_1s_2\dots s_n \,$ داریم. منظور از یک «شیفت $s$» یعنی انتقال دادن $k$ حرف اول این رشته به آخر آن. ($ 1 \leq k \leq n \,$) به عبارت دیگر یک شیفت $s$، یک رشته به صورت زیر است:‌ $$s_{k + 1} \dots s_n s_1 s_2 \dots s_k$$ حال از شما می‌خواهیم با داشتن رشته $s$، رشته‌ای از این $n$ شیفت را پیدا کنید که در **ترتیب الفبایی کمینه** باشد. در ترتیب الفبایی، رشته $a$ از رشته $b$ کمتر است اگر اولین کاراکتر $a$ که با $b$ فرق دارد، در ترتیب الفبای انگلیسی زودتر آمده باشد. # ورودی در تنها سطر ورودی یک رشته از حروف کوچک انگلیسی مثل $s$ آمده است. $$1 \leq |s| \leq 100 \, 000$$ منظور از $|s|$ طول رشته $s$ است. # خروجی در تنها سطر خروجی رشته‌ای از حروف کوچک انگلیسی را چاپ کنید که شیفتی از $s$ بوده و به صورت الفبایی کمینه باشد. # مثال ## ورودی نمونه ۱ ``` nima ``` ## خروجی نمونه ۱ ``` anim ``` شیفت‌های `nima` عبارت است از `iman`، `mani`، `anim` و `nima` که رشته‌ای که در ترتیب الفبایی بین این ۴ رشته کوچک‌ترین است `anim` خواهد بود. ## ورودی نمونه ۲ ``` acabd ``` ## خروجی نمونه ۲ ``` abdac ``` شیفت‌های `acabd` عبارت است از `cabda`، `abdac`، `bdaca`، `dacab` و `acabd` است که رشته‌ای که در ترتیب الفبایی بین این ۵ رشته کوچک‌ترین است `abdac` خواهد بود.

حل سؤال در بانک سؤالات