Compress String

Given a string lowercase alphabet s, eliminate consecutive duplicate characters from the string and return it.

That is, if a list contains repeated characters, they should be replaced with a single copy of the character. The order of the elements should not be changed.

Constraints

• 0 ≤ n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Compress-String

Examples

Example 1

Input

• s = a

Output

• answer = a

Example 2

Input

• s = aaaaaabbbccccaaaaddf

Output

• answer = abcadf

Solution