У вас есть строка $$$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$$$, если и только если выполняется один из следующих пунктов:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$): количество наборов входных данных.
Следующие $$$t$$$ строк содержат описания наборов, по две строки на набор.
В первой строке записано целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$): длина строки.
Во второй строке записана строка $$$s$$$ длины $$$n$$$, состоящая из маленьких латинских букв.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите лексикографически минимальную строку, которую вы можете увидеть.
4 10 codeforces 9 cbacbacba 3 aaa 4 bbaa
cc cbaabc aa bb
В первом примере выберем $$$k = 1$$$, чтобы получить «cc».
Во втором примере выберем $$$k = 3$$$, чтобы получить «cbaabc».
В третьем примере выберем $$$k = 1$$$, чтобы получить «aa».
В четвертом примере выберем $$$k = 1$$$, чтобы получить «bb».
| Good Bye 2021: 2022 is NEAR |
|---|
| Закончено |
