题意：
分析：
两个询问分开考虑：
- 求每次有多少只 喵 被点了名
我们一看见子串，多个模式串，第一反应就是广义SAM，可惜广义SAM做不了，因为第一个操作限制了每一个人每次只能答到一次，即每种类型的串只看做匹配一次
如果不考虑这个限制条件的话，那么我们可以建出一个广义SAM，或者用分隔符将字符串连接起来求SA数组，然后直接统计子串个数
那么我们考虑怎么消掉这个影响呢，我们发现以该询问串为子串的串在 (SAM) 上是 (parent) 树上的一颗子树，是 (SA) 数组上一段连续的区间，所以我们相当于求区间（子树的dfn序也是一段区间）内喵的种类数，这个操作很 HH的项链（不会请出门右转 P1972 )
- 求每只喵被点了多少次
我们沿着第一个问题的思路，每个询问串影响的是一段区间，而第二个问题等价于求每种喵被多少个区间覆盖到了，这个就很扫描线，我们为了保证每种串只会被每个颜色统计一次，我们就按照 HH的项链 的思想，每次只统计 ([lst[col[i]],i]) 这一段内有多少个查询区间，区间数可以通过树状数组维护差分实现
至此，此题的做法就完了，上面也分析过了，不论是 SAM 或者 SA 都能实现，但是由于 SAM 太麻烦，构建 parent 树后还要求 dfn 序，所以这里采用了 SA 的写法
tip:
其实 SA 的写法也不好写，因为 SA 需要左右分别二分才能找到对应区间，而 SAM 只需要跑匹配就能找到相应的子树了
代码：
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 5e4+4;
const int maxq = 1e5+5;
const int maxm = 1e6+5;
int n,m,qt;
int lst[maxn],ans1[maxq],ans2[maxq],fir[maxm],len[maxm],a[maxm],bel[maxm];
int sa[maxm],rk[maxm],oldrk[maxm],id[maxm],tmp[maxm],cnt[maxm],lg[maxm];
int ht[maxm][20];
struct query
{
int l,r,id;
bool operator <(const query &b)const
{
return r<b.r;
}
}q[maxq];
struct bit_tree
{
int c[maxm];
void clear(){memset(c,0,sizeof(c));}
int lowbit(int x){return x&(-x);}
void update(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
int query(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
}tr;
bool check(int x,int y,int k)
{
return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
}
void build()
{
int num=500000;
for(int i=1;i<=n;i++) cnt[rk[i]=a[i]]++;
for(int i=1;i<=num;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) sa[cnt[rk[i]]--]=i;
for(int t=1;t<=n;t<<=1)
{
int tot=0;
for(int i=n-t+1;i<=n;i++) id[++tot]=i;
for(int i=1;i<=n;i++) if(sa[i]>t) id[++tot]=sa[i]-t;
tot=0;
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[tmp[i]=rk[id[i]]]++;
for(int i=1;i<=num;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) sa[cnt[tmp[i]]--]=id[i];
memcpy(oldrk,rk,sizeof(rk));
for(int i=1;i<=n;i++) rk[sa[i]]=check(sa[i-1],sa[i],t)?tot:++tot;
num=tot;
}
for(int i=1,j=0;i<=n;i++)
{
if(j)j--;
while(a[i+j]==a[sa[rk[i]-1]+j]) j++;
ht[rk[i]][0]=j;
}
for(int j=1;j<=18;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
ht[i][j]=min(ht[i][j-1],ht[i+(1<<(j-1))][j-1]);
}
}
}
void init(int now)
{
fir[now]=n+1;len[now]=read();
for(int i=1;i<=len[now];i++) a[++n]=read(),bel[n]=now;
a[++n]=now+10000;
}
int query(int l,int r)
{
l++;
int t=lg[r-l+1];
return min(ht[l][t],ht[r-(1<<t)+1][t]);
}
int findl(int id)
{
int l=1,r=rk[fir[id]]-1,mid,ans=rk[fir[id]];
while(l<=r)
{
mid=(l+r)>>1;
if(query(mid,rk[fir[id]])<len[id])l=mid+1;
else ans=mid,r=mid-1;
}
return ans;
}
int findr(int id)
{
int l=rk[fir[id]]+1,r=n,mid,ans=rk[fir[id]];
while(l<=r)
{
mid=(l+r)>>1;
if(query(rk[fir[id]],mid)<len[id]) r=mid-1;
else ans=mid,l=mid+1;
}
return ans;
}
void work()
{
lg[0]=-1;tr.clear();
for(int i=1;i<=1000000;i++) lg[i]=lg[i>>1]+1;
m=read();qt=read();
for(int i=1;i<=m;i++) init(2*i-1),init(2*i);
for(int i=1;i<=qt;i++) init(2*m+i);
build();
for(int i=1;i<=qt;i++) q[i].l=findl(2*m+i),q[i].r=findr(2*m+i),q[i].id=i;
sort(q+1,q+qt+1);
for(int i=1,j=1;i<=qt;i++)
{
while(j<=q[i].r)
{
if(bel[sa[j]]<=2*m)
{
if(lst[(bel[sa[j]]+1)>>1]) tr.update(lst[(bel[sa[j]]+1)>>1],-1);
lst[(bel[sa[j]]+1)>>1]=j;
tr.update(j,1);
}
j++;
}
ans1[q[i].id]=tr.query(q[i].r)-tr.query(q[i].l-1);
}
for(int i=1;i<=m;i++) lst[i]=0;tr.clear();
for(int i=1;i<=qt;i++) tr.update(q[i].l,1);
for(int i=1,j=1;i<=n;i++)
{
while(j<=qt&&q[j].r<i) tr.update(q[j].l,-1),j++;
if(bel[sa[i]]<=2*m)
{
ans2[(bel[sa[i]]+1)>>1]+=tr.query(i)-tr.query(lst[(bel[sa[i]]+1)>>1]);
lst[(bel[sa[i]]+1)>>1]=i;
}
}
for(int i=1;i<=qt;i++) printf("%d
",ans1[i]);
for(int i=1;i<=m;i++) printf("%d ",ans2[i]);
}
}
int main()
{
zzc::work();
return 0;
}