不久前,Lesha 发现了一个有趣的字符串 $$$s$$$,由小写英文字母组成。 Lesha立即针对这个字符串开发了一种独特的算法并与大家分享。算法如下。
Lesha 在位置 $$$(i, i + 1)$$$ 上选择任意(可能为零)数量的对,以满足以下条件:
- 对于每对 $$$(i, i + 1)$$$ 不等式 $$$0 \le i < |s| - 1$$$ 成立;
- 对于每对 $$$(i, i + 1)$$$,等式 $$$s_i = s_{i + 1}$$$ 成立;
- 没有索引包含在超过一对中。
Lesha 感兴趣的是通过将算法应用于给定字符串的后缀,他可以获得按字典顺序排列的最小字符串。
输入
唯一一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — 仅由小写英文字母组成的初始字符串。
输出
在 $$$|s|$$$ 行中打印答案的长度和答案本身,从最长后缀的答案开始。输出可能很大,因此,当某些答案长于 $$$10$$$ 字符时,请打印答案的前 $$$5$$$ 字符,然后是“...”,然后是最后 $$$2$$$ 字符。
示例
输入 #1
abcdd
输出 #1
3 abc 2 bc 1 c 0 1 d
输入 #2
abbcdddeaaffdfouurtytwoo
输出 #2
18 abbcd...tw 17 bbcdd...tw 16 bcddd...tw 15 cddde...tw 14 dddea...tw 13 ddeaa...tw 12 deaad...tw 11 eaadf...tw 10 aadfortytw 9 adfortytw 8 dfortytw 9 fdfortytw 8 dfortytw 7 fortytw 6 ortytw 5 rtytw 6 urtytw 5 rtytw 4 tytw 3 ytw 2 tw 1 w 0 1 o
注意
考虑第一个例子。
- 最长的后缀是整个字符串“abcdd”。选择一对 $$$(4, 5)$$$,Lesha 获得“abc”。
- 下一个最长的后缀是“bcdd”。选择一对$$$(3, 4)$$$,我们得到“bc”。
- 下一个最长的后缀是“cdd”。选择一对$$$(2, 3)$$$,我们得到“c”。
- 下一个最长的后缀是“dd”。选择一对$$$(1, 2)$$$,我们得到“”(空字符串)。
- 最后一个后缀是字符串“d”。无法选择任何对,所以答案是“d”。
在第二个示例中,对于最长的后缀“abbcdddeaaffdfouurtytwoo”,选择三对 $$$(11, 12)$$$、$$$(16, 17)$$$、$$$(23, 24)$$$,我们得到“abbcdddeaadfortytw”