← 返回题目列表

Codeforces · 319/D

D. 你听说过这个词吗?

中文机器翻译题面 查看原题

字符串的子字符串是该字符串的连续子序列。因此,字符串 bca 是字符串 abcabc 的子字符串,但字符串 cc 不是。

重复块是通过将某个字符串与其自身连接而形成的字符串。因此,字符串 abcabc 是重复块,但字符串 abcabd、ababab 不是。

你有一个拉丁字符序列(字符串)。在每一步中,您都会找到作为重复块的最短子字符串,如果存在多个子字符串,则必须选择最左边的子字符串。由于子字符串的形式为 XX(X — 某个字符串),因此您可以将此子字符串替换为 X,换句话说,您删除了子字符串中的 X 个子字符串之一。重复此过程,直到字符串中不再有重复块为止。

最终的字符串会是什么样子?查看示例解释可以更准确地理解该语句。

输入

在输入的第一行中,您将获得一串小拉丁字符,长度在 1 到 50000 之间(含)。

输出

应用更改后打印最终字符串。

示例

输入 #1

abccabc

输出 #1

abc

输入 #2

aaaabaaab

输出 #2

ab

输入 #3

birdbirdbirdistheword

输出 #3

birdistheword

注意

在第一个示例中,字符串转换如下:abccabc → abcabc → abc。

在第二个示例中,字符串转换如下:aaaabaaab → aaabaaab → aabaaab → abaaab → abaab → abab → ab。