Migrated from Lutece 3276 Into Gray

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: 后缀排序，单调栈，后缀自动机

本题面由 空気力学の詩 友情提供

「我不打算原谅你们曾经的所作所为，但这不能成为迫使你们留在这个世界的理由」

「我会将我与世凪的故事，在那个世界，继续讲述下去」

「还有你的故事」

「一个在虚拟现实之外，燃烧寿命，挽救人类未来的人的故事」

空気力学の詩 在打完《白日梦的构想图》后只想对着脚本家疯狂输出。

不过为了传递积极健康的价值观，他决定刷题以转移注意力，但作为字符串苦手，他被如下所述的一道题难住了。

给定一个长度为 $n$ 的字符串 $S=S[1,n]$，求

Input

输入包含一个长度为 $n$ 的非空字符串 $S$ 。

Output

输出一个整数，代表题面中式子的值。

Samples

lhkkk

52

aadead

95

abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab

59619

Constraints

$2\le n\le 10^6$，$S$ 中只包含小写字母。

Resources

2024 UESTC ICPC Training for String