QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557138#6403. Master of PolygonpandapythonerTL 2813ms34628kbC++238.4kb2024-09-11 04:51:072024-09-11 04:51:07

Judging History

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

  • [2024-09-11 04:51:07]
  • 评测
  • 测评结果:TL
  • 用时:2813ms
  • 内存:34628kb
  • [2024-09-11 04:51:07]
  • 提交

answer

#pragma GCC optimize("Ofast,fast-math")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)



mt19937 rnd(234234);
ld pi = atan2l(0, -1);

struct vec {
    ll x, y;

    vec() {}
    vec(ll x, ll y) : x(x), y(y) {}


    bool operator==(const vec& other) const {
        return x == other.x and y == other.y;
    }
};


vec operator+(const vec& a, const vec& b) {
    return vec{ a.x + b.x, a.y + b.y };
}


vec operator-(const vec& a, const vec& b) {
    return vec{ a.x - b.x, a.y - b.y };
}


ll operator*(const vec& a, const vec& b) {
    return a.x * b.x + a.y * b.y;
}


ll operator%(const vec& a, const vec& b) {
    return a.x * b.y - a.y * b.x;
}


ll sign(ll x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

bool intersects(const vec& a, const vec& b, const vec& c, const vec& d) {
    if ((a - b) % (c - d) == 0) {
        if ((c - a) % (d - a) != 0) return false;
        if ((a - c) % (b - c) != 0) return false;
        if (max(a.x, b.x) < min(c.x, d.x) or max(c.x, d.x) < min(a.x, b.x)) return false;
        if (max(a.y, b.y) < min(c.y, d.y) or max(c.y, d.y) < min(a.y, b.y)) return false;
        return true;
    }
    if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) > 0) return false;
    if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) > 0) return false;
    return true;
}


bool intersects(const pair<vec, vec>& p, const pair<vec, vec>& q) {
    return intersects(p.first, p.second, q.first, q.second);
}


int n, q;
vector<vec> poly;
vector<pair<vec, vec>> tests;
vector<int> result;


void solve_slow() {
    result.resize(q);
    rep(i, q) {
        auto& [a, b] = tests[i];
        result[i] = false;
        rep(j, n) {
            auto& c = poly[j];
            auto& d = poly[j == n - 1 ? 0 : j + 1];
            if (intersects(a, b, c, d)) {
                result[i] = true;
                break;
            }
        }
    }
}


double get(const vec& a, const vec& b, ll x) {
    if (a.x == b.x) return a.y;
    return a.y + (double(x - a.x)) / (b.x - a.x) * (b.y - a.y);
}


vector<int> sift_ind(vector<int> ind) {
    vector<int> result;
}


vector<pair<vec, vec>> pull_lines(const vector<vector<vec>>& curves, ll xl, ll xr) {
    vector<pair<vec, vec>> result;
    for (auto& curve : curves) {
        for (int i = 0; i + 1 < len(curve); i += 1) {
            vec a = curve[i], b = curve[i + 1];
            if (make_pair(a.x, a.y) > make_pair(b.x, b.y)) swap(a, b);
            if (a.x <= xl and b.x >= xr) {
                result.push_back(make_pair(a, b));
            }
        }
    }
    return result;
}


vector<vector<vec>> cut_curves(const vector<vector<vec>>& curves, ll xl, ll xr) {
    vector<vector<vec>> result;
    for (auto& curve : curves) {
        for (int l = 0; l < len(curve); l += 1) {
            if (curve[l].x < xl or curve[l].x > xr) continue;
            int r = l;
            while (r + 1 < len(curve) and (xl <= curve[r + 1].x and curve[r + 1].x <= xr)) {
                r += 1;
            }
            int nl = max(0, l - 1);
            int nr = min(r + 1, len(curve) - 1);
            result.push_back(vector<vec>(curve.begin() + nl, curve.begin() + nr + 1));
            l = r;
        }
    }
    return result;
}


void solve_rec(vector<vector<vec>> curves, vector<int> ind, ll xl, ll xr) {
    vector<int> new_ind;
    for (auto i : ind) {
        if (!result[i] and tests[i].second.x >= xl and tests[i].first.x <= xr) new_ind.push_back(i);
    }
    ind = new_ind;
    new_ind.clear();
    if (curves.empty() or ind.empty()) {
        return;
    }
    auto lines = pull_lines(curves, xl, xr);
    curves = cut_curves(curves, xl, xr);
    auto comp = [&](pair<vec, vec> a, pair<vec, vec> b) -> bool {
        int coeff = 1;
        if (a.first.x > b.first.x) {
            swap(a, b);
            coeff = -1;
        }
        if (a.first.x == a.second.x) {
            return a.first.y * coeff < b.first.y * coeff;
        }
        if (a.first == b.first or a.second == b.first) {
            return (a.second - a.first) % (b.second - a.first) * coeff > 0;
        }
        return (a.second - a.first) % (b.first - a.first) * coeff > 0;
        };
    sort(all(lines), comp);
    if (!lines.empty()) {
        for (auto i : ind) {
            auto& [a, b] = tests[i];
            int tl = -1;
            int tr = len(lines);
            while (tl + 1 < tr) {
                int tm = (tl + tr) / 2;
                auto& [c, d] = lines[tm];
                if (intersects(lines[tm], tests[i])) {
                    result[i] = true;
                    break;
                }
                if (comp(lines[tm], tests[i])) {
                    tl = tm;
                } else {
                    tr = tm;
                }
            }
            if (result[i]) continue;
            int pos = tl;
            if (pos >= 0) {
                if (intersects(a, b, lines[pos].first, lines[pos].second)) {
                    result[i] = true;
                }
            }
            if (pos + 1 < len(lines)) {
                if (intersects(a, b, lines[pos + 1].first, lines[pos + 1].second)) {
                    result[i] = true;
                }
            }
            if (!result[i]) {
                new_ind.push_back(i);
            }
        }
        ind = new_ind;
        new_ind.clear();
    }
    if (xl == xr) {
        return;
    }
    if (xl + 1 == xr) {
        solve_rec(curves, ind, xl, xl);
        solve_rec(curves, ind, xr, xr);
        return;
    }
    ll xm = (xl + xr) / 2;
    solve_rec(curves, ind, xl, xm);
    solve_rec(curves, ind, xm, xr);
}


void solve() {
    result.assign(q, false);
    vector<vector<vec>> curves = { poly };
    curves.front().push_back(poly.front());
    vector<int> ind(q);
    rep(i, q) ind[i] = i;
    solve_rec(curves, ind, 0, 30000);
}


bool good_coord(ll x) {
    return 0 <= x and x <= 30000;
}


void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        int mx = 100;
        n = rnd() % mx + 1;
        q = rnd() % mx + 1;
        poly.resize(n);
        rep(i, n) {
            if (i == 0 or i == n - 1) {
                poly[i].x = 2;
            } else {
                poly[i].x = rnd() % mx + 3;
            }
            poly[i].y = i;
            // swap(poly[i].x, poly[i].y);
        }
        tests.resize(q);
        rep(i, q) {
            tests[i].first.x = rnd() % mx;
            tests[i].first.y = rnd() % mx;
            tests[i].second.x = rnd() % mx;
            tests[i].second.y = rnd() % mx;
            if (make_pair(tests[i].first.x, tests[i].first.y) >
                make_pair(tests[i].second.x, tests[i].second.y)) {
                swap(tests[i].first, tests[i].second);
            }
        }
        solve_slow();
        auto right_rs = result;
        solve();
        auto my_rs = result;
        if (right_rs != my_rs) {
            cout << n << " " << q << "\n";
            rep(i, n) {
                cout << poly[i].x << " " << poly[i].y << "\n";
            }
            rep(i, q) {
                cout << tests[i].first.x << " " << tests[i].first.y << " " << tests[i].second.x << " " << tests[i].second.y << "\n";
            }
            break;
        }
    }
}


signed main() {
    // stress();
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    poly.resize(n);
    rep(i, n) {
        cin >> poly[i].x >> poly[i].y;
        assert(good_coord(poly[i].x));
    }
    tests.resize(q);
    rep(i, q) {
        cin >> tests[i].first.x >> tests[i].first.y >> tests[i].second.x >> tests[i].second.y;
        assert(good_coord(tests[i].first.x));
        assert(good_coord(tests[i].second.x));
        if (make_pair(tests[i].first.x, tests[i].first.y) >
            make_pair(tests[i].second.x, tests[i].second.y)) {
            swap(tests[i].first, tests[i].second);
        }
    }
    solve();
    rep(i, q) {
        if (result[i]) {
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }
    return 0;
}


/*
3 1
2 0
6 1
2 2
1 4 4 1

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

output:

YES
YES
YES
YES
NO
YES

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: 0
Accepted
time: 294ms
memory: 22652kb

input:

20 200000
8838 9219
12190 11292
15953 7581
16690 6159
21104 5484
8978 1076
4354 1065
1261 676
12684 14159
15469 22416
13493 28027
15531 26837
18253 26053
26444 24253
22160 19958
24879 12856
28793 22156
25300 10245
14749 15078
12946 13942
26544 28338 18806 21279
5592 29200 20935 25253
28189 17513 215...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES...

result:

ok 200000 token(s): yes count is 156067, no count is 43933

Test #3:

score: 0
Accepted
time: 722ms
memory: 17084kb

input:

500 200000
17729 7936
17684 8099
17925 10195
17441 9150
17314 9604
17008 8764
17003 7525
16501 4085
16247 5851
16768 625
16492 706
15995 4316
16287 976
16032 629
15217 133
15692 4260
16153 6940
15550 5717
15493 4823
15085 4477
14465 4830
13595 4960
13721 3490
13309 2776
11167 3053
14319 2156
14626 2...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
Y...

result:

ok 200000 token(s): yes count is 197031, no count is 2969

Test #4:

score: 0
Accepted
time: 537ms
memory: 16356kb

input:

2000 200000
15746 1958
15965 1785
16322 2203
16779 3060
15774 2055
15869 2486
16141 3025
14987 1567
16314 3508
14816 1823
13841 1058
15595 3183
15716 4094
15939 4023
16426 4179
16507 5225
17035 6211
17233 5343
18059 5915
17140 5103
17154 4324
17471 4562
18065 5767
20733 10646
21651 12444
18707 6969
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199151, no count is 849

Test #5:

score: 0
Accepted
time: 183ms
memory: 15328kb

input:

2000 200000
11439 4221
11601 4531
11351 4595
10165 4725
11049 4209
9643 4623
8884 4596
8598 4376
10987 3767
10577 3606
10678 3417
10159 3481
10288 3302
11157 2781
10513 2652
10601 2489
10785 2201
9881 2932
10877 1775
9578 3034
9083 3337
8118 4188
8911 3253
10649 1785
6624 3607
6002 3749
10788 1539
8...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 1564, no count is 198436

Test #6:

score: 0
Accepted
time: 208ms
memory: 15348kb

input:

2000 200000
25931 29637
25732 29388
25090 29397
24676 29660
24268 29454
24712 28969
24252 27672
23976 28067
24211 27138
24428 27732
24389 27010
24062 26426
24278 25689
24727 26596
25281 28154
25062 26750
24927 26324
24625 25457
25456 26307
25444 25561
26008 27471
26065 27717
26065 27194
25255 24568
...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 5859, no count is 194141

Test #7:

score: 0
Accepted
time: 451ms
memory: 15416kb

input:

2000 200000
14066 4014
14235 4742
15201 5329
15389 5460
11381 3722
12856 4511
8264 2372
13039 4278
11684 3711
12888 4180
11849 3607
11431 3373
9979 2823
9099 2534
9055 2434
9393 2382
9867 2512
10315 2558
8175 1662
6480 184
5437 92
4413 100
5548 790
4362 471
4463 552
4817 748
6715 1673
5807 1562
7942...

output:

NO
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 55692, no count is 144308

Test #8:

score: 0
Accepted
time: 720ms
memory: 15604kb

input:

2000 200000
14977 2004
14689 1703
15835 1810
16896 1690
16802 1617
16193 869
15027 1025
14890 398
15977 29
17024 621
16998 991
17114 745
18865 277
18293 764
18306 941
19319 12
17810 1554
19311 271
17748 1881
15553 3843
17271 2971
18157 1924
19839 300
19482 727
19186 1301
19603 836
19522 1061
19765 1...

output:

YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 171136, no count is 28864

Test #9:

score: 0
Accepted
time: 114ms
memory: 12752kb

input:

99966 1000
25033 23639
25334 23745
25777 23856
25534 23761
24893 23589
24648 23517
24596 23501
24535 23479
24356 23416
24269 23406
24131 23319
24905 23572
24978 23588
24418 23387
23595 23085
24070 23293
23843 23200
23484 23078
23596 23125
23438 23066
23142 22915
24265 23317
23323 22980
23624 23088
2...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 1000, no count is 0

Test #10:

score: 0
Accepted
time: 164ms
memory: 13276kb

input:

99969 1000
19235 2200
19307 2137
19620 1920
19590 1908
19486 1919
19280 2087
19260 2029
19226 2197
19147 2281
19135 2254
19095 2304
19207 2101
18981 2354
18936 2288
18943 2166
18851 2224
18697 2428
19149 2332
18976 2371
18948 2403
19134 2347
19220 2323
19196 2374
19128 2467
19084 2485
19018 2464
190...

output:

NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
N...

result:

ok 1000 token(s): yes count is 173, no count is 827

Test #11:

score: 0
Accepted
time: 192ms
memory: 13356kb

input:

99976 1000
23538 24587
23600 24898
23569 24997
23628 25053
23693 25259
23691 25126
23674 25068
23623 24923
23664 25002
23713 25142
23659 24925
23558 24571
23523 24358
23569 24559
23578 24562
23637 24783
23621 24703
23685 24932
23735 25098
23768 25199
23802 25254
23768 25186
23774 25165
23645 24685
2...

output:

YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES...

result:

ok 1000 token(s): yes count is 666, no count is 334

Test #12:

score: 0
Accepted
time: 228ms
memory: 20912kb

input:

199886 1000
14938 9857
14804 10006
14968 9807
14708 10115
14761 10098
14678 10167
14648 10192
14715 10150
14497 10337
14635 10227
14596 10269
14648 10256
14774 10175
14682 10266
14490 10424
14602 10339
14754 10214
14490 10489
14360 10622
14157 10755
14299 10632
14431 10511
14245 10670
14429 10473
14...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 1000, no count is 0

Test #13:

score: 0
Accepted
time: 280ms
memory: 21676kb

input:

199901 1000
1983 26999
2038 26992
2067 26988
2231 26970
2022 26966
2763 26923
2133 26996
2353 26976
2258 26995
2211 27022
2129 27045
2138 27046
2532 27004
2630 26988
3195 26898
3060 26912
3210 26895
3069 26904
2936 26918
2839 26924
2998 26888
2696 26891
2461 26909
2257 26930
1640 26991
1708 26971
18...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 1000 token(s): yes count is 88, no count is 912

Test #14:

score: 0
Accepted
time: 278ms
memory: 20396kb

input:

199898 1000
18799 13687
18845 13550
18777 13722
18754 13747
18726 13809
18674 13927
18698 13858
18740 13747
18818 13555
18664 13906
18651 13907
18649 13898
18605 13894
18656 13746
18693 13650
18784 13527
18811 13447
18775 13570
18818 13471
18851 13382
18907 13296
18924 13316
18943 13240
18829 13393
...

output:

NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
...

result:

ok 1000 token(s): yes count is 235, no count is 765

Test #15:

score: 0
Accepted
time: 354ms
memory: 20192kb

input:

199886 1000
10118 8021
10120 8003
10112 8046
10126 8048
10157 8041
10255 8007
10140 8106
10114 8118
10137 8118
10284 8037
10259 8097
10381 8066
10302 8091
10209 8127
10185 8149
10199 8146
10314 8117
10340 8108
10261 8229
10328 8182
10333 8267
10377 8257
10465 8176
10416 8235
10421 8256
10400 8332
10...

output:

NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES...

result:

ok 1000 token(s): yes count is 762, no count is 238

Test #16:

score: 0
Accepted
time: 287ms
memory: 21752kb

input:

199879 1000
18589 2979
18584 2916
18708 2953
18498 2855
18498 2848
18472 2840
18436 2819
18649 2859
18521 2809
18573 2808
18386 2799
18442 2784
18486 2785
18648 2774
18360 2745
18649 2770
18730 2789
18716 2804
18731 2927
18751 2963
18855 2956
18826 2904
18833 2895
18848 2902
18851 2916
18922 2944
18...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 1000 token(s): yes count is 987, no count is 13

Test #17:

score: 0
Accepted
time: 1466ms
memory: 34496kb

input:

199874 200000
8778 8537
8541 8516
8372 8496
7893 8430
7794 8429
7968 8456
7837 8443
7844 8452
8024 8493
8016 8501
8137 8518
7682 8492
7633 8489
7684 8508
7633 8520
8523 8538
8449 8539
7714 8536
7660 8547
8781 8557
7918 8557
8942 8561
9037 8578
9079 8577
9031 8586
9310 8621
9280 8625
9224 8619
8927 8...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #18:

score: 0
Accepted
time: 1463ms
memory: 34628kb

input:

199886 200000
24070 3955
24089 3887
24151 3955
24147 3956
24180 3982
24256 3985
24157 3861
24147 3828
24222 3748
24287 3767
24285 3745
24363 3729
24318 3770
24341 3779
24255 3837
24336 3900
24279 3909
24359 3922
24317 3926
24267 3939
24378 3995
24420 3943
24407 4034
24419 4067
24444 4045
24442 3995
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #19:

score: 0
Accepted
time: 1414ms
memory: 33956kb

input:

199881 200000
17149 10727
17186 10704
17136 10668
17184 10671
17147 10615
17284 10700
17129 10577
17126 10568
17179 10571
17199 10594
17371 10773
17323 10689
17327 10679
17413 10826
17421 10778
17439 10828
17492 10807
17303 10623
17092 10415
17251 10535
17191 10487
17152 10442
17109 10389
17242 1051...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199974, no count is 26

Test #20:

score: 0
Accepted
time: 1140ms
memory: 33052kb

input:

199893 200000
28788 23708
28788 23330
28801 22621
28804 22517
28804 22387
28786 22396
28784 22569
28781 23598
28781 23119
28783 22714
28778 21429
28777 20858
28771 16718
28767 17297
28764 16540
28766 18109
28772 19388
28771 19492
28770 19502
28769 19226
28766 18324
28762 16664
28763 17813
28764 1860...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
N...

result:

ok 200000 token(s): yes count is 8963, no count is 191037

Test #21:

score: 0
Accepted
time: 1107ms
memory: 32276kb

input:

199904 200000
13557 23580
13524 23609
13716 23354
13735 23326
13740 23301
13921 23069
13752 23250
13850 23122
14052 22875
14077 22866
14086 22868
14394 22544
14344 22584
14392 22531
14446 22470
14552 22350
14629 22258
14644 22245
14629 22234
14601 22257
14447 22436
14349 22539
14336 22552
14405 2237...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 10793, no count is 189207

Test #22:

score: 0
Accepted
time: 1167ms
memory: 33760kb

input:

199870 200000
22975 15511
23102 15451
22820 15583
23109 15429
23101 15430
22892 15506
23324 15307
23281 15314
23121 15374
23050 15388
22799 15539
22979 15482
22876 15521
22872 15523
22832 15554
22817 15556
22742 15579
22602 15652
22715 15599
22609 15672
22530 15881
22528 15950
22583 15950
22675 1574...

output:

NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 token(s): yes count is 15176, no count is 184824

Test #23:

score: 0
Accepted
time: 1177ms
memory: 32360kb

input:

199872 200000
6841 2680
6777 3012
6771 2964
6771 2802
6730 3187
6711 3197
6665 3496
6225 5261
6648 3570
6789 3010
6795 3011
6905 2634
6902 2671
6860 2868
6680 3550
6661 3589
6628 3672
6574 3916
6434 4480
6711 3434
6900 2736
6719 3429
6894 2781
6545 4083
6542 4098
6736 3384
6846 2983
6814 3149
6689 3...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES...

result:

ok 200000 token(s): yes count is 26619, no count is 173381

Test #24:

score: 0
Accepted
time: 1296ms
memory: 33008kb

input:

199886 200000
17334 6856
18139 6745
18939 6631
19422 6563
18967 6611
18584 6679
18356 6711
18268 6722
18288 6707
17584 6811
16986 6901
17560 6799
17911 6737
17903 6743
17906 6748
17569 6812
18383 6684
18655 6652
19729 6489
20434 6385
20928 6310
21502 6225
20369 6387
19566 6506
19448 6524
18628 6642
...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO...

result:

ok 200000 token(s): yes count is 44418, no count is 155582

Test #25:

score: 0
Accepted
time: 1306ms
memory: 32212kb

input:

199864 200000
20471 23764
20465 23713
20468 23853
20478 24195
20458 23888
20467 24117
20441 23679
20441 23769
20427 23718
20422 23515
20432 23508
20416 23390
20414 23272
20404 23240
20389 23260
20440 23950
20354 23433
20374 23587
20378 23678
20432 23966
20462 24135
20402 23861
20367 23695
20336 2357...

output:

NO
NO
YES
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
YE...

result:

ok 200000 token(s): yes count is 63070, no count is 136930

Test #26:

score: 0
Accepted
time: 1443ms
memory: 31900kb

input:

199878 200000
10321 24028
10372 24050
10596 24130
10790 24185
10800 24171
10839 24173
10707 24135
10168 23980
10298 24015
10300 24013
10459 24057
10356 24020
10309 24000
10151 23944
10036 23902
10232 23941
10724 24123
10547 24051
10131 23901
10779 24118
10863 24147
10578 24020
10557 24013
10229 2387...

output:

YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
YES...

result:

ok 200000 token(s): yes count is 95620, no count is 104380

Test #27:

score: 0
Accepted
time: 1548ms
memory: 32448kb

input:

199872 200000
12605 17615
12645 17453
12632 17499
12701 17194
12744 17002
12727 17069
12692 17096
12626 17417
12662 17044
12684 16951
12673 17024
12711 17006
12719 16970
12748 16911
12739 16878
12791 16827
12783 16797
12791 16768
12746 16830
12809 16679
12751 16774
12736 16748
12751 16700
12830 1660...

output:

NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
NO
YE...

result:

ok 200000 token(s): yes count is 132363, no count is 67637

Test #28:

score: 0
Accepted
time: 1520ms
memory: 33932kb

input:

199883 200000
23919 20346
23562 19885
23557 19868
22944 19070
22448 18443
22350 18318
22455 18453
22964 19109
23268 19503
23335 19590
22979 19138
23326 19582
22782 18888
23046 19234
23044 19242
23414 19729
23268 19541
23069 19278
23056 19262
23108 19334
23095 19321
22905 19067
23037 19246
23197 1946...

output:

YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 166937, no count is 33063

Test #29:

score: 0
Accepted
time: 1586ms
memory: 32552kb

input:

199892 200000
24403 11365
24445 11216
24472 11099
24539 10829
24577 10696
24645 10467
24649 10490
24562 10843
24535 10941
24614 10697
24534 10947
24512 11193
24474 11264
24468 11259
24466 11329
24442 11438
24424 11453
24349 11664
24388 11714
24401 11728
24409 11758
24319 11883
24254 11954
24298 1184...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
...

result:

ok 200000 token(s): yes count is 184337, no count is 15663

Test #30:

score: 0
Accepted
time: 1430ms
memory: 32832kb

input:

199885 200000
25573 17804
24620 18469
25782 17666
26226 17361
25214 18061
25678 17744
25496 17879
26125 17435
26797 16972
26652 17074
26230 17382
25818 17663
26360 17298
26522 17191
26215 17400
24663 18446
26961 16901
26923 16929
25331 17998
25483 17896
26185 17429
25560 17852
24542 18545
25251 1805...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 194548, no count is 5452

Test #31:

score: 0
Accepted
time: 1380ms
memory: 33108kb

input:

199864 200000
22203 12936
22118 12953
22192 12911
22456 12703
22323 12794
22151 12905
22475 12684
22332 12765
22430 12595
22332 12725
22345 12681
22233 12820
22299 12718
22525 12420
22645 12256
22565 12407
22463 12597
22402 12717
22528 12583
22549 12556
22591 12449
22649 12255
22698 12229
22652 1235...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

ok 200000 token(s): yes count is 198307, no count is 1693

Test #32:

score: 0
Accepted
time: 1308ms
memory: 33732kb

input:

199863 200000
22050 20130
22065 20114
22174 19985
22343 19793
22265 19890
22371 19765
22430 19728
22337 19773
22456 19614
22510 19560
22586 19527
22929 19205
22847 19297
22641 19519
22930 19219
22902 19251
22905 19266
22710 19457
22580 19599
22699 19487
22585 19607
22700 19491
22399 19825
22391 1983...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199573, no count is 427

Test #33:

score: 0
Accepted
time: 1203ms
memory: 33596kb

input:

199902 200000
29212 15830
29209 15836
29376 15814
29327 15827
29390 15826
29314 15845
29426 15840
29357 15860
29408 15856
29383 15865
29304 15887
29257 15874
29272 15965
29282 15976
29164 15952
29116 15893
29145 15859
29067 15861
29022 15874
29042 15908
28955 15913
28706 15938
28646 15943
28643 1594...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199890, no count is 110

Test #34:

score: 0
Accepted
time: 1103ms
memory: 34164kb

input:

199874 200000
29188 5004
29564 5050
29973 5101
29561 5053
29859 5092
29937 5111
29680 5089
29537 5076
29988 5206
29737 5184
29696 5180
29722 5189
29841 5277
29858 5295
29958 5274
29899 5325
29956 5391
29987 5436
29971 5440
29864 5348
29898 5397
29809 5360
29525 5253
29664 5298
29799 5346
29654 5286
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 200000 token(s): yes count is 199980, no count is 20

Test #35:

score: 0
Accepted
time: 2813ms
memory: 25512kb

input:

62509 200000
1505 1
1549 2
514 2
1592 3
460 3
1634 4
487 4
1675 5
518 5
1715 6
534 6
1754 7
463 7
1792 8
472 8
1829 9
474 9
1865 10
548 10
1900 11
470 11
1934 12
519 12
1967 13
488 13
1999 14
504 14
2030 15
522 15
2060 16
458 16
2089 17
467 17
2117 18
540 18
2144 19
481 19
2170 20
472 20
2195 21
452...

output:

YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
...

result:

ok 200000 token(s): yes count is 190774, no count is 9226

Test #36:

score: -100
Time Limit Exceeded

input:

62509 200000
1 1505
2 1549
2 536
3 1592
3 514
4 1634
4 482
5 1675
5 508
6 1715
6 519
7 1754
7 537
8 1792
8 543
9 1829
9 550
10 1865
10 490
11 1900
11 515
12 1934
12 511
13 1967
13 500
14 1999
14 460
15 2030
15 453
16 2060
16 488
17 2089
17 481
18 2117
18 466
19 2144
19 486
20 2170
20 486
21 2195
21 ...

output:


result: