#include <bits/stdc++.h>
using namespace std;
namespace sais{
	template<int v,typename T>void arrset(T*const arr,const int len){
		std::memset(arr,v,len*sizeof(T));
	}
	template<typename T>void arrcpy(T*const arr1,const T*const arr2,const int len){
		std::memcpy(arr1,arr2,len*sizeof(T));
	}
	constexpr int max_n=1000000,max_char=256;
	int num[max_n+1],cur[max_n+1];
	void sais(int*a,const int n,const int k,int*sa){
		#define pus(pos) sa[cur[a[pos]]--]=pos
		#define pul(pos) sa[++cur[a[pos]]]=pos
		#define induce_sort(lmspos)\
			arrset<-1>(sa+1,n),arrcpy(cur,sum,k+1);\
			for(const int*i=lmspos+m; i>lmspos; --i)\
				pus(*i);\
			arrcpy(cur+1,sum,k);\
			for(const int*i=sa; ++i<=fin; *i>1&&!tp[*i-1]&&(pul(*i-1)));\
			arrcpy(cur,sum,k+1);\
			for(const int*i=sa+n; i>sa; --i)\
				if(*i>1&&tp[*i-1])\
					pus(*i-1);
		bool*const tp=(new bool[n])-1;
		tp[n]=1;
		for(int i=n; --i; tp[i]=(a[i]==a[i+1])?tp[i+1]:(a[i]<a[i+1]));
		int*const lms=new int[(n+4)>>1],m=0;
		num[1]=-1;
		for(int i=2; i<=n; ++i)
			num[i]=(tp[i]&&!tp[i-1])?(lms[++m]=i,m):-1;
		int*const sum=new int[k+1];
		arrset<0>(sum,k+1);
		for(const int*i=a+n; i>a; --i)
			++sum[*i];
		for(int*i=sum,*const ed=sum+k,now=*sum; ++i<=ed; now=*i+=now);
		const int*const fin=sa+n;
		induce_sort(lms);
		lms[m+1]=n;
		int*const a1=new int[m+1],k1=0;
		for(int i=1,x,y; i<=n; ++i)
			if(~(x=num[sa[i]])){
				if(!k1||lms[x+1]-lms[x]!=lms[y+1]-lms[y])
					a1[y=x]=++k1;
				else{
					for(int p1=lms[x],p2=lms[y],ed=lms[x+1]; p1<ed; ++p1,++p2)
						if(a[p1]!=a[p2]||tp[p1]!=tp[p2]){
							++k1;
							break;
						}
					a1[y=x]=k1;
				}
			}
		if(k1==m)
			for(int i=1; i<=m; ++i)
				sa[a1[i]]=i;
		else
			sais(a1,m,k1,sa);
		for(int i=1; i<=m; ++i)
			a1[i]=lms[sa[i]];
		induce_sort(a1);
		delete[] (tp+1),
		delete[] lms,
		delete[] sum,
		delete[] a1;
		#undef pus
		#undef pul
		#undef induce_sort
	}
	char s[max_n+2];
	int a[max_n+2];
	int sa[max_n+2];
	int ton[max_char+1];
	template <typename T,typename vT> inline void maxi(T&x,vT val){
		(val>x)&&(x=val);
	}
	template <typename T,typename vT> inline void mini(T&x,vT val){
		(val<x)&&(x=val);
	}
	int rk[max_n+2];
	int height[max_n+2];
	template <typename T> void write(T x){
		x>9&&(write(x/10),0);
		putchar(x%10^'0');
	}
	int st[max_n+2][20];
	void main(int n){
		int minc=max_char,maxc=0;
		memset(ton,0,sizeof(ton));
		for(int i=1; i<=n; ++i)
			ton[int(s[i])]=1,maxi(maxc,s[i]),mini(minc,s[i]);
		++n;
		ton[minc-1]=1;
		int*edd=ton+maxc;
		for(int*i=ton+minc; i<=edd; ++i)
			*i+=*(i-1);
		for(int i=1; i<n; ++i)
			a[i]=ton[int(s[i])];
		a[n]=1;
		sais(a,n,ton[maxc],sa);
		for(int i=1; i<=n; ++i)
			rk[sa[i]]=i;
		int x=0;
		for(int i=1,j; i<=n; ++i){
			for(j=sa[rk[i]-1],x&&--x; a[i+x]==a[j+x]; ++x);
			height[rk[i]-1]=x;
		}
		for(int i=n; --i; )
			for(int now=st[i][0]=height[i],j=0,d=1; j+d*2<=n; st[i][++j]=now,d<<=1)
				mini(now,st[i+d][j]);
	}
	int rmq(int l,int r){
		const int d=31^__builtin_clz(r-l);
		return min(st[l][d],st[r-(1<<d)][d]);
	}
	int lcp(int a,int b){
		// fprintf(stderr,"%d %d\n",a,b);
		a=rk[a],b=rk[b];
		const int res=a<b?rmq(a,b):rmq(b,a);
		// fprintf(stderr,"%d\n",res);
		return res;
	}
}
using namespace std;
typedef pair<int,int> pii;
constexpr int max_n=500000,max_m=500000,max_q=500000;
pii pos[max_n+1];
vector<int>dque[max_n+1];
int tr[max_m<<1];
int p[max_m+1];
void build(const int now,const int lft,const int rgt){
	if(lft==rgt-1){
		tr[now]=p[lft];
		return;
	}
	const int mid=(lft+rgt)>>1;
	const int lsn=mid<<1;
	const int rsn=lsn|1;
	build(lsn,lft,mid);
	build(rsn,mid,rgt);
	tr[now]=min(tr[lsn],tr[rsn]);
}
void update(const int now,const int lft,const int rgt,const int p){
	if(lft==rgt-1){
		tr[now]=max_n;
		return;
	}
	const int mid=(lft+rgt)>>1;
	const int lsn=mid<<1;
	const int rsn=lsn|1;
	if(p<mid)
		update(lsn,lft,mid,p);
	else
		update(rsn,mid,rgt,p);
	tr[now]=min(tr[lsn],tr[rsn]);
}
int query(const int now,const int lft,const int rgt,const int l,const int r){
	// fprintf(stderr,"%d %d  %d %d\n",lft,rgt,l,r);
	if(l<=lft&&rgt<=r)
		return tr[now];
	const int mid=(lft+rgt)>>1;
	const int lsn=mid<<1;
	const int rsn=lsn|1;
	if(r<=mid)
		return query(lsn,lft,mid,l,r);
	if(l>=mid)
		return query(rsn,mid,rgt,l,r);
	return min(query(lsn,lft,mid,l,r),query(rsn,mid,rgt,l,r));
}
int ans[max_q+1];
vector<pair<pii,int> >que[max_n+1];
char opstr[max_n+1];
int main(){
	int n,m;
	scanf("%d\n%s",&n,opstr);
	// fprintf(stderr,"n: %d\n",n);
	scanf("%d",&m);
	for(int i=0; i<m; ++i)
		scanf("%d",p+i);
	int q;
	scanf("%d",&q);
	for(int i=0,k,l,r; i<q; ++i){
		scanf("%d%d%d",&k,&l,&r);
		que[k].emplace_back(pii(l-1,r),i);
	}
	int l=1;
	for(int i=0; i<n; ++i)
		l+=bool(islower(opstr[i]));
	int r=l-1;
	for(int i=0; i<n; ++i){
		if(isupper(opstr[i]))
			sais::s[++r]=tolower(opstr[i]);
		else
			sais::s[--l]=opstr[i];
		pos[i+1]=pii(l,r);
		// fprintf(stderr,"%d: %d %d\n",i,l,r);
	}
	// for(int i=1; i<=n; ++i)
	// 	fprintf(stderr,"%c",sais::s[i]);
	// fprintf(stderr,"\n");
	sais::main(n);
	for(int i=0; i<m; ++i){
		const int dif=p[i];
		int l=dif,r=n+1;
		while(l<r-1){
			const int mid=(l+r)/2;
			if(sais::lcp(pos[mid].first,pos[mid].first+dif)>=mid-dif)
				l=mid;
			else
				r=mid;
		}
		// fprintf(stderr,"%d: %d %d\n",i,p[i],l);
		dque[l].emplace_back(i);
	}
	build(1,0,m);
	for(int i=1; i<=n; ++i){
		for(const pair<pii,int>&quer:que[i]){
			const int l=quer.first.first,r=quer.first.second;
			ans[quer.second]=query(1,0,m,l,r);
			if(ans[quer.second]>i)
				ans[quer.second]=-1;
		}
		for(const int&p:dque[i])
			update(1,0,m,p);
	}
	for(int i=0; i<q; ++i)
		printf("%d\n",ans[i]);
	return 0;
}