Description

若长度为 $n$ 的字符串 $s$ 中可以选择一个位置 $i$，使得 $\overline{s_i\cdots s_ns_1\cdots s_{i-1}}=t$，则称 $s$ 与 $t$ 循环同构。字符串 $s$ 的最小表示为与 $s$ 循环同构的所有字符串中字典序最小的字符串。

给定一个长度为 $n$ 的字符串 $s$，请求出 $s$ 的最小表示。

Input Format

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $s$。

Output Format

一行，一个字符串，为 $s$ 的最小表示。

10
caacabcaab

aabcaacabc

Hint

对于全部数据，$1\le n\le 10^7$，字符串 $s$ 仅包含小写英文字母（ASCII $97\sim 122$）。

设置以下三档部分分，用于测试不同解法：

• 对于 $20\%$ 的数据，$n\le 10^3$；
• 对于 $50\%$ 的数据，$n\le 10^5$；
• 对于 $100\%$ 的数据，无特殊限制。