该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于一个字符串 $w=w_1 w_2 \ldots w_{len}$，我们称正整数 $p\ (1\le p\le len)$ 是$w$ 的周期，当且仅当对于任意的 $i\ (1 \leq i \leq len -p)$ 都有 $w_i=w_{i+p}$。

小 Z 有一个长度为 $n$ 的字符串 $d=d_1 d_2 \ldots d_n$，他用这个字符串生成了 $n+1$ 个字符串 $S_0, S_1, S_2, \ldots, S_n$，其中 $S_0$ 是空串。接下来，对于每个 $i\ (1 \leq i \leq n)$ ：

• 如果 $d_i$ 是一个小写英文字符，那么 $S_i=d_i+S_{i-1}$ ，也就是在 $S_{i-1}$ 前面添加字符 $d_i$ 得到 $S_i$。
• 如果 $d_i$ 是一个大写英文字符，那么假设 $d_i$ 的小写形式是 $c_i$，那么 $S_i=S_{i-1}+c_i$，也就是在 $S_{i-1}$ 后面添加字符 $c_i$ 得到 $S_i$。

小 Y 有 $m$ 个整数 $p_1, p_2, \ldots, p_m$，并向你问了 $q$ 个问题：

第 $i$ 个问题会提供三个参数 $k_i, l_i, r_i$ ，请你找出最小的整数 $x$，使得 $x$ 是 $S_{k_i}$ 的周期，并且 $x$ 是 $p_{l_i}, p_{l_i+1}, \ldots, p_{r_i-1}, p_{r_i}$ 中的某个数。如果你找不到这样的整数 $x$，输出 $-1$ 。

输入格式

从 period.in 文件读入数据。

第一行一个整数 $n$ 。

第二行一个长度为 $n$ 的字符串$d=d_1 d_2 \ldots d_n$，由大写和小写的英文字符构成。

第三行一个整数 $m$ 。

第四行 $m$ 个整数 $p_1,p_2,\cdots,p_m$ 。

第五行一个整数 $q$ 。

接下来 $q$ 行，每行三个整数 $k_i,l_i,r_i$ ，代表第 $i$ 个询问。

输出格式

输出到 period.out 文件。

对于每个询问，输出一行一个整数，代表答案。

样例

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

样例 2

点击链接 ex_period2.in 和 ex_period2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，$1\le n,m,q\le 5\times 10^5,1\le p_i,k_i\le n,1\le l_i\le r_i\le m$