星期五是波利卡普斯一周中最喜欢的一天。不是因为接下来是周末,而是因为周五的课程是 2 节 IT 课、2 节数学课和 2 节文学课。当然,波利卡帕斯已经为所有人做好了准备,这与他的好友因诺森提乌斯不同。 Innocentius整个晚上都在玩他最喜欢的游戏Fur2,没有足够的时间来做文学任务。由于Innocentius不想得F,他决定完成这项任务,并在IT和数学课上读了一本名为《风暴与平静》的书(他以前在这些科目上从来没有遇到过问题)。当 IT 老师 Watkins 先生看到这一情况时,他决定给 Innocentius 布置另一项任务,让这个男孩更多地专注于课程,而不是专注于与 IT 无关的工作人员。
沃特金斯先生说,回文是一个可以在任一方向以相同方式读取的字符串,从左到右和从右到左。字符串 a、b 的串联是字符串 ab,是字符串 b 与字符串 a 连续相加的结果。当然,伊诺琴蒂斯知道这一切,但任务比他想象的要困难得多。沃特金斯先生要求更改《暴风雨与平静》中的最小字符数,以便该书的文本也将是不超过 k 个回文的串联。因诺森提斯无法完成任务,因此要求你帮助他。
输入
第一输入行包含一个非空字符串 s,它是“Storm and Calm”的文本(不带空格)。字符串s的长度不超过500个字符。字符串 s 由大写和小写拉丁字母组成。第二行包含单个数字 k(1 ≤ k ≤ |s|,其中 |s| 表示字符串 s 的长度)。
输出
在第一行打印 Innocentius 必须进行的最少更改数。在第二行打印由不超过 k 个回文组成的字符串。每个回文应该是非空的,并且由大写和小写拉丁字母组成。使用字符“+”(ASCII 代码 43)分隔连续的回文。如果存在多个解决方案,请打印其中任何一个。
字母的大小写确实很重要,即大写字母不被视为等同于相应的小写字母。
示例
输入 #1
abacaba 1
输出 #1
0 abacaba
输入 #2
abdcaba 2
输出 #2
1 abdcdba
输入 #3
abdcaba 5
输出 #3
0 a+b+d+c+aba
输入#4
abacababababbcbabcd 3
输出#4
1 abacaba+babab+bcbabcb