H. Range Periodicity Query
time limit per test
2 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

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.

Example
Input
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
Output
1
1
2
-1
3
6