typedef long long ll;
struct Node
{
    int p, l, r;
    map <char, int> nxt;
    int lnk;
    ll cnt;
    Node(int p = 0, int l = 0, int r = 0) : p(p), l(l), r(r), lnk(-1), cnt(0) {}
    int len()
    {
        return r - l;
    }
};
struct Pos
{
    int v, up;
    Pos(int v = 0, int up = 0) : v(v), up(up) {}
};
const int MAXN = 400500;
const ll MOD = 1e9 + 7;
int sz;
int root;
Node tree[MAXN];
Pos None = Pos(-1, -1);
string s;

Pos go(Pos e, char c)
{
    if (e.up == 0)
        return tree[e.v].nxt.count(c) != 0 ? Pos(tree[e.v].nxt[c], tree[tree[e.v].nxt[c]].len() - 1) : None;
    return c == s[tree[e.v].r - e.up] ? Pos(e.v, e.up - 1) : None;
}

int add(int p, int l, int r)
{
    tree[sz] = Node(p, l, r);
    tree[p].nxt[s[l]] = sz;
    return sz++;
}

int split(Pos e)
{
    if (e.up == 0)
        return e.v;
    int p = tree[e.v].p;
    if (e.up == tree[e.v].len())
        return p;
    int c = add(p, tree[e.v].l, tree[e.v].r - e.up);
    tree[e.v].p = c;
    tree[e.v].l = tree[e.v].r - e.up;
    tree[c].nxt[s[tree[e.v].l]] = e.v;
    return c;
}
int n;

Pos jump(int u, int l, int r)
{
    if (l == r)
        return Pos(u, 0);
    while (true)
    {
        u = tree[u].nxt[s[l]];
        if (tree[u].len() >= r - l)
            return Pos(u, tree[u].len() - r + l);
        l += tree[u].len();
    }
}

int lnk(int u)
{
    int p = tree[u].p;
    if (tree[u].lnk == -1)
        tree[u].lnk = split(jump(lnk(p), tree[u].l + (p == root), tree[u].r));
    return tree[u].lnk;
}

Pos expand(Pos e, int i)
{
    while (true)
    {
        Pos ne = go(e, s[i]);
        if (ne.v != -1)
            return ne;
        int u = split(e);
        add(u, i, n);
        e = Pos(lnk(u), 0);
        if (u == root)
            return e;
    }
}