Description

给定一个字符串 $s$，请求出一个最短的字符串 $t$，满足 $s$ 是 $t$ 的最长 border。

称字符串 $s$ 是字符串 $t$ 的 border，当且仅当 $s$ 是满足以下三者皆成立的字符串：

• $s$ 为 $t$ 的前缀。
• $s$ 为 $t$ 的后缀。
• $s$ 不为 $t$。

如果有多个可能的最短的 $t$，输出任意一个均可。

Input Format

一行一个只由小写英文字母组成的的字符串 $s$。

Output Format

一行一个只由小写英文字母组成的的字符串 $t$。

如果有多个可能的最短的 $t$，输出任意一个均可。

qwq

qwqwq

lingyu

lingyulingyu

aaaaaaabaa

aaaaaaabaaaaaaabaa

Hint

【样例 #1 解释】

$t=\texttt{qwqwq}$ 的最长 border 为 $s=\texttt{qwq}$，且可以证明不存在更小的符合要求的 $t$，所以输出是正确的。

$t=\texttt{qwqaqwq}$ 符合条件，但是它不是最短的，所以不是可能的输出。

$t=\texttt{qwqwqwq}$ 不符合条件，因为它的最长 border 为 $\texttt{qwqwq}$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le |s|\le 1\times10^6$，$s$ 仅由小写英文字母构成。其中，$|s|$ 表示 $s$ 的长度。