Background

Description

Given a string, look for a mirror image (backwards) string at both the beginning and end of the given string. In other words, zero or more characters at the very begining of the given string, and at the very end of the string in reverse order (possibly overlapping). For example, the string "abXYZba" has the mirror end "ab".

Format

Input

Output

Samples

abXYZba

"ab"

abca

"a"

aba

"aba"

Limitation

1s, 1024KiB for each test case.