一道比较不错**字符串**好题，貌似有很多做法可以艹过去。
比较主流的有两大类，一种是用各种**自动机**：**AC自动机**暴力搞或者是神仙的**后缀自动机**做，相比之下对于我来说不是很会。
另一种就是用**后缀数组**预处理一下，然后可以用各种数据结构（如**树状数组**）来维护，但是由于我比较菜而且数据范围不是很大所以我们可以用**莫队**来暴力的搞。
下面我们主要分析一下**SA+莫队**的算法。
首先我们考虑将所有猫的姓和名拼接在一起（注意中间还是要用特殊字符连接一下），并记录每一个位置上的字符是哪只猫的，记为$id_i$。
然后考虑对于询问，由于后缀数组的$sa$数组表示的是**排名为$i$的后缀的位置**，因此我们可以根据排名**二分**出每一个询问在$sa$数组上对应的**区间**。
再回头看这个问题，先考虑算询问的答案，首先转化为区间之后若左端点大于右端点那么这个串显然是找不到的，那么可以直接跳过。
如果是合法的区间，那么我们相当于统计这段区间中的所有$sa_i$的$id$的种类数（因为每只猫出现多次也只统计一次）
这个就直接开一个**桶**用莫队算一下即可。
然后是考虑每只猫的答案，这个我们莫队更新区间的时候判断一下，如果这只猫是第一次出现那么先将答案加上**最大的可能出现次数**，然后在删除的时候减掉即可。
时间复杂度$O(n\log n+m\sqrt n)$，可以轻松跑过。
CODE
```cpp
#include<cstdio>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#define RI register int
using namespace std;
const int N=50005,M=100005;
int blk[M+(N<<1)]; struct ques
{
int l,r,id;
inline friend bool operator <(ques A,ques B)
{
return blk[A.l]^blk[B.l]?blk[A.l]<blk[B.l]:(blk[A.l]&1?A.r<B.r:A.r>B.r);
}
}q[M]; int n,m,len,tot,a[M+(N<<1)],sa[M+(N<<1)],x,size,ans[M],id[M+(N<<1)],cnt,t[N],bkt[N],lim=10000,L,R,ret;
class FileInputOutput
{
private:
#define S 1<<21
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))
char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];
public:
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
inline void write(int x,char ch)
{
if (!x) return (void)(pc('0'),pc(ch)); RI ptop=0;
while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void Fend(void)
{
fwrite(Fout,1,Ftop,stdout);
}
#undef S
#undef tc
#undef pc
}F;
class Suffix_Array
{
private:
int rk[M+(N<<1)],t[M+(N<<1)],cnt[M+(N<<1)],size;
inline void Radix_sort(int n)
{
RI i; for (i=0;i<=size;++i) cnt[i]=0;
for (i=1;i<=n;++i) ++cnt[rk[i]];
for (i=1;i<=size;++i) cnt[i]+=cnt[i-1];
for (i=n;i;--i) sa[cnt[rk[t[i]]]--]=t[i];
}
public:
inline void build(int *a,int n)
{
RI i; size=a[n]; for (i=1;i<=n;++i) rk[i]=a[i],t[i]=i;
Radix_sort(n); for (RI p=0,w=1;p<n;size=p,w<<=1)
{
for (p=0,i=n-w+1;i<=n;++i) t[++p]=i;
for (i=1;i<=n;++i) if (sa[i]>w) t[++p]=sa[i]-w;
Radix_sort(n); swap(rk,t); rk[sa[1]]=p=1;
for (i=2;i<=n;++i) rk[sa[i]]=(t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+w]==t[sa[i]+w])?p:++p;
}
}
}SA;
inline void add(int x,int cur)
{
if (++bkt[id[x]]==1) ++ret,t[id[x]]+=cnt-cur+1;
}
inline void del(int x,int cur)
{
if (--bkt[id[x]]==0) --ret,t[id[x]]-=cnt-cur+1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (F.read(n),F.read(m),i=1;i<=n;++i) for (RI k=0;k<=1;++k)
{
for (F.read(len),j=1;j<=len;++j) F.read(a[++tot]),id[tot]=i; a[++tot]=++lim;
}
for (size=(int)sqrt(tot),i=1;i<=tot;++i) blk[i]=(i-1)/size+1;
for (SA.build(a,tot),i=1;i<=m;++i)
{
for (F.read(len),L=j=1,R=tot;j<=len;++j)
{
F.read(x); int l=L,r=R,mid; while (l<=r)
if (a[sa[mid=l+r>>1]+j-1]<x) l=mid+1; else r=mid-1;
int temp=l; l=L; r=R; while (l<=r)
if (a[sa[mid=l+r>>1]+j-1]<=x) l=mid+1; else r=mid-1;
L=temp; R=r;
}
if (L<=R) q[++cnt]=(ques){L,R,i};
}
for (sort(q+1,q+cnt+1),i=L=1,R=0;i<=cnt;++i)
{
while (L>q[i].l) add(sa[--L],i); while (R<q[i].r) add(sa[++R],i);
while (L<q[i].l) del(sa[L++],i); while (R>q[i].r) del(sa[R--],i);
ans[q[i].id]=ret;
}
for (i=1;i<=m;++i) F.write(ans[i],'\n');
for (i=1;i<=n;++i) F.write(t[i],' ');
return F.Fend(),0;
}
```