subtask0全A
subtask1WA+TLE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int N = 5e6 + 10;
const int Mod = 39989;
const double eps = 1e-9;
struct Line {
    double k, b;
    int id;
    double operator()(int x) {
        return k * x + b;
    }
};

int cmp(double x, double y) {
    if(x - y > eps) return 1;
    if(y - x > eps) return -1;
    return 0;
}
Line get(Line x, Line y, int pos) {
    if(!x.id) return y;
    if(!y.id) return x;
    if(cmp(x(pos), y(pos)) == 1) return x;
    if(cmp(x(pos), y(pos)) == -1) return y;
    return (x.id < y.id ? x : y);
}
Line val[N];
#define ls pos<<1
#define rs pos<<1|1
void update(int pos, int l, int r, Line k) {
    if(!val[pos].id) {
        val[pos] = k;
        return;
    }
    int mid = (l + r) >> 1;

    int flag = cmp(k(mid), val[pos](mid));
    int lflag = cmp(k(l), val[pos](l));
    int rflag = cmp(k(r), val[pos](r));

    if(flag == 1 || (flag == 0 && k.id < val[pos].id)) swap(k, val[pos]);
    if(l == r) return;
    if(lflag == 1 || (lflag == 0 && k.id < val[pos].id)) update(ls, l, mid, k);
    if(rflag == 1 || (rflag == 0 && k.id < val[pos].id)) update(rs, mid + 1, r, k);
}

void change(int pos, int l, int r, int ql, int qr, Line k) {
    if(ql <= l && r <= qr) {
        update(pos, l, r, k);
        return;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) change(ls, l, mid, ql, qr, k);
    if(mid + 1 <= qr) change(rs, mid + 1, r, ql, qr, k);
}

Line query(int pos, int l, int r, int qpos) {
    if(l == r) {
        return val[pos];
    }
    Line line;
    int mid = (l + r) >> 1;
    if(qpos <= mid) line = query(ls, l, mid, qpos);
    if(mid + 1 <= qpos) line = query(rs, mid + 1, r, qpos);
    return get(val[pos], line, qpos);
}

signed main() {
//	freopen("P4097_8.in","r",stdin);
    int lst = 0;
    int cnt = 0;
    int q;
    cin >> q;
    while(q--) {
        int opt;
        cin >> opt;
        if(opt == 0) {
            int x;
            cin >> x;
            x = (x + lst - 1) % Mod + 1;
            lst = query(1, 1, Mod, x).id;
            cout << lst << '\n';
        } else if(opt == 1) {
            int a1, b1, a2, b2;
            cin >> a1 >> b1 >> a2 >> b2;
            a1 = (a1 + lst - 1) % Mod + 1;
            a2 = (a2 + lst - 1) % Mod + 1;
            b1 = (b1 + lst - 1) % (1000000000) + 1;
            b2 = (b2 + lst - 1) % (1000000000) + 1;
            double k, b;
            if(a1 == a2) {
                k = 0;
                b = max(b1, b2);
            } else {
                k = 1.0 * (b1 - b2) / (a1 - a2);
                b = 1.0 * b1 - k * a1;
            }
            Line line = {k, b, ++cnt};
            change(1, 1, Mod, min(a1, a2), max(a1, a2), line);
        }
    }
    return 0;
}