У Гомера есть два друга — Алиса и Боб. Оба они фанаты строк.
Однажды Алиса и Боб решили сыграть в игру на строке \(s = s_1 s_2 \dots s_n\) длиной \(n\), состоящей из строчных английских букв. Они ходят по очереди, Алиса начинает.
В свой ход игрок должен выбрать индекс \(i\) (\(1 \leq i \leq n\)), который не был выбран ранее, и поменять \(s_i\) на любую другую строчную английскую букву \(c\), удовлетворяющую \(c \neq s_i\).
Когда все индексы уже были выбраны по одному разу, игра заканчивается.
Цель Алисы — сделать финальную строку лексикографически как можно меньше, в то время как цель Боба — сделать финальную строку лексикографически как можно больше. Оба они являются профессиональными игроками, поэтому всегда играют оптимально. Гомер не является профессиональным игроком, поэтому ему интересно, какой будет финальная строка.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Примечание
В первом наборе входных данных: Алиса делает первый ход и должна поменять единственную букву на другую, поэтому она меняет ее на «b».
Во втором наборе входных данных: Алиса меняет первую букву на «a», затем Боб меняет вторую букву на «z», Алиса меняет третью букву на «a», а затем Боб меняет четвертую букву на «z».
В третьем наборе входных данных: Алиса меняет первую букву на «b», а затем Боб меняет вторую букву на «y».