#include<bits/stdc++.h>
#define int long long
#define P 13331
#define MOD 1000000007
using namespace std;
int n,m,q,l[500003],r[500003],k[500003],ans[500003],a[500003],hs[500003],fsp[500003];
int L[500003],R[500003];
pair<int,int>qq[500003];
string opS,S;
int Que[1200003],lft,rgt,mid,delwz[500003];
vector<int>lst[500003];
vector<int>lst2[500003];
int geths(int l,int r){return (((hs[r]-hs[l-1]*fsp[r-l+1])%MOD)+MOD)%MOD;}
int val[4000003];
void build(int now,int nowl,int nowr){
	if(nowl==nowr){
		val[now]=10000000;
		return;
	}
	build(now*2,nowl,((nowl+nowr)>>1));
	build(now*2+1,((nowl+nowr)>>1)+1,nowr);
	val[now]=min(val[now*2],val[now*2+1]);
	return;
}
void modify(int now,int wz,int v,int nowl,int nowr){
	if(nowl==nowr){
		val[now]=v;
		return;
	}
	if(wz<=((nowl+nowr)>>1))modify(now*2,wz,v,nowl,((nowl+nowr)>>1));
	else modify(now*2+1,wz,v,((nowl+nowr)>>1)+1,nowr);
	val[now]=min(val[now*2],val[now*2+1]);
	return;
}
int Query(int now,int ql,int qr,int nowl,int nowr){
	if(nowl>=ql&&nowr<=qr)return val[now];
	if(qr<=((nowl+nowr)>>1))return Query(now*2,ql,qr,nowl,((nowl+nowr)>>1));
	if(ql>((nowl+nowr)>>1))return Query(now*2+1,ql,qr,((nowl+nowr)>>1)+1,nowr);
	return min(Query(now*2,ql,qr,nowl,((nowl+nowr)>>1)),Query(now*2+1,ql,qr,((nowl+nowr)>>1)+1,nowr));
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	fsp[0]=1;
	for(int i=1;i<=500000;i++)fsp[i]=fsp[i-1]*P%MOD;
	cin>>n>>opS;
	lft=700000;
	rgt=lft-1;
	for(int i=1;i<=n;i++){
		if(opS[i-1]>='A'&&opS[i-1]<='D')Que[++rgt]=opS[i-1]-'A'+'a';
		else Que[--lft]=opS[i-1];
	}
	for(int i=lft;i<=rgt;i++)S+=(char)(Que[i]);
	for(int i=1;i<=n;i++)hs[i]=(hs[i-1]*P+S[i-1])%MOD;
	L[0]=700000-lft+1;
	R[0]=699999-lft+1;
	for(int i=1;i<=n;i++){
		L[i]=L[i-1];R[i]=R[i-1];
		if(opS[i-1]>='A'&&opS[i-1]<='D')R[i]++;
		else L[i]--;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		lft=a[i];
		rgt=n;
		while(lft<rgt){
			mid=((lft+rgt)>>1)+1;
			if(geths(L[mid],R[mid]-a[i])==geths(L[mid]+a[i],R[mid]))lft=mid;
			else rgt=mid-1;
		}
		delwz[i]=lft+1;
		lst[delwz[i]].emplace_back(i);
		lst2[a[i]].emplace_back(i);
	}
	build(1,1,m);
	cin>>q;
	for(int i=1;i<=q;i++)cin>>k[i]>>l[i]>>r[i];
	for(int i=1;i<=q;i++)qq[i]=make_pair(k[i],i);
	sort(qq+1,qq+q+1);
	for(int i=1,j=0;i<=n;i++){
		for(auto j:lst2[i])modify(1,j,a[j],1,m);
		for(auto j:lst[i])modify(1,j,10000000,1,m);
		while(j+1<=q&&qq[j+1].first==i){
			j++;
			ans[qq[j].second]=Query(1,l[qq[j].second],r[qq[j].second],1,m);
		}
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==10000000)cout<<-1<<endl;
		else cout<<ans[i]<<endl;
	}
	return 0;
}