Thanos

Interview

Time limit1sMemory limit1024 MB

Summary

Given a binary string with even counts of 0s and 1s, keep exactly half of each digit and output the lexicographically smallest subsequence that remains.

Level: Medium5 of 10
Topics: Greedy, String
Solved: No attempts yet

Problem

One day, Thanos saw a string $S$ made of 0s and 1s. Strangely, the number of 0s in $S$ and the number of 1s in $S$ are both even.

In a fit of spite, Thanos wants to remove half of the 0s and half of the 1s from $S$ to form a new string $S'$ . Find the lexicographically smallest string that $S'$ can be.

Input

A single line containing the string $S$ .

Output

Print the lexicographically smallest string that can be $S'$ .

Constraints

$S$ has a length of at least $2$ and at most $500$ .

$S$ contains an even number of 0s and an even number of 1s.

Examples2

Example 1
Input
```
1010
```
Expected output
```
01
```
Example 2
Input
```
000011
```
Expected output
```
001
```