// 

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <unsigned umod>
struct modint {
  static constexpr int mod = umod;
  unsigned v;
  modint() : v(0) {}
  template <class T, must_int<T> = 0>
  modint(T x) {
    x %= mod;
    v = x < 0 ? x + mod : x;
  }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  friend ostream& operator<<(ostream& os, const modint &self) { 
    return os << raw(self); 
  }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = 1ull * v * rhs.v % umod;
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T, must_int<T> = 0>
  friend modint qpow(modint a, T b) {
    modint r = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) r *= a;
    return r;
  }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  bool operator==(const modint &rhs) const { return v == rhs.v; }
  bool operator!=(const modint &rhs) const { return v != rhs.v; }
};
template <class T, int B>
struct hashTable {
  vector<T> bas{1}, sum{1};
  hashTable& operator+=(int x) {
    bas.push_back(bas.back() * B);
    sum.push_back(sum.back() * B + x);
    return *this;
  }
  T operator()(int l, int r) {
    return sum[r] - sum[l - 1] * bas[r - l + 1];
  }
};
struct scope {
  int l, r;
};
int n, m, q, fans[500010];
scope a[500010];
char str[500010];
vector<int> bucs[500010], bucp[500010];
vector<tuple<int, int, int>> bucq[500010];
hashTable<modint<998244353>, 233> hsh;
void readStr() {
  string s;
  cin >> s;
  deque<char> q;
  for (char ch : s) {
    if ('a' <= ch && ch <= 'z') q.push_front(ch);
    else q.push_back(ch - 'A' + 'a');
  }
  int l = 1, r = n;
  for (int i = n; i >= 1; i--) {
    str[i] = q[i - 1];
    a[i] = scope{l, r};
    if ('a' <= s[i - 1] && s[i - 1] <= 'z') ++l;
    else --r;
  }
}
constexpr int N = 1 << 19;
int ans[N << 1];
void insert(int x, int k) { for (x += N; x; x >>= 1) ans[x] = min(ans[x], k); }
int query(int l, int r) {
  int ret = 1e9;
  for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) ret = min(ret, ans[l ^ 1]);
    if (r & 1) ret = min(ret, ans[r ^ 1]);
  }
  return ret;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n;
  readStr();
  for (int i = 1; i <= n; i++) hsh += str[i];
  for (int i = 1; i <= n; i++) {
    int L = 1, R = n, ans = 0;
    for (int mid = (L + R) >> 1; L <= R; mid = (L + R) >> 1) {
      auto [l, r] = a[mid];
      if (i >= mid || hsh(l, r - i) == hsh(l + i, r)) ans = mid, L = mid + 1;
      else R = mid - 1;
    }
    bucs[ans].push_back(i);
  }
  cin >> m;
  for (int i = 1, x; i <= m; i++) cin >> x, bucp[x].push_back(i);
  cin >> q;
  for (int i = 1, k, l, r; i <= q; i++) cin >> k >> l >> r, bucq[k].emplace_back(l, r, i);
  memset(ans, 0x3f, sizeof ans);
  for (int i = n; i >= 1; i--) {
    for (int p : bucs[i]) {
      for (int i : bucp[p]) insert(i, p);
    }
    for (auto [l, r, id] : bucq[i]) fans[id] = query(l, r) <= i ? query(l, r) : -1;
  }
  for (int i = 1; i <= q; i++) cout << fans[i] << endl;
  return 0;
}