Description

Input

Output

Sample Input

Sample Output

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstdio>

 #define N 500007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 int stk[N],f[N],g[N];

 struct SA

 {

     char s[N];

     int a[N],b[N],cnta[N],cntb[N],tsa[N],height[N],sa[N],rk[N*];

     void Get_SA()

     {

         for (int i=;i<=;i++)cnta[i]=;

         for (int i=;i<=n;i++)cnta[(int)s[i]]++;

         for (int i=;i<=;i++)cnta[i]+=cnta[i-];

         for (int i=n;i>=;i--)sa[cnta[(int)s[i]]--]=i;

         rk[sa[]]=;

         for (int i=;i<=n;i++)rk[sa[i]]=rk[sa[i-]]+(s[sa[i]]!=s[sa[i-]]);

         for (int i=;rk[sa[n]]!=n;i<<=)

         {

             for (int j=;j<=n;j++)a[j]=rk[j],b[j]=rk[j+i];

             for (int j=;j<=n;j++)cnta[j]=cntb[j]=;

             for (int j=;j<=n;j++)cnta[a[j]]++,cntb[b[j]]++;

             for (int j=;j<=n;j++)cnta[j]+=cnta[j-],cntb[j]+=cntb[j-];

             for (int j=n;j>=;j--)tsa[cntb[b[j]]--]=j;

             for (int j=n;j>=;j--)sa[cnta[a[tsa[j]]]--]=tsa[j];

             rk[sa[]]=;

             for (int j=;j<=n;j++)

                 rk[sa[j]]=rk[sa[j-]]+(a[sa[j]]!=a[sa[j-]]||b[sa[j]]!=b[sa[j-]]);

         }

     }

     void Get_Height()

     {

         int len=;

         for (int i=;i<=n;i++)

         {

             if (len)len--;

             while(s[i+len]==s[sa[rk[i]-]+len])len++;

             height[rk[i]]=len;

         }

     }

 }S;

 int main()

 {

     scanf("%s",S.s+);

     n=strlen(S.s+);

     ll ans=;

     for (int i=;i<=n;i++)

     {

         ans+=(ll)(i-)*i;

         ans+=(ll)i*(i-)/;

     }

     S.Get_SA();

     S.Get_Height();

     int tot=;

     for (int i=;i<=n;i++)

     {

         while(tot>&&S.height[i]<S.height[stk[tot]])

             f[stk[tot--]]=i-;

         stk[++tot]=i;

     }

     while(tot)f[stk[tot--]]=n;

     tot=;

     for (int i=n;i>=;i--)

     {

         while(tot>&&S.height[i]<=S.height[stk[tot]])g[stk[tot--]]=i+;

         stk[++tot]=i;

     }

     while(tot)g[stk[tot--]]=;

     for (int i=;i<=n;i++)

         ans-=(ll)S.height[i]*(ll)(f[i]-i+)*(ll)(i-g[i]+)*;

     printf("%lld\n",ans);

 }