19396번 - Palindrome 다국어

A palindromic string is a string that reads the same forward as it does backward.

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

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

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

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ denoting the string $s$ ($1 \le s_i \le n$; the alphabet Yuuka uses may be large, so we just denote its characters by integers from $1$ to $n$).

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

The $i$-th of the following $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$).

It is guaranteed that neither the sum of all $n$ nor the sum of all $k_i$ exceeds $10^5$.

For each question, output an integer denoting the number of palindromic substrings.