Вам задано длинное число \(a\), состоящее из \(n\) цифр (\(n\) от \(1\) до \(3 \cdot 10^5\) включительно). Оно может содержать лидирующие нули.
Вы можете поменять местами две соседние цифры, если они имеют разную четность (т.е. они имеют разный остаток от деления на \(2\)).
Например, если \(a = 032867235\) вы можете получить следующие числа за одну операцию:
- \(302867235\) если поменяете местами первую и вторую цифры;
- \(023867235\) если поменяете местами вторую и третью цифры;
- \(032876235\) если поменяете местами пятую и шестую цифры
- \(032862735\) если поменяете местами шестую и седьмую цифры;
- \(032867325\) если поменяете местами седьмую и восьмую цифры.
Обратите внимание, что вы не можете поменять местами цифры на позициях \(2\) и \(4\), потому что эти позиции не соседние. Так же, вы не можете поменять местами цифры на позициях \(3\) и \(4\), потому что эти цифры имеют одинаковую четность.
Вы можете выполнять любое (возможно, нулевое) количество таких операций.
Найдите минимальное число, которое вы можете получить.
Обратите внимание, что ответ так же может содержать лидирующие нули.
Примечание
В первом наборе вы можете выполнить следующую последовательность операций (пара цифр, которую вы меняете местами, выделена): \(0 \underline{\textbf{70}} 9 \rightarrow 0079\).
Во втором наборе изначальное число является оптимальным.
В третьем наборе вы можете выполнить следующую последовательность операций: \(246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642\).