#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int M = 4000005;
char s[N];
int n, ld, la, ndd, nd, rt[N], dfn[N];
int fa[N], l[N], d[N], D[N], ch[N][26];
int Fa[N][20], id[N], val[N], at[N];
int ls[M], rs[M], lv[M], rv[M];
long long ans, S[N], sum[M];
vector<int> e[N];
int extend(int c) {
  int p = la, np = ++nd;
  l[np] = l[p] + 1;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
  if (!p)
    fa[np] = 1;
  else {
    int q = ch[p][c];
    if (l[q] == l[p] + 1)
      fa[np] = q;
    else {
      int nq = ++nd;
      l[nq] = l[p] + 1;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
  return la = np;
}
int LCA(int x, int y) {
  if (d[x] < d[y]) swap(x, y);
  int tmp = d[x] - d[y];
  for (int i = (int)(17); i >= (int)(0); i--)
    if (tmp & (1 << i)) x = Fa[x][i];
  for (int i = (int)(17); i >= (int)(0); i--)
    if (Fa[x][i] != Fa[y][i]) x = Fa[x][i], y = Fa[y][i];
  return x == y ? x : Fa[x][0];
}
int dis(int x, int y) { return D[x] + D[y] - 2 * D[LCA(x, y)]; }
void insert(int &k, int l, int r, int p, int id) {
  k = ++nd;
  lv[k] = rv[k] = id;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (p <= mid)
    insert(ls[k], l, mid, p, id);
  else
    insert(rs[k], mid + 1, r, p, id);
}
void pushup(int x) {
  if (!ls[x] || !rs[x]) {
    int k = ls[x] + rs[x];
    sum[x] = sum[k];
    lv[x] = lv[k];
    rv[x] = rv[k];
  } else {
    sum[x] = sum[ls[x]] + sum[rs[x]];
    lv[x] = lv[ls[x]];
    rv[x] = rv[rs[x]];
    sum[x] += dis(rv[ls[x]], lv[rs[x]]);
  }
}
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]);
  pushup(x);
  return x;
}
void get_dfn(int x) {
  dfn[x] = ++*dfn;
  for (int i = (int)(0); i <= (int)(e[x].size() - 1); i++) {
    d[e[x][i]] = d[x] + 1;
    get_dfn(e[x][i]);
  }
}
void get_ans(int x) {
  for (int i = (int)(0); i <= (int)(e[x].size() - 1); i++) {
    get_ans(e[x][i]);
    rt[x] = merge(rt[x], rt[e[x][i]]);
  }
  if (rt[x]) {
    long long val = sum[rt[x]] + D[lv[rt[x]]] + D[rv[rt[x]]];
    ans += 1ll * (x == 1 ? 1 : l[x] - l[fa[x]]) * (val / 2 + 1);
  }
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  nd = la = at[n + 1] = 1;
  for (int i = (int)(n); i >= (int)(1); i--) at[i] = extend(s[i] - 'a');
  for (int i = (int)(2); i <= (int)(nd); i++) e[fa[i]].push_back(i);
  get_dfn(1);
  for (int i = (int)(1); i <= (int)(nd); i++) Fa[i][0] = fa[i], D[i] = l[i];
  for (int i = (int)(1); i <= (int)(17); i++)
    for (int j = (int)(1); j <= (int)(nd); j++)
      Fa[j][i] = Fa[Fa[j][i - 1]][i - 1];
  memset(ch, 0, sizeof(ch));
  memset(l, 0, sizeof(l));
  ndd = nd;
  nd = id[0] = la = 1;
  for (int i = (int)(1); i <= (int)(n); i++) id[i] = extend(s[i] - 'a');
  for (int i = (int)(1); i <= (int)(nd); i++) e[i].resize(0);
  for (int i = (int)(2); i <= (int)(nd); i++) e[fa[i]].push_back(i);
  for (int i = (int)(2); i <= (int)(nd); i++) ans += l[i] - l[fa[i]];
  for (int i = (int)(0); i <= (int)(n - 1); i++)
    insert(rt[id[i]], 1, ndd, dfn[at[i + 2]], at[i + 2]);
  get_ans(1);
  printf("%lld\n", ans + 1);
}

### Prompt

Please formulate 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;
const int N = 200005;
const int M = 4000005;
char s[N];
int n, ld, la, ndd, nd, rt[N], dfn[N];
int fa[N], l[N], d[N], D[N], ch[N][26];
int Fa[N][20], id[N], val[N], at[N];
int ls[M], rs[M], lv[M], rv[M];
long long ans, S[N], sum[M];
vector<int> e[N];
int extend(int c) {
  int p = la, np = ++nd;
  l[np] = l[p] + 1;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
  if (!p)
    fa[np] = 1;
  else {
    int q = ch[p][c];
    if (l[q] == l[p] + 1)
      fa[np] = q;
    else {
      int nq = ++nd;
      l[nq] = l[p] + 1;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
  return la = np;
}
int LCA(int x, int y) {
  if (d[x] < d[y]) swap(x, y);
  int tmp = d[x] - d[y];
  for (int i = (int)(17); i >= (int)(0); i--)
    if (tmp & (1 << i)) x = Fa[x][i];
  for (int i = (int)(17); i >= (int)(0); i--)
    if (Fa[x][i] != Fa[y][i]) x = Fa[x][i], y = Fa[y][i];
  return x == y ? x : Fa[x][0];
}
int dis(int x, int y) { return D[x] + D[y] - 2 * D[LCA(x, y)]; }
void insert(int &k, int l, int r, int p, int id) {
  k = ++nd;
  lv[k] = rv[k] = id;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (p <= mid)
    insert(ls[k], l, mid, p, id);
  else
    insert(rs[k], mid + 1, r, p, id);
}
void pushup(int x) {
  if (!ls[x] || !rs[x]) {
    int k = ls[x] + rs[x];
    sum[x] = sum[k];
    lv[x] = lv[k];
    rv[x] = rv[k];
  } else {
    sum[x] = sum[ls[x]] + sum[rs[x]];
    lv[x] = lv[ls[x]];
    rv[x] = rv[rs[x]];
    sum[x] += dis(rv[ls[x]], lv[rs[x]]);
  }
}
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]);
  pushup(x);
  return x;
}
void get_dfn(int x) {
  dfn[x] = ++*dfn;
  for (int i = (int)(0); i <= (int)(e[x].size() - 1); i++) {
    d[e[x][i]] = d[x] + 1;
    get_dfn(e[x][i]);
  }
}
void get_ans(int x) {
  for (int i = (int)(0); i <= (int)(e[x].size() - 1); i++) {
    get_ans(e[x][i]);
    rt[x] = merge(rt[x], rt[e[x][i]]);
  }
  if (rt[x]) {
    long long val = sum[rt[x]] + D[lv[rt[x]]] + D[rv[rt[x]]];
    ans += 1ll * (x == 1 ? 1 : l[x] - l[fa[x]]) * (val / 2 + 1);
  }
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  nd = la = at[n + 1] = 1;
  for (int i = (int)(n); i >= (int)(1); i--) at[i] = extend(s[i] - 'a');
  for (int i = (int)(2); i <= (int)(nd); i++) e[fa[i]].push_back(i);
  get_dfn(1);
  for (int i = (int)(1); i <= (int)(nd); i++) Fa[i][0] = fa[i], D[i] = l[i];
  for (int i = (int)(1); i <= (int)(17); i++)
    for (int j = (int)(1); j <= (int)(nd); j++)
      Fa[j][i] = Fa[Fa[j][i - 1]][i - 1];
  memset(ch, 0, sizeof(ch));
  memset(l, 0, sizeof(l));
  ndd = nd;
  nd = id[0] = la = 1;
  for (int i = (int)(1); i <= (int)(n); i++) id[i] = extend(s[i] - 'a');
  for (int i = (int)(1); i <= (int)(nd); i++) e[i].resize(0);
  for (int i = (int)(2); i <= (int)(nd); i++) e[fa[i]].push_back(i);
  for (int i = (int)(2); i <= (int)(nd); i++) ans += l[i] - l[fa[i]];
  for (int i = (int)(0); i <= (int)(n - 1); i++)
    insert(rt[id[i]], 1, ndd, dfn[at[i + 2]], at[i + 2]);
  get_ans(1);
  printf("%lld\n", ans + 1);
}

```