题目描述

一天，小X写完了作业，开始研究字符串，他突然想到了一个问题，该怎么找到以 $S$ 为前缀的最短回文串，小X百思不得其解，肥肠伤心，你能帮帮小X吗

输入格式

一个字符串 $S$

输出格式

以 $S$ 为前缀的最短回文串

样例:

TREE

TREERT

提示

$1 \le |S| \le 5 × 10^{5}$