The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

string suffix structures

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string *s*. Each pair of numbers *l* and *r* that fulfill the condition 1 ≤ *l* ≤ *r* ≤ |*s*|, correspond to a substring of the string *s*, starting in the position *l* and ending in the position *r* (inclusive).

Let's define the function of two strings *F*(*x*, *y*) like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string *x* are equal to string *y*. Let's sort this list of pairs according to the pair's first number's increasing. The value of function *F*(*x*, *y*) equals the number of non-empty continuous sequences in the list.

For example: *F*(*babbabbababbab*, *babb*) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

- (1, 4)
- (4, 7)
- (9, 12)
- (1, 4), (4, 7)
- (4, 7), (9, 12)
- (1, 4), (4, 7), (9, 12)

Your task is to calculate for the given string *s* the sum *F*(*s*, *x*) for all *x*, that *x* belongs to the set of all substrings of a string *s*.

Input

The only line contains the given string *s*, consisting only of small Latin letters (1 ≤ |*s*| ≤ 10^{5}).

Output

Print the single number — the sought sum.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

aaaa

Output

20

Input

abcdef

Output

21

Input

abacabadabacaba

Output

188

Note

In the first sample the function values at *x* equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying *x* the function value is 1.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2024 07:28:46 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|