代码：

#include <iostream>

#define db double

constexpr int N = 2e6 + 5,V = 39989,V2 = 1e9 + 1;
int t[N],n,op,cnt = 0;
/*
t[i] 存 线段树 i 节点最优线段编号  
*/ 
db k[N],b[N];
/*
k[i] 第 i 条线段的斜率
b[i] 第 i 条线段的截距 
*/
inline int ls(int x){
	return x << 1;
}
inline int rs(int x){
	return x << 1 | 1;
}

inline int compare(int i,int j,int x){
	/*
	check i 是否优于 j  
	*/
	db ans1 = (db)(k[i] * x + b[i]);
	db ans2 = (db)(k[j] * x + b[j]);
	if(ans1 - ans2 > 0){
		return 1;
	}
	if(ans1 - ans2 < 0){
		return -1;
	}
	return (i < j ? 0 : -1);
}
inline void update_change(int u,int id,int l,int r){
	auto &p = t[u];
	// p 直接穿址，修改 p 即修改 t[u]
	int mid = (l + r) >> 1;
	int cmp = compare(id,t[u],mid);
	if(~cmp){
		std::swap(p,id);
	}
	int cmp1 = compare(id,t[ls(u)],l);
	int cmp2 = compare(id,t[rs(u)],r);
	if(~cmp1){
		update_change(ls(u),id,l,mid);
	}
	if(~cmp2){
		update_change(rs(u),id,mid + 1,r);
	}
}
inline void add_lines(int u,int l,int r,int ql,int qr,int id){
	if(ql <= l && qr >= r){
		update_change(u,id,l,r);
		return;
	}
	int mid = (l + r) >> 1;
	if(ql <= mid) add_lines(ls(u),l,mid,ql,qr,id);
	if(qr > mid) add_lines(rs(u),mid + 1,r,ql,qr,id);
}
inline int ask(int u,int l,int r,int x,int mx){
	if(l == r){
		if(~compare(t[u],mx,x)){
			return t[u];
		}
		return mx;
	}
	int mid = (l + r) >> 1;
	if(x <= mid){
		int cmp = compare(t[u],mx,x);
		if(~cmp){
			return ask(ls(u),l,mid,x,t[u]);
		}
		return ask(ls(u),l,mid,x,mx);
	}else{
		int cmp = compare(t[u],mx,x);
		if(~cmp){
			return ask(rs(u),mid + 1,r,x,t[u]);
		}
		return ask(rs(u),mid + 1,r,x,mx);
	}
}
inline void init(int x0,int y0,int x1,int y1){
	if(x1 == x0){
		k[++ cnt] = 0;
		b[cnt] = std::max(y0,y1);
	}else{
		k[++ cnt] = (db)((y0 - y1) * 1.0 / (x0 - x1));
		b[cnt] = (db)((db)y0 - k[cnt] * 1.0 * x0);
		// kx0 + b = y0
		// b = y0 - kx0
	}
	add_lines(1,1,V,x0,x1,cnt); 
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n;
	k[0] = - 1e9;
	b[0] = - 1e9;
	int last_ans = 0;
	for(int x,x0,y0,x1,y1,i = 1;i <= n; ++ i){
		std::cin >> op;
		if(op){
			std::cin >> x0 >> y0 >> x1 >> y1;
			((x0 += last_ans - 1) %= V) += 1;
			((y0 += last_ans - 1) %= V2) += 1;
			((x1 += last_ans - 1) %= V) += 1;
			((y1 += last_ans - 1) %= V2) += 1;
			if(x0 > x1){
				std::swap(x0,x1);
				std::swap(y0,y1);
			}
//			std::cout << x0 << ' ' << y0 << ' ' << x1 << ' ' << y1 << '\n';
			::init(x0,y0,x1,y1);
//			std::cout << k[cnt] << ' ' << b[cnt] << '\n';
		}else{
			std::cin >> x;
			((x += last_ans - 1) %= V) += 1;
			std::cout << (last_ans = ask(1,1,V,x,0)) << '\n';
		}
	}
	return 0;
}