样例过不去！！！

#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=1e5+10;
const int maxn=39989;
const int mod=1e9;
const int inf=0x3f3f3f3f;
const double eps=1e-9;

struct line{
    double k,b;
}f[N];
struct tree{
    int l,r,max;
}a[N<<2];

double get(int i,int x){
    return x*f[i].k+f[i].b;
}

int compare(double x,double y){
    if(x-y>eps) return 1;
    if(x-y<eps) return -1;
    return 0;
}

void build(int p,int l,int r){
    a[p].l=l,a[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

int gmax(int x,int y,int id){
    if(compare(get(x,id),get(y,id))==1){
        return x;
    }
    if(compare(get(x,id),get(y,id))==-1){
        return y;
    }
    return x<y?x:y;
}

int quest(int p,int id){
    int l=a[p].l,r=a[p].r;
    if(l>id||r<id) return 0;
    if(l==r){
        return a[p].max;
    }
    int ans=0;
    ans=gmax(ans,quest(ls,id),id);
    ans=gmax(ans,quest(rs,id),id);
    return ans;
}

void upd(int p,int id){
    int l=a[p].l,r=a[p].r,&i=a[p].max;
    int mid=(l+r)>>1;
    if(compare(get(id,mid),get(i,mid))==1) swap(i,id);
    int ll=compare(get(id,l),get(i,l));
    int rr=compare(get(id,r),get(i,r));
    if(ll==1 || (ll==0&&i>id)) upd(ls,id);
    if(rr==1 || (rr==0&&i>id)) upd(rs,id);  
}

void update(int p,int L,int R,int id){
    int l=a[p].l,r=a[p].r;
    if(L<=l&&r<=R){
        upd(p,id);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(ls,L,R,id);
    if(R>mid) update(rs,L,R,id);
}

int main(){
    int n;
    scanf("%d",&n);
    //cout<<f[0].k<<" "<<f[0].b<<endl;
    int last=0,cnt=0;
    build(1,1,maxn);
    while(n--){
        int op;
        scanf("%d",&op);
        if(op==0){
            int q;
            scanf("%d",&q);
            q=(q+last-1+39989)%39989+1;
            last=quest(1,q);
            printf("%d\n",last);
        }else{
            int x0,y0,x1,y1;
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            cnt++;
            x0=(x0+last-1+39989)%39989+1;
            x1=(x1+last-1+39989)%39989+1;
            y0=(y0+last-1+mod)%mod+1;
            y1=(y1+last-1+mod)%mod+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            if(x0==x1){
                f[cnt].k=0;
                f[cnt].b=max(y1,y0);
            }else{
                f[cnt].k=1.0*(1.0*(y1-y0))/(1.0*(x1-x0));
                f[cnt].b=1.0*(1.0*y1-1.0*f[cnt].k*x1);
            }
            update(1,x0,x1,cnt);
        }
    }
}

样例输出

2
0
0