rt，sub2WA11~15 RE16~17

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define y1 Y1
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define P pair<double,double>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod) 
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
mt19937 rnd(time(0));
inline int read(int u=0, char c=getchar(), bool f=false){
	for (;!isdigit(c);c=getchar()) f|=c=='-';
	for (;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+c-'0';
	return f?-u:u;
}
inline void wt(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) wt(x/10);
	putchar(x%10+48);
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1; 
const int mod=998244353,g=3,gi=332748118;
const int N=1e5+10;
struct node{
	int lc,rc,id;
}tr[N<<2];
int n,root,cnt,cntedge;
struct edge{
	double k,b;
}p[N];
const double eps=1e-9;
int cmp(double x,double y){
	if(x>y+eps) return 1;
	if(y>x+eps) return -1;
	return 0;
}
double calc(int id,int x){return p[id].k*x+p[id].b;}
void add_edge(int x0,int y0,int x1,int y1){
	if(x0==x1) p[++cntedge].k=0,p[cntedge].b=max(y0,y1);
	else p[++cntedge].k=(y0-y1)*1.0/(x0-x1),p[cntedge].b=y0-p[cntedge].k*x0;
}
void pushdown(int &now,int l,int r,int v){
	if(!now) now=++cnt;
	if(!tr[now].id){
		tr[now].id=v;
		return ;
	}
	int mid=l+r>>1,u=tr[now].id;
	int bmid=cmp(calc(u,mid),calc(v,mid));
	if(bmid==1||(!bmid&&(u<v))) swap(u,v);tr[now].id=v;
	int bl=cmp(calc(u,l),calc(v,l)),br=cmp(calc(u,r),calc(v,r));
	if(bl==1||(!bl&&u<v)) pushdown(tr[now].lc,l,mid,u);
	if(br==1||(!br&&u<v)) pushdown(tr[now].rc,mid+1,r,u);
}
void modify(int &now,int l,int r,int ql,int qr,int x){
	if(!now) now=++cnt;
	if(ql<=l&&r<=qr){
		pushdown(now,l,r,x);
		return ;
	}
	int mid=l+r>>1;
	if(ql<=mid) modify(tr[now].lc,l,mid,ql,qr,x);
	if(qr>mid) modify(tr[now].rc,mid+1,r,ql,qr,x);
}
P pmax(P u,P v){
	if(cmp(u.x,v.x)==1) return u;
	if(cmp(u.x,v.x)==-1) return v;
	return u.y<v.y?u:v;
}
P query(int now,int l,int r,int pos){
	if(!now) return {0,0};
	if(l==r) return {calc(tr[now].id,pos),tr[now].id};
	int mid=l+r>>1;
	if(pos<=mid) return pmax({calc(tr[now].id,pos),tr[now].id},query(tr[now].lc,l,mid,pos));
	else return pmax({calc(tr[now].id,pos),tr[now].id},query(tr[now].rc,mid+1,r,pos));
}
main(){
	n=rd;
	int lastans=0;
	while(n--){
		bool op=rd;
		if(!op){
			int k=rd;k=(k+lastans-1)%39989+1;
			wt(lastans=query(root,1,39940,k).y,'\n');
		}
		else{
			int x0=rd,y0=rd,x1=rd,y1=rd;
			x0=(x0+lastans-1)%39989+1,x1=(x1+lastans-1)%39989+1;
			y0=(y0+lastans-1)%(int)(1e9)+1,y1=(y1+lastans-1)%(int)(1e9)+1;
			if(x0>x1) swap(x0,x1),swap(y0,y1);
			add_edge(x0,y0,x1,y1);
			modify(root,1,39940,x0,x1,cntedge);
		}
	}
	return 0;
}