У вас есть строка \(s_1 s_2 \ldots s_n\), вы стоите слева от нее и смотрите направо. Вы хотите выбрать индекс \(k\) (\(1 \le k \le n\)) и поставить зеркало после \(k\)-го символа строки, таким образом, вы будете видеть строку \(s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1\). Какую лексикографически минимальную строку вы можете увидеть?
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите лексикографически минимальную строку, которую вы можете увидеть.
Примечание
В первом примере выберем \(k = 1\), чтобы получить «cc».
Во втором примере выберем \(k = 3\), чтобы получить «cbaabc».
В третьем примере выберем \(k = 1\), чтобы получить «aa».
В четвертом примере выберем \(k = 1\), чтобы получить «bb».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa
|
cc
cbaabc
aa
bb
|