Artokhlam
Malhotra, Arthochlam, Malhotra!
Boy Akim
Once upon a time, a boy named Akim from class D' discovered a printout of the Malhotra-Kumar-Maheshwari article in the fourth compartment. Naturally, it was in Hindi. He carried it with him through the rain and later read it aloud to his friends in the evening.
His friends couldn't understand a thing, and the most skeptical among them speculated that something peculiar might have occurred: one of the pages (let's call it page number p) got wet, causing its content to transfer, first onto the reverse side (i.e., page number p+1) in a mirrored form, and then onto the subsequent page (i.e., page number p+2).
To test this theory, the students of class D' have asked you to find the longest substring in Akim's speech notes that can be expressed in the form αα^rα, where α is a string, and α^r is the reverse of α.
Input
The input file contains a string s - Akim's speech notes. The string consists only of characters with ASCII codes from 32 to 126 (inclusive) and does not exceed 100000 characters in length.
Output
In the output file, print the longest substring s that fits the form αα^rα. If there are multiple solutions, you may print any one of them. If no such substring exists, print the string "None" (without quotes).