rt.

过了 subtask0（hack 数据），但是 subtask1 只过了前 3 个点/kk

而将线段树的数组大小改成 x 的值域*4 后 subtask1 就会全 RE。

感觉很灵异求助/ll

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
void file_IO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
bool M1;
const ld eps=1e-9;
const int N=1e5+5,M=4e4+5,X=39989,Y=1e9;
struct LiChaoTree {
	struct line {
		ld k,b;
	}; line val[N];
	int p;
	int new_node(int ax,int ay,int bx,int by) {
		int k=++p;
		if(ax==bx) {
			val[k].k=0;
			val[k].b=max(ay,by);
		} else {
			val[k].k=1.0*(ay-by)/(ax-bx);
			val[k].b=1.0*ay-1.0*val[k].k*ax;
		}
		return k;
	}
	ld calc(int k,int x) {
		if(!k)
			return -INFLL;
		return val[k].k*x+val[k].b;
	}
	bool cmp(ld x,ld y,int u,int v) {
		return (x-y>eps||(y-x<eps&&u<v));
	}
	struct node {
		int l,r,x;
	}; node tree[N<<2]; //如果这里改成 M<<2 就会 RE，但是感觉开 M<<2 很对啊？
	#define ls(k) (k<<1)
	#define rs(k) (k<<1|1)
	void build(int k,int l,int r) {
		tree[k].l=l; tree[k].r=r;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		build(ls(k),l,mid);
		build(rs(k),mid+1,r);
	}
	void upd(int k,int u) {
		int &v=tree[k].x;
		if(cmp(calc(u,tree[ls(k)].r),calc(v,tree[ls(k)].r),u,v))
			swap(u,v);
		if(tree[k].l==tree[k].r)
			return;
		if(cmp(calc(u,tree[k].l),calc(v,tree[k].l),u,v))
			upd(ls(k),u);
		if(cmp(calc(u,tree[k].r),calc(v,tree[k].r),u,v))
			upd(rs(k),u);
	}
	void update(int k,int ql,int qr,int u) {
		if(ql<=tree[k].l&&tree[k].r<=qr) {
			upd(k,u);
			return;
		}
		if(ql<=tree[ls(k)].r)
			update(ls(k),ql,qr,u);
		if(qr>=tree[rs(k)].l)
			update(rs(k),ql,qr,u);
	}
	int query(int k,int qx) {
		if(tree[k].l==tree[k].r)
			return tree[k].x;
		int u=tree[k].x,v=0;
		if(qx<=tree[ls(k)].r)
			v=query(ls(k),qx);
		else
			v=query(rs(k),qx);
		return cmp(calc(u,qx),calc(v,qx),u,v)? u:v;
	}
	void ins(int ax,int ay,int bx,int by) {
		if(ax>bx) {
			swap(ax,bx);
			swap(ay,by);
		}
		update(1,ax,bx,new_node(ax,ay,bx,by));
	}
	int query(int x) {
		return query(1,x);
	}
	#undef ls
	#undef rs
}; LiChaoTree T;
void solve() {
	int q;
	scanf("%d",&q);
	T.build(1,1,X);
	int ans=0;
	while(q--) {
		int op;
		scanf("%d",&op);
		if(op==0) {
			int x;
			scanf("%d",&x);
			x=(x+ans-1)%X+1;
			printf("%d\n",ans=T.query(x));
		} else {
			int ax,ay,bx,by;
			scanf("%d%d%d%d",&ax,&ay,&bx,&by);
			ax=(ax+ans-1)%X+1;
			ay=(ay+ans-1)%Y+1;
			bx=(bx+ans-1)%X+1;
			by=(by+ans-1)%Y+1;
			T.ins(ax,ay,bx,by);
		}
	}
}
bool M2;
signed main() {
	//file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
	cerr<<"used time = "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	cerr<<"used memory = "<<(&M1-&M2)/1024/1024<<"MB\n";
	return 0;
}