У Гомера есть два друга — Алиса и Боб. Оба они фанаты строк.

Однажды Алиса и Боб решили сыграть в игру на строке $$$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$$$.