该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在复习字符串匹配，他觉得只会字符串匹配没什么意思

众所周知，字符在存储时本质上只是一个整数，于是徐老师决定开创一个新的问题——序列匹配！

徐老师会给定 $n$ 个整数，依次为 $a_1 \sim a_n$

接着给定 $q$ 次询问，每次询问会给出一个序列 $b_1 \sim b_{len}$

问 $b$ 序列在 $a$ 序列中出现了多少次？

P.S. 这里我们认为若存在一个整数 $i\ (i + len - 1 \leq n)$ 满足：$a_i \sim a_{i + len - 1}$ 和 $b_1 \sim b_{len}$ 是一样的，即对于任意 $j \in [1, len]$, 满足 $a_{i+j-1} = b_j$

则表示 $b$ 序列在 $a$ 序列的 $i$ 位置处出现了一次

输入格式

本题部分测试点要求在线处理

第一行为为一个整数 $op$ ，代表本测试点是否要求在线处理

第二行为两个整数 $n$ 和 $q$，含义如题

第三行为一个长为 $n$ 的正整数序列，表示 $a_1 \sim a_n$

接下来 $q$ 行，每行输入的第一个整数表示 $b$ 序列长度 $len$，然后依次输入 $len$ 个整数分别表示 $b_1 \sim b_{len}$

特别的，若 $op=1$，则每次输入的 $b$ 序列需要经过处理，设上一次询问的答案为 $lastans$（初始时 $lastans = 0$），则对于输入的 $b_i$ 进行 $b_i = b_i \ xor \ lastans$ 的处理后，才是真实的 $b_i$ 值

输出格式

输出 $q$ 行，每行输出一个整数表示每次询问的答案

数据范围

设 $T$ 为测试点编号，$max(b_i)$ 为 $b_i$ 真实值的最大值，对于所有数据保证 $a_i \leq 10^6$

样例输入1

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

样例输出1

2
2
3
0
3

样例输入2

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

样例输出2

2
2
3
0
3