회문

회문(palindrome)은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.

Yuuka에게 문자열 $s$가 있으며, 그녀는 이에 대해 여러 질문을 하고 싶어 한다. 각 질문에서 Yuuka는 정수 리스트 $x_1, x_2, \dots, x_k$ (여기서 $x_i$는 1부터 시작하는 위치)와 정수 $l$을 준다. $s(x, p)$를 $s$에서 위치 $x$부터 시작하는 길이 $p$의 부분 문자열이라고 하자. $t$는 $s(x_1, l), s(x_2, l), \dots, s(x_k, l)$을 차례로 이어 붙인 문자열이다. Yuuka는 $t$에 있는 회문 부분 문자열의 총 개수를 알고 싶어 한다.

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 문자열의 길이 $n$이 주어진다 ($1 \le n \le 10^5$).

둘째 줄에 문자열 $s$를 나타내는 정수 $s_1, s_2, \dots, s_n$이 주어진다 ($1 \le s_i \le n$). Yuuka가 사용하는 알파벳은 클 수 있으므로, 각 문자는 1부터 $n$까지의 정수로 나타낸다.

셋째 줄에 질문의 개수 $m$이 주어진다 ($1 \le m \le 10^5$).

이어지는 $m$개의 줄 각각에는 정수 $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$를 넘지 않는다.

각 질문마다 $t$에 있는 회문 부분 문자열의 개수를 정수로 출력한다.