Bessie 带领奶牛企图逃跑！为此，奶牛互相发送秘密二进制消息。

一贯聪明的反间谍 Farmer John 截获了 $M$ 条消息，$(1 \le M \le 50,000)$，每条的前 $b_{i}$ 位，$(1 \le b_{i} \le 10,000)$。

他列出认为奶牛在使用的 $N$ 个不完整码字，$(1 \le N \le 50,000)$。遗憾的是，只知道码字 $j$ 的前 $c_{j}$ 位，$(1 \le c_{j} \le 10,000)$。

对每个码字 $j$，计算多少条截获消息与它匹配，即消息和码字的开头位相同。你的任务是求这个数。

输入总位数，即 $b_{i}$ 与 $c_{j}$ 之和，不超过 $500,000$。

输入格式

• 第 $1$ 行：整数 $M$、$N$。

• 第 $2,\ldots,M+1$ 行：第 $i+1$ 行描述截获消息 $i$，先是整数 $b_{i}$，再是以空格分隔的 $b_{i}$ 个 0 或 1。

• 第 $M+2,\ldots,M+N+1$ 行：第 $M+j+1$ 行描述码字 $j$，先是整数 $c_{j}$，再是以空格分隔的 $c_{j}$ 个 0 或 1。

输出格式

• 第 $1,\ldots,M$ 行：第 $j$ 行是第 $j$ 个码字可匹配的消息数。

样例

输入格式 1

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

1
3
1
1
2

说明

四条消息、五个码字。消息开头为 010、1、100、110；码字开头为 0、1、01、01001、11。

0 只匹配 010：$1$ 条；1 匹配 1、100、110：$3$ 条；01 只匹配 010：$1$ 条；01001 匹配 010：$1$ 条；11 匹配 1、110：$2$ 条。

题目作者：David Benjamin 和 Jacob Steinhardt，2008