A palindrome is a string that reads the same on both sides. The string s is given. Find its longest substring that is not a palindrome.
The input file contains the string s. It consists only of lowercase letters of the Latin alphabet, is not empty, and its length does not exceed 100000 characters.
Output the answer to the problem into the output file; if there are several answers, choose the lexicographically minimal one. If all substrings of s are palindromes, output NO SOLUTION
.