Number of Substrings

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

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

Print the answer.

Examples

Input

abcbcba

Output

21

Input

mississippi

Output

53

Input

ababacaca

Output

33

Input

aaaaa

Output

5

样例

abcbcba

21