using System;

(long g, long inv) InvMod(long x, long m) {
  long a = m, b = x % m;
  long u = 0, v = 1;
  while (b != 0) {
    long q = a / b;
    (a, b) = (b, a - q * b);
    (u, v) = (v, u - q * v);
  }
  if (u < 0) u += m / a;
  return (a, u);
}

int Q = int.Parse(Console.ReadLine());
var M = new int[Q];
var Y = new int[Q];
int N = 0;
while (Q-- > 0) {
	var query = Console.ReadLine().Split(' ');
	int t = int.Parse(query[0]);
	if (t == 1) {
		int m = int.Parse(query[1]);
		int r = int.Parse(query[2]);
		if (N > 0 && Y[N - 1] < 0) {
			M[N] = m; Y[N] = -1;
		} else {
			long p = 1, y = r % m;
			for (int i = 0; i < N; i++) {
				y -= Y[i] * p % m;
				if (y < 0) y += m;
				p = p * M[i] % m;
			}
			var (g, x) = InvMod(p, m);
			if (y % g != 0) {
				M[N] = 1; Y[N] = -1;
			} else {
				M[N] = m /= (int)g;
				Y[N] = m == 1 ? 0 : (int)((y / g) * x % m);
			}
		}
		N++;
	} else if (t == 2) {
		int k = int.Parse(query[1]);
		N -= k;
	} else if (t == 3) {
		int m = int.Parse(query[1]);
		if (N > 0 && Y[N - 1] < 0) {
			Console.WriteLine(-1);
		} else {
			long x = 0;
			for (int i = N - 1; i >= 0; i--) x = (x * M[i] + Y[i]) % m;
			Console.WriteLine(x);
		}
	}
}