Antipalindrome

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.

Input

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

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.

Examples