D. String

 

 

You 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|?≤?105).

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

Copy

aaaa

output

Copy

20

input

Copy

abcdef

output

Copy

21

input

Copy

abacabadabacaba

output

Copy

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.

题意：如果某一种子串s在原串中出现了k次，根据题目定义的函数，它产生的贡献是(k+1)*k/2

这个条件很奇怪，我们尝试转化模型，就会发现这个函数相当于我们将这k个s串排成一排，每个

串和它自己以及后面的串匹配一次，总次数就是题目要求的函数

于是我们可以上后缀数组+高度数组，对于每一个后缀，和后面的每一个后缀的算一个最长公共前缀，然后根据长度统计答案

这个东西可以用单调栈搞一搞，最后每个后缀和自己可以匹配一次，也就是说如果读入的串长度为n，ans+=(n+1)*n/2

代码：

//#include"bits/stdc++.h"
#include"cstdio"
#include"map"
#include"set"
#include"cmath"
#include"queue"
#include"vector"
#include"string"
#include"ctime"
#include"stack"
#include"deque"
#include"cstdlib"
#include"cstring"
#include"iostream"
#include"algorithm"

#define db double
#define ll long long
#define vec vector<ll>
#define Mt  vector<vec>
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
//#define rep(i, x, y) for(int i=x;i<y;i++)
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
const int N   = 1e6 + 5;
const int mod = 1e9 + 7;
const int MOD = mod - 1;
const int inf = 0x3f3f3f3f;
const db  PI  = acos(-1.0);
const db  eps = 1e-10;
int sa[N];
int rk[N];
int tmp[N];
int lcp[N];
int n,k;
bool cmp(int i,int j){
    if(rk[i] != rk[j]) return rk[i]<