Solve the programming task below in a Python markdown code block.
You are given a string of length N. Calculate the number of distinct substrings of S.

Constraints

* 1 \leq N \leq 500,000
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


S


Output

Print the answer.

Examples

Input

abcbcba


Output

21


Input

mississippi


Output

53


Input

ababacaca


Output

33


Input

aaaaa


Output

5