#include <bits/stdc++.h>
using namespace std;
struct Data {
  int p;
  long long x;
};
bool cmp(const Data &A, const Data &B) { return A.x < B.x; }
struct SA {
  int rk[105000], sa[105000], c[18][105000], lg2[105000];
  Data t[105000];
  void build(char *s, int n) {
    for (int i = 1; i <= n; i++) rk[i] = s[i];
    int len = 1;
    while (len < n) {
      for (int i = 1; i <= n; i++) {
        t[i].x = 1ll * rk[i] * n;
        if (i + len <= n) t[i].x += rk[i + len];
        t[i].p = i;
      }
      sort(t + 1, t + n + 1, cmp);
      int p;
      bool flag = 1;
      for (int i = 1; i <= n; i++) {
        if (t[i].x != t[i - 1].x)
          p = i;
        else
          flag = 0;
        rk[t[i].p] = p;
      }
      if (flag) break;
      len <<= 1;
    }
    for (int i = 1; i <= n; i++) sa[rk[i]] = i;
    for (int i = 1, p = 0; i <= n; i++) {
      if (p) p--;
      while (s[i + p] == s[sa[rk[i] - 1] + p]) p++;
      c[0][rk[i]] = p;
    }
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
    for (int j = 0; j < 16; j++)
      for (int i = 1; i <= n; i++)
        c[j + 1][i] = min(c[j][i], c[j][i + (1 << j)]);
  }
  int lcp(int a, int b) {
    if (a > b) swap(a, b);
    a++;
    int t = lg2[b - a + 1];
    return min(c[t][a], c[t][b - (1 << t) + 1]);
  }
} R;
struct Node {
  int t[26], f, len;
} a[105000 << 1];
int n, tn, las;
void add(int c) {
  int np = ++tn, p = las;
  las = np;
  a[np].len = a[p].len + 1;
  for (; p && !a[p].t[c]; p = a[p].f) a[p].t[c] = np;
  if (!p)
    a[np].f = 1;
  else {
    int v = a[p].t[c];
    if (a[p].len + 1 == a[v].len)
      a[np].f = v;
    else {
      int nv = ++tn;
      a[nv] = a[v];
      a[nv].len = a[p].len + 1;
      for (; p && a[p].t[c] == v; p = a[p].f) a[p].t[c] = nv;
      a[v].f = a[np].f = nv;
    }
  }
}
void clear() {
  memset(a, 0, sizeof(Node) * (tn + 2));
  tn = las = 1;
}
vector<int> g[105000 << 1];
int siz[105000 << 1], p[105000 << 1];
void pfs(int u) {
  siz[u] = 1;
  for (int i = 0, v; i < g[u].size(); i++) {
    pfs(v = g[u][i]);
    siz[u] += siz[v];
    if (siz[v] > siz[p[u]]) p[u] = v;
  }
}
struct SufSet {
  set<int> s;
  long long o;
  void add(int x) {
    o += n - R.sa[x] + 1;
    set<int>::iterator nxt = s.lower_bound(x), pre = nxt;
    if (nxt != s.end()) o -= R.lcp(x, *nxt);
    if (pre != s.begin()) {
      o -= R.lcp(*(--pre), x);
      if (nxt != s.end()) o += R.lcp(*pre, *nxt);
    }
    s.insert(x);
  }
  void clear() {
    s.clear();
    o = 0;
  }
} T[20];
void merge(SufSet &A, SufSet &B) {
  for (set<int>::iterator it = B.s.begin(); it != B.s.end(); it++) A.add(*it);
  B.clear();
}
int tp[105000 << 1];
long long ans;
void dfs(int u, int ts) {
  if (p[u]) {
    dfs(p[u], ts);
    for (int i = 0, v; i < g[u].size(); i++)
      if ((v = g[u][i]) != p[u]) {
        dfs(v, ts + 1);
        merge(T[ts], T[ts + 1]);
      }
  }
  if (tp[u] && tp[u] + 2 <= n) T[ts].add(R.rk[tp[u] + 2]);
  ans += T[ts].o * (a[u].len - a[a[u].f].len);
}
void calc() {
  for (int i = 1; i <= tn; i++) ans += a[i].len - a[a[i].f].len;
}
char s[105000];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  R.build(s, n);
  for (int i = 1; i <= n; i++) s[i] -= 'a';
  clear();
  for (int i = 2; i <= n; i++) add(s[i]);
  calc();
  clear();
  for (int i = 1; i < n; i++) add(s[i]);
  calc();
  clear();
  for (int i = 1; i <= n; i++) add(s[i]);
  calc();
  for (int i = 2; i <= tn; i++) g[a[i].f].push_back(i);
  for (int i = 1, p = 1; i <= n; i++) tp[p = a[p].t[s[i]]] = i;
  pfs(1);
  dfs(1, 0);
  printf("%lld", ans + 2);
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

Consider a string s of n lowercase English letters. Let t_i be the string obtained by replacing the i-th character of s with an asterisk character *. For example, when s = abc, we have t_1 = \tt{*bc}, t_2 = \tt{a*c}, and t_3 = \tt{ab*}.

Given a string s, count the number of distinct strings of lowercase English letters and asterisks that occur as a substring of at least one string in the set \\{s, t_1, …, t_n \}. The empty string should be counted.

Note that *'s are just characters and do not play any special role as in, for example, regex matching.

Input

The only line contains a string s of n lowercase English letters (1 ≤ n ≤ 10^5).

Output

Print a single integer — the number of distinct strings of s, t_1, …, t_n.

Example

Input


abc


Output


15

Note

For the sample case, the distinct substrings are (empty string), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct Data {
  int p;
  long long x;
};
bool cmp(const Data &A, const Data &B) { return A.x < B.x; }
struct SA {
  int rk[105000], sa[105000], c[18][105000], lg2[105000];
  Data t[105000];
  void build(char *s, int n) {
    for (int i = 1; i <= n; i++) rk[i] = s[i];
    int len = 1;
    while (len < n) {
      for (int i = 1; i <= n; i++) {
        t[i].x = 1ll * rk[i] * n;
        if (i + len <= n) t[i].x += rk[i + len];
        t[i].p = i;
      }
      sort(t + 1, t + n + 1, cmp);
      int p;
      bool flag = 1;
      for (int i = 1; i <= n; i++) {
        if (t[i].x != t[i - 1].x)
          p = i;
        else
          flag = 0;
        rk[t[i].p] = p;
      }
      if (flag) break;
      len <<= 1;
    }
    for (int i = 1; i <= n; i++) sa[rk[i]] = i;
    for (int i = 1, p = 0; i <= n; i++) {
      if (p) p--;
      while (s[i + p] == s[sa[rk[i] - 1] + p]) p++;
      c[0][rk[i]] = p;
    }
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
    for (int j = 0; j < 16; j++)
      for (int i = 1; i <= n; i++)
        c[j + 1][i] = min(c[j][i], c[j][i + (1 << j)]);
  }
  int lcp(int a, int b) {
    if (a > b) swap(a, b);
    a++;
    int t = lg2[b - a + 1];
    return min(c[t][a], c[t][b - (1 << t) + 1]);
  }
} R;
struct Node {
  int t[26], f, len;
} a[105000 << 1];
int n, tn, las;
void add(int c) {
  int np = ++tn, p = las;
  las = np;
  a[np].len = a[p].len + 1;
  for (; p && !a[p].t[c]; p = a[p].f) a[p].t[c] = np;
  if (!p)
    a[np].f = 1;
  else {
    int v = a[p].t[c];
    if (a[p].len + 1 == a[v].len)
      a[np].f = v;
    else {
      int nv = ++tn;
      a[nv] = a[v];
      a[nv].len = a[p].len + 1;
      for (; p && a[p].t[c] == v; p = a[p].f) a[p].t[c] = nv;
      a[v].f = a[np].f = nv;
    }
  }
}
void clear() {
  memset(a, 0, sizeof(Node) * (tn + 2));
  tn = las = 1;
}
vector<int> g[105000 << 1];
int siz[105000 << 1], p[105000 << 1];
void pfs(int u) {
  siz[u] = 1;
  for (int i = 0, v; i < g[u].size(); i++) {
    pfs(v = g[u][i]);
    siz[u] += siz[v];
    if (siz[v] > siz[p[u]]) p[u] = v;
  }
}
struct SufSet {
  set<int> s;
  long long o;
  void add(int x) {
    o += n - R.sa[x] + 1;
    set<int>::iterator nxt = s.lower_bound(x), pre = nxt;
    if (nxt != s.end()) o -= R.lcp(x, *nxt);
    if (pre != s.begin()) {
      o -= R.lcp(*(--pre), x);
      if (nxt != s.end()) o += R.lcp(*pre, *nxt);
    }
    s.insert(x);
  }
  void clear() {
    s.clear();
    o = 0;
  }
} T[20];
void merge(SufSet &A, SufSet &B) {
  for (set<int>::iterator it = B.s.begin(); it != B.s.end(); it++) A.add(*it);
  B.clear();
}
int tp[105000 << 1];
long long ans;
void dfs(int u, int ts) {
  if (p[u]) {
    dfs(p[u], ts);
    for (int i = 0, v; i < g[u].size(); i++)
      if ((v = g[u][i]) != p[u]) {
        dfs(v, ts + 1);
        merge(T[ts], T[ts + 1]);
      }
  }
  if (tp[u] && tp[u] + 2 <= n) T[ts].add(R.rk[tp[u] + 2]);
  ans += T[ts].o * (a[u].len - a[a[u].f].len);
}
void calc() {
  for (int i = 1; i <= tn; i++) ans += a[i].len - a[a[i].f].len;
}
char s[105000];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  R.build(s, n);
  for (int i = 1; i <= n; i++) s[i] -= 'a';
  clear();
  for (int i = 2; i <= n; i++) add(s[i]);
  calc();
  clear();
  for (int i = 1; i < n; i++) add(s[i]);
  calc();
  clear();
  for (int i = 1; i <= n; i++) add(s[i]);
  calc();
  for (int i = 2; i <= tn; i++) g[a[i].f].push_back(i);
  for (int i = 1, p = 1; i <= n; i++) tp[p = a[p].t[s[i]]] = i;
  pfs(1);
  dfs(1, 0);
  printf("%lld", ans + 2);
  return 0;
}

```