D. Палиндромы
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Пятница — любимый день недели Поликарпа. Не потому, что за пятницей идут выходные, а потому что в пятницу по расписанию 2 урока информатики, 2 математики и 2 литературы. Поликарп, конечно, подготовился ко всем урокам, чего не скажешь о его хорошем друге Иннокентие. Иннокентий не успел подготовиться к уроку литературы, поскольку весь вечер четверга провел за игрой в любимую игру Fur2. Чтобы не получить двойку Иннокентий решил выполнить домашнее задание по литературе и прочитать книгу «Буря и затишье» во время уроков информатики и математики (с этими предметами у Иннокентия никогда не было проблем). Увидев это, учитель информатики Валерий Петрович решил дать Иннокентию задание (чтобы тот не скучал и не занимался посторонними вещами).

Валерий Петрович сказал, что палиндромом называется строка, одинаково читающаяся как слева направо, так и справа налево. А конкатенацией строк a, b называется строка ab, получающаяся последовательным приписыванием строки b к строке a. Это все Иннокентий, конечно, знал, но задание было намного сложнее, чем он мог себе представить. Валерий Петрович попросил изменить в книге «Буря и затишье» наименьшее число символов, чтобы текст книги оказался конкатенацией не более k палиндромов. С такой задачей Иннокентий не в силах справиться, поэтому попросил вас помочь ему.

Входные данные

В первой строке входных данных задана непустая строка s — текст книги «Буря и затишье» (без пробелов). Длина строки s не превосходит 500 символов. Строка s состоит из строчных и заглавных латинских букв. Во второй строке находится одно число k (1 ≤ k ≤ |s|, где |s| обозначает длину строки s).

Выходные данные

В первой строке выведите наименьшее число изменений, которые придётся сделать Иннокентию. Во второй строке выведите строку, состоящую из не более чем k палиндромов. Каждый палиндром должен быть непустым и состоять из строчных и заглавных латинских букв. Для разделения палиндромов используйте знак «+» (ASCII-код 43). Если существует несколько решений выведите любое.

Регистр букв имеет значения, то есть большая буква считается не эквивалентной соответствующей маленькой букве.

Примеры
Входные данные
abacaba
1
Выходные данные
0
abacaba
Входные данные
abdcaba
2
Выходные данные
1
abdcdba
Входные данные
abdcaba
5
Выходные данные
0
a+b+d+c+aba
Входные данные
abacababababbcbabcd
3
Выходные данные
1
abacaba+babab+bcbabcb