萌新WA了，只剩，30，没找到能够HACK自己的小数据，救一下

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>

const int mod1=39989;
const int mod2=1000000000;

using namespace std;

struct node
{
    int l,r,id;
}p[1000000];
struct linee
{
    long double k,b;
}s[1000000];

int n,len=0;

void build(int w,int l,int r)
{
    p[w].l=l;p[w].r=r;p[w].id=0;
    if(l==r)return;
    build(w*2,l,(l+r)/2);build(w*2+1,(l+r)/2+1,r);
} 

inline long double calc(int id,int x){return s[id].b+s[id].k*x;} 

void change(int w,int k,int l,int r)
{
    if(p[w].l>r||p[w].r<l)return;

    int mid=(p[w].l+p[w].r)/2;
    long double y1=calc(k,mid),y2=calc(p[w].id,mid);
    if(p[w].l>=l&&p[w].r<=r)
    {
        if(p[w].l==p[w].r)
        {
            if(y1>y2)p[w].id=k;
            return;
        }

        if(s[k].k<s[p[w].id].k)
        {
            if(y1<=y2)
                change(w*2,k,l,r);
            else
            {
                change(w*2+1,p[w].id,l,r);
                p[w].id=k;
            }
        }
        else if(s[k].k>s[p[w].id].k)
        {
            if(y1<=y2)
                change(w*2+1,k,l,r);
            else
            {
                change(w*2,p[w].id,l,r);
                p[w].id=k;
            }

        }
        else if(s[k].b>s[p[w].id].b)
        {
            p[w].id=k;
        }

        //cout<<p[w].l<<' '<<p[w].r<<' '<<p[w].id<<endl;
        return;
    }
    change(w*2,k,l,r);
    change(w*2+1,k,l,r);
}

inline void add(int x0,int y0,int x1,int y1)
{
    if(x0>x1){swap(x0,x1);swap(y0,y1);}
    len++;
    if(x0==x1){s[len].b=max(y0,y1);s[len].k=0;change(1,len,x0,x1);return;}
    s[len].k=(long double)(y1-y0)/(long double)(x1-x0);
    s[len].b=1.0*y0-s[len].k*x0;
    //cout<<x0<<' '<<y0<<' '<<x1<<' '<<y1<<endl;
    //cout<<s[len].k<<' '<<s[len].b<<endl;
    change(1,len,x0,x1);
}

int getmax(int w,int x)
{
    if(p[w].l>x||p[w].r<x||w>100000)return 0;
    //if(p[w].id==16)cout<<p[w].l<<' '<<p[w].r<<"#####\n";
    //cout<<w<<' '<<p[w].l<<' '<<p[w].r<<' '<<p[w].id<<endl; 
    int mid=(p[w].l+p[w].l)/2;
    if(p[w].l==p[w].r)return p[w].id;
    int a=getmax(w*2,x),b=getmax(w*2+1,x),c=p[w].id;
    if(b>c)swap(b,c);
    if(a>b)swap(a,b);
    if(b>c)swap(b,c);
    if(calc(a,x)>=calc(b,x)&&calc(a,x)>=calc(c,x))return a;
    if(calc(b,x)>=calc(a,x)&&calc(b,x)>=calc(c,x))return b;
    return c;
}

int main()
{
    //freopen("P4097_1.in","r",stdin);

    s[0].k=0;s[0].b=0;
    build(1,1,40000);

    bool aaa;
    int x0,y0,x1,y1,lastans=0;

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>aaa;
        if(aaa)
        {
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1+mod1)%mod1+1;
            x1=(x1+lastans-1+mod1)%mod1+1;
            y0=(y0+lastans-1+mod2)%mod2+1;
            y1=(y1+lastans-1+mod2)%mod2+1;
            add(x0,y0,x1,y1);
            //if(len==16)
            {
                //cout<<endl<<endl<<x0<<' '<<x1<<endl<<endl;
            }
        }
        else
        {
            int x;
            cin>>x;
            x=(x+lastans-1+mod1)%mod1+1;
            cout<<(lastans=getmax(1,x))<<endl;
            //printf("%d %lf %lf\n",x,calc(16,x),calc(49,x));
        }
    }
    //cout<<endl<<endl<<endl<<endl;
    return 0;
}
//0 17915