Условие
Дано неотрицательное целое число N. Переставьте его цифры так, чтобы сначала шли все чётные цифры, а затем все нечётные. Внутри каждой группы сохраните порядок следования цифр в исходном числе слева направо. Цифра 0 считается чётной. Для хранения полученного числа и промежуточных результатов его построения используйте тип long long: результат может превышать границу 32-битного int, но помещается в знаковый 64-битный тип (−2⁶³ … 2⁶³ − 1).
Ограничения
Время: 2 секунды. Память: 64 МиБ. Вывод: до 2 МиБ. Стандарты: C11 / C++17.
Входные данные
Одно целое число N. Ограничение: 0 ≤ N ≤ 2³¹ − 1.
Выходные данные
Одно целое число, полученное перестановкой цифр. Ведущие нули не выводите. Если результат равен нулю, выведите 0.
Примеры
Вход 1
12345
Ожидаемый выход
24135
Вход 2
1003
Ожидаемый выход
13
Вход 3
0
Ожидаемый выход
0