ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC 2008, Eastern subregion quarterfinals

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Cipher Message

Time limit: 1.0 second
Memory limit: 64 MB
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.
  1. He deletes all spaces and punctuation marks.
  2. He replaces all successive identical letters by one such letter.
  3. 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.

Input

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

Output the restored message.

Sample

inputoutput
wwstdaadierfflitzzz
stierlitz
Problem Author: Vladimir Yakovlev (idea by Alexander Klepinin)
Problem Source: NEERC 2008, Eastern subregion quarterfinals
To submit the solution for this problem go to the Problem set: 1654. Cipher Message