QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296253#4918. 染色MEKHANE100 ✓3657ms272148kbC++174.1kb2024-01-02 16:08:352024-01-02 16:08:35

Judging History

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

  • [2024-01-02 16:08:35]
  • 评测
  • 测评结果:100
  • 用时:3657ms
  • 内存:272148kb
  • [2024-01-02 16:08:35]
  • 提交

answer

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define pi pair<int,ui>
#define fi first
#define se second
#define mid (l+r)/2
#define ls k*2
#define rs k*2+1
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int N=3e5+5,inf=2e9;
int n,q;
struct pq{
    priority_queue<int,vector<int>,greater<int>> q1,q2;
    void push(int x){q1.push(x);}
    void pop(int x){q2.push(x);}
    bool empty(){return q1.size()==q2.size();}
    int top(){while(!q2.empty()&&q2.top()==q1.top()) q2.pop(),q1.pop(); return q1.top();}
};
pi operator +(pi x,pi y){return x.fi!=y.fi?min(x,y):pi{x.fi,x.se+y.se};}
struct sgt{
    pi t[4*N]; ull sum[4*N],tg1[4*N],tg2[4*N]; ui siz[4*N]; pq q[4*N];
    void upd(int k){
        t[k]=(t[ls]+t[rs]);
        if(!q[k].empty()&&q[k].top()<=t[k].fi) t[k]={q[k].top(),siz[k]};
        sum[k]=sum[ls]+sum[rs];
    }
    void adt1(int k,ull z){tg1[k]+=z,sum[k]+=siz[k]*z;}
    void adt2(int k,ull z,int mi){
        if(!q[k].empty()&&q[k].top()==mi) adt1(k,z);
        else if(t[k].fi==mi) tg2[k]+=z,sum[k]+=t[k].se*z;
    }
    void p_d(int k){
        if(tg1[k]) adt1(ls,tg1[k]),adt1(rs,tg1[k]),tg1[k]=0;
        if(tg2[k]) adt2(ls,tg2[k],t[k].fi),adt2(rs,tg2[k],t[k].fi),tg2[k]=0;
    }
    void build(int k,int l,int r){
        siz[k]=r-l+1;
        if(l==r){t[k]={inf,0}; return ;}
        build(ls,l,mid),build(rs,mid+1,r),upd(k);
    }
    void add(int k,int l,int r,int L,int R,ull z){
        if(L<=l&&r<=R){adt1(k,z); return ;}
        p_d(k);
        if(L<=mid) add(ls,l,mid,L,R,z);
        if(mid<R) add(rs,mid+1,r,L,R,z);
        upd(k);
    }
    void gx(int k,int l,int r,int L,int R,int z,ull z1){
        if(!q[k].empty()&&q[k].top()==z){add(k,l,r,L,R,z1); return ;}
        if(L<=l&&r<=R){adt2(k,z1,z); return ;}
        p_d(k);
        if(L<=mid) gx(ls,l,mid,L,R,z,z1);
        if(mid<R) gx(rs,mid+1,r,L,R,z,z1);
        upd(k);
    }
    void ins(int k,int l,int r,int L,int R,int z,int opt){
        if(L<=l&&r<=R){
            if(l!=r) p_d(k);
            if(opt) q[k].pop(z); else q[k].push(z);
            if(l!=r) t[k]=(t[ls]+t[rs]); else t[k]={inf,0};
            if(!q[k].empty()&&q[k].top()<=t[k].fi) t[k]={q[k].top(),siz[k]};
            return ;
        }p_d(k);
        if(L<=mid) ins(ls,l,mid,L,R,z,opt);
        if(mid<R) ins(rs,mid+1,r,L,R,z,opt);
        upd(k);
    }
    int qry(int k,int l,int r,int L,int R){
        if(L<=l&&r<=R) return t[k].fi;
        int res=(q[k].empty()?inf:q[k].top()); p_d(k);
        if(L<=mid) res=min(res,qry(ls,l,mid,L,R));
        if(mid<R) res=min(res,qry(rs,mid+1,r,L,R));
        return res;
    }
    ull qry1(int k,int l,int r,int L,int R){
        if(L<=l&&r<=R) return sum[k];
        ull res=0; p_d(k);
        if(L<=mid) res+=qry1(ls,l,mid,L,R);
        if(mid<R) res+=qry1(rs,mid+1,r,L,R);
        return res;
    }
}T;
struct qj{int l,r; bool friend operator <(qj x,qj y){return x.l==y.l?x.r<y.r:x.l<y.l;}};set<qj> se[N];
void add(int id,int l,int r){se[id].insert({l,r}),T.ins(1,1,n,l,r,id,0);}
void del(int id,int l,int r){se[id].erase({l,r}),T.ins(1,1,n,l,r,id,1);}
void split(int id,int x){
    auto it=se[id].lower_bound({x,inf});
    if(it!=se[id].begin()){
        it--; qj dq=(*it);
        if(dq.r>x) del(id,dq.l,dq.r),add(id,dq.l,x),add(id,x+1,dq.r);
    }
}
void tp(int id,int l,int r){
    split(id,l-1),split(id,r);
    while(1){
        auto it=se[id].lower_bound({l,0});
        if(it==se[id].end()||(*it).r>r) break;
        qj dq=(*it); del(id,dq.l,dq.r);
    }
}
signed main(){
    //freopen("minmex.in","r",stdin);
    //freopen("minmex.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>q,T.build(1,1,n);
    rep(i,1,q+1) add(i,1,n);
    while(q--){
        int opt,l,r,x; cin>>opt>>l>>r;
        if(opt==1) cin>>x,tp(x,l,r);
        else if(opt==2) cin>>x,tp(x,l,r),add(x,l,r);
        else if(opt==3){ull c; cin>>c; int dq=T.qry(1,1,n,l,r); T.gx(1,1,n,l,r,dq,c);}
        else cout<<T.qry1(1,1,n,l,r)<<'\n';
    }
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 21ms
memory: 106448kb

input:

1000 1000
3 722 914 2141556875752121755
3 323 347 6433743606947304931
2 142 206 439
2 117 840 195
2 127 502 56
3 168 707 15142638115094015116
4 190 257
2 88 976 475
1 319 867 351
1 682 889 409
2 406 446 196
3 28 35 4899387534800369959
2 291 546 150
1 528 617 128
1 58 122 251
2 381 400 276
4 510 958
...

output:

15128467772367689008
17361914246216994339
5483226026482017320
3033562207293358603
2081407883485577238
7431958406282818646
4664359672511637691
8517692808398202534
17884251128335023776
3389445997760709607
15161173652136060523
17246899135664170339
16659472119973467421
5618344994614112283
92650283427734...

result:

ok 288 tokens

Test #2:

score: 0
Accepted
time: 16ms
memory: 106512kb

input:

1000 1000
1 538 681 44
2 112 540 10
1 160 191 28
1 276 867 1
4 118 419
4 62 209
1 575 884 37
1 783 895 45
4 342 410
2 545 870 16
1 273 501 11
3 258 352 13270291835335737625
3 490 514 5208698592597571883
2 629 865 43
3 966 981 14431353048791951405
1 290 809 16
4 468 843
1 607 875 26
2 177 521 6
4 176...

output:

0
0
0
1090256298972435763
147836376791542005
2987455658418197192
17393388322162025577
0
15463425577465259729
5603739312727078592
9162759280430770517
5734982725161877299
17209386033616770563
4838930779004365643
849737692109005723
6426101344117061130
5419322161439603233
5062725202245147693
71096115354...

result:

ok 245 tokens

Test #3:

score: 0
Accepted
time: 15ms
memory: 106424kb

input:

1000 1000
3 99 666 17220025026447219412
4 5 483
3 749 845 16031212477837693538
3 133 609 17502764194597679430
1 20 226 5
4 251 561
4 633 824
4 200 311
4 519 771
1 441 468 4
1 143 922 2
3 125 229 12754000280540900298
1 498 505 6
1 363 450 3
2 271 554 3
1 114 704 4
2 120 814 2
3 690 982 45445988286128...

output:

7328512720450443476
7442164624875844502
14518824065043662144
15136137278022830944
9027578627713658176
14666047547670987011
9573739028108360400
15993305979184887208
14884581396130778517
17761136731703624839
13312122318790827838
14347674975080853967
17128890277609978434
9773479657321740818
15378095570...

result:

ok 256 tokens

Test #4:

score: 0
Accepted
time: 16ms
memory: 106364kb

input:

1000 1000
3 331 336 13313883338135403138
2 34 521 1
1 207 917 1
2 293 636 1
1 10 687 1
2 41 872 1
1 355 758 1
1 288 842 1
3 400 783 5775690383446019013
4 314 322
2 304 613 1
2 826 891 1
2 202 822 1
4 548 564
4 116 797
2 19 741 1
3 682 909 6383131735642614258
1 236 239 1
3 540 587 8352069600659472359...

output:

0
5953016150034565141
10352142132099319436
6096323733974212364
12116874695872864409
15347176369296045030
5941262347742323458
3620424356881155419
10127217571760838974
5461268237196718849
17374108689525300602
10962054618902200654
10589539750496832325
18040788904369214946
4431085881313941227
1086737541...

result:

ok 245 tokens

Test #5:

score: 0
Accepted
time: 7ms
memory: 106424kb

input:

1000 1000
4 508 569
3 464 647 9626512068323288850
1 261 912 260
4 11 44
4 277 438
4 284 694
2 58 226 212
1 457 503 39
2 706 712 21
4 284 619
1 512 792 423
2 157 161 53
4 277 536
1 366 980 414
1 316 876 190
3 371 886 9029081672906636708
4 194 444
2 745 753 461
3 213 319 890290010596372158
2 753 762 3...

output:

0
0
0
390789495368193264
7549612687959379704
1759106186637124642
4069257141547258216
0
17049456214560332466
12608950793396043246
15542879177249956503
5268553984485336740
3347535289204500833
1283339644428090794
900030301309717320
10617803241693535373
14165237887531480080
7981622196338660662
108862472...

result:

ok 249 tokens

Test #6:

score: 0
Accepted
time: 18ms
memory: 106452kb

input:

1000 1000
3 129 542 13655472611747991961
4 511 790
2 427 432 24
4 297 777
3 42 429 12538231273219784506
2 599 608 39
3 527 566 15984446643208694087
2 205 211 1
3 601 694 12523292657204424213
3 545 831 15344770091989840452
1 602 989 37
1 53 385 37
4 682 969
3 543 721 5478413773432004467
1 56 745 34
3...

output:

12700009880616055584
1938841074867628294
11101356538763217641
10137253135833169997
13873622059376146753
13337075822234643821
9115529121094266177
7669597812731439884
7653582597306726684
16408805096415770957
5310328737375184018
10833975347168974529
3499327095010911697
4157942280079245663
1226136409211...

result:

ok 237 tokens

Test #7:

score: 0
Accepted
time: 8ms
memory: 106336kb

input:

1000 1000
2 235 237 1
3 293 925 11446750964413798601
1 299 374 3
4 663 909
3 11 599 10235863487659693663
2 68 71 10
1 354 730 5
2 716 719 1
1 492 636 6
2 653 657 6
1 383 436 3
4 25 151
4 63 940
4 375 432
4 271 700
1 42 349 4
1 282 760 2
1 277 993 5
4 230 883
2 353 357 5
3 193 326 3721636915624045074...

output:

4995644932646857199
8682577773112482081
14198642487599396424
3213041208013041424
13539808857214091375
761700240778104149
303442926722239461
3516102455933096238
57413777171872180
7755609655116170430
4422876140281257386
5188821315335992835
12241893756112962715
16177149822898993950
340672744116294775
1...

result:

ok 262 tokens

Test #8:

score: 0
Accepted
time: 11ms
memory: 106436kb

input:

1000 1000
2 677 685 1
3 323 762 12895483491686386027
3 298 384 18175344572520049422
4 502 504
2 82 84 5
4 366 888
4 446 447
1 215 667 2
4 74 288
4 713 832
1 647 758 6
2 814 823 2
4 335 545
3 549 653 4845209895729503532
3 727 749 2017173238814894361
3 106 331 7491311112690514667
4 383 640
1 306 501 3...

output:

1792962327640054849
4602247259348913401
7344222909663220438
0
17584876078194546406
14152406924757806061
9115461223074385858
16394226226497421375
11880805806882569475
6738114177990764802
6873497294390714416
4519670768317052046
12682237596341027497
12763260220853210949
6314086074882193678
149826222253...

result:

ok 241 tokens

Test #9:

score: 0
Accepted
time: 21ms
memory: 106368kb

input:

1000 1000
1 34 37 5
3 126 206 14727478235725604056
3 654 744 18255408097680139947
1 480 887 3
2 949 957 12
2 73 73 4
2 475 479 13
2 629 633 60
2 855 863 17
4 693 699
2 841 848 16
4 99 497
2 591 593 11
4 475 475
3 662 665 9880886915713059518
2 759 767 7
3 138 500 17769308332561790789
2 377 385 1
1 63...

output:

17107392241503669933
12334116376362625112
0
6456951739835200564
9971073695561689148
2802027920063294567
1036164630077188382
17606737366739661456
3673719133547364878
14283911652166609210
10307419488382662895
7570930610113533112
4760136262978142135
2686644875969537451
16340864373011062989
166150323341...

result:

ok 238 tokens

Test #10:

score: 0
Accepted
time: 14ms
memory: 106448kb

input:

1000 1000
1 72 236 30
1 50 509 27
1 13 108 25
2 886 894 4
3 655 875 4803545865429381065
3 383 783 11671115136637467033
1 585 927 23
2 504 509 1
1 30 147 26
2 741 749 16
4 270 679
4 173 186
2 144 145 23
3 221 230 3690281936266615260
3 239 771 8308954142750294924
3 563 791 15967473094317050982
2 223 2...

output:

7741491917409221922
0
1184088091910697156
9402573550842177896
16347258322020142583
10075791157671528329
15790910225201268145
3569527660563963307
15857736879027467782
12504414326160398443
10919437795207910592
16960732844939675104
17997032562817801024
8392051279069707625
5000292839030073720
1114739402...

result:

ok 235 tokens

Subtask #2:

score: 15
Accepted

Test #11:

score: 15
Accepted
time: 987ms
memory: 168924kb

input:

300000 300000
1 237576 237663 1
3 16150 16208 9270412155482010138
2 175648 175692 1
4 190836 190849
4 199010 199097
1 73976 298801 1
3 89902 89939 6418828085116455990
3 55415 55461 12238963685511262676
3 119825 119875 8146944792877919309
3 135103 135158 218634681842812119
3 127261 127352 13291431184...

output:

0
0
0
0
0
0
12272376591028786218
0
0
0
0
0
0
0
0
0
0
0
0
0
0
954290611784159519
0
3778617232493240005
8956067326602310519
7373452729428553855
16938285947326957203
0
0
14783754218831034862
7601682967357904165
0
0
0
0
0
0
11584905325916393312
0
0
4657169178464751085
17170356428308894805
0
0
0
0
148107...

result:

ok 74906 tokens

Test #12:

score: 0
Accepted
time: 1020ms
memory: 169208kb

input:

300000 300000
3 51867 51899 1302529772508711959
1 163791 163805 1
1 176666 176684 1
2 127516 127575 1
4 31898 31983
3 151469 151497 15873092426332082486
3 206515 206568 14236701547576343621
4 238241 238324
3 61219 262809 1734847965363776922
2 220344 220393 1
2 98688 148993 1
4 55989 56049
3 298350 2...

output:

0
0
0
10681306550146550313
6652613657187526474
11475494508458717824
811486215804201182
1622972431608402364
0
15901103964711581888
3357820396972179286
4094176851202742427
5379446566603537422
16250215233565986824
15431111627897858304
0
16250215233565986824
4917765691823749552
0
0
10297212258427286974
...

result:

ok 74943 tokens

Test #13:

score: 0
Accepted
time: 1003ms
memory: 169244kb

input:

300000 300000
4 86816 86819
1 226565 246677 1
3 251963 251987 4817512795078102720
3 17122 202813 12262635941537918815
4 101129 101139
4 171789 171859
2 44072 166207 1
3 171011 171050 9516143677767859845
3 222046 222082 7458232785251868808
4 52499 166730
3 222551 222640 2035040917841558853
1 242195 2...

output:

0
5761786840950245653
3650180384843309913
13470892551030562504
16546298263213309450
3861341030454003487
15279334389549148006
5972947486560939227
0
11734734327511184880
0
10784511422263063797
16229557294797269089
3861341030454003487
10256609808236329862
15173754066743801219
0
1804317071900187272
5936...

result:

ok 74976 tokens

Test #14:

score: 0
Accepted
time: 1057ms
memory: 167604kb

input:

300000 300000
2 224303 224374 1
3 5249 5288 16547079035307299489
1 249405 249440 1
1 244932 244988 1
1 89040 89114 1
2 114166 114194 1
4 110077 110172
1 141920 141970 1
3 205203 205243 1118749945144490180
2 127281 127373 1
3 173359 173363 11110846146456890394
3 283255 283303 3242183420586937197
3 12...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2204476432060505976
0
0
0
0
0
0
0
0
0
6246016557504766932
3429185560983009296
0
0
0
0
0
0
0
0
8450492989565272908
0
0
0
244941825784500664
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10672427856181146758
0
0
14782553786312832860
0
0
0
2449418257845006640
0
0...

result:

ok 74803 tokens

Test #15:

score: 0
Accepted
time: 974ms
memory: 166804kb

input:

300000 300000
1 220731 220734 1
3 219129 219133 1441661622928400529
4 297901 297906
3 226862 226869 2997910990656207321
2 154071 154073 1
1 239514 239523 1
2 264617 264626 1
1 66677 66680 1
2 108520 108527 1
2 493 498 1
3 93536 93536 1729223806369067100
1 99697 99702 1
1 98817 98817 1
2 268169 26817...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8523192685433180568
8523192685433180568
1420532114238863428
8523192685433180568
0
0
9943724799672043996
0
11364256913910907424
0
8523192685433180568
5682128456955453712
9943724799672043996
14205321142388634280
2841064228477726856
...

result:

ok 74996 tokens

Test #16:

score: 0
Accepted
time: 1137ms
memory: 168928kb

input:

300000 300000
3 242005 245455 17402857150844839475
1 195499 202760 1
3 86348 87652 16350042050962992455
2 67513 70549 1
2 17581 20392 1
1 180566 187399 1
2 132424 136215 1
4 201 7568
4 29035 34787
4 159930 167082
4 117096 126668
3 115807 124052 6966836812432990399
4 24003 25402
3 16679 17045 1443793...

output:

0
0
0
0
0
0
0
0
0
0
1069304592552696348
0
0
0
0
0
18416266141863826215
0
0
0
3291332335248161760
0
355153960082695408
2339117343903337888
0
0
8313068146843994614
0
0
1842567308665326891
0
8807430591712594964
2810662510187183646
0
0
11269033645696727616
11110474990560302869
4659943295138724138
573269...

result:

ok 75196 tokens

Test #17:

score: 0
Accepted
time: 1097ms
memory: 168976kb

input:

300000 300000
2 129524 130230 1
3 97829 98681 14177044200280537874
1 117004 117036 1
3 75080 75625 7953158225766026866
3 222342 223044 592691174623108465
4 297810 298422
4 182525 182999
4 107197 107449
4 26126 26883
3 292284 292507 2229113056122186954
2 80055 80745 1
1 9570 10222 1
2 171443 171566 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6310142178115801295
0
0
0
0
0
0
0
0
0
14347829830854147244
0
0
0
0
0
0
0
0
3944750402169235976
0
0
14757788959901029185
1019326869378140182
0
0
0
0
10461260111479654801
0
0
16943243282109390662
0
0
0
7444098211629495683
16417881432838763511
10033696365246380464
15743721...

result:

ok 74887 tokens

Test #18:

score: 0
Accepted
time: 1147ms
memory: 167200kb

input:

300000 300000
3 60899 273136 17900506015963226324
2 255340 262254 1
1 47804 166274 1
2 228603 279002 1
1 229031 276929 1
4 136197 298489
3 162024 257244 7401373630232006099
1 215974 227652 1
3 119149 204343 7745371782660146547
1 152630 214299 1
3 96818 230022 73641545834168695
1 216242 238152 1
4 84...

output:

18154335184155868016
4395498840986882932
6677517497004993358
9589498140629496089
7527637927391730952
7561535112473928655
10721089906023321737
14674898849238760964
7537937300108454874
2088977973872526664
12681955574796639580
865433786514001673
6128943734780039177
6057697509332298715
66303342836821411...

result:

ok 74979 tokens

Test #19:

score: 0
Accepted
time: 948ms
memory: 165744kb

input:

290000 290000
4 133423 133423
1 114519 114520 1
2 184800 184802 1
2 138774 138775 1
4 157293 157294
3 81666 81668 13806851267434892022
2 116280 116281 1
1 163245 163247 1
3 289833 289835 244401869236287882
3 135164 135164 8097051466237243604
1 113225 113226 1
4 43898 43900
4 289121 289121
2 133889 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 72459 tokens

Test #20:

score: 0
Accepted
time: 889ms
memory: 164608kb

input:

290000 290000
4 130502 130504
2 15321 15322 1
3 275364 275364 4162744751939177223
4 99544 99545
4 100620 100621
3 193438 193439 13148803698890728003
2 125274 125275 1
2 241880 241882 1
3 168292 168292 2833035078327940594
3 27814 27816 10620786078931893277
4 136822 136823
3 56337 56338 74789752446323...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15159374354299362052
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 72567 tokens

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #21:

score: 15
Accepted
time: 1418ms
memory: 167608kb

input:

300000 300000
3 19765 150566 5167493634543664094
2 118662 201848 4
4 127772 255639
1 363 249365 3
3 11598 175102 16530837351901358978
4 36444 234550
2 60767 191641 3
3 76143 190023 11283165360234648940
4 151255 257891
3 69394 97478 6131272952305682140
1 45277 77429 3
2 6151 122134 2
4 48165 93810
4 ...

output:

10556488787335954570
18212772968701168848
11437199959288606460
8399299997760384588
11718115706414345024
10430039748605185716
10791380095122215184
15944361710687625976
16135961443839657432
4434563019586156035
8749535087882211887
14176305221399051252
13418003553475512102
1702668605387454355
8261145120...

result:

ok 75134 tokens

Test #22:

score: 0
Accepted
time: 1406ms
memory: 167664kb

input:

300000 300000
4 162302 243671
4 108774 189675
4 39409 141166
3 4302 54955 2032314023908047574
2 112167 175614 2
1 64603 84223 1
1 21939 276073 4
3 89118 292192 16912914609874825743
1 42029 243136 5
1 6607 89923 5
4 84686 207749
2 90483 180706 5
4 90130 210937
2 3986 206420 1
4 160909 206368
4 231903...

output:

0
0
0
15873333503526926104
17121097540592268952
805172695466921900
6811875668698915906
2154704327756035887
13361063727983507916
9957465101949901033
2361020279627774791
9944802148218948334
8933006541057953482
8419054413218512287
7499374196247153755
2322814461374996893
5063455811544017944
181317836964...

result:

ok 75143 tokens

Test #23:

score: 0
Accepted
time: 1304ms
memory: 167328kb

input:

300000 300000
2 43881 209003 3
1 38394 210807 3
4 124088 246888
3 194292 294993 14965842988217960999
2 7268 260532 1
4 55356 258209
4 30614 125800
4 12228 217949
4 100914 139051
4 8626 289740
3 137200 197340 16581754139137487738
4 171679 297284
3 151002 169014 4048109911456650022
1 17955 191264 1
4 ...

output:

0
12391434633122534786
0
13554408553097148454
0
14226546569610905359
1258947742724700382
7975676018575701868
14699654335855404245
2836428098486907892
0
0
13075627585651397960
10137199037753101868
2560291716939532668
0
0
3965759468233765114
6675482547759797918
377136551797720692
8233780657308404454
5...

result:

ok 75299 tokens

Test #24:

score: 0
Accepted
time: 1251ms
memory: 167620kb

input:

300000 300000
2 38974 122425 1
2 154324 200509 1
1 105196 177261 1
4 22602 92336
3 116731 139521 3785691812380334046
1 50394 206585 2
1 43693 45939 1
1 150585 248398 2
4 58334 279236
2 29855 234629 2
1 134837 232356 2
1 33590 187995 1
4 45353 225094
4 5143 218406
3 132984 296259 13443883199001797437...

output:

0
4280063220620334354
4280063220620334354
4280063220620334354
12942102882948317922
0
515646398438274593
13960823896323729341
15121422257949422342
4050774890096600150
6827727476066314682
17032911577039160751
14980190398974067226
0
12348257822165863135
17797920071528495114
12049883758977904352
3741833...

result:

ok 74831 tokens

Test #25:

score: 0
Accepted
time: 1481ms
memory: 168460kb

input:

300000 300000
1 108325 170825 2
1 75180 198007 2
3 198502 269481 6155319409967550256
3 118439 204702 18208507226716555567
2 84689 109898 6
3 121350 125452 3240807257604350502
3 128113 279066 3858912386055261208
4 137324 156567
1 26763 296270 6
4 217992 250340
1 150551 168667 1
4 3954 44188
2 157016 ...

output:

2927707313254266164
7111691128492120360
0
0
7511433708585490232
12996595601304901602
10014652043142889389
7925859735776492962
2433266972111213673
2026742805035658622
16936296874308042384
15891253573118700198
16759433185048414435
13582699811806992711
9181279370616959841
10493668918954980833
170597511...

result:

ok 75346 tokens

Test #26:

score: 0
Accepted
time: 1454ms
memory: 167940kb

input:

300000 300000
1 142340 290896 4
2 106118 281594 1
1 125118 239219 1
1 146645 242467 6
2 94811 267059 2
3 196962 198060 3880842098740778491
3 177618 205437 7944189581324122015
3 21555 254873 6906922927176307854
2 176525 267586 5
2 5361 119139 8
4 154526 203127
2 18293 239801 4
3 1282 60367 1538377403...

output:

4193411294427687587
10423002897193835031
11930663020839708456
10934201185410919301
11258778839841246615
10115046511841330630
14827283835751603054
12316279356792582359
17344498406486238907
3494646827640168597
6786469609441453779
9547779074663416188
17436279776526979250
9418663493905667746
85616485436...

result:

ok 74957 tokens

Test #27:

score: 0
Accepted
time: 1510ms
memory: 168112kb

input:

300000 300000
2 77465 161500 9
3 25304 294829 14617411969686562512
4 481 38496
4 35950 178143
3 165700 208373 13782567429211730264
4 80676 219358
1 5209 156204 6
4 44953 267325
3 124226 186366 14440703711647784364
2 64226 237279 2
4 67503 78504
1 97863 224182 6
2 23945 44990 5
4 31956 286477
2 10843...

output:

5253569515166627152
2942368313631946912
1345383830117124384
18273134775908787008
2051655891689768736
3655662234790267468
3774822403807394432
14646651593312881196
9680623658269568240
17891947543856660464
6982652702368533886
2839122413995951781
9566827875742796835
11372470030965632244
3027091332166732...

result:

ok 74635 tokens

Test #28:

score: 0
Accepted
time: 1514ms
memory: 167524kb

input:

300000 300000
4 135648 234202
3 29647 165926 16840015053112602038
1 217908 299002 3
3 123595 288340 8410801434116764439
1 20871 74761 6
2 7028 15409 10
3 21503 98137 9149147557498946122
3 92468 149047 16265212067444614206
2 17774 292906 3
2 193818 239889 3
2 122417 296993 9
2 27240 260758 9
2 36377 ...

output:

0
4389850629296085054
8313708654800983154
10732548206643100566
3608783094651684135
9430655813522350698
9126304236188795410
10474480979708913992
3602960950417138945
4077117209803282681
5536612977701736005
606193025646921246
17033082339588459168
15145992704860749090
10957716210918004677
15173895978271...

result:

ok 74787 tokens

Test #29:

score: 0
Accepted
time: 1502ms
memory: 169636kb

input:

300000 300000
1 919 90143 7
1 102649 289927 4
4 93497 180570
4 110729 129647
4 6932 104274
1 57964 259150 3
2 212063 221156 3
4 2903 16160
1 75245 269199 1
3 8688 280846 4292968973522761247
2 8822 165545 9
3 14333 211258 3859369225063222502
3 115193 139733 1172430629984989898
1 50676 101214 5
4 1253...

output:

0
0
0
0
11664875968724206474
9533194866715364449
15519603103440872322
0
7060733740496120096
17469470569326166257
11894769427267838791
0
9827825259028825103
14146079548446117474
11424285263444710151
10412760283937555370
113877874699649381
2335183642059929974
15114038242525386820
6162699798640173037
7...

result:

ok 75181 tokens

Test #30:

score: 0
Accepted
time: 1304ms
memory: 167660kb

input:

300000 300000
3 45045 45112 8009006353435524131
2 282429 282443 8
4 99488 99511
2 41489 41565 9
1 250350 250386 8
2 55910 55924 2
3 139663 139696 11287649816917766743
4 55202 55266
3 202760 202846 12366404193921582437
3 153465 153480 9812145719085910030
3 167776 167817 17444421041035998999
1 87025 8...

output:

0
0
0
0
0
0
0
0
0
18186103062170250361
0
0
0
0
0
0
0
0
0
0
0
0
0
0
11991416916054869196
0
14843646233087390032
0
6367304887820671070
14821396382473206458
5331491261753143882
0
0
0
10510559392090779822
3610188336539535216
16780515756041294950
1203396112179845072
9992652579057016228
0
0
16277682188744...

result:

ok 74910 tokens

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 730ms
memory: 159628kb

input:

300000 300000
1 85444 86076 59
1 41150 41411 71
1 278698 279414 45
1 238445 239202 56
1 29965 29984 49
1 282953 283272 37
1 34668 35653 86
2 198587 198744 28
1 270855 271611 58
1 2130 2965 773
1 161601 162298 937
1 50299 50435 36
1 100759 101198 64
1 120208 120543 84
1 295293 295732 34
1 112185 1129...

output:

0
0
16968625150574630951
16605993861994422737
14436884090003254733
0
3880767775473082445
6112413713545582398
0
17289176072916758003
0
0
0
10364128737969177934
0
0
995880312728861482
0
0
0
0
0
10433996744029883784
13368567004097850084
0
3861451384001627672
0
2134685396643390371
2335938625343203079
0
...

result:

ok 100167 tokens

Test #32:

score: 0
Accepted
time: 568ms
memory: 153872kb

input:

300000 300000
1 217891 287415 280
1 109091 109094 215
1 178397 178458 11
1 34114 34117 48
1 86577 86662 99
1 81392 81461 159
1 5842 5937 85
1 32285 32339 53
1 212941 212995 466
1 42038 42113 787
1 19627 19711 96
1 161983 266619 78
1 49816 222058 93
1 231964 231978 38
1 98426 98500 66
1 139172 139260...

output:

0
11692764325642035757
0
0
0
0
0
0
0
0
10626360660502640041
8974861558116311577
0
0
0
0
6828833927995630395
7675918871528237837
0
15346587511766135393
13255392782493978413
11587532788939849077
0
0
0
6764302870047383583
0
0
7400870183243479412
0
8589365144244158638
3886731025017654354
253988962743422...

result:

ok 100093 tokens

Test #33:

score: 0
Accepted
time: 598ms
memory: 153748kb

input:

300000 300000
1 160271 160305 121
2 136868 136903 52
1 25761 183215 150
1 201646 201657 75
1 178637 178641 161
1 108624 108682 194
1 21955 90478 111
1 62044 62108 103
1 18137 18150 60
2 137444 137488 63
1 169356 169437 369
1 226170 226241 21
2 250536 250571 111
1 64083 64158 265
1 179107 179148 53
1...

output:

0
0
0
10146344313931218962
18059154134718308159
0
0
5482480617044727472
4903722043315669325
8795894026302189205
1504263091099301790
0
4566381908445435572
6966530244481722998
0
0
0
8601406932323617126
0
4231971134025119261
17835338178033113319
0
0
0
0
0
0
0
0
6727335030369532119
0
1158681340578803909...

result:

ok 99470 tokens

Test #34:

score: 0
Accepted
time: 703ms
memory: 162748kb

input:

300000 300000
2 129741 129786 43
1 133731 133801 159
1 58344 83861 214
1 61033 61091 33
1 183553 183563 156
1 199271 199279 192
1 34576 34596 906
1 72891 80120 176
1 167427 167508 124
1 2964 3023 284
1 98570 98659 146
1 231952 232023 138
1 151151 151160 94
2 5131 5209 203
1 2869 2883 104
2 199205 19...

output:

0
0
4796201084925266965
0
0
0
13883685076285902517
0
0
9431529117273573445
4766573235145348929
1611897968597913432
0
0
0
2586063526252030814
0
0
16001876878405472178
17135272297629565994
0
17056443865906628232
0
4745294572652909898
8998783936939614344
7580363282108800106
0
16013946451858032933
0
477...

result:

ok 50062 tokens

Test #35:

score: 0
Accepted
time: 650ms
memory: 153100kb

input:

300000 300000
2 85463 85536 76
1 1319 173260 147
1 217533 217619 256
1 10109 10176 289
1 55109 209902 262
1 81267 132527 169
1 23758 23766 393
2 271064 271083 283
1 78575 78665 257
1 198478 198506 327
1 130300 130393 669
1 86358 86366 198
1 13014 149678 56
1 39667 39738 27
2 61722 61803 172
2 12005 ...

output:

0
0
0
0
0
211139834562940132
0
0
0
0
9937788562274929249
9903884816325715188
0
0
2249898283594756228
4847122793324524440
13389982050708360868
0
0
0
17832939713973779542
10881562150273498962
17502970485710981903
8002363826031321384
7290681287509116914
0
4376837037219638409
3099055170068370790
0
18423...

result:

ok 125092 tokens

Test #36:

score: 0
Accepted
time: 1089ms
memory: 197900kb

input:

300000 300000
1 1 600 1
1 1 598 2
1 1 596 3
1 1 594 4
1 1 592 5
1 1 590 6
1 1 588 7
1 1 586 8
1 1 584 9
1 1 582 10
1 1 580 11
1 1 578 12
1 1 576 13
1 1 574 14
1 1 572 15
1 1 570 16
1 1 568 17
1 1 566 18
1 1 564 19
1 1 562 20
1 1 560 21
1 1 558 22
1 1 556 23
1 1 554 24
1 1 552 25
1 1 550 26
1 1 548 2...

output:

0
0
0
0
0
0
2506763004086301860
17427921690879692440
0
0
0
0
0
0
0
0
0
0
0
0
12529173451446836357
0
0
8317424068741879477
0
0
0
15375344820100899566
0
0
0
0
0
0
0
0
0
0
0
6979511664378963244
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12078704023826942654
11918039685634475866
0
0
0
0...

result:

ok 75393 tokens

Test #37:

score: 0
Accepted
time: 1086ms
memory: 195972kb

input:

300000 300000
1 1 600 1
1 1 598 2
1 1 596 3
1 1 594 4
1 1 592 5
1 1 590 6
1 1 588 7
1 1 586 8
1 1 584 9
1 1 582 10
1 1 580 11
1 1 578 12
1 1 576 13
1 1 574 14
1 1 572 15
1 1 570 16
1 1 568 17
1 1 566 18
1 1 564 19
1 1 562 20
1 1 560 21
1 1 558 22
1 1 556 23
1 1 554 24
1 1 552 25
1 1 550 26
1 1 548 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
5202743784850168886
0
0
4603927467884415342
0
4603927467884415342
9749533581125811360
2088840978649544692
0
18322607265021990624
0
0
9711321466745280504
4603927467884415342
2496249307634847047
0
0
0
0
0
0
0
0
0
0
0
0
5227856238668259348
47582809777024974
1200026012580389334...

result:

ok 75238 tokens

Test #38:

score: 0
Accepted
time: 811ms
memory: 187396kb

input:

300000 300000
1 1 300000 1
1 2 299999 2
1 3 299998 3
1 4 299997 4
1 5 299996 5
1 6 299995 6
1 7 299994 7
1 8 299993 8
1 9 299992 9
1 10 299991 10
1 11 299990 11
1 12 299989 12
1 13 299988 13
1 14 299987 14
1 15 299986 15
1 16 299985 16
1 17 299984 17
1 18 299983 18
1 19 299982 19
1 20 299981 20
1 21...

output:

0
0
0
0
10718922111423336564
10718922111423336564
0
0
0
10718922111423336564
10718922111423336564
0
0
9146817304949717077
13409051668444632193
2348108605912789755
0
0
9506780142003357434
0
0
9857982858752846941
13200643887683725279
0
0
0
0
7505599624584684325
0
5415306418116098549
0
1066421420982755...

result:

ok 75210 tokens

Test #39:

score: 0
Accepted
time: 631ms
memory: 150664kb

input:

300000 300000
1 1 1500 1
1 1 1500 2
1 1 1500 3
1 1 1500 4
1 1 1500 5
1 1 1500 6
1 1 1500 7
1 1 1500 8
1 1 1500 9
1 1 1500 10
1 1 1500 11
1 1 1500 12
1 1 1500 13
1 1 1500 14
1 1 1500 15
1 1 1500 16
1 1 1500 17
1 1 1500 18
1 1 1500 19
1 1 1500 20
1 1 1500 21
1 1 1500 22
1 1 1500 23
1 1 1500 24
1 1 150...

output:

0
0
0
0
8267058594554803676
0
0
0
0
0
0
9795094952976301450
0
0
0
0
0
0
9478972841234857817
0
2336196861175781959
0
0
0
0
0
0
0
0
7132376017696382137
0
0
3089475321960576786
7596711484866781532
0
13604716112274572028
15610753335934999776
832524808219417262
0
0
0
0
0
0
0
0
0
0
0
4306695857416496340
1...

result:

ok 91846 tokens

Test #40:

score: 0
Accepted
time: 457ms
memory: 145292kb

input:

300000 300000
1 1 1500 1
1 1 1500 2
1 1 1500 3
1 1 1500 4
1 1 1500 5
1 1 1500 6
1 1 1500 7
1 1 1500 8
1 1 1500 9
1 1 1500 10
1 1 1500 11
1 1 1500 12
1 1 1500 13
1 1 1500 14
1 1 1500 15
1 1 1500 16
1 1 1500 17
1 1 1500 18
1 1 1500 19
1 1 1500 20
1 1 1500 21
1 1 1500 22
1 1 1500 23
1 1 1500 24
1 1 150...

output:

0
0
0
0
0
0
0
9251420100719027419
0
10437522002891643988
4472746676660461079
9253100888169842044
0
0
0
0
0
0
0
8566814495386720956
607008573332703067
0
14745303428233523745
0
6374585044919482064
0
10054674375899920618
1944753074502624222
2146697673259820164
0
0
0
0
0
0
0
0
0
0
0
0
0
1422096915848735...

result:

ok 90955 tokens

Subtask #5:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #41:

score: 10
Accepted
time: 233ms
memory: 118756kb

input:

40000 40000
4 576 27541
4 6386 23009
1 20941 21376 751
3 823 32062 5063552653037376179
2 13664 17318 2188
1 8143 18546 1303
1 96 22011 1709
2 20800 37184 3499
3 4098 33457 11559569033571630334
1 6686 15115 2973
3 11874 14936 5095502711361186497
4 423 21401
2 465 17984 1744
4 7029 8301
2 11477 13949 ...

output:

0
0
7508658702764009280
2818454508409587497
2691107458561732357
17091421403689417235
9257718243204186348
18298839084850992832
9718728949608108619
5190614606731169920
11954304750104910248
12646121248210666802
2227312579256095589
5111502619119685428
8250430884890452739
11243131780320731985
87960905481...

result:

ok 9994 tokens

Test #42:

score: 0
Accepted
time: 217ms
memory: 118988kb

input:

40000 40000
1 12559 31989 61
1 20540 26683 347
4 15157 37487
2 24282 26322 218
4 1359 27833
1 7254 26602 390
3 16275 21139 12479977116032246002
2 4908 14465 260
4 10322 31118
2 27812 36345 251
3 6605 36867 10550355865825144008
2 21869 33556 272
3 19324 25596 14673005058658741367
4 26342 37679
2 4961...

output:

0
0
6853922918742431474
3646519943965099888
0
6153542968187879966
11317375100468203353
14515564247017430579
1123692613983035864
8421461716963747926
11057180766482084640
7218499438058262744
16632423748903682936
12981519703119539378
6455100585298815773
10741834170238260825
5895587406382276070
15215727...

result:

ok 9998 tokens

Test #43:

score: 0
Accepted
time: 181ms
memory: 113408kb

input:

40000 40000
2 15566 23785 24
2 12710 16468 18
4 5516 17371
3 3315 13349 7262961801150345883
2 23729 28747 38
1 19232 20818 38
3 3184 29692 6742888815080704074
2 1038 35347 3
4 6222 21809
2 25565 32392 28
4 20233 28074
3 5505 28608 498741494423111384
4 18933 28203
3 9381 25723 3440819704761066563
2 9...

output:

0
7430965251653617072
9365572611306416852
9452915180814780494
9828429702921857547
1361176011493271989
1729610548391387594
14077746933625889736
9612912187363378426
4876178820848591192
8912775969232657188
4946375979248381299
10270284542887762916
1411726852422798281
13198455833731137318
167691818445823...

result:

ok 9912 tokens

Test #44:

score: 0
Accepted
time: 156ms
memory: 113024kb

input:

40000 40000
2 9034 14689 1
3 8078 24172 8446709360089751396
3 7183 29835 7453599722051325507
2 4573 18526 2
4 8131 20203
1 1835 5435 3
2 441 20550 1
3 10778 11992 15447703003373543258
3 34495 38063 7736539006391584864
1 27013 33214 1
1 31418 39483 3
4 6490 30518
3 4559 14183 8268753706355827434
1 19...

output:

7612717667627333823
9249750506545142521
6100689784483420778
7872964543753522561
10596753144290849576
6524294888743473164
5451252449228919069
1671137835218146742
750871853453121392
1489349358980656271
6411500492244724711
7109023910524010008
3116435585276723594
18174414762878528751
1113833908168544517...

result:

ok 9861 tokens

Test #45:

score: 0
Accepted
time: 134ms
memory: 116152kb

input:

40000 40000
4 5433 33171
1 9663 38939 903
3 17151 29086 489556798503134186
2 10552 19820 952
1 19329 21822 874
1 15050 29032 223
2 37346 37649 382
3 26321 30249 2479963200102780080
3 14760 29095 2734026925045709062
4 5466 16385
3 9918 38931 8415121231042101457
4 2006 24200
2 38060 38436 752
1 21540 ...

output:

0
18309202434030546972
979686583183183141
2581851821132002166
5012958776786493480
10933665070973329751
12628080033337595711
16419178355538396576
2762518489325336584
13222782748535709204
5727761150946371587
15050738623273638149
17299474625819832890
569931967967839962
9017407647608319798
7316951328699...

result:

ok 10112 tokens

Test #46:

score: 0
Accepted
time: 112ms
memory: 116256kb

input:

40000 40000
2 950 986 62
3 32665 39557 1459666198176499450
2 19953 20079 171
2 28787 28987 86
3 11890 13897 16992718997024881808
1 3626 12455 35
1 15855 36529 82
3 37186 37746 18180156315005212010
1 23269 24232 173
3 11213 19340 4696759065587628154
2 16539 16569 6
2 2899 2946 193
3 2837 10250 210882...

output:

12105169892515142560
15207756103116793500
11794421259914104692
13624790301027565746
2400203354172286864
2215748873640112924
3763435318174730947
7786144716893832273
16146982307292051892
16441554516053604807
16837160515212060861
2259579344222890040
3526780904914528886
18412540983454612307
176933060505...

result:

ok 9895 tokens

Test #47:

score: 0
Accepted
time: 84ms
memory: 112524kb

input:

40000 40000
1 33597 37399 35
1 3189 27051 33
4 29128 38689
2 28881 39271 38
4 9591 27710
2 20345 20607 5
2 23204 23413 49
3 8600 26762 5526158724337323840
4 17431 36715
2 34446 34815 35
4 11515 28618
3 2653 15822 585282263655737645
4 10269 12535
3 11483 26777 15384244170535151132
4 1531 15046
2 8475...

output:

0
0
11463529497709308160
16588044063991682048
1131920424397122879
16623280973432444722
11288569081185668380
14376690261992998376
1668074368341702052
4930851060101298228
2614792112049014607
3188055330635773710
3966359955538733297
6887038592542686756
16159820012510501165
826341539701747429
24522897197...

result:

ok 10141 tokens

Test #48:

score: 0
Accepted
time: 137ms
memory: 113880kb

input:

40000 40000
1 29905 30890 545
2 39668 39958 99
4 185 13527
2 33659 33942 16
3 4791 15377 11955402225202520566
4 9288 32278
4 1806 21644
2 30958 31154 90
3 2382 38460 10600044282569287487
2 37139 37474 11
3 17151 36696 12894272050760805953
2 22931 23010 32
3 29739 36518 12763324057917049064
4 10501 2...

output:

0
17547436625459570204
8732268497851594866
701026301823135620
8553236934023756096
4245457077681508586
10576542511136850929
5154480949819515280
4248351554003745886
17431300564677796727
6408823205966421392
12750657389420717791
17778617931738906058
16501130113232168445
17423220840960051353
106184677294...

result:

ok 9978 tokens

Test #49:

score: 0
Accepted
time: 113ms
memory: 115876kb

input:

40000 40000
4 27604 28631
2 29604 29755 14
1 1830 5370 65
1 401 27287 58
3 5772 19934 13988694129479509635
2 9867 10072 17
4 11589 39134
2 30627 30829 215
3 3984 14864 11509346671263077852
4 11811 12053
4 20893 37685
4 1176 31815
1 12470 23301 35
4 22376 25583
1 14435 33534 23
2 31419 31698 67
1 141...

output:

0
197962128235236046
16364649887748967981
0
2099217777114791253
0
2099217777114791253
0
12956974070382981388
7214100392957863815
13334987327345628689
18247441059178680252
14396813329827753491
4322569680482396718
15316119303924343622
612784626391564599
14852243166231139861
18252465950331399367
121453...

result:

ok 10006 tokens

Test #50:

score: 0
Accepted
time: 86ms
memory: 114840kb

input:

40000 40000
1 7674 9525 54
4 20790 21195
3 21059 27963 18316296184271697385
1 17831 29347 60
1 3915 9437 15
4 30267 32075
4 15044 38364
4 15961 16118
2 6544 6686 11
4 39217 39809
2 20363 20543 3
2 37851 37984 107
2 28580 28649 20
3 13965 20183 3399078880845549133
3 13020 37625 6599984329518697549
4 ...

output:

0
0
3147783043384564129
0
0
11737479225750595960
10771737015888382607
1812860509076860957
17363621120467743822
15140604598233199023
160798351867088240
6503789490688208382
12140022672524724959
10440900038123779961
3882849543552289779
11674143129754260317
13450257701895116730
16013901748674175210
9534...

result:

ok 8010 tokens

Subtask #6:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #51:

score: 30
Accepted
time: 2189ms
memory: 196360kb

input:

300000 300000
3 129611 275010 14341351429467829760
4 127236 143603
2 18751 205125 1844
4 61270 80245
3 208206 249052 14193747344989420994
2 2093 295014 2084
1 81546 149356 940
2 179606 252379 2772
2 14383 256937 2663
4 89229 126579
3 100841 188670 6555135009104383934
4 40537 225365
1 38738 145857 30...

output:

14848518730839352832
0
0
15211305378657874532
16892842552896212482
6486197657665586431
15739833644945869896
9939011811774675390
2012677554284141064
11583722257937973386
1131080345594804066
10748605953113388430
14428375485767987940
10992018949142597225
2609455098202925507
15298978000179853579
1675637...

result:

ok 75157 tokens

Test #52:

score: 0
Accepted
time: 2012ms
memory: 178424kb

input:

300000 300000
2 125196 221911 382
1 51170 155391 93
3 163057 295547 4410565431096393560
1 25386 207050 134
3 182181 298015 16644538900220565505
1 122044 157719 280
2 198991 274214 152
2 172427 256204 41
3 111051 297033 17333316754541350318
2 52535 205043 228
1 191112 224249 175
3 8723 263588 1147371...

output:

13503512360650187992
13779432954581527170
9961879177762037361
13197561688449717834
10314345330432980139
5417436424503571389
2547823627138931972
14094292696444186307
1559419488592062159
13134177668965810147
9218986549705221664
6319583390736749022
10459052197770751891
2980389259870893329
1548128586631...

result:

ok 75619 tokens

Test #53:

score: 0
Accepted
time: 1781ms
memory: 168740kb

input:

300000 300000
3 226196 270402 2287329681210043163
3 45739 282609 16338231735131611586
1 229416 286665 2
2 89237 253577 15
1 5089 288536 36
2 98301 108874 21
1 247840 286639 16
3 163956 219353 8346556662293571103
2 220313 240739 7
4 69925 297893
2 218945 292366 2
1 166817 219287 37
4 43838 183521
2 7...

output:

15686420889690912809
319240452768991744
7820460340265231523
6471366931322297854
6007619776834013853
9000729253990103902
12875408727486677404
5604777225752704820
17838784297373856974
6546440348527522854
7608219039603080219
3614723463032605130
12009578209844026988
10178907866398314416
1583645244267218...

result:

ok 75181 tokens

Test #54:

score: 0
Accepted
time: 952ms
memory: 164108kb

input:

300000 300000
3 24667 164241 8140089758993671361
2 7448 8463 496
2 289294 291657 689
2 162379 163986 194
4 158773 299265
3 71084 160139 16119120434684008070
3 147592 239651 17635894136055333219
3 35390 138300 7822799401395259692
1 134209 184587 134
3 46108 83193 15308937210818042781
3 35138 237347 2...

output:

6157442075240623901
2420392845846149742
16608681081004029824
171373620995334910
8916070919264240728
1630912095930678758
15058247536172641986
17969658327532306789
10547670295210303552
1909452101020871225
8182880904604462515
12764799399792521773
4143165622492016077
7865137146411924260
5538375022769376...

result:

ok 75017 tokens

Test #55:

score: 0
Accepted
time: 1108ms
memory: 170700kb

input:

300000 300000
1 81890 112348 120
1 56298 254290 504
4 31196 256582
4 148270 256535
1 220606 275081 1763
4 64195 299613
2 180234 180390 363
3 42933 212178 14600869814812139820
2 59920 62564 2328
4 8841 37192
3 99136 173629 4667566885026199396
2 134436 137141 2100
1 149327 216450 810
4 13778 20646
1 2...

output:

0
0
0
0
0
16408166290300799404
629987134502751208
17499611391637086236
10330910451630410443
7671986046286391828
10899370631309403317
4039050183035784004
11906539668468489274
1552119370644313302
5486998537125801643
12076529817550091528
6496937940649187769
9055315833012539707
14700299658088683520
4881...

result:

ok 74823 tokens

Test #56:

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

input:

300000 300000
4 182591 243353
1 84306 299592 224
4 239511 259350
3 67869 116437 6035107230182880481
3 11130 186457 13909329574605268337
1 71765 227338 126
3 181784 211627 5645376588146568789
3 209063 273981 11692548991175865951
2 21137 23055 112
1 126103 251071 144
3 219558 294891 150666192984797189...

output:

0
0
3980712652499161830
9050420235355229694
13264686689396884645
0
10249352494231059069
13459416985338085316
8125688644862358374
17626631330040118988
12081208742473473766
17193728623923101227
9165783539173247849
7429966195772439692
13002436411163980865
2179994942596364240
6322818338839638672
1022714...

result:

ok 74961 tokens

Test #57:

score: 0
Accepted
time: 759ms
memory: 160624kb

input:

300000 300000
1 83754 213508 221
1 10638 21714 192
3 31502 33497 1769329837798204124
3 53614 130064 12394841571247145989
3 40813 42547 18196618713267432808
3 70189 294584 17576518265468576953
4 233279 234512
3 169429 264740 630330999517702145
1 243435 280130 52
1 40639 250817 411
1 45611 129430 206
...

output:

14499252979500811202
3552459422229938111
13233327711524211412
16624900554222397127
11947342902244226086
12037224622744176429
14366974783801646087
6562521211834837544
1331421463755141920
13216251761038213073
41073780183763399
5193346301562674993
14274039798074788557
8908355504243741789
94512260277607...

result:

ok 60087 tokens

Test #58:

score: 0
Accepted
time: 697ms
memory: 159024kb

input:

300000 300000
1 17786 61422 64
4 130421 214445
2 128000 129112 231
1 107914 276217 120
3 14026 25513 17647306113950260594
1 65412 231455 226
4 198109 222064
3 20320 139647 14636914588356486202
2 287571 289994 95
1 168497 200267 276
1 45007 224444 201
1 11379 283427 142
1 37894 77409 85
2 145658 1485...

output:

0
0
4791179129042500101
2111197755057396289
3097301653437636491
2592964163452272632
5662828126329081712
15262433432947354344
1006906708678843504
3755218307145203291
3382900142500912135
5640303050347933547
8395943385049901158
15747949400828468023
10262427463728684240
5224148839721892184
5137664808285...

result:

ok 60274 tokens

Test #59:

score: 0
Accepted
time: 711ms
memory: 158968kb

input:

300000 300000
1 129320 169609 361
2 67956 70674 333
1 119238 125931 165
2 54464 56923 318
3 148134 214138 18330429125747412142
2 12707 15119 75
1 11867 100574 119
1 109774 263183 367
1 62481 253882 30
2 38992 39424 273
3 74566 241431 8693581929656401690
4 58030 59712
2 21589 22554 35
1 28598 54948 1...

output:

0
14117087291716796740
1634068529639224616
12402996554078744229
8774937183725144875
2992971545039484121
16479190985136542585
8108493207482060563
12812158074211083453
12136283098079928339
0
0
1215137701701082252
0
8659755038874979887
1911935642576936376
9031340577607113584
11300422260897997549
169794...

result:

ok 59433 tokens

Test #60:

score: 0
Accepted
time: 677ms
memory: 158708kb

input:

300000 300000
3 139422 178391 1250413038763284461
4 42237 45234
4 256304 295448
4 121142 231082
2 75550 78404 13
4 14510 104071
3 23569 131610 8475891087337422941
1 19053 163330 15
4 182889 210875
4 586 145130
3 9064 200583 4592105751873120276
3 96468 136538 1749540336401024368
4 6917 163805
2 24886...

output:

0
0
10745021938269627314
0
0
226888720573030891
10915523122509252394
13164009268035286787
14682712594391240295
6417896601893173136
0
6609073613308038483
17410066127661645022
12357656411198819508
11515672082468037544
2971791894054681113
6386339849446947520
6300314723595261294
12374300710109711156
920...

result:

ok 59840 tokens

Test #61:

score: 0
Accepted
time: 3657ms
memory: 272148kb

input:

300000 300000
1 133557 222282 4784
2 21534 282347 61257
1 115943 298165 86505
1 122925 262673 139751
1 7179 22313 12794
2 108305 127463 40110
2 123134 125141 40331
1 195050 195357 76636
2 82495 256809 29047
2 103389 158498 21617
1 66391 123040 144667
1 92042 249498 32646
1 49507 123443 12042
1 24173...

output:


result:

ok 0 tokens