Fixing Typos

1000ms

262144K

Description:

Many modern text editors automatically check the spelling of the user's text. Some editors even suggest how to correct typos.

In this problem your task to implement a small functionality to correct two types of typos in a word. We will assume that three identical letters together is a typo (for example, word "helllo" contains a typo). Besides, a couple of identical letters immediately followed by another couple of identical letters is a typo too (for example, words "helloo" and "wwaatt" contain typos).

Write a code that deletes the minimum number of letters from a word, correcting described typos in the word. You are allowed to delete letters from both ends and from the middle of the word.

Input:

The single line of the input contains word s, its length is from 1 to 200000 characters. The given word s consists of lowercase English letters.

Output:

Print such word t that it doesn't contain any typos described in the problem statement and is obtained from s by deleting the least number of letters.

If there are multiple solutions, print any of them.

Sample Input:

helloo

Sample Output:

hello

Sample Input:

woooooow

Sample Output:

woow

Note:

The second valid answer to the test from the statement is "heloo".

Informação

Provedor Codeforces

Código CF363C