rt,qwq

#include <bits/stdc++.h>
#define y1 Y1
#define ls u<<1
#define rs u<<1|1
#define eps 1e-9
using namespace std;
const int N=1e6+5,mod=39989,mod2=1e9;
int q;
int ans;
int x1[N],y1[N],x2[N],y2[N];
double K[N];
int lz[N*4];
int mx[N],mxh[N];
double calc(int id,int x){
	return 1.0*(x-x1[id])*K[id]+y1[id];
}
int comp(double x,double y){
	if(x-y > eps) return 1;
	if(y-x > eps) return -1;
	return 0;
}
void upd(int u,int l,int r,int id1){
	if(!lz[u]) {lz[u]=id1; return;}
	int &id2 = lz[u];
	int mid = (l+r)>>1;
	double res1=calc(id1,mid),res2=calc(id2,mid);
	if(comp(res1,res2)==1 || (comp(res1,res2)==0 && id1<id2))
		swap(id1,id2);
	if(l==r) return;
	if(comp(calc(id2,l),calc(id1,l))<=0) upd(ls,l,mid,id1);
	if(comp(calc(id2,r),calc(id1,r))<=0) upd(rs,mid+1,r,id1);
}
void update(int u,int l,int r,int ql,int qr,int id1){
	if(ql<=l && r<=qr) return upd(u,l,r,id1);
	int mid = (l+r)>>1;
	if(ql <= mid) update(ls,l,mid,ql,qr,id1);
	if(qr > mid) update(rs,mid+1,r,ql,qr,id1);
}
int pushup(int id1,int id2,int x){
	if(id1>id2) swap(id1,id2);
	if(id1==0) return id2;
	double res1=calc(id1,x), res2=calc(id2,x);
	if(comp(res1,res2)==-1) return id2;
	return id1;
}
int query(int u,int l,int r,int x){
	if(l==r) return lz[u];
	int mid = (l+r)>>1;
	if(x<=mid) return pushup(query(ls,l,mid,x),lz[u],x);
	return pushup(query(rs,mid+1,r,x),lz[u],x);
}
int main(){
	//freopen("P4097_1.in","r",stdin);
	cin>>q;
	int cur,op,x,y;
	while(q--){
		scanf("%d",&op);
		if(op==0){
			scanf("%d",&x);
			x = (x+ans-1)%mod+1;
			ans = query(1,1,mod,x);
			int res = comp(calc(ans,x),(double)mx[x]);
			if(res==-1 || (res==0 && mxh[x]<ans))
				ans = mxh[x];
			printf("%d\n",ans);
		}
		else{
			cur++;
			scanf("%d%d%d%d",&x1[cur],&y1[cur],&x2[cur],&y2[cur]);
			x1[cur] = (x1[cur]+ans-1)%mod+1;
			x2[cur] = (x2[cur]+ans-1)%mod+1;
			y1[cur] = (y1[cur]+ans-1)%mod2+1;
			y2[cur] = (y2[cur]+ans-1)%mod2+1;
			if(x1[cur] > x2[cur]) 
				swap(x1[cur],x2[cur]),swap(y1[cur],y2[cur]);
			if(x1[cur] == x2[cur]){
				x = x1[cur];
				y = max(y1[cur],y2[cur]);
				if(y>mx[x]) mx[x] = y, mxh[x] = cur;
			}
			else{
				K[cur] = 1.0*(y2[cur]-y1[cur])/(x2[cur]-x1[cur]);
				update(1,1,mod,x1[cur],x2[cur],cur);
			}
		}
	}
	return 0;
}