Palindrome

A palindromic string is a string that reads the same forward and backward.

Yuuka has a string $s$ and wants to ask some questions about it. In each question, Yuuka gives a list of integers $x_1, x_2, \dots, x_k$ (where $x_i$ is 1-indexed) and an integer $l$. Let $s(x, p)$ denote the substring of $s$ of length $p$ that starts at position $x$. Let $t$ be the concatenation of $s(x_1, l), s(x_2, l), \dots, s(x_k, l)$. Yuuka wants to know the total number of palindromic substrings of $t$.

The input contains zero or more test cases and ends at end-of-file. Each test case is as follows.

The first line contains the length $n$ of the string ($1 \le n \le 10^5$).

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ that denote the string $s$ ($1 \le s_i \le n$). Yuuka's alphabet may be large, so each character is written as an integer from 1 to $n$.

The third line contains the number of questions $m$ ($1 \le m \le 10^5$).

Each of the next $m$ lines contains two integers $k_i$ and $l_i$, followed by $k_i$ integers $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$).

The sum of all $n$ and the sum of all $k_i$ do not exceed $10^5$.

For each question, output the number of palindromic substrings of $t$ as an integer.