У IA есть невероятно много цветных магнитиков на её холодильнике. На каждом магнитике написана одна буква «a» или «b». Она любит играть с ними, располагая все магнитики в ряд. Однако девочка быстро устаёт и начинает думать, как сделать её развлечение ещё более интересным.
Сегодня, когда IA взглянула на холодильник, она заметила, что слово, образованное магнитиками, выглядит достаточно сомнительно. «Пожалуй, будет гораздо лучше, если я поменяю некоторые из них местами, — думает она, — но как это сделать?». Через некоторое время к ней пришла неплохая идея. IA будет рассматривать все префиксы с длинами от \(1\) до длины всего слова и для каждого префикса будет выбирать, стоит ли его развернуть или оставить как есть. Она будет рассматривать префиксы в фиксированном порядке: начнет с кратчайшего и закончит самым длинным. Она хочет получить в итоге лексикографически минимальное возможное слово. Можете ли вы помочь ей, сказав, какие именно из префиксов следует развернуть?
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Выведите ровно \(|s|\) целых чисел. Если IA следует развернуть \(i\)-й префикс (то есть подстроку с индексами от \(1\) до \(i\)), то \(i\)-е число должно быть равно \(1\), иначе оно должно быть равно \(0\).
Если существует несколько возможных последовательностей, приводящих к оптимальному ответу — выведите любую из них.
Примечание
В первом примере IA может развернуть второй и третий префикс, получив строку «abbb». Она не может получить ответ лучше, так как это наименьшая строка, которую можно получить перестановкой символов в исходной строке.
Во втором примере, она может перевернуть любое подмножество префиксов — все буквы равны «a».