题目背景
后缀仙人掌基于后缀 trie，将每个非叶子节点都与一个儿子合并，所形成的连接体称为树枝。
令 $v$ 为文本串 $T$ 的后缀 trie $STr(T)$ 的一个节点，满足 $v$ 是根或者 $v$ 不是其父亲 $w$ 的第一个儿子。那么文本串 $T$ 的后缀仙人掌 $SC(T)$ 中有树枝 $s$ 恰好包含从 $v$ 到其下第一个叶子 $u$ 路径上的所有节点。
——《Suffix Cactus》，2014，王悦同、徐毅、徐子涵
题目描述
定义一个字符串的周期是一个数 $p\in [1,len]$ 满足 $str_i=str_{i+p}, i\in[1,len-p]$。
给定一个长为 $n$ 的字符串 $d$，按以下规则生成 $n+1$ 个字符串：
- $S_0$ 为空串
- 若 $d_i$ 为小写字母，$S_i=d_i+S_{i-1}$
- 若 $d_i$ 为大写字母，设其对应的小写字母为 $c_i$，$S_i=S_{i-1}+c_i$
此处的 + 表示拼接。
给你一个长度为 $m$ 的序列 $p$，你需要回答 $q$ 次询问。每次询问给出 $k,l,r$，你需要找到 $p_l,p_{l+1},...,p_{r-1},p_r$ 中最小的数，使得该数为 $S_k$ 的一个周期。如果不存在输出 $-1$。
你不一定需要使用题目背景中的算法。
输入格式
第一行一个数 $n$ 表示字符串长度。
第二行一个长为 $n$ 的仅包含大小写字母的字符串 $d$。
第三行一个数 $m$ 表示序列长度。
第四行 $m$ 个整数表示序列 $p$。
第五行一个数 $q$ 表示询问个数。
接下来 $q$ 行，每行三个整数 $k,l,r$ 表示一组询问。
输出格式
输出 $q$ 行，每行一个整数表示答案。
样例
样例输入
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数据范围与约定
对于所有数据，$1\le n,m,q\le 5\times 10^5,1\le p_i,k_i\le n,1\le l\le r\le m$
Subtask 1（20分）：$n,m,q\le 2000$。
Subtask 2（20分）：$n\le2000,m,q\le 5\times 10^5$
Subtask 3（60分）：无特殊限制