Little Johnny (whom you may remember from when you helped him solve the palindrome problem) is now a grown-up John. He now has much more serious problems than he used to. Nevertheless, John is still interested in the properties of words.

Once, John became interested in the word adam (the name of a childhood friend), because any rotation of it results in a word that is lexicographically (dictionary-wise) greater than the original. A rotation consists of "moving" a part of the letters from the beginning of the word to its end, keeping them in the exact same order — the results of all possible rotations of the word adam are dama, amad, and mada. Soon, John came up with many more words with this property and modestly decided to call them "John's words" (in particular, all single-letter words are John's words). For example, the word aabab is a John's word, but the words abab (because after a rotation by 2 letters we get the word abab, which is not lexicographically greater than the original) and barak (a rotation by 1 letter gives arakb, which is lexicographically smaller than the original) are not.

John came up with a game that involves taking any word composed of lowercase English letters and dividing it into words that are John's words. Some words can be divided into John's words in many ways, e.g., abaabab = ab+aab+ab = ab+aab+a+b = ab+aabab = .... Nevertheless, John is interested in partitions of words into the minimum possible number of John's words.

Unfortunately, adult John does not have as much time for games as he used to, so he cannot divide very long words into John's words. Therefore, remembering your previous help, he asked you to write a program that, for a given word, determines its partition into the minimum number of John's words. Your program must be fast enough so that John does not have to wait too long for the decomposition of the word he just came up with.

Task

Write a program that: reads the word that John is currently interested in, determines its partition into the minimum number of John's words, * prints the result.

Input

The first line contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the length of the word John came up with. The next line contains exactly one word (a sequence of lowercase English letters without spaces) of length exactly $n$.

Output

The first and only line should be constructed as follows: first the word provided as input by John, then an equals sign, followed by the subsequent words of the found minimal partition separated by "+" signs (in the case where the input word itself is a John's word, it is sufficient to print the same word after the equals sign). The output should not contain any spaces. If the given word can be divided into the minimum number of John's words in several ways, any one of them should be printed.

Examples

Input 1

7
abaabab

Output 1

abaabab=ab+aabab