#include <stdio.h>

long long gcd (long long a, long long b) {
  if (b <= 0LL) {
    return a;
  }
  return gcd(b, a%b);
}

int main () {
  long long k = 0LL;
  int q = 0;
  int t = 0;
  long long x = 0LL;
  
  int res = 0;
  
  int cnt = 0;
  long long g[64] = {};
  int len = 0;
  
  res = scanf("%lld", &k);
  res = scanf("%d", &q);
  while (q > 0) {
    res = scanf("%d", &t);
    res = scanf("%lld", &x);
    if (t == 1) {
      int tmplen = 0;
      long long tmp = x;
      while (tmp > 0LL) {
        g[tmplen] = gcd(g[tmplen], tmp%k);
        tmp /= k;
        tmplen++;
      }
      if (tmplen > len) {
        len = tmplen;
      }
      cnt++;
    } else if (t == 2 && cnt < 1 && x > 1LL) {
      printf("-1\n");
    } else if (t == 2 && cnt < 1) {
      printf("0\n");
    } else if (t == 2 && cnt < 2) {
      long long g_all = k;
      for (int i = 0; i < len; i++) {
        g_all = gcd(g_all, g[i]);
      }
      if (k/g_all < x) {
        printf("-1\n");
      } else {
        long long ans = 0LL;
        printf("%lld\n", ans);
      }
    }
    q--;
  }
  
  return 0;
}