#include <iostream>
using i64=int64_t;
struct data{i64 M;i64 R;i64 nx;i64 nr;} stack[10000];
int szStack;
i64 Xmod(i64 m){
	i64 x=0,r=1;
	for(int i=0;i<szStack;i++){
		if(stack[i].M==0)return -1;
		x+=stack[i].nx*r;x%=m;
		r*=stack[i].nr;r%=m;
	}
	return x;
}
i64 Rmod(i64 m){
	i64 r=1;
	for(int i=0;i<szStack;i++){
		r*=stack[i].nr;r%=m;
	}
	return r;
}
i64 extgcd(i64 a,i64 b,i64 &x,i64 &y){
	i64 d=a;
	if(b){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}
	else{x=1;y=0;}
	return d;
}
int main(){int Q;std::cin>>Q;while(Q--){
	i64 q,x,y;
	std::cin>>q>>x;
	if(q==1){
		std::cin>>y;
		i64 a=Xmod(x),b=Rmod(x),t,u,g;
		if(a==-1){stack[szStack++]={};continue;}
		g=extgcd(x,b,t,u);
		if((y-a)%g){stack[szStack++]={};continue;}
		if(u<0)u+=x/g;
		u*=(y-a+x)/g;u%=x/g;
		stack[szStack++]={x,y,u,x/g};
	}
	if(q==2){szStack-=x;}
	if(q==3){std::cout<<Xmod(x)<<"\n";}
}return 0;}