对于一个字符串 $w = w_1w_2 \dots w_{\text{len}}$，如果对于所有 $1 \le i \le \text{len} - p$ 都有 $w_i = w_{i+p}$，且 $1 \le p \le \text{len}$，则称整数 $p$ 为 $w$ 的一个周期。

给定一个长度为 $n$ 的字符串 $d = d_1d_2 \dots d_n$，用于生成 $n+1$ 个字符串 $S_0, S_1, S_2, \dots, S_n$。其中 $S_0$ 为空串，对于所有 $1 \le i \le n$：

• 当 $d_i$ 为小写英文字母时，$S_i = d_i + S_{i-1}$。
• 当 $d_i$ 为大写英文字母时，设其对应的小写字母为 $c_i$，则 $S_i = S_{i-1} + c_i$。

此处“+”表示字符串连接。

随后给定一个整数序列 $p_1, p_2, \dots, p_m$。你需要回答 $q$ 次询问，每次询问给定三个整数 $k, l$ 和 $r$。你需要找到 $p_l, p_{l+1}, \dots, p_{r-1}, p_r$ 中满足是字符串 $S_k$ 的周期的最小值，如果不存在，则输出无解。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示非空字符串的数量。 第二行包含一个长度为 $n$ 的字符串 $d$，由大小写英文字母组成。 第三行包含一个整数 $m$ ($1 \le m \le 500\,000$)，表示序列 $p$ 的长度。 第四行包含 $m$ 个整数 $p_1, p_2, \dots, p_m$ ($1 \le p_i \le n$)。 第五行包含一个整数 $q$ ($1 \le q \le 500\,000$)，表示询问次数。 接下来的 $q$ 行，每行包含三个整数 $k, l$ 和 $r$ ($1 \le k \le n, 1 \le l \le r \le m$)，表示一次询问。

输出格式

对于每次询问，输出一行，包含一个整数表示答案。注意，若无解，请输出“-1”。

样例

样例输入 1

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