#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 5e6 + 5;
struct Edge {
  int to, nxt;
  Edge() = default;
  Edge(int a, int b) : to(a), nxt(b) {}
} e[MAXN << 1];
int head[MAXN], edge_cnt = 1;
int lst = 1, cnt = 1, len[MAXN], fa[MAXN], ch[MAXN][26];
int n, c[MAXN], pos[MAXN], dis[MAXN], ord[MAXN];
int dep[MAXN], siz[MAXN], son[MAXN], fat[MAXN];
int ls[MAXM], rs[MAXM], tree_cnt, rt[MAXN];
int top[MAXN], dfn[MAXN], dfn_cnt;
long long ans = 0;
char s[MAXN];
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void add_edge(int x, int y) {
  e[++edge_cnt] = Edge{y, head[x]};
  head[x] = edge_cnt;
}
void dfs_son(int x, int fath) {
  dep[x] = dep[fath] + 1;
  siz[x] = 1, fat[x] = fath;
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fath) continue;
    dfs_son(y, x), siz[x] += siz[y];
    if (siz[y] > siz[son[x]]) son[x] = y;
  }
}
void dfs_chain(int x, int tp) {
  top[x] = tp, dfn[x] = ++dfn_cnt;
  if (son[x]) dfs_chain(son[x], tp);
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fat[x] || y == son[x]) continue;
    dfs_chain(y, y);
  }
}
inline int query_lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fat[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
inline int query_dis(int x, int y) { return dis[query_lca(x, y)]; }
struct Node {
  int l, r;
  long long sum;
  Node() = default;
  Node(int a, int b, int c = 0) : l(a), r(b), sum(c) {}
} val[MAXM];
Node operator+(const Node &A, const Node &B) {
  Node ans(0, 0, 0);
  ans.l = A.l, ans.r = B.r;
  ans.sum = A.sum + B.sum;
  ans.sum -= query_dis(A.r, B.l);
  return ans;
}
inline void pushup(int cur) {
  if (!ls[cur] && !rs[cur]) return;
  if (!ls[cur])
    val[cur] = val[rs[cur]];
  else if (!rs[cur])
    val[cur] = val[ls[cur]];
  else
    val[cur] = val[ls[cur]] + val[rs[cur]];
}
void modify(int l, int r, int p, int &cur) {
  if (!cur) cur = ++tree_cnt;
  if (l == r) return val[cur] = {p, p, dis[p]}, void();
  if (dfn[p] <= ((l + r) >> 1)) modify(l, ((l + r) >> 1), p, ls[cur]);
  if (dfn[p] > ((l + r) >> 1)) modify(((l + r) >> 1) + 1, r, p, rs[cur]);
  pushup(cur);
}
void merge(int &x, int y) {
  if (!x || !y) return x |= y, void();
  merge(ls[x], ls[y]);
  merge(rs[x], rs[y]);
  pushup(x);
}
inline void insert(int c) {
  int p = lst, np = lst = ++cnt;
  len[np] = len[p] + 1;
  while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
  if (!p) return fa[np] = 1, void();
  int q = ch[p][c];
  if (len[q] == len[p] + 1) return fa[np] = q, void();
  int nq = ++cnt;
  fa[nq] = fa[q], fa[q] = fa[np] = nq;
  len[nq] = len[p] + 1, memcpy(ch[nq], ch[q], sizeof(ch[q]));
  while (ch[p][c] == q) ch[p][c] = nq, p = fa[p];
}
inline void clear() {
  lst = cnt = 1;
  memset(fa, 0, sizeof(fa));
  memset(ch, 0, sizeof(ch));
}
inline void prepare() {
  for (int i = 1; i <= cnt; i++) c[len[i]]++;
  for (int i = 1; i <= n; i++) c[i] += c[i - 1];
  for (int i = cnt; i; i--) ord[c[len[i]]--] = i;
}
inline void modify(int a, int b) {
  if (a < 1 || a > n) return;
  modify(1, dfn_cnt, pos[a], rt[b]);
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a'), pos[i] = lst;
    ans += len[lst] - len[fa[lst]];
    if (i == n - 1) ans <<= 1;
  }
  clog << ans << endl;
  memcpy(dis, len, sizeof(dis));
  for (int i = 2; i <= cnt; i++) add_edge(fa[i], i);
  dfs_son(1, 0), dfs_chain(1, 1);
  reverse(s + 1, s + n + 1), clear();
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a');
    modify(n - (len[lst] + 2) + 1, lst);
    if (i != n) ans += len[lst] - len[fa[lst]];
  }
  clog << ans << endl;
  prepare();
  for (int i = cnt; i > 1; i--) {
    int x = ord[i], f = fa[x];
    ans += 1ll * (len[x] - len[f]) * val[rt[x]].sum;
    merge(rt[f], rt[x]);
  }
  printf("%lld\n", ans + 2);
  return 0;
}

### 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 MAXN = 2e5 + 5;
const int MAXM = 5e6 + 5;
struct Edge {
  int to, nxt;
  Edge() = default;
  Edge(int a, int b) : to(a), nxt(b) {}
} e[MAXN << 1];
int head[MAXN], edge_cnt = 1;
int lst = 1, cnt = 1, len[MAXN], fa[MAXN], ch[MAXN][26];
int n, c[MAXN], pos[MAXN], dis[MAXN], ord[MAXN];
int dep[MAXN], siz[MAXN], son[MAXN], fat[MAXN];
int ls[MAXM], rs[MAXM], tree_cnt, rt[MAXN];
int top[MAXN], dfn[MAXN], dfn_cnt;
long long ans = 0;
char s[MAXN];
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void add_edge(int x, int y) {
  e[++edge_cnt] = Edge{y, head[x]};
  head[x] = edge_cnt;
}
void dfs_son(int x, int fath) {
  dep[x] = dep[fath] + 1;
  siz[x] = 1, fat[x] = fath;
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fath) continue;
    dfs_son(y, x), siz[x] += siz[y];
    if (siz[y] > siz[son[x]]) son[x] = y;
  }
}
void dfs_chain(int x, int tp) {
  top[x] = tp, dfn[x] = ++dfn_cnt;
  if (son[x]) dfs_chain(son[x], tp);
  for (int i = head[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fat[x] || y == son[x]) continue;
    dfs_chain(y, y);
  }
}
inline int query_lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fat[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
inline int query_dis(int x, int y) { return dis[query_lca(x, y)]; }
struct Node {
  int l, r;
  long long sum;
  Node() = default;
  Node(int a, int b, int c = 0) : l(a), r(b), sum(c) {}
} val[MAXM];
Node operator+(const Node &A, const Node &B) {
  Node ans(0, 0, 0);
  ans.l = A.l, ans.r = B.r;
  ans.sum = A.sum + B.sum;
  ans.sum -= query_dis(A.r, B.l);
  return ans;
}
inline void pushup(int cur) {
  if (!ls[cur] && !rs[cur]) return;
  if (!ls[cur])
    val[cur] = val[rs[cur]];
  else if (!rs[cur])
    val[cur] = val[ls[cur]];
  else
    val[cur] = val[ls[cur]] + val[rs[cur]];
}
void modify(int l, int r, int p, int &cur) {
  if (!cur) cur = ++tree_cnt;
  if (l == r) return val[cur] = {p, p, dis[p]}, void();
  if (dfn[p] <= ((l + r) >> 1)) modify(l, ((l + r) >> 1), p, ls[cur]);
  if (dfn[p] > ((l + r) >> 1)) modify(((l + r) >> 1) + 1, r, p, rs[cur]);
  pushup(cur);
}
void merge(int &x, int y) {
  if (!x || !y) return x |= y, void();
  merge(ls[x], ls[y]);
  merge(rs[x], rs[y]);
  pushup(x);
}
inline void insert(int c) {
  int p = lst, np = lst = ++cnt;
  len[np] = len[p] + 1;
  while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
  if (!p) return fa[np] = 1, void();
  int q = ch[p][c];
  if (len[q] == len[p] + 1) return fa[np] = q, void();
  int nq = ++cnt;
  fa[nq] = fa[q], fa[q] = fa[np] = nq;
  len[nq] = len[p] + 1, memcpy(ch[nq], ch[q], sizeof(ch[q]));
  while (ch[p][c] == q) ch[p][c] = nq, p = fa[p];
}
inline void clear() {
  lst = cnt = 1;
  memset(fa, 0, sizeof(fa));
  memset(ch, 0, sizeof(ch));
}
inline void prepare() {
  for (int i = 1; i <= cnt; i++) c[len[i]]++;
  for (int i = 1; i <= n; i++) c[i] += c[i - 1];
  for (int i = cnt; i; i--) ord[c[len[i]]--] = i;
}
inline void modify(int a, int b) {
  if (a < 1 || a > n) return;
  modify(1, dfn_cnt, pos[a], rt[b]);
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a'), pos[i] = lst;
    ans += len[lst] - len[fa[lst]];
    if (i == n - 1) ans <<= 1;
  }
  clog << ans << endl;
  memcpy(dis, len, sizeof(dis));
  for (int i = 2; i <= cnt; i++) add_edge(fa[i], i);
  dfs_son(1, 0), dfs_chain(1, 1);
  reverse(s + 1, s + n + 1), clear();
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a');
    modify(n - (len[lst] + 2) + 1, lst);
    if (i != n) ans += len[lst] - len[fa[lst]];
  }
  clog << ans << endl;
  prepare();
  for (int i = cnt; i > 1; i--) {
    int x = ord[i], f = fa[x];
    ans += 1ll * (len[x] - len[f]) * val[rt[x]].sum;
    merge(rt[f], rt[x]);
  }
  printf("%lld\n", ans + 2);
  return 0;
}

```