小 Jas（你可能还记得，以前曾帮他解决过回文问题）现在已经长大了。他现在面临的问题比以前严重得多。尽管如此，Jan 仍然对单词的性质很感兴趣。

有一次，Jan 对单词 adam 感兴趣（这是他儿时玩伴的名字），因为它的任何循环移位在字典序上都比它本身大。循环移位是指将单词开头的一部分字母移到末尾，并保持它们的顺序不变——adam 的所有可能循环移位结果为 dama、amad 和 mada。不久之后，Jan 发明了更多具有这种性质的单词，并谦虚地将它们称为“Jan 单词”（特别地，所有单字母单词都是 Jan 单词）。例如，aabab 是一个 Jan 单词，但 abab 不是（因为将其循环移位 2 位后得到 abab，在字典序上并不比它本身大），barak 也不是（循环移位 1 位得到 arakb，在字典序上比它本身小）。

Jan 发明了一个游戏：取任意一个由小写英文字母组成的单词，将其分割成若干个 Jan 单词。有些单词可以通过多种方式分割成 Jan 单词，例如 abaabab = ab+aab+ab = ab+aab+a+b = ab+aabab = ....。尽管如此，Jan 对将单词分割成最少数量的 Jan 单词很感兴趣。

不幸的是，成年后的 Jan 没有那么多时间玩游戏了，所以他不能再把很长的单词分割成 Jan 单词。因此，他记得你以前的帮助，请求你编写一个程序，对于给定的单词，求出将其分割成最少数量的 Jan 单词的方案。你的程序必须足够快，这样 Jan 就不必等待太久就能得到他想出的单词的分割结果。

题目描述

编写一个程序： 读取 Jan 感兴趣的单词； 确定将其分割成最少数量的 Jan 单词的方案； * 输出结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000000$)，表示 Jan 发明的单词长度。下一行包含一个长度恰好为 $n$ 的单词（即由小写英文字母组成的字符串，不含空格）。

输出格式

输出仅一行，格式如下：首先是 Jan 输入的单词，然后是一个等号 =，接着是找到的最小分割方案中的单词，单词之间用 + 号连接（如果输入的单词本身就是一个 Jan 单词，则等号后直接输出该单词即可）。输出不应包含任何空格。如果给定的单词可以通过多种方式分割成最少数量的 Jan 单词，则输出其中任意一种即可。

样例

输入 1

7
abaabab

输出 1

abaabab=ab+aabab