各位观众，各位观众，您现在收看的是第 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) \bmod 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

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

对于第一个询问，由于长度为 $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\texttt{s}$

空间限制：$1\texttt{GB}$

下载

样例数据下载