QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#595798#65. Two AntennasRikku_eq100 ✓472ms56576kbC++144.7kb2024-09-28 14:29:102024-09-28 14:29:13

Judging History

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

  • [2024-09-28 14:29:13]
  • 评测
  • 测评结果:100
  • 用时:472ms
  • 内存:56576kb
  • [2024-09-28 14:29:10]
  • 提交

answer

#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000000000001
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
using namespace std;
typedef long long ll;

struct SegT
{
    struct Seg { int ls, rs; ll mx, hmx, tg, htg; } tr[N*2];
    int rt, tot;

    void build (int &u, int l, int r)
    {
        if (!u) { u=++tot; }
        tr[u]=(Seg){ ls(u), rs(u), -INF, -INF, 0, 0 };
        if (l==r) { return; }
        int md=(l+r)>>1;
        build(ls(u), l, md);
        build(rs(u), md+1, r);
    }

    void pushdown (int u)
    {
        if (tr[u].tg==0 && tr[u].htg==0) { return; }
        tr[ls(u)].hmx=max(tr[ls(u)].hmx, tr[ls(u)].mx+tr[u].htg); tr[ls(u)].mx+=tr[u].tg;
        tr[ls(u)].htg=max(tr[ls(u)].htg, tr[ls(u)].tg+tr[u].htg); tr[ls(u)].tg+=tr[u].tg;
        tr[rs(u)].hmx=max(tr[rs(u)].hmx, tr[rs(u)].mx+tr[u].htg); tr[rs(u)].mx+=tr[u].tg;
        tr[rs(u)].htg=max(tr[rs(u)].htg, tr[rs(u)].tg+tr[u].htg); tr[rs(u)].tg+=tr[u].tg;
        tr[u].tg=0; tr[u].htg=0;
    }
    void pushup (int u)
    {
        tr[u].mx=max(tr[ls(u)].mx, tr[rs(u)].mx);
        tr[u].hmx=max(tr[ls(u)].hmx, tr[rs(u)].hmx);
    }

    void upd (int u, int l, int r, int id, ll num)
    {
        if (l==r) { tr[u].mx=num; tr[u].hmx=max(tr[u].hmx, num); return; }
        pushdown(u);
        int md=(l+r)>>1;
        if (id<=md) upd(ls(u), l, md, id, num);
        else upd(rs(u), md+1, r, id, num);
        pushup(u);
    }
    void add (int u, int l, int r, int ql, int qr, ll num)
    {
        if (l>qr || r<ql) { return; }
        if (ql<=l && r<=qr) {
            tr[u].mx+=num; tr[u].hmx=max(tr[u].hmx, tr[u].mx);
            tr[u].tg+=num; tr[u].htg=max(tr[u].htg, tr[u].tg);
            return;
        }
        pushdown(u);
        int md=(l+r)>>1;
        add(ls(u), l, md, ql, qr, num);
        add(rs(u), md+1, r, ql, qr, num);
        pushup(u);
    }
    ll qrymx (int u, int l, int r, int ql, int qr)
    {
        if (l>qr || r<ql) { return -INF; }
        if (ql<=l && r<=qr) { return tr[u].hmx; }
        pushdown(u);
        int md=(l+r)>>1;
        ll resl=qrymx(ls(u), l, md, ql, qr);
        ll resr=qrymx(rs(u), md+1, r, ql, qr);
        return max(resl, resr);
    }

} ST;

int n, Q;
ll ans[N];
vector <int> ins[N], del[N];
struct Qry { int l, id; };
vector <Qry> qq[N], qq2[N];
struct Pnt { int h, a, b; } p[N];

void sol ()
{
    for (int i=1; i<=n; i++) {
        int l=i+p[i].a, r=i+p[i].b;
        r=min(r, n); l=min(l, r+1);
        if (l<=r) { ins[l].push_back(i); del[r+1].push_back(i); }
    }

    ST.build(ST.rt, 1, n);
    for (int i=1; i<=n; i++) {
        for (int j=0; j<(int)ins[i].size(); j++) {
            ST.upd(ST.rt, 1, n, ins[i][j], -p[ins[i][j]].h);
        }
        for (int j=0; j<(int)del[i].size(); j++) {
            ST.upd(ST.rt, 1, n, del[i][j], -INF);
        }

        int l=i-p[i].b, r=i-p[i].a;
        l=max(l, 1); r=max(l-1, r);

        if (l<=r) { ST.add(ST.rt, 1, n, l, r, p[i].h); }
        for (int j=0; j<(int)qq[i].size(); j++) {
            ans[qq[i][j].id]=max(ans[qq[i][j].id], ST.qrymx(ST.rt, 1, n, qq[i][j].l, i));
        }
        if (l<=r) { ST.add(ST.rt, 1, n, l, r, -p[i].h); }
    }
}

void sol2 ()
{
    for (int i=0; i<=n+1; i++) { del[i].clear(); ins[i].clear(); }

    for (int i=1; i<=n; i++) {
        int l=i-p[i].b, r=i-p[i].a;
        l=max(l, 1); r=max(l-1, r);
        if (l<=r) { del[l-1].push_back(i); ins[r].push_back(i); }

        for (int j=0; j<(int)qq[i].size(); j++) {
            qq2[qq[i][j].l].push_back((Qry){ i, qq[i][j].id });
        }
    }

    ST.build(ST.rt, 1, n);
    for (int i=n; i>=1; i--) {
        for (int j=0; j<(int)ins[i].size(); j++) {
            ST.upd(ST.rt, 1, n, ins[i][j], -p[ins[i][j]].h);
        }
        for (int j=0; j<(int)del[i].size(); j++) {
            ST.upd(ST.rt, 1, n, del[i][j], -INF);
        }

        int l=i+p[i].a, r=i+p[i].b;
        r=min(r, n); l=min(l, r+1);

        if (l<=r) { ST.add(ST.rt, 1, n, l, r, p[i].h); }
        for (int j=0; j<(int)qq2[i].size(); j++) {
            ans[qq2[i][j].id]=max(ans[qq2[i][j].id], ST.qrymx(ST.rt, 1, n, i, qq2[i][j].l));
        }
        if (l<=r) { ST.add(ST.rt, 1, n, l, r, -p[i].h); }
    }
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d %d %d", &p[i].h, &p[i].a, &p[i].b);
    }

    scanf("%d", &Q);
    for (int i=1; i<=Q; i++) {
        int l, r; scanf("%d %d", &l, &r);
        qq[r].push_back((Qry){ l, i });
        ans[i]=-1;
    }

    sol(); sol2();
    
    for (int i=1; i<=Q; i++) { printf("%d\n", ans[i]); }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 2ms
memory: 24304kb

input:

111
2342163 25 76
738276997 50 52
1669890 26 40
14902411 56 81
899007094 32 85
422634516 2 71
936109680 79 100
638713463 109 110
119468142 28 104
713258492 104 107
267306336 1 39
973810399 87 90
835929417 43 86
335127775 12 104
840490095 39 66
459253103 11 104
706538155 4 101
194912428 82 96
9492220...

output:

-1
-1
828818552
-1
-1
958376243
-1
736480018
-1
-1
-1
828818552
648812417
648812417
-1
-1
736480018
-1
-1
-1
828818552
-1
828818552
828818552
609416339
350445999
828818552
-1
-1
828818552
557668751
864679211
-1
-1
828818552
736480018
828818552
-1
-1
-1
648812417
828818552
828818552
-1
736480018
-1
-...

result:

ok 68 lines

Test #2:

score: 2
Accepted
time: 0ms
memory: 26420kb

input:

300
735013405 266 284
438296241 68 114
24046243 256 286
709242874 110 281
798805511 198 202
804692776 1 278
590054369 126 242
435774303 124 171
529488852 96 256
414611064 117 297
721973791 296 296
478157232 282 285
427227260 76 172
626616969 24 116
153512861 157 277
616835099 150 290
872611184 33 69...

output:

872339035
927050227
-1
972252127
-1
-1
674377255
813598637
813151017
972252127
944993850
860280776
951978417
927050227
944993850
-1
872339035
815698155
815698155
956834566
967502843
-1
648434460
-1
144411997
944993850
951978417
674377255
964406530
967502843
831394612
972252127
815698155
972252127
-1...

result:

ok 187 lines

Test #3:

score: 2
Accepted
time: 4ms
memory: 26472kb

input:

229
750442988 131 222
564719763 197 198
664000672 184 200
672344036 206 212
964649664 91 139
854930075 82 132
648923774 112 174
737387688 106 148
588670044 127 217
154573679 137 165
273609238 23 28
52983135 168 213
835318106 42 84
70005585 186 213
670737974 144 162
765809363 208 213
129621551 68 169...

output:

267011185
949865918
180860106
-1
794633145
80719202
-1
890866090
250125811
-1
-1
890866090
931845293
-1
485341202
-1
-1
-1
-1
607770042
-1
949865918
514173632
680052837
-1
331422812
635969957
331422812
890866090
508409406
-1
311294738
933309075
-1
-1
-1
949865918
890866090
470124750
794633145
-1
607...

result:

ok 300 lines

Test #4:

score: 2
Accepted
time: 4ms
memory: 26464kb

input:

300
378362905 9 199
356507721 26 263
426722694 285 291
604732888 98 107
763649006 80 173
654782832 97 104
109974358 271 293
382031287 265 280
957573396 138 220
348062643 121 126
784725696 86 111
783386041 4 45
404011830 266 272
61590501 64 299
215463566 280 291
111318418 176 274
788870998 131 201
32...

output:

-1
983376106
903669260
983376106
-1
788350249
-1
-1
-1
885220456
967158786
-1
952730577
-1
838353580
-1
983376106
-1
481007624
152628603
684565551
-1
-1
788350249
274820451
391805363
152628603
-1
481007624
-1
-1
932836644
-1
227821564
788350249
932836644
897642488
172124902
-1
-1
-1
788350249
-1
897...

result:

ok 300 lines

Test #5:

score: 2
Accepted
time: 4ms
memory: 26528kb

input:

254
675456110 102 211
448492118 238 246
820890604 56 107
516692295 129 249
426994513 206 208
436850287 230 231
353897431 4 58
909933991 248 252
450603599 139 140
709868603 119 202
601358700 226 249
500524474 24 147
303746814 35 152
49155004 242 242
65634174 106 207
300210427 76 109
836488160 172 235...

output:

943900139
-1
844142462
943900139
-1
-1
-1
-1
858087986
621288262
491944918
952622939
-1
731935963
852679398
-1
6104631
-1
944798360
756188457
870983439
981631140
-1
-1
973861769
-1
-1
-1
434449398
870983439
-1
-1
-1
973861769
-1
340743990
-1
844142462
952622939
922438420
-1
-1
866495252
756188457
-1...

result:

ok 121 lines

Test #6:

score: 2
Accepted
time: 4ms
memory: 26420kb

input:

300
268216784 129 172
387013021 132 295
835840160 39 138
338097708 173 213
447998961 46 101
114944800 15 26
260632256 275 297
401080358 79 110
293253696 212 218
367482259 107 268
824267616 221 232
227829760 270 286
812559432 75 175
338085342 180 206
594558937 183 267
739319075 6 192
151783031 143 21...

output:

932793484
932793484
-1
955482444
768115955
564637306
-1
955482444
969965918
955482444
910147685
976729186
-1
784502461
976729186
632336914
-1
270425765
67699608
632336914
932793484
976729186
428028140
-1
-1
976729186
932793484
768115955
784502461
932793484
-1
-1
-1
969965918
-1
922051931
768115955
-...

result:

ok 136 lines

Test #7:

score: 2
Accepted
time: 0ms
memory: 24360kb

input:

276
221739989 134 266
882531779 263 275
231194092 209 272
709010205 4 209
544740779 261 268
952882550 6 267
539116259 158 205
299400395 139 241
923810023 9 188
345905146 104 239
612187995 129 164
742288759 89 112
541001701 180 194
473527180 231 263
493500125 168 194
666181395 54 155
607149474 70 197...

output:

864022404
905891685
674341097
-1
892203564
864022404
864022404
384176657
-1
260008917
751785923
-1
875253794
-1
904807026
905891685
260008917
991616355
-1
926027040
-1
674341097
-1
961400559
991616355
904807026
-1
-1
-1
905891685
864022404
-1
821029521
-1
-1
991616355
864022404
-1
-1
-1
821029521
67...

result:

ok 300 lines

Test #8:

score: 2
Accepted
time: 0ms
memory: 26476kb

input:

300
417068593 289 292
777801873 292 294
221470340 184 264
914008748 35 131
706748979 53 242
752038592 175 243
289949695 249 276
999202919 34 273
477398378 36 139
197611565 65 69
798179437 98 242
894150402 47 294
798719056 254 266
555107337 266 293
321276949 85 131
794816085 33 208
123604811 174 214
...

output:

-1
-1
-1
717236759
848347506
-1
665850652
841359383
997139795
-1
665850652
747045257
-1
885888463
841359383
628792397
-1
921351997
628792397
-1
842568272
841359383
921992916
813966788
848347506
628792397
-1
665850652
921992916
-1
921351997
841359383
867530446
867530446
726047348
921992916
921992916
...

result:

ok 300 lines

Test #9:

score: 2
Accepted
time: 3ms
memory: 26532kb

input:

111
242077832 11 107
85240073 78 91
954216740 102 107
11667399 69 83
202952807 94 108
886576575 28 57
465376592 104 105
961568023 54 108
433097368 21 42
634314286 14 56
504468650 54 79
460432133 68 71
212485904 57 98
13636641 1 14
210642973 20 87
645748836 81 87
350544920 98 106
363904919 103 106
57...

output:

-1
-1
-1
575550802
486083920
795644381
-1
-1
-1
930044160
795644381
-1
795644381
355316568
575550802
959648928
347415172
933778489
-1
-1
-1
906750711
836328852
-1
-1
795644381
241890466
959648928
-1
836328852
-1
959648928
836328852
-1
933778489
522245966
-1
-1
795644381
355316568
-1
836328852
836328...

result:

ok 293 lines

Test #10:

score: 2
Accepted
time: 0ms
memory: 26404kb

input:

300
291682036 88 242
748510667 202 240
827360407 9 291
559890096 131 274
918704609 184 296
62268455 47 177
145240975 230 255
480249205 105 131
657768325 243 286
141414674 270 278
17186802 261 288
759021241 137 147
375425594 100 134
982578823 143 212
491858468 11 158
584169961 258 278
125923937 116 1...

output:

764587783
954356467
764587783
763829844
957256513
936015577
959258003
-1
954356467
-1
725890631
764587783
-1
764587783
954356467
-1
725890631
939647187
-1
954356467
954356467
954356467
457616727
725890631
-1
764587783
763829844
596300770
954356467
-1
558119287
954356467
-1
764587783
869873844
626215...

result:

ok 241 lines

Test #11:

score: 2
Accepted
time: 2ms
memory: 26460kb

input:

64
869352152 20 56
311016796 19 42
740742255 13 30
179585337 31 34
517427140 33 55
720194533 49 63
211093914 11 51
40361850 37 46
383940026 44 49
443693990 42 59
505035714 61 62
993768411 23 25
987537493 43 50
125258582 58 60
846135230 51 59
368411133 49 50
133779952 49 52
814654841 50 57
580983166 ...

output:

-1
-1
-1
-1
369889252
-1
563215153
-1
369889252
336864035
563215153
563215153
-1
396959317
-1
563215153
968949481
-1
-1
-1
-1
-1
968949481
849611060
336864035
-1
-1
336864035
-1
-1
-1
-1
968949481
396959317
-1
336864035
-1
-1
-1
-1
396959317
631331415
396959317
968949481
563215153
369889252
-1
36988...

result:

ok 300 lines

Test #12:

score: 2
Accepted
time: 4ms
memory: 26412kb

input:

300
942501288 32 215
793815601 162 178
305422439 90 141
136758254 156 225
810202677 113 282
338125654 280 299
35086992 88 207
657468728 235 246
397843754 145 171
939897792 114 271
376653947 112 239
760644678 50 263
402377185 96 231
930391147 243 250
27305011 127 294
593762925 292 293
216058992 217 2...

output:

938766838
588298937
771949376
760266036
491652644
-1
859156647
-1
760266036
-1
-1
938766838
908513297
607961655
908513297
764044360
813012088
859156647
881381717
938766838
813012088
938766838
588298937
-1
908513297
588298937
962485473
938766838
760266036
760266036
-1
938766838
97104745
938766838
881...

result:

ok 300 lines

Test #13:

score: 2
Accepted
time: 0ms
memory: 26480kb

input:

250
143394442 125 128
143394439 124 127
143394432 123 126
143394441 122 125
838109762 125 126
838109761 124 127
707707813 124 128
707707816 123 127
707707819 123 126
707707812 122 125
67969849 125 127
67969848 124 126
639767527 125 127
639767523 124 126
639767517 123 125
153113806 115 137
153113803 ...

output:

-1
-1
-1
-1
-1
-1
50000992
-1
-1
-1
50000992
50000936
-1
-1
-1
50000728
-1
50000957
50000992
50000992
-1
-1
-1
-1
-1
-1
50000686
-1
-1
-1
-1
-1
-1
-1
-1
50000936
-1
50000936
-1
50000991
-1
-1
-1
50000992
-1
-1
50000936
-1
-1
-1
-1
-1
50000830
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000734
500...

result:

ok 153 lines

Test #14:

score: 2
Accepted
time: 4ms
memory: 26532kb

input:

252
689078643 126 128
689078634 125 127
689078634 124 126
378503721 126 128
378503720 125 127
378503712 124 126
906320567 126 148
906320564 125 147
906320566 124 146
906320569 123 145
906320573 116 144
906320572 115 143
906320567 114 142
906320564 113 141
906320566 112 140
906320567 111 139
90632056...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
50000872
50000872
50000872
-1
-1
-1
-1
-1
-1
-1
-1
50000834
-1
-1
-1
-1
-1
50000648
-1
-1
-1
-1
-1
50000653
-1
50000872
-1
-1
-1
-1
-1
50000872
-1
-1
-1
-1
50000855
50000682
-1
-1
50000834
-1
-1
-1
-1
-1
-1
50000872
-1
-1
-1
-1
-1
-1
-1
50000872
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300 lines

Test #15:

score: 2
Accepted
time: 3ms
memory: 26460kb

input:

250
813588695 125 126
813588693 124 128
168966530 123 127
168966534 122 126
250410261 125 126
250410269 120 151
565724040 119 150
565724046 118 149
170475303 117 148
170475312 116 147
800652816 115 146
800652810 114 145
800652811 113 144
800652820 112 143
608606505 111 142
608606499 110 141
29017982...

output:

50000966
-1
-1
-1
-1
-1
-1
-1
50000966
-1
-1
-1
50000966
-1
50000725
-1
-1
-1
-1
-1
-1
50000966
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000966
-1
-1
-1
50000853
-1
-1
-1
-1
-1
-1
-1
14592978
-1
50000966
-1
50000659
43841957
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000829
-1
-1
-1
50000966
-1
50000795
...

result:

ok 184 lines

Test #16:

score: 2
Accepted
time: 2ms
memory: 26480kb

input:

250
765453455 125 126
765453456 124 125
598255533 125 126
598255539 124 125
608720660 125 127
608720655 124 126
608720664 123 125
306558312 125 126
306558303 124 125
700060685 125 126
700060684 124 125
870760272 125 126
870760266 124 125
807063625 125 127
807063629 124 126
807063635 123 125
47772561...

output:

50000825
-1
50000833
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000516
-1
50000913
-1
-1
-1
-1
-1
-1
-1
50000910
-1
-1
50000913
-1
-1
-1
-1
50000825
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000825
50000913
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000583
-1
50000833
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
500009...

result:

ok 300 lines

Test #17:

score: 2
Accepted
time: 4ms
memory: 26408kb

input:

254
469115335 127 130
469115337 126 129
469115340 125 128
469115337 124 127
227420119 127 130
227420111 126 129
227420114 125 128
227420113 124 130
886600501 126 130
886600491 125 129
886600498 124 128
886600492 116 175
906187487 115 174
906187477 114 173
906187484 113 172
516252217 112 171
51625221...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000941
-1
-1
-1
-1
50000802
-1
-1
-1
-1
29791472
-1
-1
-1
50000813
-1
-1
-1
50000941
-1
-1
-1
50000687
50000941
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000823
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000778
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 211 lines

Test #18:

score: 2
Accepted
time: 2ms
memory: 26532kb

input:

250
180860129 125 127
180860123 124 126
180860133 123 125
684434370 122 128
684434366 121 127
684434365 123 126
684434374 122 125
490452747 125 127
490452750 124 126
490452744 123 125
77236508 125 126
77236506 124 125
748055153 125 127
748055148 124 126
748055156 123 125
102170888 125 127
102170895 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
50000954
50000954
-1
-1
-1
-1
-1
-1
-1
-1
50000954
50000954
50000901
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000944
-1
50000944
-1
-1
50000953
-1
50000927
-1
-1
-1
-1
-1
50000954
-1
-1
-1
50000953
-1
-1
-1
-1
39672264
50000901
-1
-1
-1
-1
-1
-1
50000753
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300 lines

Test #19:

score: 2
Accepted
time: 4ms
memory: 26464kb

input:

252
341597849 126 127
341597853 125 126
852529461 126 128
852529462 123 127
852529458 124 126
780677154 126 127
780677159 125 126
629345373 126 128
629345368 125 127
629345373 117 132
183781736 116 131
183781744 115 130
183781740 114 129
183781741 113 128
203771697 112 127
203771692 111 126
36739089...

output:

-1
-1
-1
50000916
-1
-1
-1
50000863
-1
-1
-1
-1
-1
50000915
-1
-1
-1
-1
50000916

result:

ok 19 lines

Test #20:

score: 2
Accepted
time: 3ms
memory: 26532kb

input:

252
628913381 126 129
628913377 125 128
628913384 124 127
628913383 123 126
247792338 126 129
247792336 125 128
247792341 124 127
247792344 123 126
731723547 126 128
731723540 125 127
731723549 124 127
168050840 123 129
168050842 125 128
168050838 124 127
168050846 123 126
894945506 124 128
89494550...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000979
-1
-1
-1
-1
-1
-1
50000979
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000815
-1
50000979
50000967
-1
50000967
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000979
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300 lines

Test #21:

score: 2
Accepted
time: 0ms
memory: 26404kb

input:

250
599413832 125 127
599413830 124 126
599413833 123 125
509355271 125 128
509355270 121 129
509355268 120 128
509355265 119 127
101088551 125 128
101088552 124 127
101088556 123 126
101088546 122 125
834898056 125 127
834898059 124 126
834898053 112 126
852410932 111 126
852410939 124 125
90124065...

output:

-1
-1
-1
50000634
-1
50000980
-1
50000981
-1
-1
-1
50000808
50000981
-1
-1
-1
-1
-1
-1
50000981
-1
-1
-1
50000947
-1
-1
-1
-1
-1
-1
-1
-1
50000981
-1
-1
-1
50000731
-1
-1
-1
-1
50000977
50000981
-1
50000981
-1
-1
-1
50000878
-1
-1
50000977
-1
10494526
-1
-1
-1
-1
50000642
-1
50000981
50000981
-1
-1
...

result:

ok 280 lines

Test #22:

score: 2
Accepted
time: 6ms
memory: 26532kb

input:

254
683627071 127 132
683627064 126 131
683627068 125 130
769572360 124 129
769572357 123 128
769572351 122 127
695907438 121 140
695907440 120 139
695907445 119 138
695907436 118 137
575742431 117 136
575742423 126 129
575742427 125 128
575742432 124 127
154362662 127 129
154362662 126 128
15436265...

output:

50000758
-1
-1
-1
-1
50000806
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000806
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
203175
-1
-1
-1
50000806
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000774
-1
-1
-1
50000806
50000806
50000774
-1
-1
50000774
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
38449563...

result:

ok 300 lines

Test #23:

score: 2
Accepted
time: 6ms
memory: 26392kb

input:

250
109763402 125 128
109763408 124 127
109763411 123 126
109763401 122 125
184567952 125 126
184567942 124 125
899463597 125 126
899463593 124 125
749734025 125 127
749734031 124 126
749734022 123 125
732550400 114 172
732550395 113 171
732550394 112 170
775499362 111 169
775499367 110 168
77549937...

output:

-1
-1
50000865
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000982
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000982
-1
-1
50000982
-1
-1
-1
50000982
-1
50000982
50000981
-1
-1
-1
-1
-1
-1
50000982
-1
-1
50000981
-1
-1
-1
-1
-1
50000925
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000982
50000982
-1
-1
50000925
50000982
-1
-1
-1
-1
-1
-1
...

result:

ok 269 lines

Test #24:

score: 2
Accepted
time: 6ms
memory: 26424kb

input:

252
793248685 126 129
793248684 125 150
793248682 124 149
793248677 123 148
823049878 122 147
823049877 121 146
823049877 120 145
823049876 119 144
790305772 118 143
790305767 117 142
790305773 116 141
790305774 115 140
108177882 114 139
108177884 113 138
108177886 112 137
591740131 111 136
59174012...

output:

-1
-1
-1
-1
-1
-1
-1
-1
50000823
-1
-1
-1
-1
50000936
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000936
-1
50000813
50000932
50000936
50000936
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000936
-1
-1
50000935
-1
50000936
50000644
50000823
-1
-1
50000823
-1
-1
-1
-1
-1
50000823
-1
...

result:

ok 300 lines

Subtask #2:

score: 11
Accepted

Dependency #1:

100%
Accepted

Test #25:

score: 11
Accepted
time: 48ms
memory: 30152kb

input:

867
2342163 639 818
738276997 650 808
1669890 716 733
14902411 456 763
899007094 250 640
422634516 184 769
936109680 427 688
638713463 363 736
119468142 232 769
713258492 758 818
267306336 133 685
973810399 317 352
835929417 651 790
335127775 340 461
840490095 187 278
459253103 285 578
706538155 662...

output:

972231330
996450160
972231330
753895133
670078844
744182892
972231330
882517975
-1
249739764
891308260
912334718
912334718
972231330
966251412
960709741
972231330
-1
883689071
972231330
891308260
725033182
979458879
910170109
-1
996808251
-1
-1
858198338
-1
966251412
965284232
-1
761636040
515813871...

result:

ok 149168 lines

Test #26:

score: 11
Accepted
time: 9ms
memory: 26876kb

input:

2000
735013405 19 323
438296241 1396 1894
24046243 979 1614
709242874 287 491
798805511 41 960
804692776 1080 1426
590054369 1577 1903
435774303 291 1883
529488852 1844 1920
414611064 1879 1927
721973791 1557 1624
478157232 1801 1932
427227260 1633 1782
626616969 1344 1592
153512861 794 1986
6168350...

output:

753289711
952146433
646264879
979749485
663981697
-1
-1
871956646
985790328
850936448
929310774
974418670
979749485
900371406
765410804
935458100
979749485
855484352
929310774
183887845
940122763
983202188
991778171
985174409
991778171
983202188
985790328
659942116
991778171
940795744
979749485
9857...

result:

ok 14687 lines

Test #27:

score: 11
Accepted
time: 78ms
memory: 31328kb

input:

1641
750442988 1519 1578
564719763 521 1482
664000672 732 1531
672344036 466 856
964649664 1375 1469
854930075 614 1363
648923774 52 889
737387688 1166 1508
588670044 639 933
154573679 1341 1381
273609238 1211 1304
52983135 780 871
835318106 634 1053
70005585 1318 1586
670737974 964 1578
765809363 1...

output:

988589964
910990781
-1
-1
974497621
978813240
880982968
946105175
978339368
976001015
771653039
966574970
964092250
297170232
839707712
988589964
903481263
988589964
641956704
990104293
791947724
812745209
966574970
942171242
988589964
978339368
903481263
946105175
703013450
988589964
-1
974497621
9...

result:

ok 200000 lines

Test #28:

score: 11
Accepted
time: 76ms
memory: 31060kb

input:

2000
378362905 1552 1701
356507721 845 1086
426722694 1404 1596
604732888 317 1345
763649006 820 1473
654782832 722 1103
109974358 1959 1990
382031287 366 516
957573396 778 1014
348062643 1063 1536
784725696 753 1422
783386041 827 934
404011830 1691 1756
61590501 984 1671
215463566 648 999
111318418...

output:

945118467
933512747
986749120
960291198
716720534
962548217
812007296
960362489
830671376
981873266
-1
885395403
982278260
982278260
-1
981873266
916828625
988611949
982278260
724820450
986749120
126354869
982278260
976158610
945118467
628282356
901652856
982278260
952784939
977527909
986749120
8853...

result:

ok 200000 lines

Test #29:

score: 11
Accepted
time: 47ms
memory: 30208kb

input:

961
675456110 504 868
448492118 774 794
820890604 232 508
516692295 40 427
426994513 280 570
436850287 804 914
353897431 748 878
909933991 519 841
450603599 486 582
709868603 642 802
601358700 71 638
500524474 789 822
303746814 68 695
49155004 183 711
65634174 766 915
300210427 672 776
836488160 173...

output:

752707030
672921906
333788664
979410699
968777257
333788664
762437108
991315435
979410699
-1
984163192
990183361
715987915
-1
973200763
979410699
945063489
979410699
-1
991315435
979410699
356380219
991315435
333788664
715987915
627417570
-1
948382191
991315435
945063489
880192870
991315435
67292190...

result:

ok 147821 lines

Test #30:

score: 11
Accepted
time: 45ms
memory: 29896kb

input:

2000
268216784 1914 1925
387013021 433 1861
835840160 678 1509
338097708 1425 1488
447998961 153 1789
114944800 1669 1694
260632256 1257 1603
401080358 506 1361
293253696 1806 1840
367482259 333 898
824267616 1644 1719
227829760 150 1076
812559432 1189 1601
338085342 398 616
594558937 135 859
739319...

output:

197651708
923094571
985899497
867809859
997725559
966904682
972030131
990912957
990912957
-1
985899497
-1
909066674
985899497
953715951
797075611
847921634
963773470
-1
990912957
887443887
668874018
-1
-1
787943574
987820224
982509219
-1
921238857
985899497
996143698
957303997
-1
990912957
921238857...

result:

ok 132636 lines

Test #31:

score: 11
Accepted
time: 49ms
memory: 30472kb

input:

270
221739989 75 116
882531779 29 181
231194092 136 199
709010205 160 235
544740779 205 242
952882550 132 165
539116259 56 223
299400395 81 221
923810023 59 175
345905146 65 70
612187995 206 256
742288759 155 170
541001701 154 216
473527180 195 257
493500125 82 192
666181395 141 215
607149474 69 202...

output:

981866203
993799701
924697063
993799701
993799701
-1
-1
924697063
991969542
993799701
-1
983538910
937648922
208685366
991969542
-1
-1
-1
993799701
884942801
362719235
978654974
842629312
591387793
991969542
-1
208685366
-1
978654974
987675164
-1
991969542
-1
-1
937648922
738381964
-1
993799701
9937...

result:

ok 200000 lines

Test #32:

score: 11
Accepted
time: 77ms
memory: 31068kb

input:

2000
417068593 914 1924
777801873 1121 1878
221470340 771 1389
914008748 1152 1831
706748979 1739 1956
752038592 1307 1728
289949695 1068 1342
999202919 215 1287
477398378 527 798
197611565 1389 1957
798179437 695 842
894150402 1919 1988
798719056 22 126
555107337 1597 1857
321276949 719 1043
794816...

output:

540145466
992156184
986798980
980270765
997618936
632287677
986460207
454634336
821274391
891735153
-1
-1
721198518
-1
770674806
901698640
-1
-1
-1
982831329
741656148
965857536
986460207
971076416
992156184
821274391
971076416
-1
997618936
992156184
940035684
992156184
508431528
508431528
992156184...

result:

ok 200000 lines

Test #33:

score: 11
Accepted
time: 67ms
memory: 31328kb

input:

1209
242077832 735 885
85240073 424 1093
954216740 1100 1111
11667399 385 1069
202952807 374 725
886576575 150 597
465376592 478 510
961568023 502 545
433097368 677 1016
634314286 60 1087
504468650 446 569
460432133 158 216
212485904 603 938
13636641 599 682
210642973 830 873
645748836 1207 1207
350...

output:

968392059
884474978
972371310
964296718
-1
964296718
-1
839609435
952358828
-1
45874355
992350513
965165872
985554498
883840136
964296718
987152771
-1
994383235
972371310
964296718
-1
839609435
920431917
-1
839609435
918847479
968392059
905512292
964296718
568863966
603567961
964296718
918847479
-1
...

result:

ok 193193 lines

Test #34:

score: 11
Accepted
time: 37ms
memory: 28712kb

input:

2000
291682036 1513 1698
748510667 1556 1588
827360407 1575 1808
559890096 183 1744
918704609 808 1588
62268455 906 1527
145240975 1329 1411
480249205 433 1047
657768325 1477 1880
141414674 899 1939
17186802 728 1841
759021241 1778 1872
375425594 1565 1954
982578823 1076 1484
491858468 569 1181
5841...

output:

-1
984360844
991963197
803247178
980311267
956370394
-1
913151473
-1
984360844
991963197
984360844
-1
984360844
792274330
976088897
-1
981472015
967616719
951849562
894518784
984360844
918344852
910188819
809824787
981472015
993758819
986721925
-1
-1
672926896
913151473
716683269
-1
883966485
-1
-1
...

result:

ok 95641 lines

Test #35:

score: 11
Accepted
time: 80ms
memory: 31752kb

input:

1475
869352152 175 1339
311016796 706 1346
740742255 1236 1303
179585337 346 364
517427140 380 1337
720194533 222 341
211093914 180 1208
40361850 1205 1349
383940026 1194 1384
443693990 1019 1458
505035714 294 583
993768411 1029 1463
987537493 252 857
125258582 79 1009
846135230 258 1312
368411133 4...

output:

996711468
629139005
996711468
-1
-1
993464139
986051892
975051348
987824838
-1
-1
-1
988285431
993421269
885338591
987824838
993390153
986051892
986051892
-1
633451768
996711468
923977564
-1
993464139
357906087
993464139
307752998
-1
993464139
-1
-1
-1
973963369
860748908
307752998
923977564
9860518...

result:

ok 200000 lines

Test #36:

score: 11
Accepted
time: 80ms
memory: 31068kb

input:

2000
942501288 1714 1737
793815601 1190 1236
305422439 901 945
136758254 1598 1739
810202677 1671 1752
338125654 946 1989
35086992 1425 1750
657468728 710 1331
397843754 1662 1768
939897792 118 197
376653947 294 749
760644678 792 1577
402377185 1078 1777
930391147 1125 1612
27305011 1174 1973
593762...

output:

936859411
979259535
952778721
979259535
-1
982498107
830331734
993292293
-1
988515361
988515361
975167066
985475225
979259535
882707892
993292293
993292293
398202831
982498107
-1
-1
-1
989028038
141651596
987799242
882707892
952778721
985475225
806051884
971689975
982498107
989028038
-1
983214226
97...

result:

ok 200000 lines

Test #37:

score: 11
Accepted
time: 41ms
memory: 29184kb

input:

1952
204098824 976 978
204098825 975 977
204098833 974 976
675116417 976 979
675116422 975 978
675116414 974 977
675116421 973 976
91728676 976 978
91728680 975 977
91728678 974 976
847422782 976 979
847422785 975 978
847422789 974 977
847422792 973 976
146923798 976 979
146923795 975 978
146923794 ...

output:

-1
-1
-1
50000999
-1
-1
-1
50000984
-1
-1
-1
-1
50000999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000943
-1
50000983
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000999
-1
-1
-1
50000953
-1
-1
-1
-1
-1
-1
-1
-1
50000996
-1
50000999
-1
-1
-1
-1
-1
50000999
-1
-1
-1
50000947
50000999
-1
-1
50000999
-1
-1
-1
...

result:

ok 114453 lines

Test #38:

score: 11
Accepted
time: 71ms
memory: 30980kb

input:

1950
498635841 975 977
498635841 974 976
498635850 973 983
622910237 972 982
622910235 971 981
615483753 970 980
615483753 969 979
615483756 968 978
615483749 967 977
646309018 966 977
646309013 965 976
646309010 964 979
695343686 975 978
695343686 974 977
695343693 973 976
695343696 972 975
2803475...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
50000997
-1
-1
50000960
-1
50000966
50000658
-1
50000998
50000997
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000886
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #39:

score: 11
Accepted
time: 14ms
memory: 27212kb

input:

1956
807572391 978 981
807572384 977 980
807572393 976 979
807572391 975 979
169138800 978 980
169138798 973 993
169138807 972 992
217754381 971 991
217754379 970 990
217754374 969 989
186113900 968 988
186113901 967 987
186113908 966 986
186113899 965 985
778051120 964 984
778051126 963 983
7780511...

output:

-1
-1
50000994
-1
-1
-1
-1
-1
-1
50000993
50000994
-1
50000993
-1
-1
-1
50000993
-1
-1
-1
-1
-1
50000994
-1
-1
-1
50000985
-1
50000993
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000994
-1
-1
-1
-1
-1
-1
-1
-1
50000993
50000993
-1
-1
-1
50000985
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000994
-1
-1
-1
...

result:

ok 27384 lines

Test #40:

score: 11
Accepted
time: 75ms
memory: 31004kb

input:

1954
361275307 977 979
361275300 976 978
361275298 975 977
479989060 977 979
479989061 976 978
479989055 972 978
804710084 977 978
804710076 976 977
761357037 977 980
761357040 976 979
761357033 975 978
761357033 966 979
301692323 965 978
301692315 976 977
232729624 977 979
232729623 976 978
2327296...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000985
-1
-1
-1
-1
-1
50000968
-1
50000998
-1
-1
-1
-1
-1
50000999
-1
-1
-1
-1
50000980
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000995
-1
-1
-1
-1
-1
-1
50000996
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000996
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #41:

score: 11
Accepted
time: 55ms
memory: 30272kb

input:

1950
946532903 975 977
946532908 974 976
946532910 973 975
305535891 975 976
305535893 974 975
381184467 975 978
381184463 974 977
381184465 973 976
381184469 972 975
825029929 975 978
825029932 974 977
825029925 973 976
825029926 972 975
683165181 962 978
683165177 974 977
683165182 973 976
6831651...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000995
-1
-1
-1
-1
-1
50000995
50000995
-1
-1
50000985
-1
50000988
50000994
-1
-1
50000985
-1
50000985
-1
-1
50000995
-1
-1
50000984
-1
-1
-1
-1
50000956
-1
50000995
-1
-1
50000985
-1
-1
-1
-1
50000995
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 145611 lines

Test #42:

score: 11
Accepted
time: 75ms
memory: 30852kb

input:

1952
772157166 976 977
772157167 975 976
104947842 976 977
104947839 973 977
120957499 972 977
120957502 975 976
885580889 976 979
885580891 975 978
885580897 974 977
885580890 973 976
930947278 976 978
930947276 975 977
930947271 974 976
99853528 976 977
99853530 975 976
182688526 976 978
182688528...

output:

-1
-1
-1
-1
-1
-1
-1
50000990
-1
-1
-1
-1
-1
50000993
-1
-1
50000988
50000993
-1
50000988
50001000
-1
50000990
-1
-1
-1
-1
-1
50000951
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
50000993
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
50000776
-1
50000867
-1
-1
50000971
-1
50000951
-1
500010...

result:

ok 200000 lines

Test #43:

score: 11
Accepted
time: 24ms
memory: 28220kb

input:

1950
583581828 975 976
583581827 974 975
221535961 975 976
221535969 972 1032
727470097 971 1031
727470103 970 1030
742534269 969 1029
742534268 968 1028
742534259 967 1027
742534264 966 1026
449807506 965 1025
449807496 964 1024
449807500 963 1023
449807499 962 1022
188878182 961 1021
188878179 960...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000980
-1
-1
-1
-1
-1
-1
-1
50000980
-1
-1
-1
-1
-1
50000992
-1
50000999
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
50000969
-1
50000998
50000998
-1
-1
-1
-1
50000999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000999
50000998
-1
-1
-1
...

result:

ok 65219 lines

Test #44:

score: 11
Accepted
time: 71ms
memory: 30952kb

input:

1954
445478926 977 978
445478920 976 977
724641525 977 978
724641519 974 1538
329316258 973 1537
329316265 972 1536
329316256 971 1535
329316262 970 1534
822283831 969 1533
822283833 968 1532
822283824 967 1531
822283829 966 1530
706433548 965 1529
706433539 964 1528
706433543 963 1527
423698435 962...

output:

-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000994
-1
-1
-1
50001000
-1
-1
-1
-1
50001000
-1
-1
-1
50000992
-1
-1
-1
-1
-1
50000899
-1
-1
-1
50000995
-1
-1
50000994
50000994
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000936
-1
-1
-1
-1
325...

result:

ok 200000 lines

Test #45:

score: 11
Accepted
time: 12ms
memory: 27360kb

input:

1962
381965195 981 983
381965199 980 982
381965202 979 981
704751045 981 983
704751037 980 982
704751037 979 981
87934540 981 984
87934536 974 995
87934537 973 994
87934540 972 993
419623814 971 992
419623821 970 991
419623824 969 990
419623817 968 989
808779651 967 988
808779660 966 987
487846193 9...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
50000787
-1
-1
-1
50000922
-1
-1
-1
-1
-1
50000997
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000997
-1
50000997
-1
-1
50000998
-1
-1
-1
-1
-1
-1
50000988
50000933
...

result:

ok 33480 lines

Test #46:

score: 11
Accepted
time: 76ms
memory: 31016kb

input:

1954
237670117 977 979
237670119 976 978
237670121 975 977
294248937 974 987
294248927 973 986
294248935 972 985
294248929 971 984
592080572 970 983
592080580 969 982
592080570 968 981
836392176 977 980
836392174 976 979
836392184 975 978
836392180 974 977
255183803 977 979
255183809 976 978
2551838...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000942
-1
-1
-1
-1
-1
-1
-1
50000987
-1
50000987
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000987
-1
-1
-1
50000987
-1
-1
-1
-1
50000987
50000918
-1
-1
-1
-1
-1
-1
-1
50000678
-1
-1
50000987
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000987
...

result:

ok 200000 lines

Test #47:

score: 11
Accepted
time: 18ms
memory: 27724kb

input:

1950
826353977 975 976
826353984 974 977
741093284 973 977
741093288 972 976
741093283 971 975
640858411 975 977
640858411 974 976
640858401 973 975
656540528 975 977
656540525 966 977
656540530 965 976
197155287 964 976
197155283 963 979
11612692 962 978
11612694 974 977
11612693 973 976
11612690 9...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
50000983
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000985
50000958
-1
-1
-1
-1
-1
50000985
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000979
-1
-1
-1
-1
-1
50000985
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000984
-1
-1
-1
-1
...

result:

ok 50469 lines

Test #48:

score: 11
Accepted
time: 75ms
memory: 30992kb

input:

1952
716151336 976 979
716151328 975 978
716151327 974 977
716151334 973 976
427214963 976 978
427214964 975 977
427214959 974 977
508651030 976 979
508651035 968 989
508651028 967 988
508651027 966 987
372196043 965 986
372196034 964 985
372196037 963 984
100929368 962 983
100929369 961 982
1009293...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
50000931
-1
-1
-1
-1
50000998
-1
50000998
-1
-1
-1
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
50000966
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
50000998
-1
-1
-1
-1
-1
-1
-1
50000896
-1
-1
-1
-1
-1
50000998
-1
-1
-1
50000997
50000998
-1
-1
50000984
-1
...

result:

ok 200000 lines

Subtask #3:

score: 22
Accepted

Test #49:

score: 22
Accepted
time: 227ms
memory: 46292kb

input:

179825
2342163 108549 159456
738276997 86996 90187
1669890 80080 105339
14902411 174494 177180
899007094 135456 178826
422634516 81580 147876
936109680 77457 155526
638713463 81787 150676
119468142 164826 167174
713258492 52936 91838
267306336 157071 162761
973810399 10675 157410
835929417 149623 17...

output:

999974157

result:

ok single line: '999974157'

Test #50:

score: 22
Accepted
time: 266ms
memory: 48580kb

input:

200000
735013405 160382 180860
438296241 78818 157402
24046243 41160 42554
709242874 68247 71171
798805511 35999 117249
804692776 190921 191179
590054369 44526 199082
435774303 154400 189263
529488852 149648 183300
414611064 39654 99464
721973791 41375 122421
478157232 175554 192949
427227260 71502 ...

output:

999989439

result:

ok single line: '999989439'

Test #51:

score: 22
Accepted
time: 176ms
memory: 42260kb

input:

140501
750442988 29339 110318
564719763 85481 93022
664000672 28112 97092
672344036 17006 48276
964649664 41815 77021
854930075 16054 105679
648923774 111452 133228
737387688 128806 135693
588670044 30039 46461
154573679 106981 119381
273609238 109431 117274
52983135 54620 124272
835318106 51354 126...

output:

999989325

result:

ok single line: '999989325'

Test #52:

score: 22
Accepted
time: 258ms
memory: 48560kb

input:

200000
378362905 40423 112670
356507721 78546 147663
426722694 187260 197016
604732888 104517 196087
763649006 148861 173099
654782832 181828 187729
109974358 97945 146146
382031287 24999 103678
957573396 21047 184653
348062643 158294 198871
784725696 71475 90079
783386041 99900 156901
404011830 632...

output:

999980476

result:

ok single line: '999980476'

Test #53:

score: 22
Accepted
time: 110ms
memory: 36660kb

input:

92387
675456110 42040 73124
448492118 4768 5288
820890604 42012 65925
516692295 88590 91076
426994513 58150 65220
436850287 38202 61709
353897431 58494 61393
909933991 45383 77397
450603599 37378 56272
709868603 20786 77641
601358700 84995 90506
500524474 59927 76120
303746814 56398 84912
49155004 8...

output:

999949625

result:

ok single line: '999949625'

Test #54:

score: 22
Accepted
time: 265ms
memory: 48600kb

input:

200000
268216784 62758 71863
387013021 147599 166566
835840160 188284 195749
338097708 100650 149838
447998961 124371 149354
114944800 1782 63331
260632256 104844 163286
401080358 82727 120692
293253696 142252 171086
367482259 89982 157190
824267616 81931 158028
227829760 177597 191930
812559432 119...

output:

999973961

result:

ok single line: '999973961'

Test #55:

score: 22
Accepted
time: 217ms
memory: 47304kb

input:

173443
221739989 62924 155326
882531779 112974 136389
231194092 109126 171394
709010205 145181 150318
544740779 3767 107778
952882550 18105 123670
539116259 95985 104860
299400395 3702 8245
923810023 78183 168084
345905146 118606 136188
612187995 54755 82677
742288759 138017 165777
541001701 68870 1...

output:

999962806

result:

ok single line: '999962806'

Test #56:

score: 22
Accepted
time: 267ms
memory: 48612kb

input:

200000
417068593 15254 141376
777801873 195883 199983
221470340 97343 141897
914008748 65401 71603
706748979 157418 162435
752038592 35372 108558
289949695 93679 144851
999202919 42740 97857
477398378 26694 73961
197611565 120419 179490
798179437 195466 197334
894150402 138790 178261
798719056 65857...

output:

999924799

result:

ok single line: '999924799'

Test #57:

score: 22
Accepted
time: 35ms
memory: 31756kb

input:

31707
242077832 26159 27495
85240073 6754 24533
954216740 6304 9141
11667399 29249 29757
202952807 4700 12419
886576575 5206 14374
465376592 29460 30574
961568023 16326 24339
433097368 5927 11738
634314286 1462 26252
504468650 29520 30727
460432133 5706 16152
212485904 8955 26978
13636641 11525 1204...

output:

999738376

result:

ok single line: '999738376'

Test #58:

score: 22
Accepted
time: 260ms
memory: 48448kb

input:

200000
291682036 63508 71666
748510667 198287 198799
827360407 24129 24696
559890096 87815 154106
918704609 33273 185223
62268455 9722 166063
145240975 143917 183188
480249205 8006 130075
657768325 185362 187239
141414674 120283 165081
17186802 134837 178175
759021241 112494 158114
375425594 140328 ...

output:

999993693

result:

ok single line: '999993693'

Test #59:

score: 22
Accepted
time: 157ms
memory: 41708kb

input:

125300
869352152 23399 25457
311016796 81651 98224
740742255 93693 121325
179585337 118976 120533
517427140 20720 51512
720194533 12949 51320
211093914 47863 57367
40361850 39185 87359
383940026 69333 93615
443693990 95982 114347
505035714 53242 84369
993768411 91118 108802
987537493 67919 124998
12...

output:

999969226

result:

ok single line: '999969226'

Test #60:

score: 22
Accepted
time: 263ms
memory: 48504kb

input:

200000
942501288 121403 175420
793815601 62426 101190
305422439 21487 41484
136758254 19569 83829
810202677 127628 192158
338125654 56010 94249
35086992 151025 160625
657468728 199153 199851
397843754 16522 115030
939897792 190434 191517
376653947 184280 190707
760644678 136469 199802
402377185 4350...

output:

999995834

result:

ok single line: '999995834'

Test #61:

score: 22
Accepted
time: 167ms
memory: 45536kb

input:

199954
309650510 99977 99980
309650514 99976 99979
309650520 99975 99978
309650515 99974 99977
764966678 99977 99978
764966681 99976 99977
468949173 99977 99978
468949174 99976 99977
694361564 99977 99978
694361567 99976 99977
747432192 99977 99980
747432200 99976 99979
747432193 99975 99978
7474321...

output:

50001001

result:

ok single line: '50001001'

Test #62:

score: 22
Accepted
time: 161ms
memory: 45180kb

input:

199952
108165962 99976 99979
108165958 99975 100045
108165966 99974 100044
108165959 99973 100043
170953775 99972 100042
170953777 99971 100041
170953769 99970 100040
170953779 99969 100039
304074557 99968 100038
304074557 99967 100037
304074554 99966 100036
561435170 99965 100035
561435178 99964 10...

output:

50001001

result:

ok single line: '50001001'

Test #63:

score: 22
Accepted
time: 155ms
memory: 44532kb

input:

199952
649443497 99976 99978
649443490 99975 99977
649443489 99974 99976
598126309 99976 99977
598126303 99975 99976
313728868 99976 99977
313728872 99975 99976
216456418 99976 99978
216456408 99975 99977
216456408 99974 99976
848698916 99976 99978
848698923 99975 99977
848698913 99974 99976
8603700...

output:

50001001

result:

ok single line: '50001001'

Test #64:

score: 22
Accepted
time: 132ms
memory: 44660kb

input:

199956
876931600 99978 99980
876931592 99977 99979
876931593 99976 99978
369277741 99978 100000
369277741 99977 99999
369277744 99976 99998
369277746 99975 99997
369277740 99974 99996
369277744 99973 99995
369277740 99972 99994
369277746 99971 99993
369277747 99970 99992
369277743 99969 99991
369277...

output:

50001001

result:

ok single line: '50001001'

Test #65:

score: 22
Accepted
time: 178ms
memory: 45940kb

input:

199954
912377013 99977 99980
912377011 99976 99979
912377006 99975 99986
912377007 99974 99985
750300719 99977 99984
750300720 99976 99983
750300728 99975 99982
653107877 99974 99981
653107884 99973 99980
758967200 99977 99980
758967195 99976 99979
758967205 99975 99978
758967202 99974 99977
2048227...

output:

50001001

result:

ok single line: '50001001'

Test #66:

score: 22
Accepted
time: 165ms
memory: 45328kb

input:

199956
263463511 99978 99979
263463504 99977 99978
892866429 99978 99981
892866419 99977 99980
892866427 99976 99979
892866428 99975 99978
433129268 99978 99981
433129266 99977 99980
433129260 99976 99979
433129258 99975 99978
548975408 99978 99980
548975405 99977 99979
548975399 99976 99978
2146881...

output:

50001001

result:

ok single line: '50001001'

Test #67:

score: 22
Accepted
time: 168ms
memory: 44868kb

input:

199954
414745043 99977 99979
414745040 99976 99978
414745048 99975 99989
656967992 99974 99988
656967996 99973 99987
656968000 99972 99986
507724558 99971 99985
507724559 99970 99984
507724556 99969 99983
507724553 99968 99982
259130314 99977 99979
259130310 99976 99978
259130310 99975 99979
3316003...

output:

50001001

result:

ok single line: '50001001'

Test #68:

score: 22
Accepted
time: 161ms
memory: 44968kb

input:

199950
557717783 99975 99976
557717791 99974 99975
359596173 99975 99976
359596183 99974 99975
289806748 99975 99978
289806748 99974 99977
289806745 99973 99976
289806754 99972 99975
473188290 99967 100319
473188287 99966 100318
789892823 99965 100317
789892827 99964 100316
175696648 99963 100315
17...

output:

50001001

result:

ok single line: '50001001'

Test #69:

score: 22
Accepted
time: 144ms
memory: 45408kb

input:

199952
431775777 99976 99979
431775775 99975 99978
431775784 99974 99977
431775776 99973 99976
350771836 99972 100009
350771840 99971 100008
350771835 99970 100007
350771837 99969 100006
139983014 99968 100005
139983009 99967 100004
139983007 99966 100003
679731873 99965 100002
679731874 99964 10000...

output:

50001001

result:

ok single line: '50001001'

Test #70:

score: 22
Accepted
time: 158ms
memory: 45268kb

input:

199950
220171276 99975 99976
220171271 99974 99993
576065653 99973 99992
576065662 99972 99991
576065654 99971 99990
622429724 99970 99989
622429716 99969 99988
758348938 99968 99987
758348936 99967 99986
758348939 99966 99985
127092419 99965 99984
127092415 99964 99983
118309648 99963 99982
1183096...

output:

50001001

result:

ok single line: '50001001'

Test #71:

score: 22
Accepted
time: 169ms
memory: 45296kb

input:

199952
582712794 99976 99977
582712793 99975 99976
66349177 99974 100018
66349183 99973 100017
66349183 99972 100016
216507778 99971 100015
216507781 99970 100014
216507778 99969 100013
216507773 99968 100012
593107280 99967 100011
593107279 99966 100010
593107276 99965 100009
640920277 99964 100008...

output:

50001001

result:

ok single line: '50001001'

Test #72:

score: 22
Accepted
time: 128ms
memory: 44288kb

input:

199954
41802970 99977 99978
41802972 99976 99977
631895260 99977 99978
631895258 99976 99977
104306880 99977 99979
104306883 99976 99978
104306886 99975 99978
695515329 99976 99980
695515325 99976 99979
695515326 99975 99978
695515321 99974 99977
458654444 99977 99978
458654449 99976 99978
330137457...

output:

50001001

result:

ok single line: '50001001'

Subtask #4:

score: 65
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #73:

score: 65
Accepted
time: 370ms
memory: 53492kb

input:

179825
2342163 108549 159456
738276997 86996 90187
1669890 80080 105339
14902411 174494 177180
899007094 135456 178826
422634516 81580 147876
936109680 77457 155526
638713463 81787 150676
119468142 164826 167174
713258492 52936 91838
267306336 157071 162761
973810399 10675 157410
835929417 149623 17...

output:

999527451
999546180
223420066
999792656
999748408
999527451
999792656
998559911
999941495
999699622
999844689
999785684
964366104
999384950
999922184
999546180
998418346
999974157
999922184
999922184
999779650
999699622
999869920
999200740
999974157
993403882
999699622
999838467
986741923
999941495
...

result:

ok 149168 lines

Test #74:

score: 65
Accepted
time: 286ms
memory: 49348kb

input:

200000
735013405 160382 180860
438296241 78818 157402
24046243 41160 42554
709242874 68247 71171
798805511 35999 117249
804692776 190921 191179
590054369 44526 199082
435774303 154400 189263
529488852 149648 183300
414611064 39654 99464
721973791 41375 122421
478157232 175554 192949
427227260 71502 ...

output:

999739769
945371876
999989439
999693017
999578577
999989439
999121369
999450342
983034357
999258539
998886995
999989439
999693017
999554779
999693017
999675194
999638787
999989439
999766205
999343915
999989439
999693017
999675194
999989439
999556276
999989439
999160117
999675194
999927248
999989439
...

result:

ok 14687 lines

Test #75:

score: 65
Accepted
time: 354ms
memory: 50032kb

input:

140501
750442988 29339 110318
564719763 85481 93022
664000672 28112 97092
672344036 17006 48276
964649664 41815 77021
854930075 16054 105679
648923774 111452 133228
737387688 128806 135693
588670044 30039 46461
154573679 106981 119381
273609238 109431 117274
52983135 54620 124272
835318106 51354 126...

output:

992033715
998937926
999774241
999926815
999708154
999708154
999742887
999708154
-1
999757873
999989325
998367873
997135395
999708154
998255485
-1
985409907
999584516
987117628
999538060
999947094
963953317
999757873
997999118
987844887
996628542
-1
999989325
999429130
999805980
998255485
999910317
-...

result:

ok 200000 lines

Test #76:

score: 65
Accepted
time: 466ms
memory: 56576kb

input:

200000
378362905 40423 112670
356507721 78546 147663
426722694 187260 197016
604732888 104517 196087
763649006 148861 173099
654782832 181828 187729
109974358 97945 146146
382031287 24999 103678
957573396 21047 184653
348062643 158294 198871
784725696 71475 90079
783386041 99900 156901
404011830 632...

output:

999824896
999976134
999980476
726514486
999976134
992310991
999824896
997692464
998376873
997201049
-1
996846565
999882859
997003924
995535444
998998675
999869096
999976134
999980476
999980476
995049938
997877405
998000273
999754549
997003924
999568866
888566597
999824896
999980476
997248308
9999753...

result:

ok 200000 lines

Test #77:

score: 65
Accepted
time: 215ms
memory: 41744kb

input:

92387
675456110 42040 73124
448492118 4768 5288
820890604 42012 65925
516692295 88590 91076
426994513 58150 65220
436850287 38202 61709
353897431 58494 61393
909933991 45383 77397
450603599 37378 56272
709868603 20786 77641
601358700 84995 90506
500524474 59927 76120
303746814 56398 84912
49155004 8...

output:

999743765
975851886
996124980
999872254
999659661
999371550
999721401
958932112
995427219
998618273
999773085
999455191
996326312
998650548
994654146
999870806
999455191
999371550
999870806
999721401
996603442
998784246
995647514
990505650
999455191
999870806
999455191
997438672
989677493
999659661
...

result:

ok 147821 lines

Test #78:

score: 65
Accepted
time: 411ms
memory: 54436kb

input:

200000
268216784 62758 71863
387013021 147599 166566
835840160 188284 195749
338097708 100650 149838
447998961 124371 149354
114944800 1782 63331
260632256 104844 163286
401080358 82727 120692
293253696 142252 171086
367482259 89982 157190
824267616 81931 158028
227829760 177597 191930
812559432 119...

output:

909857052
994961762
999441388
984927196
999968137
997336517
999742483
999441388
999731487
999973961
999441388
999420260
993646956
852745349
999731487
997336517
999973961
998313067
999973961
999973961
962682865
999420260
996718004
999712623
997710038
992970056
998894331
999973961
861997532
999968137
...

result:

ok 132636 lines

Test #79:

score: 65
Accepted
time: 421ms
memory: 54744kb

input:

173443
221739989 62924 155326
882531779 112974 136389
231194092 109126 171394
709010205 145181 150318
544740779 3767 107778
952882550 18105 123670
539116259 95985 104860
299400395 3702 8245
923810023 78183 168084
345905146 118606 136188
612187995 54755 82677
742288759 138017 165777
541001701 68870 1...

output:

999768797
920555394
999897972
995772727
998392400
998484699
998484699
999916672
998484699
991900860
999962806
999897972
999365557
999459149
877608533
999916672
998355115
999789119
998420263
997488780
999789119
999746674
999962806
999459149
998821211
999897972
997616614
917694170
999789119
999651915
...

result:

ok 200000 lines

Test #80:

score: 65
Accepted
time: 467ms
memory: 56536kb

input:

200000
417068593 15254 141376
777801873 195883 199983
221470340 97343 141897
914008748 65401 71603
706748979 157418 162435
752038592 35372 108558
289949695 93679 144851
999202919 42740 97857
477398378 26694 73961
197611565 120419 179490
798179437 195466 197334
894150402 138790 178261
798719056 65857...

output:

997693617
999840148
995288194
999491088
999840148
999643175
999183654
998744974
999565876
-1
999840148
999683779
947771808
997804665
981508154
999806897
969750570
999643175
982975517
999643175
999806897
993978587
999840148
999643175
999840148
999863480
997148220
998744974
999643175
995860572
9995658...

result:

ok 200000 lines

Test #81:

score: 65
Accepted
time: 160ms
memory: 35036kb

input:

31707
242077832 26159 27495
85240073 6754 24533
954216740 6304 9141
11667399 29249 29757
202952807 4700 12419
886576575 5206 14374
465376592 29460 30574
961568023 16326 24339
433097368 5927 11738
634314286 1462 26252
504468650 29520 30727
460432133 5706 16152
212485904 8955 26978
13636641 11525 1204...

output:

984947203
999258078
948851176
996950308
923576303
979182449
192921623
999485227
999563869
997295014
998380371
999435461
995845506
948297661
-1
999563869
918972637
511697595
-1
998255076
999306479
999306479
999435461
984287542
998218620
-1
984274611
998633730
945257561
997736366
995884970
839470977
9...

result:

ok 193193 lines

Test #82:

score: 65
Accepted
time: 371ms
memory: 53132kb

input:

200000
291682036 63508 71666
748510667 198287 198799
827360407 24129 24696
559890096 87815 154106
918704609 33273 185223
62268455 9722 166063
145240975 143917 183188
480249205 8006 130075
657768325 185362 187239
141414674 120283 165081
17186802 134837 178175
759021241 112494 158114
375425594 140328 ...

output:

999798398
998058866
994385519
999841597
966219773
999715012
999968266
987087972
999799612
999926496
999650036
995242084
999524920
999370331
995242084
997355571
999426544
999935543
995939309
999475166
999106423
999841597
999910466
999475166
999715012
998880945
999935543
999650036
999323118
975852187
...

result:

ok 95641 lines

Test #83:

score: 65
Accepted
time: 317ms
memory: 48664kb

input:

125300
869352152 23399 25457
311016796 81651 98224
740742255 93693 121325
179585337 118976 120533
517427140 20720 51512
720194533 12949 51320
211093914 47863 57367
40361850 39185 87359
383940026 69333 93615
443693990 95982 114347
505035714 53242 84369
993768411 91118 108802
987537493 67919 124998
12...

output:

-1
982405470
990906132
999593630
-1
985969862
999834557
999214491
997269606
999002388
999130825
-1
985969862
999002388
999834557
996787777
907667902
999214491
999328068
994116417
988906021
999593630
967763448
862979474
473688100
999884740
999707250
994116417
999214491
999466198
998085319
999804573
-...

result:

ok 200000 lines

Test #84:

score: 65
Accepted
time: 472ms
memory: 56572kb

input:

200000
942501288 121403 175420
793815601 62426 101190
305422439 21487 41484
136758254 19569 83829
810202677 127628 192158
338125654 56010 94249
35086992 151025 160625
657468728 199153 199851
397843754 16522 115030
939897792 190434 191517
376653947 184280 190707
760644678 136469 199802
402377185 4350...

output:

999899890
999823205
999590329
999749719
993428136
999683051
999176517
961945375
999381150
999788932
999788932
941728997
999899890
996279422
999701981
999672040
999705377
982178664
989169595
998293616
999982006
999706417
971872666
999519082
999683051
999788932
999899890
998118237
999949216
961945375
...

result:

ok 200000 lines

Test #85:

score: 65
Accepted
time: 283ms
memory: 51008kb

input:

199954
309650510 99977 99980
309650514 99976 99979
309650520 99975 99978
309650515 99974 99977
764966678 99977 99978
764966681 99976 99977
468949173 99977 99978
468949174 99976 99977
694361564 99977 99978
694361567 99976 99977
747432192 99977 99980
747432200 99976 99979
747432193 99975 99978
7474321...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
50001000
-1
50001001
35777803
-1
-1
-1
-1
-1
-1
50001000
50001000
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000965
50001000
-1
50001001
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
...

result:

ok 114453 lines

Test #86:

score: 65
Accepted
time: 338ms
memory: 53176kb

input:

199952
108165962 99976 99979
108165958 99975 100045
108165966 99974 100044
108165959 99973 100043
170953775 99972 100042
170953777 99971 100041
170953769 99970 100040
170953779 99969 100039
304074557 99968 100038
304074557 99967 100037
304074554 99966 100036
561435170 99965 100035
561435178 99964 10...

output:

-1
-1
50001000
50001001
-1
-1
50001000
-1
50001001
50001001
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
50001001
-1
-1
50001000
-1
-1
50001000
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
50001001
50001000
-1
50001000
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #87:

score: 65
Accepted
time: 183ms
memory: 45984kb

input:

199952
649443497 99976 99978
649443490 99975 99977
649443489 99974 99976
598126309 99976 99977
598126303 99975 99976
313728868 99976 99977
313728872 99975 99976
216456418 99976 99978
216456408 99975 99977
216456408 99974 99976
848698916 99976 99978
848698923 99975 99977
848698913 99974 99976
8603700...

output:

50001001
50001000
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000947
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 27384 lines

Test #88:

score: 65
Accepted
time: 319ms
memory: 52620kb

input:

199956
876931600 99978 99980
876931592 99977 99979
876931593 99976 99978
369277741 99978 100000
369277741 99977 99999
369277744 99976 99998
369277746 99975 99997
369277740 99974 99996
369277744 99973 99995
369277740 99972 99994
369277746 99971 99993
369277747 99970 99992
369277743 99969 99991
369277...

output:

-1
-1
-1
-1
50000997
-1
-1
-1
50001000
-1
-1
-1
50001000
-1
50000816
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
50001000
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
50001000
-1
-1
...

result:

ok 200000 lines

Test #89:

score: 65
Accepted
time: 312ms
memory: 52176kb

input:

199954
912377013 99977 99980
912377011 99976 99979
912377006 99975 99986
912377007 99974 99985
750300719 99977 99984
750300720 99976 99983
750300728 99975 99982
653107877 99974 99981
653107884 99973 99980
758967200 99977 99980
758967195 99976 99979
758967205 99975 99978
758967202 99974 99977
2048227...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
34214538
-1
-1
-1
50001000
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
50001000
50001001
-1
-1
50001000
-1
50000798
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 145611 lines

Test #90:

score: 65
Accepted
time: 349ms
memory: 53352kb

input:

199956
263463511 99978 99979
263463504 99977 99978
892866429 99978 99981
892866419 99977 99980
892866427 99976 99979
892866428 99975 99978
433129268 99978 99981
433129266 99977 99980
433129260 99976 99979
433129258 99975 99978
548975408 99978 99980
548975405 99977 99979
548975399 99976 99978
2146881...

output:

-1
-1
-1
-1
-1
-1
695249
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
50000999
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
50001000
-1
50001000
50000999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
50000999
-1
-1
-1
-1
-1
-1
50001000
50001000
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 200000 lines

Test #91:

score: 65
Accepted
time: 221ms
memory: 48220kb

input:

199954
414745043 99977 99979
414745040 99976 99978
414745048 99975 99989
656967992 99974 99988
656967996 99973 99987
656968000 99972 99986
507724558 99971 99985
507724559 99970 99984
507724556 99969 99983
507724553 99968 99982
259130314 99977 99979
259130310 99976 99978
259130310 99975 99979
3316003...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
50000999
-1
50001000
-1
-1
50001000
-1
-1
-1
-1
50001000
-1
50001000
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
50001000
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
500010...

result:

ok 65219 lines

Test #92:

score: 65
Accepted
time: 350ms
memory: 52896kb

input:

199950
557717783 99975 99976
557717791 99974 99975
359596173 99975 99976
359596183 99974 99975
289806748 99975 99978
289806748 99974 99977
289806745 99973 99976
289806754 99972 99975
473188290 99967 100319
473188287 99966 100318
789892823 99965 100317
789892827 99964 100316
175696648 99963 100315
17...

output:

-1
-1
50001000
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
50001000
-1
...

result:

ok 200000 lines

Test #93:

score: 65
Accepted
time: 184ms
memory: 47288kb

input:

199952
431775777 99976 99979
431775775 99975 99978
431775784 99974 99977
431775776 99973 99976
350771836 99972 100009
350771840 99971 100008
350771835 99970 100007
350771837 99969 100006
139983014 99968 100005
139983009 99967 100004
139983007 99966 100003
679731873 99965 100002
679731874 99964 10000...

output:

-1
-1
-1
-1
14178188
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
50001001
-1
-1
-1
-1
50001000
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
500010...

result:

ok 33480 lines

Test #94:

score: 65
Accepted
time: 330ms
memory: 53220kb

input:

199950
220171276 99975 99976
220171271 99974 99993
576065653 99973 99992
576065662 99972 99991
576065654 99971 99990
622429724 99970 99989
622429716 99969 99988
758348938 99968 99987
758348936 99967 99986
758348939 99966 99985
127092419 99965 99984
127092415 99964 99983
118309648 99963 99982
1183096...

output:

-1
-1
-1
50001000
-1
-1
50001001
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
18107
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
50001001
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
50000955
-1
50001001
-1
-1
...

result:

ok 200000 lines

Test #95:

score: 65
Accepted
time: 217ms
memory: 47996kb

input:

199952
582712794 99976 99977
582712793 99975 99976
66349177 99974 100018
66349183 99973 100017
66349183 99972 100016
216507778 99971 100015
216507781 99970 100014
216507778 99969 100013
216507773 99968 100012
593107280 99967 100011
593107279 99966 100010
593107276 99965 100009
640920277 99964 100008...

output:

-1
50001000
-1
-1
50001001
-1
-1
-1
-1
-1
-1
50000968
-1
50001000
50000994
-1
-1
-1
-1
50001000
50001000
-1
-1
50001001
-1
-1
50000655
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
50001001
-1
50001001
50001001
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 50469 lines

Test #96:

score: 65
Accepted
time: 334ms
memory: 52148kb

input:

199954
41802970 99977 99978
41802972 99976 99977
631895260 99977 99978
631895258 99976 99977
104306880 99977 99979
104306883 99976 99978
104306886 99975 99978
695515329 99976 99980
695515325 99976 99979
695515326 99975 99978
695515321 99974 99977
458654444 99977 99978
458654449 99976 99978
330137457...

output:

50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
50000999
-1
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
43237437
40943505
-1
-1
-1
-1
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
50001001
-1
-1
-1
-1
-1
-1
50001001
-1
-1
-1
-1
-1
-1
-1
-1
50001000
-1
-1
50000999
-1
50001000
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
500009...

result:

ok 200000 lines

Extra Test:

score: 0
Extra Test Passed