回文串是指正读和反读都相同的字符串。

Yuuka 有一个字符串 $s$，她想询问关于它的一些问题。在每个问题中，Yuuka 会给你一个整数列表 $x_1, x_2, \dots, x_k$（其中 $x_i$ 为 1-indexed）和一个整数 $l$。令 $t$ 为 $s(x_1, l), s(x_2, l), \dots, s(x_k, l)$ 的拼接，其中 $s(x, p)$ 是 $s$ 中从位置 $x$ 开始、长度为 $p$ 的子串。Yuuka 想知道 $t$ 中回文子串的总数。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$，表示字符串的长度（$1 \le n \le 10^5$）。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，表示字符串 $s$（$1 \le s_i \le n$；Yuuka 使用的字母表可能很大，因此我们仅用 $1$ 到 $n$ 的整数来表示其字符）。

第三行包含一个整数 $m$，表示询问次数（$1 \le m \le 10^5$）。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $k_i$ 和 $l_i$，随后是 $k_i$ 个整数 $x_{i,1}, x_{i,2}, \dots, x_{i,k_i}$（$1 \le k_i \le 10^5$，$1 \le l_i \le n$，$k_i \cdot l_i \le 10^9$，$1 \le x_{i,j} \le n - l_i + 1$）。

保证所有 $n$ 之和以及所有 $k_i$ 之和均不超过 $10^5$。

输出格式

对于每个询问，输出一个整数，表示回文子串的数量。

样例

输入 1

9
1 2 1 2 1 2 1 2 1
3
3 3 1 4 7
9 1 1 2 3 4 5 6 7 8 9
4 3 1 2 1 2

输出 1

25
25
42