记录编号	216466	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	assassain	是否通过	通过
代码语言	C++	运行时间	0.674 s
提交时间	2015-12-29 09:55:52	内存使用	9.85 MiB

#define MAXN 200010UL
#include <cstdio>
#include <map>
#include <vector>
#include <queue>

using namespace std;

int n, m, num, bg[500100], v[400010], ans[MAXN], lt[MAXN], rt[MAXN], mid[MAXN], c[400010], w[400010];

struct ME {
	ME *fl;
	map<int, ME*>op;
	vector<int>ch;
	int last_x, id, se;
}*Rt;

void Insert(ME *rt,int len,int k) {
	for(int i = 1 ; i <= len ; ++ i) {
		if(!rt->op[c[i]]) {
			rt->op[c[i]] = new ME();
			rt->op[c[i]]->id = ++ num;
			rt->ch.push_back(c[i]);
		}
		rt = rt->op[c[i]];
	}
	bg[k] = rt->id;
	++ rt->se;
	return;
}

void Get_fail() {
	queue<ME*>q;
	q.push(Rt);
	while(!q.empty()) {
		ME *tmp = q.front();
		q.pop();
		int len = tmp->ch.size();
		for(int i = 0 ; i < len ; ++ i) {
			ME *p = tmp->fl;
			int np = tmp->ch[i];
			while(p&&!p->op[np]) p = p->fl;
			if(!p) tmp->op[np]->fl = Rt;
			else tmp->op[np]->fl = p->op[np];
			q.push(tmp->op[np]);
		}
	}
	return;
}

void Work(ME *rt,int l,int r,int k) {
	for(int i = l ; i <= r ; ++ i) {
		if(rt->op[w[i]]) {
			rt = rt->op[w[i]];
		} else {
			ME *p = rt->fl;
			while(p&&!p->op[w[i]]) p = p->fl;
			if(!p) rt = Rt;
			else rt = p->op[w[i]];
		}
		ME *tmp = rt;
		while(tmp&&tmp->last_x!=k) {
			ans[k] += tmp->se;
			tmp->last_x = k;
			++ v[tmp->id];
			tmp = tmp->fl;
		}
	}
	return;
}

int main() {
	freopen("wtfname.in", "r", stdin);
	freopen("wtfname.out", "w", stdout);
	int x;
	Rt = new ME();
	scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= n ; ++ i) {
		scanf("%d", &x);
		lt[i] = rt[i-1]+1;
		mid[i] = lt[i]+x-1;
		for(int j = 0 ; j < x ; ++ j) scanf("%d", &w[lt[i]+j]);
		scanf("%d", &x);
		rt[i] = mid[i]+x;
		for(int j = 1 ; j <= x ; ++ j) scanf("%d", &w[mid[i]+j]);
	}
	for(int i = 1 ; i <= m ; ++ i) {
		scanf("%d", &x);
		for(int j = 1 ; j <= x ; ++ j) scanf("%d", &c[j]);
		Insert(Rt, x, i);
	}
	Get_fail();
	for(int i = 1 ; i <= n ; ++ i) {
		Work(Rt, lt[i], mid[i], i);
		Work(Rt, mid[i]+1, rt[i], i);
	}
	for(int i = 1 ; i <= m ; ++ i) {
		printf("%d\n", v[bg[i]]);
	}
	if(n) printf("%d", ans[1]);
	for(int i = 2 ; i <= n ; ++ i) {
		printf(" %d", ans[i]);
	}
	return 0;
}