Algorithms and Data Structures

Remove consecutive duplicates from a string

Given a string s, you are asked to remove all the consecutive duplicate letters from it. As long as there are consecutive equal letters, the leftmost two of those should be removed. This process should be repeated until no consecutive equal letters are present in the string s. So, the final string should not contain any consecutive duplicate letters.

Input

The input contains a single line s (1 ≀ |s| ≀ ).

Output

The programs should print the resulting string after removals.

Examples

Input
Output
abbac
c
dabbaaa
d
helloo!oo
he!
xabbay
xy
abcddcba
γ…€

Explanation

  1. abbac β†’ aac β†’ c
  1. dabbaaa β†’ daaaa β†’ daa β†’ d
  1. helloo!oo β†’ heoo!oo β†’ he!oo β†’ he!
  1. xabbay β†’ xaay β†’ xy
  1. abcddcba β†’ abccba β†’ abba β†’ aa β†’
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue