I - ABCBA Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

S を接頭辞に持つ最短の回文を 1 つ求めてください。

制約

  • S は英大文字からなる長さ 1 以上 500000 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。
解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

ABC

出力例 1

ABCBA

ABCBA は S= ABC を接頭辞に持つ最短の回文です。

入力例 2

Z

出力例 2

Z

Z は S= Z を接頭辞に持つ最短の回文です。

入力例 3

TREE

出力例 3

TREERT

TREERT は S= TREE を接頭辞に持つ最短の回文です。

Score : 500 points

Problem Statement

Find one shortest palindrome that has S as its prefix.

Constraints

  • S is a string of length between 1 and 500000, inclusive, consisting of uppercase English letters.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.
If multiple solutions exist, any of them is accepted.

Sample Input 1

ABC

Sample Output 1

ABCBA

ABCBA is a shortest palindrome that has S= ABC as its prefix.

Sample Input 2

Z

Sample Output 2

Z

Z is a shortest palindrome that has S= Z as its prefix.

Sample Input 3

TREE

Sample Output 3

TREERT

TREERT is a shortest palindrome that has S= TREE as its prefix.