题目描述

《求目标串》

【求目标串】 给定一个字符串 s，请求出一个最短的字符串 t，满足 s 是 t 的最长 border。 称字符串 s 是字符串 t 的 border，当且仅当 s 是满足以下三者皆成立的字符串： 1、s 为 t 的前缀。 2、s 为 t 的后缀。 3、s 不为 t。 如果有多个可能的最短的 t，输出任意一个均可。

输入格式

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

输出格式

一行一个只由小写英文字母组成的的字符串 t。 如果有多个可能的最短的 t，输出任意一个均可。

样例

输入样例 1

qwq

输出样例 1

qwqwq

输入样例 2

abcdef

输出样例 2

abcdefabcdef

输入样例 3

lingyu

输出样例 3

lingyulingyu

输入样例 4

ababab

输出样例 4

abababab

输入样例 5

aaaaaaabaa

输出样例 5

aaaaaaabaaaaaaabaa

输入样例 6

abcabcabd

输出样例 6

abcabcabdabcabcabd