Вам задана строка \(s\) длины \(n\), состоящая из букв a и/или b.
Пусть \(\operatorname{AB}(s)\) — это количество вхождений строки ab в \(s\) как подстроки. Аналогично, \(\operatorname{BA}(s)\) — это количество вхождений ba в \(s\) как подстроки.
За один шаг, вы можете выбрать индекс \(i\) и заменить \(s_i\) на букву a или b.
Какое наименьшее количество шагов нужно сделать, что бы достигнуть строки в которой \(\operatorname{AB}(s) = \operatorname{BA}(s)\)?
Напоминание:
Количество вхождений строки \(d\) в \(s\) как подстроки — это количество индексов \(i\) (\(1 \le i \le |s| - |d| + 1\)) таких, что подстрока \(s_i s_{i + 1} \dots s_{i + |d| - 1}\) равна \(d\). Например, \(\operatorname{AB}(\)aabbbabaa\() = 2\) так как есть ровно два индекса \(i\): \(i = 2\) с aabbbabaa и \(i = 6\) с aabbbabaa.
Выходные данные
Для каждого набора входных данных, выведите результирующую строку \(s\), в которой \(\operatorname{AB}(s) = \operatorname{BA}(s)\), и которую вы получите, сделав наименьшее возможное количество ходов.
Если существует несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных, и \(\operatorname{AB}(s) = 0\), и \(\operatorname{BA}(s) = 0\) (строка ab (ba) ни разу не входит в строку b). А потому мы можем оставить \(s\) нетронутой.
Во втором наборе, \(\operatorname{AB}(s) = 2\) и \(\operatorname{BA}(s) = 2\). Строку \(s\) можно оставить нетронутой.
В третьем наборе, \(\operatorname{AB}(s) = 1\) и \(\operatorname{BA}(s) = 0\). Можно, например, заменить \(s_1\) на b, сделав оба значения равными нулю.
В четвертом наборе, \(\operatorname{AB}(s) = 2\) и \(\operatorname{BA}(s) = 1\). Можно, например, заменить \(s_6\) на a, сделав оба значения равными \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
b
aabbbabaa
abbb
abbaab
|
b
aabbbabaa
bbbb
abbaaa
|