Problem: 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.

Input

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).

Output

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.

Examples

Input

abacaba
1


Output

0
abacaba


Input

abdcaba
2


Output

1
abdcdba


Input

abdcaba
5


Output

0
a+b+d+c+aba


Input

abacababababbcbabcd
3


Output

1
abacaba+babab+bcbabcb

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class _T>
inline _T sqr(const _T &first) {
  return first * first;
}
template <class _T>
inline string tostr(const _T &a) {
  ostringstream os("");
  os << a;
  return os.str();
}
const long double PI = 3.1415926535897932384626433832795L;
const long double EPS = 1e-9;
char TEMPORARY_CHAR;
const int INF = 1e9;
inline void fft(vector<complex<long double> > &a, bool invert) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) j -= bit;
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1) {
    long double ang = 2 * PI / len * (invert ? -1 : 1);
    complex<long double> wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      complex<long double> w(1);
      for (int j = 0; j < len / 2; ++j) {
        complex<long double> u = a[i + j], v = a[i + j + len / 2] * w;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        w *= wlen;
      }
    }
  }
  if (invert)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
inline void input(int &a) {
  a = 0;
  while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') &&
         (TEMPORARY_CHAR != '-')) {
  }
  char neg = 0;
  if (TEMPORARY_CHAR == '-') {
    neg = 1;
    TEMPORARY_CHAR = getchar();
  }
  while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {
    a = (a << 3) + (a << 1) + TEMPORARY_CHAR - '0';
    TEMPORARY_CHAR = getchar();
  }
  if (neg) a = -a;
}
inline void out(long long a) {
  if (!a) putchar('0');
  if (a < 0) {
    putchar('-');
    a = -a;
  }
  char s[20];
  int i;
  for (i = 0; a; ++i) {
    s[i] = '0' + a % 10;
    a /= 10;
  }
  for (int j = (i)-1; j >= 0; j--) putchar(s[j]);
}
inline int nxt() {
  int(ret);
  input((ret));
  ;
  return ret;
}
struct lnum {
  vector<int> a;
  int base;
  lnum(int num = 0, int base = 1000000000) : base(base) {
    if (!num) a.resize(1);
    while (num) {
      a.push_back(num % base);
      num /= base;
    }
  }
  inline int len() const { return a.size(); }
  lnum &operator=(const lnum &l) {
    if (this != &l) {
      a = l.a;
      base = l.base;
    }
    return *this;
  }
  inline friend lnum operator+(const lnum &l, const lnum &r) {
    lnum ret(0, l.base);
    int base = l.base;
    int ln = l.len(), rn = r.len();
    int n = max(ln, rn);
    ret.a.resize(n);
    int o = 0;
    for (int i = 0; i < n; ++i) {
      int s = o;
      if (i < ln) s += l.a[i];
      if (i < rn) s += r.a[i];
      o = s >= base;
      if (o) s -= base;
      ret.a[i] = s;
    }
    if (o) ret.a.push_back(1);
    return ret;
  }
  inline friend lnum operator-(const lnum &l, const lnum &r) {
    lnum ret(0, l.base);
    int base = l.base;
    int n = l.len();
    int rn = r.len();
    ret.a.resize(n);
    int o = 0;
    for (int i = 0; i < n; ++i) {
      int s = l.a[i] - o;
      if (i < rn) s -= r.a[i];
      o = s < 0;
      if (o) s += base;
      ret.a[i] = s;
    }
    if (ret.len() > 1 && !ret.a.back()) ret.a.pop_back();
    return ret;
  }
  inline friend lnum operator*(const lnum &l, const lnum &r) {
    lnum ret(0, l.base);
    int base = l.base;
    if (l.len() * r.len() > 1000000) {
      vector<complex<long double> > fa(l.a.begin(), l.a.end()),
          fb(r.a.begin(), r.a.end());
      int n = 1;
      while (n < max(l.len(), r.len())) n <<= 1;
      n <<= 1;
      fa.resize(n), fb.resize(n);
      fft(fa, false), fft(fb, false);
      for (int i = 0; i < n; ++i) fa[i] *= fb[i];
      fft(fa, true);
      ret.a.resize(n);
      for (int i = 0; i < n; ++i) ret.a[i] = int(fa[i].real() + 0.5);
      int carry = 0;
      for (int i = 0; i < n; ++i) {
        ret.a[i] += carry;
        carry = ret.a[i] / base;
        ret.a[i] %= base;
      }
    } else {
      ret.a.resize(l.len() + r.len());
      for (int i = 0; i < l.len(); ++i)
        for (int j = 0, carry = 0; j < r.len() || carry; ++j) {
          long long cur = ret.a[i + j] +
                          (long long)l.a[i] * (j < r.len() ? r.a[j] : 0) +
                          carry;
          ret.a[i + j] = cur % base;
          carry = cur / base;
        }
    }
    while (ret.len() > 1 && !ret.a.back()) ret.a.pop_back();
    return ret;
  }
  inline friend lnum operator/(const lnum &l, const int &r) {
    lnum ret(0, l.base);
    ret.a.resize(l.len());
    int carry = 0;
    for (int i = l.len() - 1; i >= 0; --i) {
      long long cur = l.a[i] + (long long)carry * l.base;
      ret.a[i] = cur / r;
      carry = cur % r;
    }
    while (ret.len() > 1 && ret.a.back() == 0) ret.a.pop_back();
    return ret;
  }
  inline friend bool operator<(const lnum &l, const lnum &r) {
    if (l.len() < r.len()) return true;
    if (l.len() > r.len()) return false;
    int n = l.len();
    for (int i = n - 1; i >= 0; --i) {
      if (l.a[i] < r.a[i]) return true;
      if (l.a[i] > r.a[i]) return false;
    }
    return false;
  }
  inline friend bool operator>(const lnum &l, const lnum &r) { return r < l; }
  inline friend bool operator==(const lnum &l, const lnum &r) {
    if (l.len() != r.len()) return false;
    int n = l.len();
    for (int i = n - 1; i; --i) {
      if (l.a[i] != r.a[i]) return false;
    }
    return true;
  }
  inline friend bool operator!=(const lnum &l, const lnum &r) {
    return !(l == r);
  }
  inline void print() {
    if (base == 1000000000) {
      printf("%d", a.back());
      for (int i = a.size() - 2; i >= 0; --i) printf("%09d", a[i]);
    } else {
      for (int i = a.size() - 1; i >= 0; --i) printf("%d", a[i]);
    }
  }
};
int main() {
  string s;
  cin >> s;
  int n = s.length();
  int ans[n][n];
  memset((ans), 0, sizeof(ans));
  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j)
      for (int k = 0; k < (j - i + 1) / 2; ++k)
        if (s[i + k] != s[j - k]) ++ans[i][j];
  int(k);
  input((k));
  ;
  int dp[n + 1][k + 1];
  int p[n + 1][k + 1];
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= k; ++j) dp[i][j] = 1e9;
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 1; j <= k; ++j)
      for (int l = 0; l <= i; ++l)
        if (dp[i + 1][j] > dp[l][j - 1] + ans[l][i]) {
          dp[i + 1][j] = dp[l][j - 1] + ans[l][i];
          p[i + 1][j] = l;
        }
  int best = 1;
  for (int i = 1; i <= k; ++i)
    if (dp[n][i] < dp[n][best]) best = i;
  cout << dp[n][best] << endl;
  vector<string> t;
  int cur = n;
  while (best) {
    t.push_back(s.substr(p[cur][best], cur - p[cur][best]));
    cur = p[cur][best];
    --best;
  }
  reverse((t).begin(), (t).end());
  for (int i = 0; i < t.size(); ++i) {
    if (i) cout << "+";
    for (int j = 0; j < t[i].length(); ++j)
      if (t[i][j] != t[i][t[i].length() - 1 - j])
        t[i][j] = t[i][t[i].length() - 1 - j];
    cout << t[i];
  }
  cout << endl;
}