Palindromes

Interview

Time limit2sMemory limit512 MB

Summary

For each string, find the leftmost single-character deletion that leaves a palindrome, or report that none exists.

Level: Medium4 of 10
Topics: String, Two pointers, Brute force, Implementation
Solved: No attempts yet

Problem

A palindrome reads the same forwards and backwards. Given a string of lowercase letters, decide whether deleting exactly one character makes it a palindrome. Because one character is removed, the resulting string is one shorter than the original.

Input

Up to 30 lines, each containing 3 to 30 lowercase letters. The final line contains only # and must not be processed.

Output

Print one line of output for each input line. If deleting one letter can make a palindrome, print that palindrome. If it cannot, print not possible.

More than one deletion may give a palindrome. For example, madmam becomes mamam if the d is deleted, or madam if the middle m is deleted. In that case print the palindrome obtained by deleting the earliest letter, so try the deletion positions from left to right and print the first result that is a palindrome.

Examples4

Example 1

Input

radars
rayon
madmam
#

Expected output

radar
not possible
mamam

Example 2
Input
```
aba
aaa
abc
#
```
Expected output
```
aa
aa
not possible
```
Example 3
Input
```
abcba
abccba
abcdba
#
```
Expected output
```
abba
abcba
abdba
```
Example 4
Input
```
abc
#
```
Expected output
```
not possible
```