DNPALIN - Double Near Palindromes

C-3PO is an expert in pretty much every language. His conversation with R2-D2 are always fun to observe in that R2-D2 speaks in Droid, C-3PO speak in English, and they understand each other perfectly! Anyway, humans and droids both enjoy playing word games. A palindrome is a word or sequence of one or more letters that reads the same forwards and backwards. A near palindrome is a word or sequence that can be changed to or kept a palindrome by changing exactly one letter to a different letter. For example. BAT is a near palindrome, since changing the T to a B would make the word a palindrome: BAB. PEEP is not a near palindrome: although PEEP is palindrome, changing any letter would remove its palindrome status. A double near palindrome is a word or sequence that consist of two near palindromes concatenated together. For example, BATMAN is a double near palindrome, since BAT and MAN are both near palindromes. Given a list of words, you are to determine which words are double near palindromes and which are not.

Input

The input consists of one or more words. All words (except the last) will be inclusively between 1 and 25 letters long and will consist of entirely of capital letters. The last word will be *END* and is not be processed; it simply indicates the end of the input. There may be any number of spaces and characters before, after, and between words.

Output

The output cases are to appear in the same order in which they appear in the input. For each input case, you are to print either w is a double near palindrome. or w is not a double near palindrome. whichever is appropriate, where w is the input word. Exactly one should follow each output case (meaning there should be no blank lines in the output).

Example

Input:
BATMAN
CONSTANTINOPLE
*END*

Output:
BATMAN is a double near palindrome.
CONSTANTINOPLE is not a double near palindrome.

Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:2007 U.Nacional - Circuito de Maratones ACIS / REDIS

hide comments
2009-06-01 04:06:39 Vaibhav
Just a query: A concatenation of two strings a[1..m] and b[1..n] is c = a[1..m] + b[1..n], right?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.