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

---

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