#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0;
  bool flg = false;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') flg = true;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
  return flg ? -x : x;
}
char s[100010];
int n;
int p[100010];
struct C {
  int f, p, l;
  bool e;
  int tr[26];
} c[200010];
int ctot = 1;
int ins(int g, int d, int p) {
  int x = ++ctot;
  c[x].p = p, c[x].l = c[g].l + 1, c[x].e = 1;
  for (; g && !c[g].tr[d]; c[g].tr[d] = x, g = c[g].f)
    ;
  if (!g) return c[x].f = 1, x;
  int h = c[g].tr[d];
  if (c[h].l == c[g].l + 1) return c[x].f = h, x;
  int w = ++ctot;
  c[w].f = c[h].f, c[w].p = p, c[w].l = c[g].l + 1, c[w].e = 0;
  memcpy(c[w].tr, c[h].tr, 26 << 2);
  c[x].f = c[h].f = w;
  for (; g && c[g].tr[d] == h; c[g].tr[d] = w, g = c[g].f)
    ;
  return x;
}
int dfn[200010], id[200010];
int st[18][200010], bt[200010];
int dep[200010], tot[200010];
vector<int> e[200010];
inline int chk(int x, int y) { return dep[x] < dep[y] ? x : y; }
inline int getlca(int x, int y) {
  if (x == y) return x;
  x = id[x], y = id[y];
  if (x > y) swap(x, y);
  --y;
  const int &lg = bt[y - x + 1];
  return chk(st[lg][x], st[lg][y - (1 << lg) + 1]);
}
void dfs0(int x, int f, int d) {
  dep[x] = d;
  dfn[++*dfn] = x, id[x] = ++*id;
  st[0][-1 + *id] = f;
  tot[x] = c[x].e;
  for (const int &y : e[x]) dfs0(y, x, d + 1), tot[x] += tot[y];
}
int D;
inline int getlen(int x, int y) {
  x += D, y += D;
  return D + c[getlca(p[x], p[y])].l;
}
struct Cmp {
  bool operator()(int x, int y) const {
    x += D, y += D;
    int l = c[getlca(p[x], p[y])].l;
    return s[x + l] < s[y + l];
  }
};
struct B {
  set<int, Cmp> st;
  long long w;
  void ins(int x) {
    auto it = st.insert(x).first, pre = it, suf = it;
    w += c[p[x]].l;
    if (++suf != st.end()) w -= getlen(x, *suf);
    if (it != st.begin()) {
      w -= getlen(x, *--pre);
      if (suf != st.end()) w += getlen(*pre, *suf);
    }
  }
  void del(int x) {
    auto it = st.find(x), pre = it, suf = it;
    assert(it != st.end());
    w -= c[p[x]].l;
    if (++suf != st.end()) w += getlen(x, *suf);
    if (it != st.begin()) {
      w += getlen(x, *--pre);
      if (suf != st.end()) w -= getlen(*pre, *suf);
    }
    st.erase(it);
  }
} b[200010];
long long ans;
long long getsum(long long l, int t) { return 1LL * (l + l + t - 1) * t / 2; }
void dfs1(int x) {
  if (e[x].size()) {
    int z = -1;
    for (const int &y : e[x]) {
      dfs1(y);
      ans += getsum(b[y].w - c[y].l + 1, c[y].l - c[x].l - 1);
      if (!~z || tot[y] > tot[z]) z = y;
    }
    D = c[x].l + 1;
    swap(b[x], b[z]);
    B &g = b[x];
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.ins(x);
      }
    ans += g.w - D + 1;
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.del(x);
      }
    --D;
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.ins(x);
        b[y].st.clear();
      }
    if (c[x].e) g.ins(c[x].p);
  } else {
    B &g = b[x];
    D = c[x].l;
    g.ins(c[x].p);
  }
}
void solve() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  int lst = 1;
  p[n + 1] = 1;
  for (int i(n), _i(1); i >= _i; i--) p[i] = lst = ins(lst, s[i] - 'a', i);
  for (int i(2), _i(ctot); i <= _i; i++) e[c[i].f].push_back(i);
  dfs0(1, 0, 1);
  bt[0] = -1;
  for (int i(1), _i(ctot); i <= _i; i++) bt[i] = bt[i >> 1] + 1;
  for (int j(1), _j(17); j <= _j; j++)
    for (int i(1), _i(ctot - (1 << j)); i <= _i; i++)
      st[j][i] = chk(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
  dfs1(1);
  ans += b[1].w + 1;
  printf("%lld\n", ans);
}
int main() {
  for (int T = 1; T--;) solve();
  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;
int read() {
  int x = 0;
  bool flg = false;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') flg = true;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
  return flg ? -x : x;
}
char s[100010];
int n;
int p[100010];
struct C {
  int f, p, l;
  bool e;
  int tr[26];
} c[200010];
int ctot = 1;
int ins(int g, int d, int p) {
  int x = ++ctot;
  c[x].p = p, c[x].l = c[g].l + 1, c[x].e = 1;
  for (; g && !c[g].tr[d]; c[g].tr[d] = x, g = c[g].f)
    ;
  if (!g) return c[x].f = 1, x;
  int h = c[g].tr[d];
  if (c[h].l == c[g].l + 1) return c[x].f = h, x;
  int w = ++ctot;
  c[w].f = c[h].f, c[w].p = p, c[w].l = c[g].l + 1, c[w].e = 0;
  memcpy(c[w].tr, c[h].tr, 26 << 2);
  c[x].f = c[h].f = w;
  for (; g && c[g].tr[d] == h; c[g].tr[d] = w, g = c[g].f)
    ;
  return x;
}
int dfn[200010], id[200010];
int st[18][200010], bt[200010];
int dep[200010], tot[200010];
vector<int> e[200010];
inline int chk(int x, int y) { return dep[x] < dep[y] ? x : y; }
inline int getlca(int x, int y) {
  if (x == y) return x;
  x = id[x], y = id[y];
  if (x > y) swap(x, y);
  --y;
  const int &lg = bt[y - x + 1];
  return chk(st[lg][x], st[lg][y - (1 << lg) + 1]);
}
void dfs0(int x, int f, int d) {
  dep[x] = d;
  dfn[++*dfn] = x, id[x] = ++*id;
  st[0][-1 + *id] = f;
  tot[x] = c[x].e;
  for (const int &y : e[x]) dfs0(y, x, d + 1), tot[x] += tot[y];
}
int D;
inline int getlen(int x, int y) {
  x += D, y += D;
  return D + c[getlca(p[x], p[y])].l;
}
struct Cmp {
  bool operator()(int x, int y) const {
    x += D, y += D;
    int l = c[getlca(p[x], p[y])].l;
    return s[x + l] < s[y + l];
  }
};
struct B {
  set<int, Cmp> st;
  long long w;
  void ins(int x) {
    auto it = st.insert(x).first, pre = it, suf = it;
    w += c[p[x]].l;
    if (++suf != st.end()) w -= getlen(x, *suf);
    if (it != st.begin()) {
      w -= getlen(x, *--pre);
      if (suf != st.end()) w += getlen(*pre, *suf);
    }
  }
  void del(int x) {
    auto it = st.find(x), pre = it, suf = it;
    assert(it != st.end());
    w -= c[p[x]].l;
    if (++suf != st.end()) w += getlen(x, *suf);
    if (it != st.begin()) {
      w += getlen(x, *--pre);
      if (suf != st.end()) w -= getlen(*pre, *suf);
    }
    st.erase(it);
  }
} b[200010];
long long ans;
long long getsum(long long l, int t) { return 1LL * (l + l + t - 1) * t / 2; }
void dfs1(int x) {
  if (e[x].size()) {
    int z = -1;
    for (const int &y : e[x]) {
      dfs1(y);
      ans += getsum(b[y].w - c[y].l + 1, c[y].l - c[x].l - 1);
      if (!~z || tot[y] > tot[z]) z = y;
    }
    D = c[x].l + 1;
    swap(b[x], b[z]);
    B &g = b[x];
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.ins(x);
      }
    ans += g.w - D + 1;
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.del(x);
      }
    --D;
    for (const int &y : e[x])
      if (y ^ z) {
        for (const auto &x : b[y].st) g.ins(x);
        b[y].st.clear();
      }
    if (c[x].e) g.ins(c[x].p);
  } else {
    B &g = b[x];
    D = c[x].l;
    g.ins(c[x].p);
  }
}
void solve() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  int lst = 1;
  p[n + 1] = 1;
  for (int i(n), _i(1); i >= _i; i--) p[i] = lst = ins(lst, s[i] - 'a', i);
  for (int i(2), _i(ctot); i <= _i; i++) e[c[i].f].push_back(i);
  dfs0(1, 0, 1);
  bt[0] = -1;
  for (int i(1), _i(ctot); i <= _i; i++) bt[i] = bt[i >> 1] + 1;
  for (int j(1), _j(17); j <= _j; j++)
    for (int i(1), _i(ctot - (1 << j)); i <= _i; i++)
      st[j][i] = chk(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
  dfs1(1);
  ans += b[1].w + 1;
  printf("%lld\n", ans);
}
int main() {
  for (int T = 1; T--;) solve();
  return 0;
}

```