#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;T f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) print(x/10);
	putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=500007,inf=0x3f3f3f3f;
const ll base=13331,mod=998244353;
struct node{int l,r,id;};
int n,m,q,l[N],r[N],a[N],ans[N];
char s[N]; string sl,sr; ll ha[N],pw[N];
vector<int>p[N],upd[N]; vector<node>ask[N];
struct segment_tree
{
	#define ls (rt<<1)
	#define rs (rt<<1|1)
	int f[N<<2];
	void build(int rt,int l,int r)
	{
		f[rt]=inf;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void update(int rt,int l,int r,int p,int x)
	{
		if(l==r) return f[rt]=x,void();
		int mid=(l+r)>>1;
		if(p<=mid) update(ls,l,mid,p,x);
		else update(rs,mid+1,r,p,x);
		f[rt]=min(f[ls],f[rs]);
	}
	int ask(int rt,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R) return f[rt];
		int mid=(l+r)>>1,res=inf;
		if(L<=mid) res=min(res,ask(ls,l,mid,L,R));
		if(R>mid) res=min(res,ask(rs,mid+1,r,L,R));
		return res;
	}
	#undef ls
	#undef rs
}Tr;
ull gethash(int l,int r){return (ha[r]+mod-ha[l-1]*pw[r-l+1]%mod)%mod;}
bool check(int i,int x)
{return gethash(l[i],l[i]+i-x-1)==gethash(r[i]+x-i+1,r[i]);}
void update(int i,int opt)
{
	for(auto pos:p[i])
	{
		if(opt==1) Tr.update(1,1,m,pos,i);
		else Tr.update(1,1,m,pos,inf);
	}
}
int main()
{
	read(n); scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		char c=s[i];
		if('A'<=c&&c<='Z')
			sr.push_back(c-'A'+'a');
		else sl.push_back(c);
	}
	reverse(sl.begin(),sl.end());
	l[0]=sl.size()+1; r[0]=sl.size();
	for(int i=1;i<=n;i++)
	{
		char c=s[i]; l[i]=l[i-1]; r[i]=r[i-1];
		('A'<=c&&c<='Z')?r[i]++:l[i]--;
	}
	for(int i=0;i<sl.size();i++) s[i+1]=sl[i];
	for(int i=0;i<sr.size();i++) s[i+sl.size()+1]=sr[i];
	pw[0]=1; read(m);
	for(int i=1;i<=m;i++)
		read(a[i]),p[a[i]].push_back(i);
	for(int i=1;i<=n;i++)
		pw[i]=pw[i-1]*base%mod,
		ha[i]=(ha[i-1]*base+s[i])%mod;
	for(int i=1;i<=n;i++)
	{
		int ml=i,mr=n,mid,res=i;
		while(ml<=mr)
		{
			mid=(ml+mr)>>1;
			if(check(mid,i))
				res=mid,ml=mid+1;
			else mr=mid-1;
		}
		upd[res+1].push_back(i);
	}
	read(q); Tr.build(1,1,m);
	for(int i=1,k,l,r;i<=q;i++)
		read(k,l,r),ask[k].push_back({l,r,i});
	for(int i=1;i<=n;i++)
	{
		update(i,1);
		for(auto x:upd[i])
			update(x,-1);
		for(auto [l,r,id]:ask[i])
			ans[id]=Tr.ask(1,1,m,l,r);
	}
	for(int i=1;i<=q;i++)
		print(ans[i]==inf?-1:ans[i],'\n');
	return 0;
}