题目描述

周五是 Polycarpus 一周中最喜欢的日子。不是因为后面就是周末，而是因为周五的课是两节信息技术、两节数学和两节文学。当然，Polycarpus 全都预习好了，不像他的伙伴 Innocentius——Innocentius 整晚都在玩他最爱的游戏 Fur2，没时间做文学作业。Innocentius 不想挂科，于是决定在信息技术课和数学课上补做作业、读那本《风暴与平静》（这两科他从没遇到过问题）。当信息技术老师 Watkins 先生看到这一幕时，他决定给 Innocentius 出一道新题，好让这孩子把注意力放回课堂上。

Watkins 先生说：回文串是指从左往右读和从右往左读都相同的字符串。字符串 $a$、$b$ 的拼接是把 $b$ 接在 $a$ 后面得到的字符串 $ab$。这些 Innocentius 当然都知道，但这道题比他想象的难得多：Watkins 先生要求把《风暴与平静》的文本修改最少数量的字符，使整本书的文本变成至多 $k$ 个回文串的拼接。Innocentius 做不出来，只好请你帮忙。

输入格式

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

输出格式

第一行输出 Innocentius 需要修改的最少字符数。第二行输出由至多 $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