Best String

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

Description

Given a string, you use some letters or digits to creat a new string, this new string have three properties.
1. any two adjacent letter aren't the same.
2. the new string have the biggest length.
3. the new string have the biggest lexicographical ordering.

Input

The input consists of multiple test cases. Each test case contain a string, the string is consist of 'a'~'z', 'A' - 'Z' and '0' - '9'. the length of string is not exceed 500.

Output

For each case, print the new string.

Sample Input

2 abaa 001

Sample Output

aba 010

Hint

zhengfeng

Source

2010 ACM-ICPC Multi-University Training Con

提交代码