题目描述

一节数学课上,几位大佬因教学内容过于简单,偷偷开始了聊天,为了彰显他们的智慧,他们的聊天内容都经过了加密。信息是二进制的,共有 $M$($1≤M≤50000$)条,侦察能力很强的老师已经拦截了部分的聊天内容,知道了第 i 条二进制信息的前 $b_i$ ($1≤b_i ≤10000$)位,他同时知道,学生们使用 $N$($1≤N≤50000$)条暗号.但是,他仅仅知道第 $j$ 条暗号的前 $c_j$($1≤c_j ≤10000$)位。

对于每条暗号 j,他想知道有多少截得的聊天能够和它匹配。也就是说,有多少信息和这条暗号有着相同的前缀。当然,这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中,信息位数的总数(即 $\sum b_i + \sum c_i$)不会超过 $500000$。


输入格式

第一行两个整数M和N。
接下来一共M行,第i行的第一个整数为b_i,随后紧跟b_i个0或1的整数,表示第i条聊天信息。
接下来一共N行,第i行的第一个整数为c_i,随后紧跟c_i个0或1的整数,表示第i条暗号。


输出格式

输出共N行,第i行表示与第i个暗号匹配的聊天信息的数量。


样例数据

输入

4 5 
3 0 1 0 
1 1 
3 1 0 0 
3 1 1 0 
1 0 
1 1 
2 0 1 
5 0 1 0 0 1 
2 1 1 

输出

1 
3 
1 
1 
2 

备注


信息

时间限制: 3s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务