CF137D.Palindromes

Friday is Polycarpus' favourite day of the week. Not because it is followed by the weekend, but because the lessons on Friday are 2 IT lessons, 2 math lessons and 2 literature lessons. Of course, Polycarpus has prepared to all of them, unlike his buddy Innocentius. Innocentius spent all evening playing his favourite game Fur2 and didn't have enough time to do the literature task. As Innocentius didn't want to get an F, he decided to do the task and read the book called "Storm and Calm" during the IT and Math lessons (he never used to have problems with these subjects). When the IT teacher Mr. Watkins saw this, he decided to give Innocentius another task so that the boy concentrated more on the lesson and less — on the staff that has nothing to do with IT.

Mr. Watkins said that a palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. A concatenation of strings a, b is a string ab that results from consecutive adding of string b to string a. Of course, Innocentius knew it all but the task was much harder than he could have imagined. Mr. Watkins asked change in the "Storm and Calm" the minimum number of characters so that the text of the book would also be a concatenation of no more than k palindromes. Innocentius can't complete the task and therefore asks you to help him.

星期五是波利卡普斯最喜欢的一周中的日子。这并不是因为星期五之后就是周末，而是因为在星期五有两节信息技术课、两节数学课和两节文学课。当然，波利卡普斯为所有这些课程都做了充分准备，而他的朋友无辜者（Innocentius）却并非如此。无辜者整个晚上都在玩他最喜欢的游戏《Fur2》，以至于没有足够的时间完成文学作业。由于无辜者不想得一个“F”（不及格），他决定在信息技术课和数学课上完成这项作业，并阅读名为《风暴与宁静》（"Storm and Calm"）的书（他在这两门学科上向来从不遇到困难）。当信息技术老师沃特金斯先生（Mr. Watkins）看到这一幕时，他决定给无辜者布置另一项任务，以便让这个男孩将更多注意力集中于课堂内容，而更少地关注那些与信息技术毫无关系的事情。

沃特金斯先生解释道：回文（palindrome）是一个字符串，它无论从左到右读还是从右到左读，结果都完全相同。字符串 $a$ 与 $b$ 的连接（concatenation）是指将字符串 $b$ 连续添加到字符串 $a$ 末尾所形成的字符串 $ab$。当然，无辜者对这些概念早已了然于胸，但这次的任务却远比他所能想象的要困难得多。沃特金斯先生要求：修改《风暴与宁静》这本书的文本，使其成为至多 $k$ 个回文串的连接，且修改的字符数量应达到最小。无辜者无法独立完成这项任务，因此请求你的帮助。

The first input line contains a non-empty string s which is the text of "Storm and Calm" (without spaces). The length of the string s does not exceed 500 characters. String s consists of uppercase and lowercase Latin letters. The second line contains a single number k (1 ≤ k ≤ |s|, where |s| represents the length of the string s).

第一行输入包含一个非空字符串 $s$，该字符串为小说《风暴与平静》的文本（不含空格）。字符串 $s$ 的长度不超过 500 个字符。字符串 $s$ 仅由大写和小写的拉丁字母组成。第二行输入为一个整数 $k$（$1 ≤ k ≤ |s|$，其中 $|s|$ 表示字符串 $s$ 的长度）。

Print on the first line the minimum number of changes that Innocentius will have to make. Print on the second line the string consisting of no more than k palindromes. Each palindrome should be non-empty and consist of uppercase and lowercase Latin letters. Use the character "+" (ASCII-code 43) to separate consecutive palindromes. If there exist several solutions, print any of them.

The letters' case does matter, that is an uppercase letter is not considered equivalent to the corresponding lowercase letter.

第一行输出 Innocentius 所需进行的最少修改次数。
第二行输出一个由至多 $k$ 个回文串组成的字符串。每个回文串必须非空，且仅由大写和小写拉丁字母组成。使用字符 “+”（ASCII 码 43）分隔相邻的回文串。若存在多种可行解，输出任意一种即可。

注意：字母的大小写敏感，即大写字母与对应的小写字母不视为等价。