Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, строки «z», «aa», «aba» и «abccba» — палиндромы, а «codeforces» и «ab» — нет. Вы ненавидите палиндромы, потому что они вызывают у вас дежавю.
Дана строка \(s\). Вы должны вставить ровно один символ 'a' в \(s\). Если таким образом можно получить строку, которая не является палиндромом, вам нужно найти одну из них. В противном случае следует сообщить, что это невозможно.
Например, предположим, что \(s=\) «cbabc». Вставив 'a', можно получить «acbabc», «cababc», «cbaabc», «cbabac», или «cbabca». Строка «cbaabc» — палиндром, и не подходит, поэтому вы должны вывести другую из вышеперечисленных строк.
Выходные данные
Для каждого набора входных данных, если нет решения, выведите «NO».
В противном случае выведите «YES», а в следующей строке выведите строку длиной \(|s|+1\). Если есть несколько решений, можно вывести любое из них.
Вы можете выводить каждый символ «YES» и «NO» в любом регистре.
Примечание
Первый набор входных данных описан в условии.
Во втором наборе входных данных можно получить либо «aab», либо «aba». Но «aba» — это палиндром, поэтому «aab» — единственный правильный ответ.
В третьем наборе входных данных «zaza» и «zzaa» — правильные ответы, а «azza» — нет.
В четвертом наборе входных данных «baa» — единственный правильный ответ.
В пятом наборе входных данных мы можем получить только «aa», что является палиндромом. Следовательно, ответ «NO».
В шестом наборе входных данных «anutforajaroftuna» — палиндром, но вставка 'a' в любом другом месте подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
cbabc
ab
zza
ba
a
nutforajaroftuna
|
YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna
|