/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#include <deque> 
#define pr pair <int, int>
#define mr make_pair
#define LL long long
#define ls tree[p].L
#define rs tree[p].R
#define uLL unsigned long long
using namespace std;
const int MAXN = 5e5 + 5, inf = 0x3f3f3f3f, Mod = 998244353;
struct node {
	int L, R, id;
	node() {}
	node(int x, int y, int z) { L = x; R = y; id = z; }
};
int n, L[MAXN], R[MAXN], m, q, ans[MAXN];
deque <char> que;
char S[MAXN], s[MAXN];
vector <int> v[MAXN];
vector <pr> qwq[MAXN];
vector <node> qry[MAXN];
LL Hash[MAXN], P[MAXN];
void read(int &x) {
	x = 0; bool f = 1; char C = getchar();
	for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
	for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
	x = (f ? x : -x);
}
LL gethash(int l, int r) {
	return ((Hash[r] - Hash[l - 1] * P[r - l + 1]) % Mod + Mod) % Mod;
}
int check(int x, int len) {
	if(R[x] - L[x] + 1 <= len) return 1;
	return gethash(L[x], R[x] - len) == gethash(L[x] + len, R[x]);
}
struct sgt {
	int L, R, minn;
}tree[MAXN << 2];
void build(int p, int l, int r) {
	tree[p].L = l; tree[p].R = r; tree[p].minn = inf;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
}
void cng(int p, int x, int val) {
	if(tree[p].L == tree[p].R) {
		tree[p].minn = val; return;
	}
	int mid = (tree[p].L + tree[p].R) >> 1;
	if(x <= mid) cng(p << 1, x, val);
	else cng(p << 1 | 1, x, val);
	tree[p].minn = min(tree[p << 1].minn, tree[p << 1 | 1].minn);
}
int query(int p, int ql, int qr) {
	if(ql > qr) return inf;
	if(tree[p].L >= ql && tree[p].R <= qr) return tree[p].minn;
	int mid = (tree[p].L + tree[p].R) >> 1;
	if(mid < ql) return query(p << 1 | 1, ql, qr);
	if(mid >= qr) return query(p << 1, ql, qr);
	return min(query(p << 1, ql, qr), query(p << 1 | 1, ql, qr));
}
int main() {
	scanf("%d%s", &n, S + 1); int now = 0, x, y, z;
	for(int i = 1; i <= n; i ++) {
		if(S[i] >= 'a' && S[i] <= 'z') now ++, que.push_front(S[i]);
		else que.push_back(S[i] - 'A' + 'a');
		if(i == 1) now = 1;
	}
	n = 0;
	while(!que.empty()) s[++ n] = que.front(), que.pop_front();
	L[1] = now; R[1] = now; P[0] = 1;
//	for(int i = 1; i <= n; i ++) printf("%c", s[i]);
	for(int i = 1; i <= n; i ++) {
		Hash[i] = (Hash[i - 1] * 2007391 + s[i]) % Mod;
		P[i] = P[i - 1] * 2007391 % Mod;
	}
	for(int i = 2; i <= n; i ++) {
		L[i] = L[i - 1]; R[i] = R[i - 1];
		if(S[i] >= 'a' && S[i] <= 'z') L[i] --;
		else R[i] ++;
	}
	for(int i = 1; i <= n; i ++) {
		int l = 1, r = n, mid, res = 0;
		while(l <= r) {
			mid = (l + r) >> 1;
			if(check(mid, i)) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		if(res >= i) qwq[res].emplace_back(mr(i, 1)), qwq[i - 1].emplace_back(mr(i, -1));
	}
	read(m);
	for(int i = 1; i <= m; i ++) {
		read(x); v[x].emplace_back(i);
	}
	read(q); build(1, 1, m);
	for(int i = 1; i <= q; i ++) {
		read(z); read(x); read(y); qry[z].emplace_back(node(x, y, i));
	}
	for(int i = n; i >= 1; i --) {
		for(auto j : qwq[i]) {
			for(auto k : v[j.first]) {
				if(j.second == 1) cng(1, k, j.first);
				else cng(1, k, inf);
			}
		}
		for(auto j : qry[i]) ans[j.id] = query(1, j.L, j.R);
	}
	for(int i = 1; i <= q; i ++) printf("%d\n", ans[i] == inf ? -1 : ans[i]);
	return 0;
}
/*
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
*/