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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static ArrayList<Integer> adj[];
	static PrintWriter out = new PrintWriter(System.out);
	public static int mod = 1000000007;

	static int notmemo[][];
	static int k;
	static long a[];
	static int b[];
	static int m;
	static char c[];


	static int trace[];
	static int h;
	static int x;
	static int ans1;
	static int ans2;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		String s=sc.nextLine();
		c=s.toCharArray();
		 k=sc.nextInt();
		memo=new int[c.length+1][k+1];
		notmemo=new int[c.length+1][c.length+1];
		
		for (int i = 0; i < memo.length; i++) {
			Arrays.fill(memo[i],-1);
			Arrays.fill(notmemo[i],-1);
			
		}
		 out.println( dp(0,0));
	//out.flush();
		 trace(0,0);
		out.flush();
	}
	static void trace(int i ,int count) {
		if(i>=c.length) {
			return ;
		}
		if(count>k) {
			return;
		}
		int ans=dp(i,count);
		for (int j =i; j < c.length; j++) {
		if(dp(j+1,count+1)+changes(i, j)==ans) {
		int end=j;
		int chaos=0;
			for(int idx=i; idx<=j&&end>=0; idx++) {
			out.print(c[idx]);
			c[end]=c[idx];
			end--;
			chaos=idx;
		    }
			if(chaos<c.length-1) {
				out.print("+");
			}
			trace(j+1,count+1);
				return;	
				
		}
		}
	
	}
	static  int dp(int i,int count) {
		if(count>k) {
			return (int) 1e9;
		}
		if(i>=c.length) {
			return 0;
		}
		if(memo[i][count]!=-1) {
			return memo[i][count];
		}
	    int ans=(int) 1e9;
		for (int j =i; j < c.length; j++) {
			ans=Math.min(ans, dp(j+1,count+1)+changes(i,j));
		}
		return memo[i][count]=ans;
		
	}	
	
	static int changes(int i,int j) {
		if(i>=j) {
			return 0;
		}
		if(notmemo[i][j]!=-1) {
			return notmemo[i][j];
		}
		if(c[i]!=c[j]) {
			notmemo[i][j]=1+changes(i+1, j-1);
		}
		else {
			notmemo[i][j]=changes(i+1, j-1);
				
		}
		return notmemo[i][j];
	}
		

	static class book implements Comparable<book> {
		int idx;
		long score;

		public book(int i, long s) {
			idx = i;
			score = s;
		}

		public int compareTo(book o) {
			return (int) (o.score - score);
		}
	}

	static class library implements Comparable<library> {
		int numofbooks;
		int signup;
		int shiprate;
		int idx;

		public library(int a, int b, int c, int idx) {
			numofbooks = a;
			signup = b;
			shiprate = c;
			this.idx = idx;
		}

		@Override
		public int compareTo(library o) {
		if(signup==o.signup) {
			  return o.numofbooks-numofbooks;
		}
		return signup - o.signup;
		
		}
	}


	
	static boolean isPal(String s) {
		int j = s.length() - 1;
		c = s.toCharArray();
		Arrays.sort(c);
		for (int i = 0; i < c.length; i++) {

		}
		return true;
	}

	static String s;

	static boolean isOn(int S, int j) {
		return (S & 1 << j) != 0;
	}

	static int y, d;

	static void extendedEuclid(int a, int b) {
		if (b == 0) {
			x = 1;
			y = 0;
			d = a;
			return;
		}
		extendedEuclid(b, a % b);
		int x1 = y;
		int y1 = x - a / b * y;
		x = x1;
		y = y1;
	}

	static boolean f = true;

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;

		SegmentTree(int[] in) {
			array = in;
			N = in.length - 1;
			sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}
		}

		void update_point(int index, int val) // O(log n)
		{
			index += N - 1;
			sTree[index] += val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = Math.max(sTree[index << 1], sTree[index << 1 | 1]);
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		int query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		int query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			// propagate(node, b, mid, e);
			int q1 = query(node << 1, b, mid, i, j);
			int q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return Math.max(q1, q2);

		}
	}

	static int memo[][];

	static long nCr1(int n, int k) {
		if (n < k)
			return 0;
		if (k == 0 || k == n)
			return 1;
		if (comb[n][k] != -1)
			return comb[n][k];
		if (n - k < k)
			return comb[n][k] = nCr1(n, n - k);
		return comb[n][k] = ((nCr1(n - 1, k - 1) % mod) + (nCr1(n - 1, k) % mod)) % mod;
	}

	static class UnionFind {
		int[] p, rank, setSize;
		int numSets;
		int max[];

		public UnionFind(int N) {
			max = new int[N];
			p = new int[numSets = N];
			rank = new int[N];
			setSize = new int[N];
			for (int i = 0; i < N; i++) {
				p[i] = i;
				setSize[i] = 1;
				max[i] = i;
			}
		}

		public int findSet(int i) {
			return p[i] == i ? i : (p[i] = findSet(p[i]));
		}

		public boolean isSameSet(int i, int j) {
			return findSet(i) == findSet(j);
		}

		public void unionSet(int i, int j) {
			if (isSameSet(i, j))
				return;
			numSets--;
			int x = findSet(i), y = findSet(j);
			if (rank[x] > rank[y]) {
				p[y] = x;
				setSize[x] += setSize[y];
				max[x] = Math.max(max[x], max[y]);

			} else {
				p[x] = y;
				setSize[y] += setSize[x];
				if (rank[x] == rank[y])
					rank[y]++;
				max[y] = Math.max(max[x], max[y]);

			}
		}

		private int getmax(int j) {
			return max[findSet(j)];
		}

		public int numDisjointSets() {
			return numSets;
		}

		public int sizeOfSet(int i) {
			return setSize[findSet(i)];
		}
	}

	/**
	 * private static void trace(int i, int time) { if(i==n) return;
	 * 
	 * 
	 * long ans=dp(i,time);
	 * if(time+a[i].t<a[i].burn&&(ans==dp(i+1,time+a[i].t)+a[i].cost)) {
	 * 
	 * trace(i+1, time+a[i].t);
	 * 
	 * l1.add(a[i].idx); return; } trace(i+1,time);
	 * 
	 * }
	 **/

	static class incpair implements Comparable<incpair> {
		int a;
		long b;
		int idx;

		incpair(int a, long dirg, int i) {
			this.a = a;
			b = dirg;
			idx = i;
		}

		public int compareTo(incpair e) {
			return (int) (b - e.b);
		}
	}

	static class decpair implements Comparable<decpair> {
		int a;
		long b;
		int idx;

		decpair(int a, long dirg, int i) {
			this.a = a;
			b = dirg;
			idx = i;
		}

		public int compareTo(decpair e) {
			return (int) (e.b - b);
		}
	}

	static long allpowers[];

	static class Quad implements Comparable<Quad> {
		int u;
		int v;
		char state;
		int turns;

		public Quad(int i, int j, char c, int k) {
			u = i;
			v = j;
			state = c;
			turns = k;
		}

		public int compareTo(Quad e) {
			return (int) (turns - e.turns);
		}

	}

	static long dirg[][];
	static Edge[] driver;

	static int n;

	static class Edge implements Comparable<Edge> {
		int node;
		long cost;

		Edge(int a, long dirg) {
			node = a;
			cost = dirg;
		}

		public int compareTo(Edge e) {
			return (int) (cost - e.cost);
		}
	}

	static long manhatandistance(long x, long x2, long y, long y2) {
		return Math.abs(x - x2) + Math.abs(y - y2);
	}

	static long fib[];

	static long fib(int n) {
		if (n == 1 || n == 0) {
			return 1;
		}
		if (fib[n] != -1) {
			return fib[n];
		} else
			return fib[n] = ((fib(n - 2) % mod + fib(n - 1) % mod) % mod);
	}

	static class Pair implements Comparable<Pair> {
		int a, b;

		Pair(int x, int y) {
			a = x;
			b = y;
		}

		@Override
		public int compareTo(Pair c) {
			return b-c.b;
		}

	}

	static long[][] comb;

	static class Triple implements Comparable<Triple> {

		int l;
		int r;
		long cost;
		int idx;

		public Triple(int a, int b, long l1, int l2) {
			l = a;
			r = b;
			cost = l1;
			idx = l2;
		}

		public int compareTo(Triple x) {
			if (l != x.l || idx == x.idx)
				return l - x.l;
			return -idx;
		}

	}

	static TreeSet<Long> primeFactors(long N) // O(sqrt(N) / ln sqrt(N))
	{
		TreeSet<Long> factors = new TreeSet<Long>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			while (N % p == 0) {
				factors.add((long) p);
				N /= p;
			}
			if (primes.size() > idx + 1)
				p = primes.get(++idx);
			else
				break;
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.add(N); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static boolean visited[];

	/**
	 * static int bfs(int s) { Queue<Integer> q = new LinkedList<Integer>();
	 * q.add(s); int count=0; int maxcost=0; int dist[]=new int[n]; dist[s]=0;
	 * while(!q.isEmpty()) {
	 * 
	 * int u = q.remove(); if(dist[u]==k) { break; } for(Pair v: adj[u]) {
	 * maxcost=Math.max(maxcost, v.cost);
	 * 
	 * 
	 * 
	 * if(!visited[v.v]) {
	 * 
	 * visited[v.v]=true; q.add(v.v); dist[v.v]=dist[u]+1; maxcost=Math.max(maxcost,
	 * v.cost); } }
	 * 
	 * } return maxcost; }
	 **/
	public static boolean FindAllElements(int n, int k) {
		int sum = k;
		int[] A = new int[k];
		Arrays.fill(A, 0, k, 1);

		for (int i = k - 1; i >= 0; --i) {

			while (sum + A[i] <= n) {

				sum += A[i];
				A[i] *= 2;
			}
		}
		if (sum == n) {
			return true;
		} else
			return false;
	}

	static boolean vis2[][];

	static boolean f2 = false;

	static long[][] matMul(long[][] a2, long[][] b, int p, int q, int r) // C(p x r) = A(p x q) x (q x r) -- O(p x q x
																			// r)
	{
		long[][] C = new long[p][r];
		for (int i = 0; i < p; ++i) {
			for (int j = 0; j < r; ++j) {
				for (int k = 0; k < q; ++k) {
					C[i][j] = (C[i][j] + (a2[i][k] % mod * b[k][j] % mod)) % mod;
					C[i][j] %= mod;
				}

			}
		}
		return C;
	}

	static ArrayList<Pair> a1[];
	static int memo1[];

	static boolean vis[];
	static TreeSet<Integer> set = new TreeSet<Integer>();

	static long modPow(long ways, long count, long mod) // O(log e)
	{
		ways %= mod;
		long res = 1;
		while (count > 0) {
			if ((count & 1) == 1)
				res = (res * ways) % mod;
			ways = (ways * ways) % mod;
			count >>= 1;
		}
		return res % mod;
	}

	static long gcd(long ans, long b) {
		if (b == 0) {
			return ans;
		}
		return gcd(b, ans % b);
	}

	static int[] isComposite;
	static int[] valid;

	static ArrayList<Integer> primes;
	static ArrayList<Integer> l;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();
		l = new ArrayList<>();
		valid = new int[N + 1];
		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				l.add(i);
				valid[i] = 1;

				for (int j = i * 2; j <= N; j += i) { // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
					isComposite[j] = 1;

				}
			}

		for (int i = 0; i < primes.size(); i++) {
			for (int j : primes) {
				if (primes.get(i) * j > N) {
					break;
				}
				valid[primes.get(i) * j] = 1;
			}
		}
	}

	public static long[] schuffle(long[] sad) {
		for (int i = 0; i < sad.length; i++) {
			int x = (int) (Math.random() * sad.length);
			long temp = sad[x];
			sad[x] = sad[i];
			sad[i] = temp;
		}
		return sad;
	}

	static int V;
	static long INF = (long) 1E16;

	static class Edge2 {
		int node;
		long cost;
		long next;

		Edge2(int a, int c, Long long1) {
			node = a;
			cost = long1;
			next = c;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}