A binary string is called special if:

The number of 1s is equal to the number of 0s. For every prefix of the string, the number of 1s is greater than or equal to the number of 0s.

You are given a special binary string S. In one operation, you may choose two adjacent special substrings and swap them. Your task is to obtain the lexicographically largest string possible after performing any number of operations.

Problem

Input

A single line containing a binary string S.

Output

Print the lexicographically largest string obtainable.

Constraints

• 1 ≤ |S| ≤ 5 × 10^4
• S is guaranteed to be a special binary string.

Example 1

Input

11011000

Output

11100100

Explanation

The string can be decomposed into special substrings and rearranged optimally: 11011000 → 1100 + 1000 → rearrange recursively → 11100100