Jan

Little Johnny (you may remember him from when you once helped check his solution to a palindrome problem) has grown up and is now simply Jan. He still loves the hidden properties of words.

One day Jan became fascinated by the word adam, because every rotation of it produces a word that is later than it in lexicographic (dictionary) order. A rotation moves some letters from the front of the word to its end, keeping their order: the rotations of adam are dama, amad and mada.

Jan named every word with this property a Jan word (in particular, every single-letter word is a Jan word). For example, aabab is a Jan word, but abab is not (rotating it by two letters gives abab again, which is not later than the original), and barak is not either (rotating it by one letter gives arakb, which comes earlier).

Jan then invented a game: take any word made of lowercase English letters and split it into Jan words. Some words can be split in many ways, for example

abaabab = ab+aab+ab = ab+aab+a+b = ab+aabab = ...

Jan is interested only in splits that use the minimum possible number of Jan words.

Write a program that reads Jan's word, finds a split of it into the minimum number of Jan words, and prints the result.

The first line contains one integer $n$ ($1 \le n \le 1000000$), the length of the word. The second line contains exactly one word: a string of lowercase English letters, without spaces, of length exactly $n$.

Print a single line: first the input word, then an = sign, then the words of the minimum split separated by + signs. If the input word is itself a Jan word, print that word once after the =. The output must contain no spaces. The minimum split is unique, so exactly one correct answer exists.