You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

消消乐(^_^)。

Description

给定一个字符串 $s$，你要对其进行如下操作：

• 找到一个长度 $\le \left \lfloor\dfrac{n}{2}\right \rfloor$ 的最长的前缀，使得其左右翻转后恰好为 $s$ 的后缀，删除该前缀和后缀。

你要输出 $s$ 在删除完毕后的样子。

Input

一行一个字符串 $s$。

Output

输出操作后的字符串。

Samples

aabbaa

样例解释1

前缀为 aab，后缀为 baa。

整个串 $s$ 都被删除了。

aabbccbaa

bcc

样例解释2

前缀为 aab，后缀为 baa。

还剩下 bcc。

aabbcccbbaa

c

样例解释3

前缀为 aabbc，后缀为 cbbaa。

还剩下 c。

Limitation

• 对于 $30\%$ 的数据，$1\le |s| \le 10^3$。
• 对于另外 $20\%$ 的数据，保证 $s$ 是回文串。
• 对于另外 $20\%$ 的数据，保证 $s$ 的每个字符随机从字符集中选择。
• 对于 $100\%$ 的数据，$1\le |s| \le 10^6$，$s$ 中的每个字符都是小写字母。