Мистер Китаюта любезно предоставил Вам строку s из строчных букв латинского алфавита. Он просит вас вставить ровно одну строчную букву латинского алфавита в s так, чтобы получился палиндром. Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, «noon», «testset» и «a» — палиндромы, а «test» и «kitayuta» — нет.
Вы можете выбрать любую строчную букву латинского алфавита и вставить её в любую позицию s, в частности, можно вставить в начало или в конец s. Букву надо вставить, даже если данная строка уже является палиндромом.
Если возможно вставить одну строчную букву латинского алфввита в s так, чтобы получившаяся строка была палиндромом, выведите состояние строки после вставки. В противном случае выведите «NA». Если возможно получить более одного палиндрома, можно вывести любой из них.
Выходные данные
Если можно превратить строку s в палиндром, вставив одну строчную букву латинского алфавита, выведите итоговую строку в единственной строке. В противном случае выведите «NA» (без кавычек, регистр имеет значение). Если существует более одного решения, будет засчитано любое.
Примечание
В первом можно добавить «r> к концу строки «revive», чтобы получить палиндром «reviver».
Во втором примере решений несколько. Например, «eve» также будет засчитан.
В третьем примере невозможно превратить «kitayuta» в палиндром путем прибавления одной буквы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
revive
|
reviver
|
|
2
|
ee
|
eye
|
|
3
|
kitayuta
|
NA
|