Текущий пароль Монокарпа на Codeforces — это строка \(s\), состоящая из строчных латинских букв. Монокарп считает, что его текущий пароль слишком слабый, поэтому он хочет вставить ровно одну строчную латинскую букву в пароль, чтобы сделать его сильнее. Монокарп может выбрать любую букву и вставить ее в любое место, даже перед первым символом или после последнего символа.
Монокарп считает, что сила пароля пропорциональна времени, которое ему требуется для его ввода. Время, необходимое для ввода пароля, рассчитывается следующим образом:
- время для ввода первого символа составляет \(2\) секунды;
- для каждого символа, кроме первого, время ввода составляет \(1\) секунда, если он такой же, как предыдущий символ, или \(2\) секунды в противном случае.
Например, время, необходимое для ввода пароля abacaba, составляет \(14\); время, необходимое для ввода пароля a, составляет \(2\); время, необходимое для ввода пароля aaabacc, составляет \(11\).
Вам нужно помочь Монокарпу — вставить строчную латинскую букву в его пароль так, чтобы получившийся пароль требовал максимально возможное время для ввода.
Выходные данные
Для каждого набора входных данных выведите новый пароль — строку, которую можно получить из \(s\), вставив одну строчную латинскую букву. Строка, которую вы выводите, должна занимать максимальное возможное время для ввода. Если есть несколько ответов, выведите любой из них.