#include <bits/stdc++.h>
using namespace std;
const int S = 13;
const int Full = (1 << S) - 1;
int prime[50] = {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},
    tot = 25;
char block[800][1 << S][25];
int mm[10010][26], to[100000];
unsigned long long all[15][15][16][200];
unsigned long long tmp[200];
int tmp2[25];
int ans[25];
int key(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  return c - 'A' + 10;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    long long x;
    scanf("%lld", &x);
    for (int j = 0; j < tot; j++) {
      mm[i][j] = x % prime[j];
    }
  }
  for (int i = 0; i < S; i++) {
    to[1 << i] = i;
  }
  for (int i = 0; i < n; i += S) {
    int s = min(S, n - i);
    for (int j = 0; j < 25; j++) {
      block[i / S][0][j] = 1;
    }
    for (int mask = 1; mask < (1 << s); mask++) {
      int lowbit = mask & -mask;
      for (int j = 0; j < 25; j++) {
        block[i / S][mask][j] =
            block[i / S][mask - lowbit][j] * mm[i + to[lowbit]][j] % prime[j];
      }
    }
  }
  for (int d = 2; d <= 16; d++) {
    int pw = 1;
    for (int j = 0; pw < n; j++, pw *= d) {
      for (int i = 0; i < n; i++) {
        int val = 0, len = 0, x = i, cnt = 0;
        while (x) {
          if (j == cnt) val = x % d;
          x /= d, len++, cnt++;
        }
        all[d - 2][j][val][i / (4 * S)] |= 1ull << (i % (4 * S));
      }
    }
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int d;
    char s[50];
    long long a;
    scanf("%d", &d);
    scanf("%s", s), scanf("%lld", &a);
    int m = strlen(s);
    for (int j = 0; j < tot; j++) {
      ans[j] = a % prime[j];
    }
    for (int j = 0; j <= ((n - 1) / (4 * S)); j++) {
      tmp[j] = (1ull << 4 * S) - 1;
    }
    long long pw = 1;
    for (int i = m - 1; i >= 0; i--) {
      if (pw >= n) {
        if (s[i] != '?' && s[i] != '0') {
          for (int j = 0; j <= ((n - 1) / (4 * S)); j++) {
            tmp[j] = 0;
          }
        }
        continue;
      }
      pw *= d;
      if (s[i] == '?') continue;
      int val = key(s[i]);
      for (int j = 0; j <= ((n - 1) / (4 * S)); j++) {
        tmp[j] &= all[d - 2][m - i - 1][val][j];
      }
    }
    int nn = m;
    while (pw < n) {
      for (int j = 0; j <= ((n - 1) / (4 * S)); j++) {
        tmp[j] &= all[d - 2][nn][0][j];
      }
      pw *= d, nn++;
    }
    for (int k = 0; k < 25; k++) {
      tmp2[k] = 1;
    }
    for (int j = 0; j <= ((n - 1) / (4 * S)); j++) {
      int be = j * 4 * S, pp = be / S;
      for (int k = 0; k < 25; k++) {
        if (n - be > 0)
          tmp2[k] =
              tmp2[k] * block[pp][tmp[j] & ((1 << min(S, n - be)) - 1)][k];
        if (n - be - S > 0)
          tmp2[k] =
              tmp2[k] *
              block[pp + 1][tmp[j] >> S & ((1 << min(S, n - be - S)) - 1)][k];
        tmp2[k] -= tmp2[k] / prime[k] * prime[k];
        if (n - be - 2 * S > 0)
          tmp2[k] =
              tmp2[k] * block[pp + 2][tmp[j] >> 2 * S &
                                      ((1 << min(S, n - be - 2 * S)) - 1)][k];
        if (n - be - 3 * S > 0)
          tmp2[k] =
              tmp2[k] * block[pp + 3][tmp[j] >> 3 * S &
                                      ((1 << min(S, n - be - 3 * S)) - 1)][k];
        tmp2[k] -= tmp2[k] / prime[k] * prime[k];
      }
    }
    int pos = 0;
    while (pos < tot && (ans[pos] + tmp2[pos]) % prime[pos] != 0) pos++;
    if (pos == tot)
      printf("-1\n");
    else
      printf("%d\n", prime[pos]);
  }
  return 0;
}
