Антипалиндром (28%)

Время: 1 сек.
Память: 16 Мб
Сложность: 28%

Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом.

Формат ввода

Входной файл input.txt содержит строку s. Она состоит только из строчных букв английского алфавита, не пуста, а ее длина не превышает 100 000 символов.

Формат вывода

В выходной файл output.txt выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Примеры

Ввод	Вывод
abba	abb
abc	abc
aaaaa	NO SOLUTION