#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
using i64=int64_t;
using u64=uint64_t;
using u128=__uint128_t;
namespace isPrime {
constexpr u64 qpow(u64 a,u64 b,u64 p) {
   u64 res=1;
   for(;b;b>>=1,a=a*a%p)
      if(b&1) res=res*a%p;
   return res;
}
constexpr bool checkPrime(u64 p) {
   if(p==1) return false;
   u64 d=__builtin_ctzll(p-1),s=(p-1)>>d;
   for(auto a:{2,3,5,7,11,13,82,373}) {
      if(a%p==0) continue;
      u64 x=qpow(a,s,p),y=0;
      for(int i=0;i<d;i++,x=y) {
         y=(u128)x*x%p;
         if(y==1&&x!=1&&x!=p-1)
            return false;
      } if(y!=1) return false;
   } return true;
}
}
// gen prime in [L,R)
template<u64 __start=0>
constexpr u64 genPrime(u64 l,u64 r) {
   using isPrime::checkPrime;
   u64 x=__start^0x113817;
   for(char c:__TIME__ __TIMESTAMP__)
      x+=c,x^=x<<13,x^=x>>7,x^=x<<17;
   while(true) {
      x^=x<<13,x^=x>>7,x^=x<<17;
      auto y=l+x%(r-l);
      if(checkPrime(y)) return y;
   } return 0;
}
}
namespace asnown {
using i32=int32_t;
using u32=uint32_t;
using i64=int64_t;
using u64=uint64_t;
using i128=__int128_t;
using u128=__uint128_t;
constexpr i32 inverse(i32 a,i32 m) {
   i64 r=1;
   while(a>1) { r=r*(m-m/a)%m,a=m%a; }
   return r;
}
template<i32 m>
class static_modint { 
   using mint=static_modint;
public:
   constexpr static_modint() : v(0) {}
   constexpr static_modint(i32 v) : v(normal(v%m)) {}
   constexpr static_modint(u32 v) : v(v%m) {}
   constexpr static_modint(i64 v) : v(normal(v%m)) {}
   constexpr static_modint(u64 v) : v(v%m) {}
   constexpr static_modint(i128 v) : v(normal(v%m)) {}
   constexpr static_modint(u128 v) : v(v%m) {}
   constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
   constexpr u32 val() const { return v; }
   constexpr static u32 mod() { return m; }
   constexpr explicit operator bool() const { return v; }
   constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
   constexpr mint pow(i64 b) const { assert(b>=0); 
      mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
   constexpr mint operator+() const { return *this; }
   constexpr mint operator-() const { return mint()-*this; }
   constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
   constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
   constexpr mint& operator++() { return (*this)+=1; }
   constexpr mint& operator--() { return (*this)-=1; }
   constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
   constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
   constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
   constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
   constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
   constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
   constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
   constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
   constexpr friend mint operator++(mint &v,i32) { auto tmp=v; v+=1; return tmp; }
   constexpr friend mint operator--(mint &v,i32) { auto tmp=v; v-=1; return tmp; }
   constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
   constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
   constexpr bool operator==(const mint& p) const { return val()==p.val(); }
   constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
   u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
const int B = asnown::genPrime<>(100,300);
using hint=asnown::static_modint<asnown::genPrime<B>(1e8,1e9)>;
const int N = 5e5+55;
int n,m,Q;
string s; int low;
deque<char> t;
int st[N];
hint pw[N],h[N];
vector<int> c[N],pos[N];
namespace SGT {
const int N = ::N<<2;
#define mid ((L+R)>>1)
#define ls (u<<1)
#define rs (ls|1)
int mn[N];
void build(int u,int L,int R) {
   mn[u]=0x3f3f3f3f;
   if(L==R) return ;
   build(ls,L,mid),build(rs,mid+1,R);
}
void update(int u,int L,int R,int x,int k) {
   if(L==R) return void(mn[u]=k);
   if(x<=mid) update(ls,L,mid,x,k);
   else update(rs,mid+1,R,x,k);
   mn[u]=min(mn[ls],mn[rs]);
}
int query(int u,int L,int R,int l,int r) {
   if(l<=L&&R<=r) return mn[u];
   if(r<=mid) return query(ls,L,mid,l,r);
   if(l> mid) return query(rs,mid+1,R,l,r);
   return min(query(ls,L,mid,l,r),query(rs,mid+1,R,l,r));
}
#undef mid
#undef ls
#undef rs
}
vector<tuple<int,int,int>> q[N];
int ans[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   Solve();
}
void Solve() {
   cin>>n>>s,s=' '+s;
   for(int i=1;i<=n;i++) {
      if(isupper(s[i])) t.emplace_back(tolower(s[i]));
      else ++low,t.emplace_front(s[i]);
   } t.emplace_front(' ');
   st[0]=low+1;
   pw[0]=1;
   for(int i=1;i<=n;i++) {
      st[i]=st[i-1]-bool(islower(s[i]));
      pw[i]=pw[i-1]*B; h[i]=h[i-1]*B+t[i];
   }
   for(int i=1;i<=n;i++) {
      int l=i,r=n,mid;
      while(l<r) {
         mid=l+r+1>>1;
         if(h[st[mid]+mid-i-1]-pw[mid-i]*h[st[mid]-1]
          ==h[st[mid]+mid-1]-pw[mid-i]*h[st[mid]+i-1])
            l=mid; else r=mid-1;
      }
      c[l].emplace_back(i);
   }
   cin>>m;
   SGT::build(1,1,m);
   for(int i=1;i<=m;i++) {
      int x; cin>>x; pos[x].emplace_back(i);
   }
   cin>>Q;
   for(int i=1;i<=Q;i++) {
      int k,l,r; cin>>k>>l>>r;
      q[k].emplace_back(l,r,i);
   }
   for(int i=n;i>=1;i--) {
      for(auto cc:c[i]) for(auto x:pos[cc])
         SGT::update(1,1,m,x,cc);
      for(auto [l,r,id]:q[i]) {
         ans[id]=SGT::query(1,1,m,l,r);
         if(ans[id]>i) ans[id]=-1;
      }
   }
   for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}