struct SAM{

    static const int maxn =   * ;

    struct node{

        node*nxt[],*fail;

        int len;

    };

    node*root;int cnt;

    node no[maxn];

    node*newnode(){

        return &no[cnt++];

    }

    SAM(){

        cnt = ;

        root = newnode();

    }

    node* add(node*p,int c){

        node*cur = newnode();

        cur->len = p->len+;

        while(p &&!p->nxt[c])p->nxt[c] = cur,p = p->fail;

        if(!p){

            cur->fail = root;return cur;

        }

        node*q = p->nxt[c];

        if(q->len == p->len+){

            cur->fail = q;

        }else{

            node*nq = newnode();

            *nq = *q;

            nq->len = p->len+;

            q->fail = cur->fail = nq;

            while(p&&p->nxt[c]==q)p->nxt[c] = nq,p = p->fail;

        }

        return cur;

    }

    ll getNumOfDistinctSubstrings(){

        auto ans = ;

        REP(i,,cnt)ans+=no[i].len-no[i].fail->len;

        return (ans);

    }

};