QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534396#2557. Lagduongnc000AC ✓868ms211900kbC++1414.3kb2024-08-27 09:07:122024-08-27 09:07:12

Judging History

你现在查看的是最新测评结果

  • [2024-08-27 09:07:12]
  • 评测
  • 测评结果:AC
  • 用时:868ms
  • 内存:211900kb
  • [2024-08-27 09:07:12]
  • 提交

answer

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2.5e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

struct Rectangle {
    int x1, y1, x2, y2;

    friend istream & operator >> (istream &in, Rectangle &r) {
        return in >> r.x1 >> r.y1 >> r.x2 >> r.y2;
    }

    void apply(int dx, int dy) {
        x1 += dx, x2 += dx;
        y1 += dy, y2 += dy;
    }
} a[mxN];

struct Op {
    int x, y, val1, val2;
    Op(int x, int y, int val1, int val2) : x(x), y(y), val1(val1), val2(val2) {}
};

struct Query {
    int x, y, idx;

    Query() {}
    Query(int x, int y, int idx) : x(x), y(y), idx(idx) {}
};

struct FenwickTree {
    struct node {
        i64 a, b; //ax + b;

        node() : a(0), b(0) {}
        node(i64 a, i64 b) : a(a), b(b) {}
    
        node operator + (node rhs) {
            return node(a + rhs.a, b + rhs.b);
        }

        node operator - (node rhs) {
            return node(a - rhs.a, b - rhs.b);
        }

        i64 eval(i64 x) {
            return a * x + b;
        }
    };

    int n;
    vector<node> data;

    FenwickTree(int n) : n(n), data(n + 1) {}

    void reset() {
        data.assign(n + 1, node());
    }

    void update(int idx, node val) {
        if (idx < 1) return;
        // cout << idx << " " << val.a << " " << val.b << endl;
        while (idx <= n) {
            data[idx] = data[idx] + val;
            // cout << idx << " " << data[idx].a << " " << data[idx].b << endl;
            idx += idx & -idx;
        }
    }

    node get(int idx) {
        // cout << "get: " << idx << endl;
        node res;
        while (idx) {
            res = res + data[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    node get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

int n, m, q;
vector<Op> wte, stn, nwtse, setnw, swtne, rnwtse, rsetnw;
vector<Query> queries;
int ofs_x, ofs_y;
i64 ans[mxN];

// pretty copable

void add_wte(int x, int y, int val, int d) {
    x += ofs_x, y += ofs_y;
    wte.emplace_back(x, y, val, val * (-x + 1));
    wte.emplace_back(x + d, y, -val, val * (x + d - 1));
    // cout << x << " " << y << ": " << val << " " << val * (-x + 1) << endl;
    // cout << x + d << " " << y << ": " << -val << " " << val * (x + d - 1) << endl;
}

void west_to_east() {
    sort(all(wte), [&](Op A, Op B) {
        return A.x < B.x;
    });
    sort(all(queries), [&](Query A, Query B) {
        return A.x < B.x;
    });

    FenwickTree fenw(mxN - 5);
    int ptr = 0, ptrq = 0;
    for (int i = 1; i <= mxN - 5; ++i) {
        // cout << i << endl;
        while (ptr < isz(wte) && wte[ptr].x == i) {
            fenw.update(wte[ptr].y, {wte[ptr].val1, wte[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(queries) && queries[ptrq].x == i) {
            ans[queries[ptrq].idx] += fenw.get(queries[ptrq].y).eval(i);
            ++ptrq;
        }
    }
}

void add_stn(int x, int y, int val, int d) {
    x += ofs_x, y += ofs_y;
    stn.emplace_back(x, y, val, val * (-y + 1));
    stn.emplace_back(x, y + d, -val, val * (y + d - 1));
}

void south_to_north() {
    sort(all(stn), [&](Op A, Op B) {
        return A.y < B.y;
    });
    sort(all(queries), [&](Query A, Query B) {
        return A.y < B.y;
    });

    FenwickTree fenw(mxN - 5);
    int ptr = 0, ptrq = 0;
    for (int i = 1; i <= mxN - 5; ++i) {
        // cout << i << endl;
        while (ptr < isz(stn) && stn[ptr].y == i) {
            fenw.update(stn[ptr].x, {stn[ptr].val1, stn[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(queries) && queries[ptrq].y == i) {
            ans[queries[ptrq].idx] += fenw.get(queries[ptrq].x).eval(i);
            ++ptrq;
        }
    }
}

// bruh bruh lmao

void add_nwtse(int x, int y, int val, int d) {
    x += ofs_x, y += ofs_y;
    nwtse.emplace_back(x, y, val, val * (-y + 1));
    nwtse.emplace_back(x + d, y + d, -val, val * (y + d - 1));
    // cout << x << " " << y << " " << val << " " << val * (-y + 1) << endl;
    // cout << x + d << " " << y + d << " " << -val << " " << val * (y + d - 1) << endl;
}

void northwest_to_southeast() {
    sort(all(nwtse), [&](Op A, Op B) {
        return A.x - A.y < B.x - B.y;
    });
    sort(all(queries), [&](Query A, Query B) {
        return A.x - A.y < B.x - B.y;
    });

    FenwickTree fenw(mxN - 5);
    int ptr = 0, ptrq = 0;
    for (int i = 1 - (mxN - 5); i <= (mxN - 5) - 1; ++i) {
        // cout << i << endl;
        while (ptr < isz(nwtse) && nwtse[ptr].x - nwtse[ptr].y == i) {
            fenw.update(nwtse[ptr].y, {nwtse[ptr].val1, nwtse[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(queries) && queries[ptrq].x - queries[ptrq].y == i) {
            ans[queries[ptrq].idx] += fenw.get(queries[ptrq].y).eval(queries[ptrq].y);
            ++ptrq;
        }
    }
}

void add_setnw(int x, int y, int val, int d) {
    x += ofs_x, y += ofs_y;
    setnw.emplace_back(x, y, val, val * (-x + 1));
    setnw.emplace_back(x + d, y + d, -val, val * (x + d - 1));
    // cout << "setnw: " << x << " " << y << " " << val << " " << val * (-x + 1) << endl;
    // cout << "setnw: " << x + d << " " << y + d << " " << -val << " " << val * (x + d - 1) << endl;
}

void southeast_to_northwest() {
    sort(all(setnw), [&](Op A, Op B) {
        return A.x - A.y > B.x - B.y;
    });
    sort(all(queries), [&](Query A, Query B) {
        return A.x - A.y > B.x - B.y;
    });

    FenwickTree fenw(mxN - 5);
    int ptr = 0, ptrq = 0;
    for (int i = (mxN - 5) - 1; i >= 1 - (mxN - 5); --i) {
        // cout << i << endl;
        while (ptr < isz(setnw) && setnw[ptr].x - setnw[ptr].y == i) {
            fenw.update(setnw[ptr].x, {setnw[ptr].val1, setnw[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(queries) && queries[ptrq].x - (queries[ptrq].y - 1) == i) {
            ans[queries[ptrq].idx] += fenw.get(queries[ptrq].x).eval(queries[ptrq].x);
            ++ptrq;
        }
    }
}

pair<int, int> rotate_point(int x, int y) {
    // assert(y > 0 && 250000 - x + 1 > 0);
    return {y, 250000 - x + 1};
}

void add_rnwtse(int x, int y, int val, int d) {
    // if (x > mxN - 5 || y > mxN - 5) return;
    tie(x, y) = rotate_point(x, y);
    x += ofs_x, y += ofs_y;
    rnwtse.emplace_back(x, y, val, val * (-y + 1));
    rnwtse.emplace_back(x + d, y + d, -val, val * (y + d - 1));
    // cout << "rnwtse: " << x << " " << y << " " << val << " " << val * (-y + 1) << "\n";
    // cout << "rnwtse: " << x + d << " " << y + d << " " << -val << " " << val * (y + d - 1) << endl;
    // cout << x << " " << y << " " << val << endl;
}

void rotate_northwest_to_southeast() {
    sort(all(rnwtse), [&](Op A, Op B) {
        return A.x - A.y < B.x - B.y;
    });
    vector<Query> rqueries;
    for (auto [x, y, idx] : queries) {
        tie(x, y) = rotate_point(x, y);
        rqueries.emplace_back(x, mxN - 5, idx);
        rqueries.emplace_back(x, y - 1, -idx);
        // cout << x << " " << mxN - 5 << " " << y - 1 << endl;
    }
    sort(all(rqueries), [&](Query A, Query B) {
        return A.x - A.y < B.x - B.y;
    });

    FenwickTree fenw(mxN + 10);
    int ptr = 0, ptrq = 0;
    for (int i = -mxN; i <= mxN; ++i) {
        // cout << i << endl;
        while (ptr < isz(rnwtse) && rnwtse[ptr].x - rnwtse[ptr].y == i) {
            fenw.update(rnwtse[ptr].y + 1, {rnwtse[ptr].val1, rnwtse[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(rqueries) && rqueries[ptrq].x - rqueries[ptrq].y == i) {
            int cidx = rqueries[ptrq].idx;
            ans[abs(cidx)] += fenw.get(rqueries[ptrq].y + 1).eval(rqueries[ptrq].y) * (cidx > 0 ? 1 : -1);
            ++ptrq;
        }
    }
}

void add_rsetnw(int x, int y, int val, int d) {
    // if (x > mxN - 5 || y > mxN - 5) return;
    tie(x, y) = rotate_point(x, y);
    x += ofs_x, y += ofs_y;
    rsetnw.emplace_back(x, y, val, val * (-x + 1));
    rsetnw.emplace_back(x + d, y + d, -val, val * (x + d - 1));
    // cout << "rsetnw: " << x << " " << y << " " << val << " " << val * (-x + 1) << endl;
    // cout << "rsetnw: " << x + d << " " << y + d << " " << -val << " " << val * (x + d - 1) << endl;
}

void rotate_southeast_to_northwest() {
    sort(all(rsetnw), [&](Op A, Op B) {
        return A.x - A.y > B.x - B.y;
    });
    vector<Query> rqueries;
    for (auto [x, y, idx] : queries) {
        tie(x, y) = rotate_point(x, y);
        // cout << x << " " << y << endl;
        rqueries.emplace_back(x, mxN - 5, idx);
        rqueries.emplace_back(x, y - 1, -idx);
    }
    sort(all(rqueries), [&](Query A, Query B) {
        return A.x - A.y > B.x - B.y;
    });

    FenwickTree fenw(mxN);
    int ptr = 0, ptrq = 0;
    for (int i = mxN; i >= -mxN; --i) {
        // cout << i << endl;
        while (ptr < isz(rsetnw) && rsetnw[ptr].x - rsetnw[ptr].y == i) {
            fenw.update(rsetnw[ptr].x, {rsetnw[ptr].val1, rsetnw[ptr].val2});
            ++ptr;
        }
        // cout << endl;
        while (ptrq < isz(rqueries) && rqueries[ptrq].x - (rqueries[ptrq].y - 1) == i) {
            int cidx = rqueries[ptrq].idx;
            ans[abs(cidx)] += fenw.get(rqueries[ptrq].x).eval(rqueries[ptrq].x) * (cidx > 0 ? 1 : -1);
            ++ptrq;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        ofs_x = 0, ofs_y = 0;
        add_wte(a[i].x1, a[i].y1, 1, 1);
        add_wte(a[i].x2 + 1, a[i].y1, -1, 1);
        add_wte(a[i].x1, a[i].y2 + 1, -1, 1);
        add_wte(a[i].x2 + 1, a[i].y2 + 1, 1, 1);
    }

    for (int i = 1; i <= m; ++i) {
        int tp, idx, d;
        cin >> tp >> idx >> d;
        if (tp == 0) { // (1, 0)
            ofs_x = 1, ofs_y = 0;
            add_wte(a[idx].x1, a[idx].y1, 1, d);
            add_wte(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_wte(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_wte(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            a[idx].apply(d, 0);
        }
        else if (tp == 1) { // (1, 1)
            ofs_x = 1, ofs_y = 1;
            add_nwtse(a[idx].x1, a[idx].y1, 1, d);
            add_nwtse(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_nwtse(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_nwtse(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            add_setnw(a[idx].x1, a[idx].y1, 1, d);
            add_setnw(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_setnw(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_setnw(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            a[idx].apply(d, d);
        }
        else if (tp == 2) { // (0, 1)
            ofs_x = 0, ofs_y = 1;
            add_stn(a[idx].x1, a[idx].y1, 1, d);
            add_stn(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_stn(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_stn(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            a[idx].apply(0, d);
        }
        else if (tp == 3) { // (-1, 1)
            ofs_x = 1, ofs_y = 1;
            add_rnwtse(a[idx].x1, a[idx].y1, 1, d);
            add_rnwtse(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_rnwtse(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_rnwtse(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            add_rsetnw(a[idx].x1, a[idx].y1, 1, d);
            add_rsetnw(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_rsetnw(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_rsetnw(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            a[idx].apply(-d, d);
        }
        else if (tp == 4) { // (-1, 0)
            a[idx].apply(-d, 0);
            ofs_x = 0, ofs_y = 0;
            add_wte(a[idx].x1, a[idx].y1, 1, d);
            add_wte(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_wte(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_wte(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            // cout << endl;
        }
        else if (tp == 5) { // (-1, -1)
            a[idx].apply(-d, -d);
            ofs_x = 0, ofs_y = 0;
            add_nwtse(a[idx].x1, a[idx].y1, 1, d);
            add_nwtse(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_nwtse(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_nwtse(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            add_setnw(a[idx].x1, a[idx].y1, 1, d);
            add_setnw(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_setnw(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_setnw(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
        }
        else if (tp == 6) { // (0, -1)
            a[idx].apply(0, -d);
            ofs_x = 0, ofs_y = 0;
            add_stn(a[idx].x1, a[idx].y1, 1, d);
            add_stn(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_stn(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_stn(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
        }
        else { // (1, -1)
            a[idx].apply(d, -d);
            ofs_x = 0, ofs_y = 0;
            add_rnwtse(a[idx].x1, a[idx].y1, 1, d);
            add_rnwtse(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_rnwtse(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_rnwtse(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
            add_rsetnw(a[idx].x1, a[idx].y1, 1, d);
            add_rsetnw(a[idx].x2 + 1, a[idx].y1, -1, d);
            add_rsetnw(a[idx].x1, a[idx].y2 + 1, -1, d);
            add_rsetnw(a[idx].x2 + 1, a[idx].y2 + 1, 1, d);
        }
    }

    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        queries.emplace_back(x, y, i);
    }

    west_to_east();
    south_to_north();
    northwest_to_southeast();
    southeast_to_northwest();
    rotate_northwest_to_southeast();
    rotate_southeast_to_northwest();

    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 9776kb

input:

1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2

output:

0
2
1

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 9604kb

input:

2 0 3
3 3 7 7
4 4 6 6
5 5
3 7
8 8

output:

2
1
0

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 9612kb

input:

10 10 10
45066 44774 106240 221436
22774 27403 164972 196292
35788 27798 154149 71660
8624 14258 47662 205040
9479 49585 89304 70902
24893 32999 218506 41529
27023 49837 175362 52663
21858 40287 135949 41957
12106 48095 80386 230759
41236 37600 169685 129218
7 6 5009
4 5 2577
0 5 37640
3 10 34168
1 ...

output:

0
8229
0
0
0
112970
3975
33943
95614
0

result:

ok 10 tokens

Test #4:

score: 0
Accepted
time: 787ms
memory: 209244kb

input:

249983 250000 250000
111104 145198 111104 145198
144828 160567 144828 160567
61230 137274 61230 137274
101294 65087 101294 65087
71606 235076 71606 235076
112838 56089 112838 56089
215472 230660 215472 230660
203596 175791 203596 175791
51286 6725 51286 6725
35435 139352 35435 139352
124096 225262 1...

output:

0
0
0
2
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
2
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
0
2
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
0
2
0
2
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
...

result:

ok 250000 tokens

Test #5:

score: 0
Accepted
time: 788ms
memory: 203076kb

input:

249984 250000 250000
48723 142920 48723 142920
42846 7020 42846 7020
168740 16539 168740 16539
162811 246695 162811 246695
90832 70471 90832 70471
164946 108115 164946 108115
52710 170953 52710 170953
152081 149387 152081 149387
180801 190447 180801 190447
248549 12446 248549 12446
84288 41045 84288...

output:

1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
2
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
...

result:

ok 250000 tokens

Test #6:

score: 0
Accepted
time: 780ms
memory: 203096kb

input:

249985 250000 250000
51750 114835 51750 114835
223568 70768 223568 70768
52057 80396 52057 80396
7032 19520 7032 19520
84250 130058 84250 130058
223951 225549 223951 225549
172651 169758 172651 169758
67862 83384 67862 83384
244909 98361 244909 98361
244367 109731 244367 109731
77184 99932 77184 999...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
3
1
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
2
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 250000 tokens

Test #7:

score: 0
Accepted
time: 812ms
memory: 207152kb

input:

249986 250000 250000
213561 145261 213561 145261
154290 108709 154290 108709
126862 118445 126862 118445
101253 201128 101253 201128
103476 5053 103476 5053
26060 60278 26060 60278
9889 77347 9889 77347
233643 241573 233643 241573
91720 38979 91720 38979
207480 15528 207480 15528
70080 191523 70080 ...

output:

0
0
0
0
2
0
1
0
0
0
0
1
0
0
0
1
0
0
1
2
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
2
1
1
0
0
1
0
0
0
0
0
0
0
1
2
1
0
0
1
1
0
1
1
0
2
0
2
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
2
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
1
...

result:

ok 250000 tokens

Test #8:

score: 0
Accepted
time: 793ms
memory: 208188kb

input:

249987 250000 250000
216588 117176 216588 117176
85013 172457 85013 172457
234372 215006 234372 215006
162771 191248 162771 191248
122703 64640 122703 64640
78169 119200 78169 119200
64422 43448 64422 43448
207936 149761 207936 149761
188532 196893 188532 196893
170594 80109 170594 80109
30272 33113...

output:

0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
2
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
2
1
2
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
2
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
3
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
2
0
0
1
0
0
0
0
...

result:

ok 250000 tokens

Test #9:

score: 0
Accepted
time: 790ms
memory: 203484kb

input:

249988 250000 250000
128399 114898 128399 114898
233031 18910 233031 18910
91881 28863 91881 28863
6992 155561 6992 155561
83417 150035 83417 150035
162982 236634 162982 236634
184364 16444 184364 16444
123717 83758 123717 83758
35343 163319 35343 163319
133708 210098 133708 210098
23168 92000 23168...

output:

0
1
0
2
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
2
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
...

result:

ok 250000 tokens

Test #10:

score: 0
Accepted
time: 766ms
memory: 203596kb

input:

249989 250000 250000
131426 119516 131426 119516
131049 56850 131049 56850
7902 92720 7902 92720
101213 119873 101213 119873
102643 242326 102643 242326
189282 38660 189282 38660
21601 232545 21601 232545
72202 241947 72202 241947
157963 71233 157963 71233
155334 50488 155334 50488
16064 183591 1606...

output:

0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
1
0
0
0
0
0
0
0
1
2
0
1
0
0
0
0
0
...

result:

ok 250000 tokens

Test #11:

score: 0
Accepted
time: 773ms
memory: 207540kb

input:

249990 250000 250000
12449 137387 12449 137387
25171 43925 25171 43925
221610 122926 221610 122926
236803 81988 236803 81988
203229 164505 203229 164505
76605 42532 76605 42532
99306 77885 99306 77885
138833 57908 138833 57908
227906 216730 227906 216730
15009 15462 15009 15462
238262 23617 238262 2...

output:

0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
2
1
0
0
0
0
0
1
0
0
1
...

result:

ok 250000 tokens

Test #12:

score: 0
Accepted
time: 742ms
memory: 206244kb

input:

249993 250000 250000
114906 104746 114906 104746
34633 242067 34633 242067
37242 104097 37242 104097
236762 733 236762 733
235099 217187 235099 217187
22531 53617 22531 53617
111019 207275 111019 207275
194688 90986 194688 90986
235636 5880 235636 5880
180158 83125 180158 83125
184246 15686 184246 1...

output:

1
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
2
0
1
0
0
1
0
1
0
2
0
0
0
0
0
1
0
0
0
1
3
0
0
0
1
1
1
1
0
0
0
1
0
0
0
1
1
0
0
2
1
0
1
1
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
...

result:

ok 250000 tokens

Test #13:

score: 0
Accepted
time: 803ms
memory: 203688kb

input:

249993 250000 250000
245147 203610 245167 203635
96069 88680 96087 88701
208532 32796 208541 32806
224771 19169 224788 19192
212693 9981 212710 10005
227566 102954 227581 102965
198009 36247 198020 36249
80552 91346 80571 91353
117917 124370 117920 124377
14126 210410 14139 210426
99372 35642 99385 ...

output:

80
19
25
12
15
2
22
17
33
14
74
2
7
69
46
1
33
36
63
59
30
4
62
9
34
19
43
0
24
13
18
50
105
4
33
43
36
10
50
71
94
52
51
14
28
24
47
42
20
39
38
31
22
29
15
34
21
36
53
7
18
39
87
3
18
50
81
0
26
43
42
45
61
42
37
15
86
24
40
27
32
12
87
25
30
1
31
26
2
41
41
17
52
28
15
66
45
0
79
29
25
42
22
14
2...

result:

ok 250000 tokens

Test #14:

score: 0
Accepted
time: 851ms
memory: 205716kb

input:

249993 250000 250000
74489 50119 75567 51423
33810 129242 34853 129566
16370 218492 16999 218538
237538 142013 238813 142182
213223 68463 213817 69010
245861 71168 247969 71978
148267 227853 150637 228279
100696 65744 100870 67399
215581 221256 216761 222654
159117 17671 161066 18569
43172 54571 437...

output:

379660
465536
286893
423535
138874
204685
240535
209347
380866
436718
379123
455907
445418
469774
399027
213008
405954
525966
395504
486000
384133
316918
339239
446639
9172
418549
478140
367486
14245
240545
491915
386884
170399
362704
392916
282263
300705
198454
297791
227586
477152
139315
387241
22...

result:

ok 250000 tokens

Test #15:

score: 0
Accepted
time: 825ms
memory: 207252kb

input:

249993 250000 250000
71 392 161678 128221
879 54 190106 229069
605 10 168517 31453
823 698 20984 238076
699 570 56295 181515
616 904 122099 121313
78 463 98790 177483
337 965 232169 178187
858 332 46907 217033
342 300 164876 121474
717 496 192949 232404
836 973 27971 248785
812 702 212543 249621
192...

output:

952098177
899011428
1152307896
982456203
341594315
125948357
106047830
529196406
1008619247
1949262541
622920162
1771142245
1353424172
1044581020
408599281
6311578
1639208651
64922968
1859451740
1485954636
226897163
927258489
38740400
28553077
2088931598
1619496744
750043126
185116490
267211840
7853...

result:

ok 250000 tokens

Test #16:

score: 0
Accepted
time: 803ms
memory: 207148kb

input:

249994 250000 250000
85229 142068 85229 142068
182651 55815 182651 55815
144752 167954 144752 167954
80984 208150 80984 208150
221622 26774 221622 26774
74640 105643 74640 105643
230960 140672 230960 140672
110469 249174 110469 249174
140960 222306 140960 222306
143272 180410 143272 180410
177142 10...

output:

0
0
0
0
1
2
0
0
0
0
0
0
2
0
0
0
0
2
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
0
3
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
2
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
0
0
2
0
0
0
0
0
0
0
0
...

result:

ok 250000 tokens

Test #17:

score: 0
Accepted
time: 779ms
memory: 203180kb

input:

249994 250000 250000
44173 135916 44175 135934
139295 135630 139317 135631
222348 249320 222373 249322
81965 99598 81979 99601
24336 7830 24341 7843
243493 48882 243497 48896
173830 188008 173846 188033
82268 104483 82287 104503
26401 169075 26417 169077
243795 67125 243803 67150
173626 139040 17363...

output:

82
13
36
107
25
35
56
54
13
77
18
55
56
27
67
100
55
133
24
33
68
14
7
51
60
49
41
30
41
26
34
14
37
1
58
19
35
14
67
37
47
94
76
93
74
66
43
39
71
40
40
37
41
40
19
28
18
27
48
53
37
53
56
105
6
27
30
4
30
36
26
16
43
58
37
34
54
48
22
32
2
1
17
23
10
22
51
14
4
36
51
9
49
56
68
14
30
59
6
44
0
40
...

result:

ok 250000 tokens

Test #18:

score: 0
Accepted
time: 849ms
memory: 205252kb

input:

249994 250000 250000
165902 87567 166820 89290
110404 144303 111829 146786
85893 142498 87274 144076
152947 171035 154155 171803
216737 130536 219064 131807
133215 148807 133834 150027
96838 114650 98367 115326
234690 77319 237187 79130
128102 170897 130586 173330
217755 230913 218050 233397
138286 ...

output:

474283
216140
460070
276920
71291
231757
87340
201546
308318
176776
357877
247615
222196
456554
248889
477171
242250
455273
378803
332013
277416
214478
406217
167924
285712
433554
438554
407117
326545
458251
361717
189172
538669
306685
288320
234196
163838
326251
240658
403035
352253
396277
125429
4...

result:

ok 250000 tokens

Test #19:

score: 0
Accepted
time: 841ms
memory: 208588kb

input:

249994 250000 250000
324 389 113440 228437
379 66 232887 52117
533 990 78376 246729
277 192 61915 208450
106 968 174205 141138
144 259 168660 220978
693 850 77483 229851
828 19 244386 54007
717 55 175674 126695
603 258 164012 88481
140 391 18547 80679
293 466 58297 236922
484 531 86156 66615
764 897...

output:

746303107
1393634445
1451157310
2137644357
21814190
378434671
218116599
108514100
1825465916
171375957
937901368
330385537
1241746376
1289457891
712311402
1454224089
1854036697
1559953200
10501645
1400601047
637334801
213846001
314647701
41915032
880455089
1064838013
1936288400
189483021
1733886058
...

result:

ok 250000 tokens

Test #20:

score: 0
Accepted
time: 785ms
memory: 205864kb

input:

249995 250000 250000
29744 139791 29744 139791
80670 126460 80670 126460
28069 14515 28069 14515
142501 172462 142501 172462
215040 86361 215040 86361
126749 223076 126749 223076
68198 80965 68198 80965
58954 183171 58954 183171
205067 130220 205067 130220
106385 53504 106385 53504
195846 166163 195...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
2
1
0
1
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
0
2
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
2
1
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
...

result:

ok 250000 tokens

Test #21:

score: 0
Accepted
time: 820ms
memory: 205144kb

input:

249995 250000 250000
42800 215043 42809 215059
35700 79425 35704 79445
133010 16268 133033 16292
145467 170915 145471 170925
232776 14791 232776 14796
103486 150743 103492 150749
46497 192948 46514 192966
83984 64841 84007 64856
28926 66959 28929 66974
232600 79773 232617 79774
153838 45243 153844 4...

output:

23
11
16
34
97
41
78
0
38
96
30
31
19
29
29
48
15
15
58
30
25
29
45
20
39
34
12
25
39
58
14
87
15
35
70
37
26
36
9
4
15
67
57
6
4
15
39
30
18
18
16
6
53
51
37
11
56
15
16
55
33
35
95
1
17
21
69
87
11
41
25
13
29
45
61
18
80
0
31
7
91
44
53
17
51
68
34
43
0
93
48
10
24
40
61
28
32
0
27
48
20
24
27
36...

result:

ok 250000 tokens

Test #22:

score: 0
Accepted
time: 833ms
memory: 205108kb

input:

249995 250000 250000
209408 104411 210170 106565
139090 59567 140894 61703
223929 66504 226061 67114
136868 100262 138002 101624
120455 44905 122002 46908
247466 157934 249106 159579
76694 101243 77390 102168
21388 188690 23715 190644
40623 199730 41906 200696
197202 96858 198344 98427
6504 211484 7...

output:

442435
308450
260856
248891
420140
207991
334110
529104
84637
360781
475214
510221
416183
487817
438141
414317
188556
235676
247428
455410
322913
482884
454373
344015
464936
6909
270039
359562
410417
243595
466962
227315
468035
330009
256666
374625
258438
315342
429359
444920
211834
327303
370126
35...

result:

ok 250000 tokens

Test #23:

score: 0
Accepted
time: 828ms
memory: 205124kb

input:

249995 250000 250000
280 491 127513 28804
366 782 225202 11309
164 163 236940 171900
219 173 154288 241919
409 765 44010 151113
479 805 165076 72833
899 941 4815 180017
319 178 57555 242542
872 586 169298 172604
376 113 225270 117994
372 286 93956 228907
46 470 202481 237225
860 873 209473 246686
82...

output:

1957004167
999353948
992177313
703006947
333888389
1891988065
373831726
1476610249
166691155
1206838743
2096932628
1700428851
513276952
262834362
2129977644
937755363
6896836
1841438766
751934729
356128859
1407596329
1582903027
1538869539
534208662
34125097
1816865110
1873501297
61849224
140746400
1...

result:

ok 250000 tokens

Test #24:

score: 0
Accepted
time: 773ms
memory: 205004kb

input:

249996 250000 250000
67 137513 67 137513
44096 190208 44096 190208
135578 78372 135578 78372
236722 162583 236722 162583
234266 204460 234266 204460
185753 90510 185753 90510
122731 53962 122731 53962
543 91360 543 91360
51879 70838 51879 70838
69499 150789 69499 150789
188742 199242 188742 199242
9...

output:

0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
0
2
0
1
0
0
2
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
2
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
...

result:

ok 250000 tokens

Test #25:

score: 0
Accepted
time: 775ms
memory: 205448kb

input:

249996 250000 250000
238623 147350 238640 147360
26147 220417 26151 220421
146826 85971 146834 85991
158593 1370 158594 1390
44419 12640 44429 12656
213454 96670 213467 96679
178252 241555 178270 241565
241634 181132 241649 181134
187385 111664 187408 111671
212294 186463 212305 186469
124938 148641...

output:

53
32
2
0
43
54
34
20
6
81
22
25
20
7
26
78
5
29
36
55
11
19
51
64
0
14
28
56
74
86
22
13
72
25
19
22
22
46
30
22
71
3
30
83
13
0
29
13
78
94
36
101
0
20
9
10
57
3
93
45
41
23
2
12
39
51
10
25
46
22
37
28
39
5
129
13
35
33
38
58
7
19
103
87
69
26
41
33
63
45
26
23
70
27
8
68
51
61
53
3
27
0
21
39
1
...

result:

ok 250000 tokens

Test #26:

score: 0
Accepted
time: 813ms
memory: 205156kb

input:

249996 250000 250000
53322 42062 53929 42146
67980 222332 70155 224122
45953 238010 46343 240144
72882 129284 73949 131245
44776 59070 45555 59297
214013 235574 214164 237632
25265 87835 27621 89017
55585 152357 57738 154463
121452 1667 121538 3672
8341 131112 10326 131758
22426 140247 24850 141318
...

output:

318143
198909
469588
353126
302138
330214
458426
419266
238411
452636
355402
517882
171608
258750
406799
208021
321284
380243
293280
47366
142391
285204
228668
470805
478586
142624
352050
118794
410772
321005
389771
419960
250241
363068
348122
192577
381507
387532
358643
204879
501594
355616
159613
...

result:

ok 250000 tokens

Test #27:

score: 0
Accepted
time: 827ms
memory: 205088kb

input:

249996 250000 250000
828 784 79570 27410
162 498 19279 32110
388 631 147096 137664
866 667 196412 77854
816 162 162920 245174
7 351 149028 161034
514 137 180556 231194
106 528 57412 182266
731 604 49064 133514
45 775 172861 34752
91 886 168852 77887
503 259 233807 237313
532 702 32133 63680
99 975 1...

output:

1470364062
1505353372
1433870272
81603440
1504254176
62678066
1741317866
1035937214
1688170608
1786314948
6083602
1006923391
1924439021
1434434839
4028658
1757182043
1525843687
862495005
1200595784
1099006169
367871
1435847037
1413111292
528916435
390875008
1137503860
515566109
1239379817
1231982481...

result:

ok 250000 tokens

Test #28:

score: 0
Accepted
time: 771ms
memory: 205036kb

input:

249997 250000 250000
194582 109428 194582 109428
192114 3957 192114 3957
25792 142229 25792 142229
113647 126895 113647 126895
3492 14047 3492 14047
20566 142536 20566 142536
242673 20062 242673 20062
199028 249549 199028 249549
148690 228752 148690 228752
91125 56586 91125 56586
148934 40833 148934...

output:

0
0
1
0
1
0
0
2
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
2
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 250000 tokens

Test #29:

score: 0
Accepted
time: 827ms
memory: 206160kb

input:

249997 250000 250000
237249 123323 237270 123334
69373 164213 69373 164227
57488 155673 57494 155688
15787 175841 15812 175841
96926 19601 96949 19606
176602 51710 176604 51710
7252 152453 7272 152460
140196 194269 140215 194284
189911 9548 189917 9568
191988 95957 192008 95961
105150 54844 105174 5...

output:

58
2
26
12
74
4
35
76
51
11
40
29
29
37
3
8
26
53
49
41
11
50
7
10
28
39
22
8
47
3
51
45
26
20
2
13
28
0
50
44
0
28
30
1
43
32
38
131
15
34
36
0
53
3
34
69
6
76
29
31
44
16
59
12
7
59
12
42
31
91
47
14
45
46
29
1
16
61
32
12
44
64
1
45
100
14
11
11
46
13
3
44
13
55
64
10
16
90
46
48
51
76
35
34
23
1...

result:

ok 250000 tokens

Test #30:

score: 0
Accepted
time: 842ms
memory: 206212kb

input:

249997 250000 250000
96827 206610 97278 207113
244370 58404 244426 59856
183988 162016 185126 163182
135995 10603 136980 10661
195994 121142 196001 122097
101367 244701 102539 247169
53028 222132 54559 223560
189579 184536 191554 186794
33973 30500 35359 31035
87584 244557 87923 246785
117540 21101 ...

output:

326284
474410
374646
437659
338096
141591
341812
471695
376109
388633
347137
245483
344517
305142
381934
415264
433659
414686
212030
404019
385133
166696
336914
390387
166188
190987
374656
233584
252396
429074
403435
391645
411723
448675
197150
115767
278014
425620
447540
239034
333885
188826
289292...

result:

ok 250000 tokens

Test #31:

score: 0
Accepted
time: 835ms
memory: 205412kb

input:

249997 250000 250000
784 885 93644 127730
662 510 249452 41551
211 316 56851 63347
320 160 186391 99179
927 855 83485 205091
343 898 145444 210938
425 228 158546 232313
597 687 120582 8238
886 327 229080 229567
114 437 183462 1463
515 77 244452 225411
960 456 67085 175201
909 235 155452 242941
670 3...

output:

1641463318
1289147609
634643968
1366076829
800329331
863945184
7067328
33455950
159992348
5588216
1838271614
157017318
6253037
1486551151
258181345
488717689
493293852
516971587
1589646495
183015913
611948698
507150921
1026680647
1939885880
1457884715
250737645
1742471771
1085977552
988243972
142939...

result:

ok 250000 tokens

Test #32:

score: 0
Accepted
time: 773ms
memory: 207000kb

input:

249998 250000 250000
164905 139854 164905 139854
122836 41897 122836 41897
100597 21494 100597 21494
175164 91207 175164 91207
246910 106338 246910 106338
72675 9970 72675 9970
79910 210355 79910 210355
82105 183545 82105 183545
245502 195178 245502 195178
21535 121167 21535 121167
109126 99720 1091...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
2
2
0
1
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
2
1
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
2
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
...

result:

ok 250000 tokens

Test #33:

score: 0
Accepted
time: 824ms
memory: 206260kb

input:

249998 250000 250000
183097 149671 183103 149676
59820 108008 59820 108029
218125 69443 218143 69454
79288 247159 79302 247174
158544 173383 158559 173399
183416 100792 183425 100814
129895 157392 129912 157395
141912 163739 141931 163741
201548 54253 201567 54268
180793 55826 180808 55839
179404 15...

output:

19
38
43
75
23
56
32
15
70
29
13
28
12
33
42
50
28
0
31
1
54
17
62
60
13
9
81
0
0
48
43
2
74
41
15
96
30
55
0
24
2
37
53
47
38
42
50
15
18
25
23
52
34
37
5
5
15
21
48
26
2
7
38
26
53
0
28
50
44
35
61
21
59
33
23
17
35
19
10
130
36
64
27
41
25
17
37
48
39
12
14
14
88
3
45
10
27
5
33
8
30
5
40
12
13
6...

result:

ok 250000 tokens

Test #34:

score: 0
Accepted
time: 853ms
memory: 203680kb

input:

249998 250000 250000
188241 144262 188540 145196
173260 73464 173699 74570
153716 86021 155609 86218
72009 187329 72927 187978
99711 35511 101439 37186
67914 154032 70103 154412
201191 108928 201889 110605
155265 48407 157066 50808
46289 227641 46478 229210
146222 31311 147400 32616
33666 49660 3395...

output:

105236
271979
350758
471670
321119
196092
113435
378067
260659
229155
356579
223203
502495
401839
446193
452713
246615
238042
292027
443918
384987
354013
366600
392036
146650
294981
302749
453148
230730
150844
400739
310241
156839
202987
317884
317609
165481
288143
221961
172835
205445
437313
363013...

result:

ok 250000 tokens

Test #35:

score: 0
Accepted
time: 836ms
memory: 205816kb

input:

249998 250000 250000
229 690 242645 125848
457 418 43527 62543
139 785 227368 29112
967 950 30467 133458
526 845 150634 101697
574 740 130099 50433
144 423 85390 35488
793 742 234410 196669
745 154 171456 88380
783 291 245615 30976
42 868 70155 74582
417 949 160020 226946
285 577 28769 174010
538 35...

output:

51790289
217143262
7561936
1344166636
80877961
301885404
1201620768
1142726162
1224190891
1609709827
1245387522
709244168
1810935278
1217644241
145662995
2135671102
706038956
1311299695
313422559
1895972424
919546372
1019703695
1522816837
145421372
1435332882
892142888
580162561
1809186445
172120549...

result:

ok 250000 tokens

Test #36:

score: 0
Accepted
time: 791ms
memory: 211900kb

input:

249999 250000 250000
109420 111769 109420 111769
20854 138350 20854 138350
233914 85351 233914 85351
19385 81328 19385 81328
16136 224437 16136 224437
124784 94699 124784 94699
167148 176456 167148 176456
56398 124438 56398 124438
92314 103092 92314 103092
17352 1157 17352 1157
134726 191310 134726 ...

output:

0
0
0
0
2
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
1
0
0
1
0
2
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
2
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
...

result:

ok 250000 tokens

Test #37:

score: 0
Accepted
time: 828ms
memory: 207664kb

input:

249999 250000 250000
34903 228798 34913 228805
206200 154958 206208 154963
85120 242299 85127 242306
92415 77613 92426 77638
117009 24411 117034 24433
52521 46719 52544 46740
105716 205999 105738 206021
196408 176877 196426 176892
110032 202112 110046 202114
160487 215295 160489 215310
159616 114820...

output:

50
12
72
27
28
29
95
45
15
11
43
37
27
0
80
8
10
0
21
41
0
35
11
66
29
42
29
50
46
21
68
93
26
0
12
12
10
108
20
39
17
29
67
0
64
0
64
2
47
27
0
19
56
39
49
78
13
55
21
85
71
20
32
58
35
44
22
50
58
63
67
2
27
53
24
0
16
117
0
47
11
0
22
63
39
4
52
31
26
21
13
2
6
0
81
84
31
36
30
2
121
34
45
26
16
...

result:

ok 250000 tokens

Test #38:

score: 0
Accepted
time: 868ms
memory: 204964kb

input:

249999 250000 250000
231746 161105 231881 162462
181341 236229 182154 236989
144048 189015 144196 190745
135122 216351 135966 217590
123829 118188 124789 120595
202769 83968 203477 84770
228955 95521 231312 97451
189463 59982 191090 60038
127118 129375 128607 129482
225465 144756 227498 145146
49589...

output:

273524
327245
378115
374535
298881
272300
338745
407440
483236
317289
498370
348136
335640
226918
340931
462381
299757
396575
296431
168240
479475
398768
289811
381979
153919
292251
201906
347642
354708
211762
288648
419496
250178
196315
419197
314903
331545
344003
346520
311556
268971
124757
319499...

result:

ok 250000 tokens

Test #39:

score: 0
Accepted
time: 842ms
memory: 204940kb

input:

249999 250000 250000
185 687 7718 237720
149 430 86501 134593
66 957 137226 141674
717 443 71695 166440
637 242 20247 60319
102 799 125708 150803
759 219 64084 87264
580 900 47875 136202
900 172 102471 184729
851 953 244559 49640
466 764 94802 171858
170 442 241594 226738
957 406 38821 240005
109 74...

output:

971248347
852914734
1246915291
370972692
1142629498
80366611
252787712
1352524964
1352920679
1018581898
845666832
1282476498
722002560
58145243
953169985
492979544
693838603
98291727
287648568
78790483
771125924
1169780698
122512701
466966107
145106687
1734121842
1192038
1790729111
747080453
9833026...

result:

ok 250000 tokens

Test #40:

score: 0
Accepted
time: 797ms
memory: 207832kb

input:

250000 250000 250000
9736 86114 9736 86114
130601 195167 130601 195167
141666 242366 141666 242366
113589 11330 113589 11330
170378 219429 170378 219429
232589 170228 232589 170228
151899 226657 151899 226657
62041 140608 62041 140608
3645 101146 3645 101146
193363 38685 193363 38685
193129 196825 1...

output:

0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
2
0
1
0
0
0
0
2
0
1
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
3
0
0
0
0
0
2
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
...

result:

ok 250000 tokens

Test #41:

score: 0
Accepted
time: 810ms
memory: 206996kb

input:

250000 250000 250000
22155 15200 22163 15212
39382 21749 39398 21762
44192 226432 44203 226443
7896 19336 7913 19338
14000 93194 14007 93202
132531 3037 132552 3060
68481 78121 68499 78133
167105 238070 167105 238074
2967 208180 2975 208199
127255 210299 127271 210318
203352 179905 203356 179922
196...

output:

5
37
40
2
33
71
70
13
23
73
33
27
47
25
30
60
90
39
10
32
77
61
13
1
37
54
69
0
97
61
100
118
45
97
9
1
103
87
54
112
34
6
2
63
73
26
42
10
44
59
47
0
0
44
36
18
23
25
5
62
42
53
23
66
10
22
30
31
0
50
3
17
0
0
15
46
69
74
49
26
15
57
68
24
55
3
25
1
47
0
24
7
17
24
36
20
30
31
56
10
41
24
33
27
43
...

result:

ok 250000 tokens

Test #42:

score: 0
Accepted
time: 834ms
memory: 205144kb

input:

250000 250000 250000
174459 102667 175202 104267
159696 64937 161741 65409
152818 166525 154128 167860
109410 52977 111837 53477
131549 62940 132863 63555
144433 66670 146588 68730
97634 3581 98736 4569
227591 98965 229146 101356
152014 105805 152757 108187
19303 101224 20361 102035
19562 5513 21181...

output:

398567
487428
221955
224877
384643
212136
88762
286329
271235
293105
260027
362665
344586
399935
184876
346635
72242
264948
258903
319940
181617
191109
525840
423735
176873
195890
301678
357789
205369
300372
259397
481091
178019
162132
317801
321905
340127
450379
264374
411998
353929
269739
253889
3...

result:

ok 250000 tokens

Test #43:

score: 0
Accepted
time: 818ms
memory: 205012kb

input:

250000 250000 250000
608 147 109826 113976
398 538 3042 173086
979 738 198485 127318
715 481 239354 31128
70 960 86663 243657
370 631 21099 57985
676 391 198645 138819
923 710 139918 223708
493 215 212145 2940
80 255 112259 32266
659 929 115174 227544
978 731 90212 135700
189 167 44071 154394
433 71...

output:

1851379593
332352285
1511655668
447822131
1516314385
129633116
1214301
1301471593
1087860758
613113350
2123201659
1921197084
1996729461
256605399
579896
645794678
1431831008
268449395
21110527
257467628
1028517182
534856487
661428630
1471568919
3821175
27028082
14315240
533415458
918735640
871161473...

result:

ok 250000 tokens