题目描述

小 $A$ 有 $M$ 个由数字 "01" 构成的二进制数组，小 $B$ 有 $N$ 个由数字 "01" 构成的二进制数组。

请问小 $B$ 的每个二进制数组可以和小 $A$ 的多少个二进制数组完成前缀匹配。

这里前缀匹配的含义是：如果小 $B$ 的第 $i$ 个二进制数组是小 $A$ 的第 $j$ 个二进制数组的前缀，或者小 $A$ 的第 $j$ 个二进制数组是小 $B$ 的第 $i$ 个二进制数组的前缀，都可以称为这两个二进制数组完成了前缀匹配。

输入格式

第 $1$ 行读入两个整数 $M, N$。

接下来 $M$ 行，每行先读入一个整数 $X_i$，表示小 $A$ 的二进制数组的长度，再读入 $X_i$ 个由数字 $0$ 或 $1$ 构成的数组。

接下来 $N$ 行，每行先读入一个整数 $Y_i$，表示小 $B$ 的二进制数组的长度，再读入 $Y_i$ 个由数字 $0$ 或 $1$ 构成的数组。

输出格式

输出 $N$ 行，第 $i$ 行输出的是小 $B$ 的第 $i$ 个二进制数组可以和小 $A$ 的二进制数组完成匹配的数组数量。

样例

输入

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

输出

1
3
1
1
2

输入

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

输出

1
3
3
2
1

数据范围

对于 $10\%$ 的数据，满足 $1 \le M, N \le 10$，$1 \le X_i, Y_i \le 10$，$\sum X_i + \sum Y_i \le 30$。

对于 $100\%$ 的数据，满足 $1 \le M, N \le 50000$，$1 \le X_i, Y_i \le 10000$，$\sum X_i + \sum Y_i \le 500000$。