#include <bits/stdc++.h>
using namespace std;
const int inft = 1000000009;
const int MAXN = 1000006, N = 25;
inline int put(char ss) {
  if (ss <= '9' && ss >= '0') return ss - '0';
  return 10 + ss - 'A';
}
inline char rput(int a) {
  if (a <= 9) return '0' + a;
  return 'A' + a - 10;
}
int mn[20][MAXN], n, d, S;
char ss[MAXN];
long long mod[4] = {1224469897, 1503325967, 1336143462, 937397015}, t[MAXN], c;
int V[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
           43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97},
    G[] = {2, 2, 3, 0, 1, 1, 0, 3, 2, 3, 2, 0, 1,
           1, 0, 2, 3, 0, 1, 2, 3, 3, 2, 1, 0};
map<string, pair<pair<int, int>, pair<int, int> > > M[20];
vector<int> nn[20];
string s;
inline void mnoz(pair<pair<int, int>, pair<int, int> > &A,
                 pair<pair<int, int>, pair<int, int> > B) {
  A.first.first = 1LL * A.first.first * B.first.first % mod[0];
  A.first.second = 1LL * A.first.second * B.first.second % mod[1];
  A.second.first = 1LL * A.second.first * B.second.first % mod[2];
  A.second.second = 1LL * A.second.second * B.second.second % mod[3];
}
pair<pair<int, int>, pair<int, int> > get(int poz, bool eq) {
  if (M[d].find(s) != M[d].end()) return M[d][s];
  pair<pair<int, int>, pair<int, int> > ans =
      make_pair(pair<int, int>(1, 1), pair<int, int>(1, 1));
  if (poz == S) {
    int licz = 0;
    for (int i = 0; i < (S); ++i) licz += mn[d][S - i - 1] * put(s[i]);
    ans.first = pair<int, int>(t[licz] % mod[0], t[licz] % mod[1]);
    ans.second = pair<int, int>(t[licz] % mod[2], t[licz] % mod[3]);
  } else {
    if (s[poz] != '?') {
      if (!eq || put(s[poz]) <= nn[d][poz])
        mnoz(ans, get(poz + 1, eq && nn[d][poz] == put(s[poz])));
    } else {
      for (int i = 0; i < (eq ? nn[d][poz] + 1 : d); ++i) {
        s[poz] = rput(i);
        mnoz(ans, get(poz + 1, eq && nn[d][poz] == i));
      }
      s[poz] = '?';
    }
  }
  return M[d][s] = ans;
}
void solve() {
  scanf("%d", &n);
  for (int i = 0; i < (n); ++i) scanf("%I64d", &t[i]);
  for (int dd = 0; dd < (17); ++dd)
    if (dd > 1) {
      int temp = n - 1;
      nn[dd].push_back(temp % dd);
      temp /= dd;
      while (temp) {
        nn[dd].push_back(temp % dd);
        temp /= dd;
      }
      reverse((nn[dd]).begin(), (nn[dd]).end());
    }
  int m;
  scanf("%d", &m);
  long long ans[4];
  for (int ii = 0; ii < (m); ++ii) {
    scanf("%d %s %I64d", &d, ss, &c);
    s = string(ss);
    while (s.length() < nn[d].size()) s = '0' + s;
    bool ok = true;
    if (s.length() > nn[d].size()) {
      for (int i = 0; i < (s.length() - nn[d].size()); ++i)
        if (s[i] != '0' && s[i] != '?') ok = false;
    }
    s = s.substr(s.length() - nn[d].size());
    S = s.length();
    if (ok) {
      pair<pair<int, int>, pair<int, int> > w = get(0, 1);
      ans[0] = w.first.first;
      ans[1] = w.first.second;
      ans[2] = w.second.first;
      ans[3] = w.second.second;
    } else
      for (int i = 0; i < (4); ++i) ans[i] = 1;
    for (int i = 0; i < (4); ++i) ans[i] = (ans[i] + c) % mod[i];
    bool oki = false;
    for (int i = 0; i < (N); ++i)
      if (ans[G[i]] % V[i] == 0) {
        printf("%d\n", V[i]);
        oki = true;
        break;
      }
    if (!oki) printf("-1\n");
  }
}
int main() {
  for (int dd = 0; dd < (17); ++dd)
    if (dd > 1) {
      mn[dd][0] = 1;
      for (int j = 0; j < (MAXN); ++j)
        if (j) mn[dd][j] = min(mn[dd][j - 1] * dd, MAXN + 5);
    }
  solve();
  return 0;
}
