Repetition-Free String

You are given a string s. Your task is to transform the string into a repetition-free string by removing the fewest number of characters such that no two adjacent characters are identical. In other words, if two consecutive characters are the same, you must remove the extra occurrences so that only one instance remains.

If there are multiple ways to achieve this, you must choose the one which is lexicographically smallest.

More formally, let the input string be represented as \( s = s_1s_2\ldots s_n \). You are to remove a set of indices \( I \) such that for the resulting string \( t \), where \( t = s_1' s_2' \ldots s_k' \), we have \( s_i' \neq s_{i+1}' \) for all valid indices, and the number of removed characters \( |I| \) is minimized. If there are several such strings, output the one with the smallest lexicographical order.

Examples:

• For s = "aaaa", the answer is a.
• For s = "ababab", the answer is ababab.
• For s = "aabbcc", the answer is abc.
• For s = "aabac", the answer is abac.
• For s = "abbaaacddc", the answer is abacdc.
• For s = "abcdabcdab", the answer is abcdabcdab.

inputFormat

The input consists of a single line containing a non-empty string s.

The string may consist of lowercase and uppercase letters as well as other printable characters.

outputFormat

Output a single line containing the transformed repetition-free string.

## sample

aaaa

a

</p>