各位观众，各位观众，您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的环城马拉松比赛中，天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜，最后战成 $233:233$ 平。考虑到迟迟不能决出胜者，比赛组委会决定临时更换比赛项目，而被选中的则是在跳蚤大陆流行已久的运动项目——维护数据结构。

维护数据结构可是个大麻烦！首先我来介绍一下数据结构比赛的规则，你有一个长度为 $n$ 的排列 $a$，比赛分为 $q$ 轮，第 $i$ 轮选手将会得到长度为 $m_i$ 的排列 $b_i$，对于一个 $x$（$1\le x\le n-m_i+1$)，它被称为合法的仅当序列 $a_x,a_{x+1},\cdots ,a_{x+m_i-1}$ 与序列 $b$ 相似，现在你需要统计合法的 $x$ 的数量。

两个序列长度为 $m$ 的序列 $u$ 和 $v$ 被称为相似的，当且仅当对于任意 $1\le i<j\le n$，要么 $u_i<u_j,v_i<v_j$，要么 $u_i>u_j,v_i>v_j$。

你看，现在所有的序列都已经给出了，选手们已经开始着手计算了。这看上去将会是一场非常激烈的比赛啊。

观众朋友们也可以和选手同台竞技，最早给出答案的观众可以获得小高铁一列哦。

输入格式

第一行一个只可能是 $0$ 或者 $1$ 的自然数 $\mathrm{type}$，含义在下面解释。

接下来一行一个正整数 $n,q$。

接下来一行 $n$ 个正整数，表示排列 $a$。

接下来 $q$ 行，其中第 $i$ 行的第一个整数为 $m_i$，接下来 $m_i$ 个正整数，表示排列 $b_i$。

注意给出的 $b_i$ 可能是经过加密的，如果 $\mathrm{type}=1$，那么假设上一个询问的答案为 $\mathrm{ans}$（若为第一个询问则 $\mathrm{ans}=0$），则应该进行变换 $c_{i,(j+\mathrm{ans}-1)mod{m}_i+1}=b_{i,j}$ 得到 $c_i$ 并将 $c_i$ 作为这次的询问序列。

输出格式

输出 $q$ 行，每行一个整数表示每个询问对应的合法的 $x$ 的数量。

样例一

input

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

output

5
2
2

explanation

实际上的三个询问序列分别是： $$\{1\},\{1,2\},\{1,3,2\}$$

对于第一个询问，由于长度为 $1$，所有长度为 $1$ 的区间都和询问序列相似。

对于后两个询问，$x$ 可以为 $1,3$。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

在所有数据中，满足 $1\le n\le 100000,\sum m_i\le 500000,1\le m_i\le n$, $a$ 和 $b_i$ 均为排列。

时间限制：$1\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$

下载

样例数据下载