#include <bits/stdc++.h>   using namespace std;   int pri[26] = {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, -1};   long long mo[5] = {223092870ll, 2756205443ll, 907383479ll, 42600829ll, 97ll};   int N, M, d, t, len, i, j, u;   int b[100];   long long a[20000], c, ans;   char ss[100];   vector<long long> f[17][5];   int num(int d, char c) {     return c ==  ?  ? d : (c <=  9  ? c -  0  : c -  A  + 10);   }   void prework() {     int i, j, k, l;     for (i = 2; i <= 16; i++) {       for (j = 0, k = l = 1; k <= N; k *= i, l *= i + 1)         ;       for (j = 0; j < 5; j++) f[i][j].resize(l, -1);     }   }   int calc(int d, int p) {     int i, j, x = 0, y = 0;     for (i = 0; i < t; i++) x = x * (d + 1) + b[i];     if (f[d][p][x] != -1) return x;     f[d][p][x] = 1;     for (i = 0; i < t; i++)       if (b[i] == d) {         for (j = 0; j < d; j++)           b[i] = j, f[d][p][x] = (f[d][p][x] * f[d][p][calc(d, p)]) % mo[p];         b[i] = d;         return x;       }     for (i = 0; i < t; i++) y = y * d + b[i];     if (y < N) f[d][p][x] = a[y] % mo[p];     return x;   }   int main() {     scanf( %d , &N);     for (i = 0; i < N; i++) scanf( %I64d , &a[i]);     scanf( %d , &M);     prework();     while (M--) {       scanf( %d%s%I64d , &d, ss, &c);       for (j = 1, t = 0; j <= N; t++, j *= d)         ;       len = strlen(ss);       for (j = 0; j < t; j++)         if (len - t + j >= 0)           b[j] = num(d, ss[len - t + j]);         else           b[j] = 0;       for (i = 0; i < 5; i++) {         j = calc(d, i);         ans = (f[d][i][j] + c) % mo[i];         for (j = 0; j < 25; j++)           if (mo[i] % pri[j] == 0 && ans % pri[j] == 0) break;         if (j < 25) break;       }       printf( %d n , pri[j]);     }   }   