#include<map>

#include<cstdio>

#include<algorithm>

#define pii pair

#define mpii make_pair

#define MN 410000

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while(read_ca<''||read_ca>'') {if (read_ca=='-') read_f=-;read_ca=getchar();}

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

const int MOD=;

struct na{int p,*st;}Y[MN<<];

bool operator < (na a,na b){return a.p<b.p;}

inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}

int n,m,L[MN],a[MN],ro[MN],RO[MN*],ls[MN*],rs[MN*],LS[MN*],RS[MN*],S[MN*],NUM,x[MN],y[MN],z[MN],T=,num=,_num=,mmh[MN],MMH=,t[MN],w[MN],ze[MN];

void ADD(int &p,int l,int r,int pos,int v){

    if (!p) p=++_num;S[p]+=v;

    if (l==r) return;

    int mid=l+r>>;

    if (pos<=mid) ADD(LS[p],l,mid,pos,v);else ADD(RS[p],mid+,r,pos,v);

}

void add(int &p,int l,int r,int pos,int x,int v){

    if (!p) p=++num;ADD(RO[p],,T,x,v);

    if (l==r) return;

    int mid=l+r>>;

    if (pos<=mid) add(ls[p],l,mid,pos,x,v);else add(rs[p],mid+,r,pos,x,v);

}

int ASK(int p,int l,int r,int k){

    if (!p) return ;

    if (l==r) return S[p];

    int mid=l+r>>;

    return k<=mid?ASK(LS[p],l,mid,k):ASK(RS[p],mid+,r,k);

}

int p_ask(int p,int l,int r,int pos,int x){

    if (ASK(RO[p],,T,x)==) return -;

    if (pos<=l) return -;

    if (l==r) return l;

    int mid=l+r>>;

    int w=p_ask(rs[p],mid+,r,pos,x);

    if (w!=-) return w;

    return p_ask(ls[p],l,mid,pos,x);

}

int s_ask(int p,int l,int r,int pos,int x){

    if (ASK(RO[p],,T,x)==) return -;

    if (pos>=r) return -;

    if (l==r) return l;

    int mid=l+r>>;

    int w=s_ask(ls[p],l,mid,pos,x);

    if (w!=-) return w;

    return s_ask(rs[p],mid+,r,pos,x);

}

inline int mi(int x,int y){

    int mmh=;

    while (y){

        if (y&) mmh=1LL*mmh*x%MOD;

        x=1LL*x*x%MOD;y>>=;

    }

    return mmh;

}

map<pii<int,int>,int> ma;

map<pii<int,int>,int>::iterator it;

inline void del(int x,int v){

    if(!ze[v])M(MMH+=mmh[v]);

    if (ma.find(mpii(x,v))==ma.end()) ma[mpii(x,v)]=1LL*(L[x]-L[x-])*(L[x]-L[x-]+)/%MOD;

    if (!ma[mpii(x,v)]) ze[v]--;else mmh[v]=1LL*mmh[v]*mi(ma[mpii(x,v)],MOD-)%MOD;

}

inline void add(int x,int v){if (!ma[mpii(x,v)]) ze[v]++;else mmh[v]=1LL*mmh[v]*ma[mpii(x,v)]%MOD;if(!ze[v])M(MMH-=mmh[v]);}

int main(){

    n=read();m=read();

    for (int i=;i<=n;i++) L[i]=L[i-]+read();

    for (int i=;i<=n;i++){

        for (int j=L[i-];j<L[i];j++) Y[++NUM].p=a[j]=read(),Y[NUM].st=&a[j];

        MMH=1LL*(L[i]-L[i-])*(L[i]-L[i-]+)/%MOD*MMH%MOD;

    }

    for (int i=;i<=m;i++) x[i]=read(),y[i]=read(),Y[++NUM].p=z[i]=read(),Y[NUM].st=&z[i];

    sort(Y+,Y++NUM);

    for (int i=;i<=NUM;i++) T+=i==||Y[i].p!=Y[i-].p,*Y[i].st=T;

    for (int i=;i<=T;i++) mmh[i]=MMH,ze[i]=;

    MMH=1LL*MMH*T%MOD;

    for (int i=;i<=n;i++)

    for (int j=L[i-];j<L[i];j++)add(ro[i],,L[i]-L[i-],j-L[i-]+,a[j],);

    for (int i=;i<=n;i++){

        for (int j=L[i-];j<L[i];j++)

        if (!t[a[j]]) w[j]=(1LL*(j-L[i-]+)*(j-L[i-])>>)%MOD,t[a[j]]=j+;else w[j]=((1LL*(j+-t[a[j]])*(j-t[a[j]])>>)+w[t[a[j]]-])%MOD,t[a[j]]=j+;

        int s=mi(1LL*(L[i]-L[i-])*(L[i]-L[i-]+)/%MOD,MOD-);

        for (int j=L[i]-;j>=L[i-];j--) if (t[a[j]]){

            M(w[j]+=1LL*(L[i]-t[a[j]]+)*(L[i]-t[a[j]])/%MOD);

            mmh[a[j]]=1LL*mmh[a[j]]*s%MOD;

            if (!w[j]) ze[a[j]]++;else mmh[a[j]]=1LL*mmh[a[j]]*w[j]%MOD;

            ma[mpii(i,a[j])]=w[j];

            t[a[j]]=;

        }

    }

    for (int i=;i<=T;i++) if (!ze[i]) M(MMH-=mmh[i]);

    printf("%d\n",MMH);

    for (int i=;i<=m;i++){

        int pos=L[x[i]-]+y[i]-;

        del(x[i],a[pos]);del(x[i],z[i]);

        int l=p_ask(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],a[pos]),r=s_ask(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],a[pos]);

        if (l==-) l=;if (r==-) r=L[x[i]]-L[x[i]-]+;

        it=ma.find(mpii(x[i],a[pos]));

        M(it->second+=1LL*(r-y[i])*(y[i]-l)%MOD);

        l=p_ask(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],z[i]),r=s_ask(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],z[i]);

        if (l==-) l=;if (r==-) r=L[x[i]]-L[x[i]-]+;

        it=ma.find(mpii(x[i],z[i]));

        M(it->second-=1LL*(r-y[i])*(y[i]-l)%MOD);

        add(x[i],a[pos]);add(x[i],z[i]);

        add(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],a[pos],-);

        add(ro[x[i]],,L[x[i]]-L[x[i]-],y[i],z[i],);a[pos]=z[i];

        printf("%d\n",MMH);

    }

}