#GYM104639H. Range Periodicity Query
Range Periodicity Query
Description
For a string $w=w_1w_2\dots w_{len}$, we say that an integer $p$ is a period of $w$ if $w_i = w_{i+p}$ holds for all $i$ ($1 \leq i \leq len - p$) and $1\leq p\leq len$.
You will be given a string $d=d_1d_2\dots d_n$ to generate $n+1$ strings $S_0,S_1,S_2,\dots,S_n$, where $S_0$ is an empty string, and for all $i$ ($1 \leq i \leq n$):
- When $d_i$ is a lowercase English letter, $S_i=d_i+S_{i-1}$.
- When $d_i$ is an uppercase English letter, assume its lowercase version is $c_i$, then $S_i=S_{i-1}+c_i$.
Here, "+" denotes concatenation of strings.
You will then be given a sequence of integers $p_1,p_2,\dots,p_m$. You need to answer $q$ queries, in each query, you will be given three integers $k$, $l$ and $r$. You need to find the minimum number among $p_{l},p_{l+1},\dots,p_{r-1},p_r$ such that it is a period of string $S_k$, or determine there is no answer.
The first line contains a single integer $n$ ($1 \leq n \leq 500\,000$) denoting the number of non-empty strings.
The second line contains a string $d$ of length $n$ consists of lowercase and uppercase English letters.
The third line contains a single integer $m$ ($1 \leq m \leq 500\,000$) denoting the length of the sequence $p$.
The fourth line contains $m$ integers $p_1,p_2,\dots,p_m$ ($1 \leq p_i \leq n$).
The fifth line contains a single integer $q$ ($1 \leq q \leq 500\,000$) denoting the number of queries.
Each of the next $q$ lines contains three integers $k$, $l$ and $r$ ($1\leq k\leq n$, $1\leq l\leq r\leq m$), denoting a query.
For each query, print a single line containing an integer denoting the answer. Note that when there is no answer, please print "-1" instead.
Input
The first line contains a single integer $n$ ($1 \leq n \leq 500\,000$) denoting the number of non-empty strings.
The second line contains a string $d$ of length $n$ consists of lowercase and uppercase English letters.
The third line contains a single integer $m$ ($1 \leq m \leq 500\,000$) denoting the length of the sequence $p$.
The fourth line contains $m$ integers $p_1,p_2,\dots,p_m$ ($1 \leq p_i \leq n$).
The fifth line contains a single integer $q$ ($1 \leq q \leq 500\,000$) denoting the number of queries.
Each of the next $q$ lines contains three integers $k$, $l$ and $r$ ($1\leq k\leq n$, $1\leq l\leq r\leq m$), denoting a query.
Output
For each query, print a single line containing an integer denoting the answer. Note that when there is no answer, please print "-1" instead.
7
AABAAba
9
4 3 2 1 7 5 3 6 1
6
1 4 4
2 1 4
2 1 3
3 3 5
5 4 7
7 8 9
1
1
2
-1
3
6