Practice Greedy algorithms with the exercise "Maximising integers"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Greedy algorithms

Statement

Goal

You are given an integer N. Your goal is to create the largest integer possible.

To do this, you may swap any two adjacent digits as long as they are of different parity. For example, you may swap an odd digit and an even digit, but not two even digits. You may perform as many swaps as you like.

Input

One integer N.

Output

The maximised integer. (You do not need to worry about leading zeros, as they will never be optimal.)

Constraints

N consists of at most 900 digits.

Example

Input

Output

Solve it

A higher resolution is required to access the IDE