#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int ls[N * 30], rs[N * 30], lx[N * 30], rx[N * 30], dfn[N], s[N * 2][20], len,
    tp, d[N], b[N * 2], cnt, ps[N], pp[N], rt[N];
ll sum[N * 30], ans;
vector<int> G[N];
char S[N];
struct sam {
  int ch[N][26], fa[N], l[N], c[N], id[N], lst = 1, cnt = 1;
  void extend(int c) {
    int cur = ++cnt, p = lst;
    l[cur] = l[p] + 1;
    lst = cur;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = cur;
    if (!p)
      fa[cur] = 1;
    else {
      int q = ch[p][c];
      if (l[p] + 1 == l[q])
        fa[cur] = q;
      else {
        int clone = ++cnt;
        fa[clone] = fa[q];
        fa[q] = fa[cur] = clone;
        l[clone] = l[p] + 1;
        memcpy(ch[clone], ch[q], sizeof(ch[q]));
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = clone;
      }
    }
  }
  void bud() {
    for (int i = (1); i <= (cnt); ++i) c[l[i]]++;
    for (int i = (1); i <= (len + 1); ++i) c[i] += c[i - 1];
    for (int i = (cnt); i >= (1); --i) id[c[l[i]]--] = i;
  }
} A, B;
void dfs(int u) {
  s[++tp][0] = u;
  dfn[u] = tp;
  for (int &v : G[u]) d[v] = d[u] + 1, dfs(v), s[++tp][0] = u;
}
inline int ck(int x, int y) { return d[x] < d[y] ? x : y; }
inline int lca(int u, int v) {
  int l = dfn[u], r = dfn[v];
  if (l > r) swap(l, r);
  int t = b[r - l + 1];
  return ck(s[l][t], s[r - (1 << t) + 1][t]);
}
inline void up(int x) {
  lx[x] = ls[x] ? lx[ls[x]] : lx[rs[x]];
  rx[x] = rs[x] ? rx[rs[x]] : rx[ls[x]];
  sum[x] = sum[ls[x]] + sum[rs[x]];
  if (ls[x] && rs[x]) sum[x] -= B.l[lca(rx[ls[x]], lx[rs[x]])];
}
void upd(int &o, int l, int r, int x) {
  if (!o) o = ++cnt;
  if (l == r) {
    lx[o] = rx[o] = s[x][0];
    sum[o] = B.l[s[x][0]];
    return;
  }
  int mid = (l + r) >> 1;
  x > mid ? upd(rs[o], mid + 1, r, x) : upd(ls[o], l, mid, x);
  up(o);
}
int merge(int x, int y) {
  if (!x || !y) return x | y;
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  up(x);
  return x;
}
void out(int o, int l, int r) {
  if (!o) return;
  if (l == r) {
    printf("%d ", lx[o]);
    return;
  }
  int mid = (l + r) >> 1;
  out(ls[o], l, mid);
  out(rs[o], mid + 1, r);
}
int main() {
  scanf("%s", S + 1);
  len = strlen(S + 1);
  A.l[1] = B.l[1] = 1;
  pp[len + 1] = ps[0] = 1;
  for (int i = (len); i >= (1); --i) B.extend(S[i] - 97), pp[i] = B.lst;
  for (int i = (1); i <= (len); ++i) A.extend(S[i] - 97), ps[i] = A.lst;
  A.bud();
  for (int i = (2); i <= (B.cnt); ++i) G[B.fa[i]].push_back(i);
  dfs(1);
  for (int i = (0); i <= (len - 1); ++i) upd(rt[ps[i]], 1, tp, dfn[pp[i + 2]]);
  for (int i = (2); i <= (tp); ++i) b[i] = b[i >> 1] + 1;
  for (int i = (1); i <= (19); ++i)
    for (int j = (1); j <= (tp - (1 << i) + 1); ++j)
      s[j][i] = ck(s[j][i - 1], s[j + (1 << i - 1)][i - 1]);
  for (int i = (A.cnt); i >= (1); --i) {
    int x = A.id[i];
    ans += (A.l[x] - A.l[A.fa[x]]) * (sum[rt[x]] + 1);
    rt[A.fa[x]] = merge(rt[A.fa[x]], rt[x]);
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your task is to create a CPP solution to 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;
using ll = long long;
const int N = 2e5 + 10;
int ls[N * 30], rs[N * 30], lx[N * 30], rx[N * 30], dfn[N], s[N * 2][20], len,
    tp, d[N], b[N * 2], cnt, ps[N], pp[N], rt[N];
ll sum[N * 30], ans;
vector<int> G[N];
char S[N];
struct sam {
  int ch[N][26], fa[N], l[N], c[N], id[N], lst = 1, cnt = 1;
  void extend(int c) {
    int cur = ++cnt, p = lst;
    l[cur] = l[p] + 1;
    lst = cur;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = cur;
    if (!p)
      fa[cur] = 1;
    else {
      int q = ch[p][c];
      if (l[p] + 1 == l[q])
        fa[cur] = q;
      else {
        int clone = ++cnt;
        fa[clone] = fa[q];
        fa[q] = fa[cur] = clone;
        l[clone] = l[p] + 1;
        memcpy(ch[clone], ch[q], sizeof(ch[q]));
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = clone;
      }
    }
  }
  void bud() {
    for (int i = (1); i <= (cnt); ++i) c[l[i]]++;
    for (int i = (1); i <= (len + 1); ++i) c[i] += c[i - 1];
    for (int i = (cnt); i >= (1); --i) id[c[l[i]]--] = i;
  }
} A, B;
void dfs(int u) {
  s[++tp][0] = u;
  dfn[u] = tp;
  for (int &v : G[u]) d[v] = d[u] + 1, dfs(v), s[++tp][0] = u;
}
inline int ck(int x, int y) { return d[x] < d[y] ? x : y; }
inline int lca(int u, int v) {
  int l = dfn[u], r = dfn[v];
  if (l > r) swap(l, r);
  int t = b[r - l + 1];
  return ck(s[l][t], s[r - (1 << t) + 1][t]);
}
inline void up(int x) {
  lx[x] = ls[x] ? lx[ls[x]] : lx[rs[x]];
  rx[x] = rs[x] ? rx[rs[x]] : rx[ls[x]];
  sum[x] = sum[ls[x]] + sum[rs[x]];
  if (ls[x] && rs[x]) sum[x] -= B.l[lca(rx[ls[x]], lx[rs[x]])];
}
void upd(int &o, int l, int r, int x) {
  if (!o) o = ++cnt;
  if (l == r) {
    lx[o] = rx[o] = s[x][0];
    sum[o] = B.l[s[x][0]];
    return;
  }
  int mid = (l + r) >> 1;
  x > mid ? upd(rs[o], mid + 1, r, x) : upd(ls[o], l, mid, x);
  up(o);
}
int merge(int x, int y) {
  if (!x || !y) return x | y;
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  up(x);
  return x;
}
void out(int o, int l, int r) {
  if (!o) return;
  if (l == r) {
    printf("%d ", lx[o]);
    return;
  }
  int mid = (l + r) >> 1;
  out(ls[o], l, mid);
  out(rs[o], mid + 1, r);
}
int main() {
  scanf("%s", S + 1);
  len = strlen(S + 1);
  A.l[1] = B.l[1] = 1;
  pp[len + 1] = ps[0] = 1;
  for (int i = (len); i >= (1); --i) B.extend(S[i] - 97), pp[i] = B.lst;
  for (int i = (1); i <= (len); ++i) A.extend(S[i] - 97), ps[i] = A.lst;
  A.bud();
  for (int i = (2); i <= (B.cnt); ++i) G[B.fa[i]].push_back(i);
  dfs(1);
  for (int i = (0); i <= (len - 1); ++i) upd(rt[ps[i]], 1, tp, dfn[pp[i + 2]]);
  for (int i = (2); i <= (tp); ++i) b[i] = b[i >> 1] + 1;
  for (int i = (1); i <= (19); ++i)
    for (int j = (1); j <= (tp - (1 << i) + 1); ++j)
      s[j][i] = ck(s[j][i - 1], s[j + (1 << i - 1)][i - 1]);
  for (int i = (A.cnt); i >= (1); --i) {
    int x = A.id[i];
    ans += (A.l[x] - A.l[A.fa[x]]) * (sum[rt[x]] + 1);
    rt[A.fa[x]] = merge(rt[A.fa[x]], rt[x]);
  }
  printf("%lld\n", ans);
  return 0;
}

```