CF319D.Have You Ever Heard About the Word?

A substring of a string is a contiguous subsequence of that string. So, string bca is substring of string abcabc, but string cc is not.

A repeating block is a string formed by concatenating some string with itself. So, string abcabc is a repeating block, but strings abcabd, ababab are not.

You've got a sequence of Latin characters (string). At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. As the substring is of form XX (X — some string) you replace this substring with X, in other words you delete one of the X substrings in the substring. You repeat this process until there remains no repeating block in the string.

How would the final string looks like? Look at the sample explanation to understand the statement more precise.

字符串的子串是指该字符串的一个连续子序列。例如，字符串 bca 是字符串 abcabc 的子串，但字符串 cc 不是。

重复块（repeating block）是指将某个字符串与其自身连接所形成的字符串。例如，字符串 abcabc 是一个重复块，但字符串 abcabd、ababab 不是。

你有一个由拉丁字母字符组成的序列（即字符串）。在每一步中，你需找出最短的、是重复块的子串；若存在多个这样的子串，则必须选择最左侧的那个。由于该子串形如 XX（其中 X 为某个字符串），你将该子串替换为 X，即删除该子串中的一个 X。你不断重复此过程，直到字符串中不再含有任何重复块为止。

最终得到的字符串是什么？请参阅样例解释以更准确地理解题意。

In the first line of input you're given a string of small Latin characters with length between 1 to 50000, inclusive.

输入的第一行给出一个由小写拉丁字母组成的字符串，其长度在 1 到 50000（含）之间。

Print the final string after applying changes.

输出应用更改后的最终字符串。

At the first sample the string transforms as follows: abccabc  →  abcabc  →  abc.

At the second sample the string transforms as follows: aaaabaaab  →  aaabaaab  →  aabaaab  →  abaaab  →  abaab  →  abab  →  ab.

第一个样例中，字符串的变换过程如下：abccabc  →  abcabc  →  abc。

第二个样例中，字符串的变换过程如下：aaaabaaab  →  aaabaaab  →  aabaaab  →  abaaab  →  abaab  →  abab  →  ab。