Согласно новой парольной политике осталось одно требование к паролю - он не должен являться палиндромом. Поэтому нужно проверить и исправить все существующие пароли.

Для заданной строки s найдите её наибольшую по длине подстроку, не являющуюся палиндромом.

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

На вход подаётся одна строка s. Она состоит только из строчных букв латинского алфавита, не пуста, а ее длина не превышает 100000 символов.

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

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

Пример