简单来说就是对于每条线段，先把它拆成\(O(logn)\)条，然后对于每一条再\(O(logn)\)判断在所有子区间的优劣程度

//minamoto#include
    
     #define R register int#define ls (p<<1)#define rs (p<<1|1)#define fp(i,a,b) for(R i=a,I=b+1;i
     
      I;--i)#define go(u) for(R i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)inline int max(const R&x,const R&y){return x>y?x:y;}inline int min(const R&x,const R&y){return x
      
       '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e5+5;struct node{    int l,r,id;    double yl,yr;    node(int x1=0,int y1=0,int x2=0,int y2=0,int i=0){        l=x1,r=x2;yl=y1,yr=y2;id=i;        if (l==r) yl=yr=max(yl,yr);    }    double get(int x){return l==r?yl:yl+(k()*(x-l));}    double k(){return (yr-yl)/(r-l);}    void lm(int x){yl=get(x);l=x;}    void rm(int x){yr=get(x);r=x;}};bool cmp(node a,node b,int x){    return a.get(x)==b.get(x)?a.id
       
        b.get(x);}struct TR{    node tr[N<<2];    void build(int p,int l,int r){        tr[p].l=l,tr[p].r=r;if(l==r)return;        R mid=(l+r)>>1;        build(ls,l,mid),build(rs,mid+1,r);    }    node query(int p,int l,int r,int x){        if(l==r)return tr[p];node res;R mid=(l+r)>>1;        res=(x<=mid)?query(ls,l,mid,x):query(rs,mid+1,r,x);        return cmp(res,tr[p],x)?res:tr[p];    }    void update(int p,int l,int r,node x){        if(tr[p].l>x.l)x.lm(tr[p].l);        if(tr[p].r
        
         >1;        if(cmp(x,tr[p],mid))swap(tr[p],x);        if(l==r||min(tr[p].yl,tr[p].yr)>=max(x.yl,x.yr))return;        tr[p].k()<=x.k()?update(rs,mid+1,r,x):update(ls,l,mid,x);    }    void insert(int p,int l,int r,node x){        if(x.l>r||x.r
         
          x.l)x.lm(tr[p].l);if(tr[p].r
          
           >1; insert(ls,l,mid,x),insert(rs,mid+1,r,x); }}T;int lastans,cnt,n=39989,lim=1e9,m,op,k,x,y,xx,yy;node res;int main(){// freopen("testdata.in","r",stdin); T.build(1,1,n);m=read(); while(m--){ op=read(); if(!op){ k=read(),k=(k+lastans-1)%n+1; lastans=T.query(1,1,n,k).id; print(lastans); }else{ x=read(),y=read(),xx=read(),yy=read(); x=(x+lastans-1)%n+1,xx=(xx+lastans-1)%n+1; y=(y+lastans-1)%lim+1,yy=(yy+lastans-1)%lim+1; if(x>xx)swap(x,xx),swap(y,yy); res=node(x,y,xx,yy,++cnt),T.insert(1,1,n,res); } }return Ot(),0;}