struct SAM {

    static const int MAXN = 1e6 + 10;

    struct State {
        int nxt[26];
        int len;
        int lnk;
    } st[2 * MAXN];

    int siz;
    int lst;

    void Init() {
        siz = 0;
        lst = 0;
        ms(st[0].nxt);
        st[0].len = 0;
        st[0].lnk = -1;
    }

    void Extend(int c) {
        int u = ++siz;
        st[u].len = st[lst].len + 1;
        int p = lst;
        while(p != -1 && st[p].nxt[c] != 0) {
            st[p].nxt[c] = u;
            p = st[p].lnk;
        }
        if(p == -1)
            st[u].lnk = 0;
        else {
            int q = st[p].nxt[c];
            if(st[p].len + 1 == st[q].len)
                st[u].lnk = q;
            else {
                int v = ++siz;
                mc(st[v].nxt, st[q].nxt);
                st[v].len = st[p].len + 1;
                st[v].lnk = st[q].lnk;
                while(p != -1 && st[p].nxt[c] == q) {
                    st[p].nxt[c] = v;
                    p = st[p].lnk;
                }
                st[q].lnk = st[u].lnk = v;
            }
        }
        lst = u;
    }

} sam;