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

见题面

见题面