Müller tried to catch Stierlitz red-handed many times, but always
failed because Stierlitz could ever find some excuse. Once Stierlitz was
looking through his email messages. At that moment, Müller entered
secretly and watched a meaningless sequence of symbols appear on the screen.
“A cipher message,” Müller thought.
“UTF-8,” Stierlitz thought.
It is known that Stierlitz ciphers messages by the following method.
- He deletes all spaces and punctuation marks.
- He replaces all successive identical letters by one such letter.
- He inserts two identical letters at an arbitrary place many times.
Try to restore a message as it was after the second step. For that, remove from
the message all pairs of identical letters inserted at the third step.
The only input line contains a message ciphered by Stierlitz. The message
consists of lowercase English letters and its length is at most 200000.
Output the restored message.
Problem Author: Vladimir Yakovlev (idea by Alexander Klepinin)
Problem Source: NEERC 2008, Eastern subregion quarterfinals