#include<bits/stdc++.h>
#define ll long long
#define P 114517
#define MOD 1000000007
using namespace std;
int n,m,q,l[500003],r[500003],k[500003],ans[500003],a[500003];
ll fsp[500003],hs[500003];
int L[500003],R[500003];
string opS,S;
int Que[1200003],lft,rgt,mid;
vector<int>lst[500003];
vector<int>lst2[500003];
vector<int>qlst[500003];
ll geths(int l,int r){return (((hs[r]-hs[l-1]*fsp[r-l+1])%MOD)+MOD)%MOD;}
int val[4000003],www[500003];
void build(int now,int nowl,int nowr){
	val[now]=10000000;
	if(nowl==nowr)www[nowl]=now;
	if(nowl==nowr)return;
	build(now*2,nowl,((nowl+nowr)>>1));
	build(now*2+1,((nowl+nowr)>>1)+1,nowr);
	return;
}
void modify(int wz,int v){
	val[www[wz]]=v;
	for(int i=www[wz]>>1;i;i>>=1)val[i]=min(val[i<<1],val[i<<1|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));
}
int 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]<='Z')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]<='Z')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;
		}
		lst[lft+1].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++)qlst[k[i]].emplace_back(i);
	for(int i=1;i<=n;i++){
		for(auto j:lst2[i])modify(j,a[j]);
		for(auto j:lst[i])modify(j,10000000);
		for(auto j:qlst[i])ans[j]=Query(1,l[j],r[j],1,m);
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==10000000)cout<<-1<<endl;
		else cout<<ans[i]<<endl;
	}
	return 0;
}