题目内容

给定一个字符串 $s$，请你判断它是否由一个较短的字符串重复多次构成。如果可以，输出最短的重复段字符串+重复次数；否则输出字符串本身。

例如：

• "$abab$" 可以由 "$ab$" 重复 $2$ 次得到，输出 $ab2$。
• "$abcabcabc$" 可以由 "$abc$" 重复 $3$ 次得到，输出 $abc3$。
• "$aaaa$" 可以由 "$a$" 重复 $4$ 次得到，也可以由 "$aa$" 重复 $2$ 次得到，按照最短的字符串输出，输出 $a4$。
• "$ababa$" 无法由某个子串重复多次构成，输出 $ababa$。

输入描述

一个字符串 $s$，仅包含数字 $0$-$9$、小写字母 $a$-$z$、大写字母 $A$-$Z$，字符串长度 $1 \le n \le 10^6$。

输出描述

一段字符串 $s\_new$，$s\_new$ 重复次数，字符串长度 $1 \le n \le 10^6$。

样例1

输入

aaabbb

输出

aaabbb

说明

它无法被分割成至少两个完全相同的部分。