У IA есть невероятно много цветных магнитиков на её холодильнике. На каждом магнитике написана одна буква «a» или «b». Она любит играть с ними, располагая все магнитики в ряд. Однако девочка быстро устаёт и начинает думать, как сделать её развлечение ещё более интересным.

Сегодня, когда IA взглянула на холодильник, она заметила, что слово, образованное магнитиками, выглядит достаточно сомнительно. «Пожалуй, будет гораздо лучше, если я поменяю некоторые из них местами, — думает она, — но как это сделать?». Через некоторое время к ней пришла неплохая идея. IA будет рассматривать все префиксы с длинами от $$$1$$$ до длины всего слова и для каждого префикса будет выбирать, стоит ли его развернуть или оставить как есть. Она будет рассматривать префиксы в фиксированном порядке: начнет с кратчайшего и закончит самым длинным. Она хочет получить в итоге лексикографически минимальное возможное слово. Можете ли вы помочь ей, сказав, какие именно из префиксов следует развернуть?

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

• $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
• в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.