题目背景

$$\begin{array}{cr} \text{在燥热的黑暗中}\\ \text{折叠陈旧的心}\\ \text{不禁开始自我怀疑}\\ \text{布满}\overset{\text{Wrong Answer}}{\text{谬误}}\text{的曾经}\\ &\text{——《第一首歌》} \end{array} $$

---

那个绝对不能忘却的人，如今还能在回忆中找到些许线索吗？

她的名字，即使只记得一部分，泠珞也想要请你帮忙还原呢。

题目描述

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

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

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

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

输入格式

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

输出格式

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

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

qwq

qwqwq

lingyu

lingyulingyu

aaaaaaabaa

aaaaaaabaaaaaaabaa

提示

【样例 #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$ 的长度。

子任务编号	分值	$\vert s\vert\le$	特殊性质
$1$	$17$	$4$	无
$2$	$29$	$3\times10^3$
$3$	$11$	$1\times10^6$	$s$ 仅由一种字符组成
$4$	$43$		无