#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
}
int T=1;
const int N=5e5+10;
int l[N],r[N];
string s;
const int ba=131;
#define ull unsigned long long
ull ha[N],jc[N];
deque<char>d;
ull has(int l,int r) {
	return ha[r]-ha[l-1]*jc[r-l+1];
}
int n,m;
int pl[N];
struct node{
	int l,r,p,id;
	friend bool operator<(const node&a,const node&b) {
		return a.r<b.r;
	}
}a[N];
struct query{
	int l,r,k,id;
	friend bool operator<(const query&a,const query&b) {
		return a.k>b.k;
	}
}qu[N];
struct sgt{
	int l,r;
	int Min;
}tr[N<<2];
void up(int x) {
	tr[x].Min=min(tr[x<<1].Min,tr[x<<1|1].Min);
}
void build(int u,int l,int r) {
	tr[u]={l,r};
	if(l==r) {
		tr[u].Min=INT_MAX;
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	up(u);
}
void modify(int u,int x,int k) {
	if(tr[u].l==tr[u].r) {
		tr[u].Min=k;
		return;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(mid>=x) modify(u<<1,x,k);
	else modify(u<<1|1,x,k);
	up(u);
}
int Ans(int u,int l,int r) {
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Min;
	int mid=tr[u].l+tr[u].r>>1,res=1e18;
	if(mid>=l) res=Ans(u<<1,l,r);
	if(mid<r) res=min(res,Ans(u<<1|1,l,r));
	return res;
}
int ans[N];
void solve() {
	in(n);
	cin>>s;
	for(auto to:s) {
		if(to>='a'&&to<='z') d.push_back(to);
		else d.push_front(to-'A'+'a');
	}
	s=" "+s;
	rep(i,1,n) {
		if(s[i]>='A'&&s[i]<='Z') {
			pl[1]++;
			pl[i]--;
		}
		r[i]=i;
		l[i]=1;
	}
	rep(i,1,n) pl[i]+=pl[i-1],l[i]+=pl[i],r[i]+=pl[i];
	s=" ";
	while(d.size()) {
		s+=d.front();
		d.pop_front();
	}
	jc[0]=1;
	rep(i,1,n) ha[i]=ha[i-1]*ba+s[i]-'a'+1,jc[i]=jc[i-1]*ba;
	in(m);
	rep(i,1,m) {
		in(a[i].p);
		int ll=a[i].p,rr=n,res=0;
		while(ll<=rr) {
			int mid=ll+rr>>1;
			if(has(l[mid]+a[i].p,r[mid])==has(l[mid],r[mid]-a[i].p)) ll=mid+1,res=mid;
			else rr=mid-1;
		}
		a[i].l=a[i].p;
		a[i].r=res;
		a[i].id=i;
	}
	sort(a+1,a+1+m);
	int q;
	in(q);
	rep(i,1,q) in(qu[i].k),in(qu[i].l),in(qu[i].r),qu[i].id=i;
	sort(qu+1,qu+1+q);
	build(1,1,m);
	int now=m;
	rep(i,1,q) {
		while(qu[i].k<=a[now].r&&now) {
			modify(1,a[now].id,a[now].p);
			now--;
		}
		ans[qu[i].id]=Ans(1,qu[i].l,qu[i].r);
		if(ans[qu[i].id]>qu[i].k) ans[qu[i].id]=-1;
	}
	rep(i,1,q) {
		cout<<ans[i]<<endl;
	}
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}
/*
 7
 AABAAba
 1
 1
*/