У Васи есть строка \(s\) длины \(n\). Он решает применить к ней следующее преобразование:
- Выберите целое \(k\), (\(1 \leq k \leq n\)).
- Для \(i\) от \(1\) до \(n-k+1\), переверните подстроку \(s[i:i+k-1]\) строки \(s\). К примеру, если строка \(s\) равна qwer и \(k = 2\), то строка пройдет следующую последовательность изменений:
- qwer (начальная строка)
- wqer (после переворачивания первой подстроки длины \(2\))
- weqr (после переворачивания второй подстроки длины \(2\))
- werq (после переворачивания последней подстроки длины \(2\))
Следовательно, получившаяся строка после преобразования \(s\) с \(k = 2\) равна werq.
Вася хочет выбрать такое \(k\), чтобы строка, полученная в результате преобразования, была лексикографически минимальной возможной среди всех выборов \(k\). Среди всех таких \(k\) он хочет выбрать наименьшее. Так как он занят посещением Felicity 2020, он просит вашей помощи.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите две строки:
В первой строке выведите лексикографически минимально возможную строку \(s'\), получающуюся как результат преобразования.
Во второй строке выведите подходящее значение \(k\) (\(1 \leq k \leq n\)), которое вы выбрали для преобрразования. Если несколько значений \(k\) дают лексикографически минимальную строку, выведите минимальное \(k\) среди них.
Примечание
В первом наборе тестовых данных примера, преобразование строки abab даст следующие результаты:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p
|
abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1
|