• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک رشته از حروف کوچک انگلیسی به نام $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 خواهد بود.