2023 年上海市大学生程序设计竞赛 - 五月赛

你最后还是决定饮茶放工，出去和队友吃火锅。不过在此之前火锅店老板已经对评论区进行了一次公关，你已经看不到多少中肯的评价了。同时，你也在评论区发现了一些端倪：因为老板请了水军，评论区的评论呈现出有一些有趣的特点。例如每一条评论的开头都离不开某几句话，因此你用一个小写字母 （a - z） 来表示一种评论。

你还发现评论都是用比较拙劣的自动化工具刷的，因为不仅只有几种评论，依次查看评论甚至发现了 循环节。根据你多年的脚本经验，这个脚本里面有一个长度为 $p$ 的评论列表，这个脚本会按顺序循环往复地发布这 $p$ 条评论。如果我们用字符串 $s=s_1{s}_2\dots s_{|s|}$ 表示一系列连续的评论，那么我们说 $p$ 是 $s$ 的循环节，当且仅当：

• $p\le |s|$;
• $\mathrm{\forall }1\le i\le |s|-p,s_i=s_{i+p}$.

你现在爬取了评论区所有的 $n$ 条评论，你很好奇老板刷评论的脚本里面的评论列表长什么样。不过，在老板操作以前可能已经存在一些评论了，你不知道老板是从哪一条评论开始用脚本刷评论的，因此你想知道每一个后缀的周期性。具体而言，对于 $i=1\dots n$，假设最后的 $i$ 条评论是用脚本刷的，你需要求出脚本中所有可能循环节的大小（也即评论列表长度）之和 $a_i$ :
$$a_i=\sum _{p\text{是}{s}_{n-i+1\dots n}\text{的周期}}p.$$