题目内容

给定一个字符串 $s$。如果存在某个长度严格小于 $|s|$ 的非空字符串 $t$ 以及整数 $k \ge 2$，使得 $s$ 恰好等于 $t$ 连续拼接 $k$ 次的结果，就称 $s$ 具有完全重复结构。

当 $s$ 具有完全重复结构时，请找出长度最小的满足条件的字符串 $t$，并将 $t$ 与对应的重复次数 $k = |s| / |t|$ 拼接后输出；当 $s$ 不具有完全重复结构时，直接输出 $s$ 本身。

约束条件：

• 字符串 $s$ 的长度 $n$ 满足 $1 \le n \le 10^6$。
• $s$ 仅由字符 0 到 9、a 到 z、A 到 Z 组成。

输入描述

输入包含一行，一个字符串 $s$。

输出描述

输出一行。如果 $s$ 具有完全重复结构，则输出最短重复单元字符串，紧接着输出重复次数；否则输出原始字符串 $s$。

样例1

输入

ababab

输出

ab3

说明

字符串 ababab 的长度为 6。它可以写成 ab 连续拼接 3 次，即 $s = (ab)(ab)(ab)$。

若重复单元长度为 1，则整个串应由同一个字符组成，但这里含有 a 和 b，所以不成立。因此长度最小的重复单元是 ab，对应重复次数为 3，输出为 ab3。

样例2

输入

abcab

输出

abcab

说明

不存在满足条件的重复单元，输出原串 abcab。

样例3

输入

a

输出

a

说明

字符串 a 的长度为 1。

重复单元必须是非空字符串，因此长度至少为 1。又要求长度严格小于原串长度 1，没有更短的单元可用，所以不具有完全重复结构，直接输出 a。

样例4

输入

aaaa

输出

a4

说明

字符串 aaaa 的长度为 4。它可以写成 a 连续拼接 4 次，即 $s = (a)(a)(a)(a)$。

最短重复单元为 a，重复次数为 4，因此输出为 a4。