QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718187#9608. 皮鞋的多项式Nesraychan100 ✓1003ms932848kbC++144.9kb2024-11-06 19:54:552024-11-06 19:54:57

Judging History

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

  • [2024-11-06 19:54:57]
  • 评测
  • 测评结果:100
  • 用时:1003ms
  • 内存:932848kb
  • [2024-11-06 19:54:55]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 100100
#define M 300300
#define mod 998244353
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
IL int power(reg int x,reg int p){reg int r=1; for(;p;p>>=1,x=Mul(x,x))if(p&1)r=Mul(r,x); return r;}

namespace NTT
{

int r[M],grt[M+M],a[M],b[M],len;

IL void prework(reg int n)
{
    for(len=1;len<=n;len<<=1);
    for(reg int i=0;i<len;++i)a[i]=b[i]=0,r[i]=r[i>>1]+(i&1)*len>>1;
}

IL void dft(reg int *f)
{
    for(reg int i=len;i--;)if(r[i]>i)std::swap(f[i],f[r[i]]);
    for(reg int k=2,i,j,x,y;k<=len;k<<=1)for(i=0;i<len;i+=k)for(j=i;j<i+k/2;++j)
        x=f[j],y=Mul(f[j+k/2],grt[k+j-i]),f[j]=Add(x,y),f[j+k/2]=Sub(x,y);
}

IL void idft(reg int *f)
{
    dft(f),std::reverse(f+1,f+len);
    reg int inv=mod-(mod-1)/len;
    for(reg int i=len;i--;)f[i]=Mul(f[i],inv);
}

}

using namespace NTT;

const int B=2e3;
int n,q,m,p[N],ans,lim;
std::vector<int>x[N],y[N],G[N],s[N<<2];
int f[N][B+5];

IL void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u);}

template<class T>IL void clear(reg T &a){T b; std::swap(a,b);}

void dc(reg int o,reg int l,reg int r)
{
    if(l==r)return s[o]=y[l],void();
    reg int mid=l+r>>1,ls=o<<1,rs=o<<1|1;
    dc(ls,l,mid),dc(rs,mid+1,r);
    reg int mx=s[ls].size()+s[rs].size()-2;
    prework(mx);
    for(reg int i=0;i<s[ls].size();++i)a[i]=s[ls][i];
    for(reg int i=0;i<s[rs].size();++i)b[i]=s[rs][i];
    clear(s[ls]),clear(s[rs]);
    dft(a),dft(b);
    for(reg int i=0;i<len;++i)a[i]=Mul(a[i],b[i]);
    idft(a),clear(s[o]),s[o].resize(mx+1);
    for(reg int i=0;i<=mx;++i)s[o][i]=a[i];
}

int left[N],id[N],blo[N],cnt,fa[N],L[N],R[N];
int g[(N/B)*2+10][N],con[N/B+5][M];
short pre[N/B+5][M];

void dfs(reg int u)
{
    left[u]=p[u],L[u]=cnt+1;
    if(p[u]<B)for(reg int i=0;i<=p[u];++i)f[u][i]=x[u][i];
    for(auto v:G[u])if(v!=fa[u])
    {
        fa[v]=u,dfs(v);
        static int nf[N];
        reg int up1=left[u],up2=left[v];
        if(up1+up2<B)
        {
            for(reg int i=0;i<=up1+up2;++i)nf[i]=0;
            for(reg int i=0,j;i<=up1;++i)for(j=0;j<=up2;++j)
                Pls(nf[i+j],Mul(f[u][i],f[v][j]));
            for(reg int i=0;i<=up1+up2;++i)f[u][i]=nf[i];
        }
        left[u]+=left[v];
    }
    if(left[u]>=B||u==1)
        id[u]=++cnt,left[u]=0,f[u][0]=1;
    R[u]=cnt;
}

std::map<std::pair<int,int>,int>mp;
int tot;

IL int init(reg int l,reg int r)
{
    if(l>r)l=1,r=0;
    if(mp.count({l,r}))return mp[{l,r}];
    mp[{l,r}]=++tot;
    if(l>r)
    {
        for(reg int i=0;i<=lim;++i)g[tot][i]=1;
        return tot;
    }
    for(reg int i=0;i<len;++i)
        if(pre[r][i]==pre[l-1][i])a[i]=Mul(con[r][i],l>1?power(con[l-1][i],mod-2):1);
        else a[i]=0;
    idft(a);
    for(reg int i=0;i<=lim;++i)g[tot][i]=a[i];
    for(reg int i=1;i<=lim;++i)Pls(g[tot][i],g[tot][i-1]);
    return tot;
}

IL int min(reg int x,reg int y){return x<y?x:y;}

main()
{
    for(reg int k=2,w,i;k<M;k<<=1)
    {
        w=power(3,(mod-1)/k),grt[k]=1;
        for(i=1;i<k/2;++i)grt[k+i]=Mul(grt[k+i-1],w);
    }
    n=read(),q=read();
    for(reg int i=1,j;i<=n;++i)
    {
        lim+=p[i]=read(),x[i].resize(p[i]+1);
        for(j=0;j<=p[i];++j)x[i][j]=read();
    }
    for(reg int i=1;i<n;++i)add(read(),read());
    dfs(1);
    for(reg int i=1,j;i<=n;++i)
    {
        for(j=i;!id[j];j=fa[j]);
        blo[i]=j;
    }
    for(reg int i=1,j,b;i<=n;++i)if(b=id[i])
    {
        m=0;
        for(j=1;j<=n;++j)if(blo[j]==i)y[++m]=x[j];
        dc(1,1,m),prework(lim);
        for(j=0;j<s[1].size();++j)a[j]=s[1][j];
        dft(a);
        for(j=0;j<len;++j)
            if(a[j])con[b][j]=a[j];
            else pre[b][j]=con[b][j]=1;
    }
    for(reg int i=2,j;i<=cnt;++i)for(j=0;j<len;++j)
        con[i][j]=Mul(con[i][j],con[i-1][j]),pre[i][j]+=pre[i-1][j];
    for(reg int x,l,r,b,i;q--;)
    {
        x=read()^ans,l=read()^ans,r=min(lim,read()^ans);
        if(l>r)
        {
            printf("%d\n",ans=0);
            continue;
        }
        b=init(L[x],R[x]);
        if(blo[x]==x)
        {
            printf("%d\n",ans=Sub(g[b][r],l?g[b][l-1]:0));
            continue;
        }
        ans=0;
        for(i=0;i<=left[x];++i)
        {
            if(r>=i)Pls(ans,Mul(f[x][i],g[b][r-i]));
            if(l-1>=i)Dec(ans,Mul(f[x][i],g[b][l-i-1]));
        }
        printf("%d\n",ans);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 51ms
memory: 51136kb

input:

1977 200000
0 883734638
1 497045124 50605999
0 467033353
8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524
0 111009203
0 980468811
1 965285721 647475291
0 55665482
0 810210109
5 99482052 915734955 536563337 860629716 489661090 127640528
4 452261176 414532348 8...

output:

0
0
0
1462214
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
709010908
0
0
0
0
0
0
0
0
0
0
0
0
0
0
362560754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
887205253
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
532388854
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 200000 numbers

Test #2:

score: 7
Accepted
time: 54ms
memory: 51136kb

input:

1969 200000
1 928278040 49291189
0 106316044
7 355985609 701602147 528629206 472008316 626845782 871506163 793475066 634852555
0 193911795
1 498772599 387035156
2 244940676 15788848 225049996
8 257966353 171785747 687353797 643745787 25069581 248781417 212047281 295151595 525248876
2 606862291 21936...

output:

0
0
702752596
0
0
0
564436252
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
539882987
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
421207407
0
0
0
0
0
...

result:

ok 200000 numbers

Test #3:

score: 7
Accepted
time: 52ms
memory: 51180kb

input:

2000 200000
0 230695610
4 400302240 129755410 740309716 633048240 594259574
2 261261651 610028309 279096898
0 306295327
1 411519353 880936332
4 458323735 111990362 693959473 50334178 49499787
0 451592459
1 114402580 931927324
4 639243873 254122580 669324541 571247271 275880979
0 440954066
1 43964805...

output:

0
0
801713754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
807839363
0
845789441
0
0
0
0
0
0
0
0
180971215
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
791867965
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
514100741
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
995968989
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8782...

result:

ok 200000 numbers

Test #4:

score: 7
Accepted
time: 161ms
memory: 49860kb

input:

1978 200000
1 191987956 540466676
1 120742551 206257774
2 744430486 875250521 181042024
0 103091601
0 304724279
0 649017453
0 145685556
0 599144446
0 364188280
0 57833875
3 414338956 791946816 770890256 830048461
0 819249191
0 755199883
1 758814940 693449562
1 280052104 142092003
0 214207528
0 85521...

output:

0
0
0
0
0
0
0
0
0
0
0
0
574798441
0
0
551851346
0
0
0
0
0
0
298923018
0
0
0
0
0
706319639
0
0
932127532
0
0
0
0
506810290
0
0
375480684
0
0
0
0
0
575707276
0
769974190
0
0
0
0
0
0
0
0
0
255132253
234643792
0
436442475
0
0
0
0
0
0
770777820
0
0
0
0
382421721
0
0
10702740
0
0
912641116
0
679541132
0
0...

result:

ok 200000 numbers

Test #5:

score: 7
Accepted
time: 48ms
memory: 51456kb

input:

1997 200000
1 609381747 833571580
1 102342468 526127035
1 880931004 909374728
2 103826707 729151512 34293902
1 273372046 293953096
0 554926428
0 676458000
1 401799287 357803550
1 695810053 794616522
0 748711966
1 967175820 34877055
2 257806263 264285746 818013686
1 576641758 75701100
0 795476926
0 7...

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
996352329
0
0
0
0
61024835
0
0
424430639
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
392760029
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
442026045...

result:

ok 200000 numbers

Subtask #2:

score: 3
Accepted

Test #6:

score: 3
Accepted
time: 1003ms
memory: 628336kb

input:

98154 200000
0 948053956
0 149079029
0 871940052
0 888807640
0 284687863
0 760258916
0 916765457
0 121680504
0 210430381
0 162441114
0 640680402
0 269559148
0 706423649
0 619089994
0 776236890
0 44769489
0 863235377
0 283984837
0 251593760
0 863377054
0 40488948
0 100272768
0 628132233
0 18841959
0 ...

output:

0
160622568
939846745
221659137
0
312930382
620657950
975124531
0
241389446
233242086
656904774
0
666641212
127400637
0
0
61866892
388266897
17714856
158666308
181172732
0
231863345
0
0
993493871
0
945624744
0
53582097
0
553931157
940627115
0
864491900
0
0
910285591
0
0
0
0
810021023
0
957355731
870...

result:

ok 200000 numbers

Test #7:

score: 3
Accepted
time: 935ms
memory: 702808kb

input:

98566 200000
0 209181684
0 889317979
0 925862494
0 861680823
0 629292192
0 781545895
0 58892045
0 300501945
0 510137985
0 764792857
0 551445762
0 771899874
0 828696971
0 260462870
0 535761660
0 532161459
0 187099
0 691412616
0 891055462
0 283180276
0 446617517
0 928434806
0 974119517
0 895921491
0 8...

output:

0
541915644
0
0
0
344789573
37160095
0
0
378148422
0
27407348
0
510146116
0
0
593724632
308323897
0
208041958
834526238
308130263
413718362
0
0
452600858
215844992
0
0
138748183
0
597752749
0
0
0
131857104
0
0
583969453
644145934
277456647
0
730806159
210434799
329144450
0
271266199
0
0
532721033
33...

result:

ok 200000 numbers

Subtask #3:

score: 20
Accepted

Test #8:

score: 20
Accepted
time: 487ms
memory: 808712kb

input:

97330 200000
2 356080749 854511831 888131963
0 533633039
0 260190631
0 217335008
2 998111375 903316988 891866314
0 507509609
0 556810297
1 190927168 988903728
1 270553180 387224380
0 360295480
0 775464651
0 755424805
0 71030175
0 690904984
0 702271750
0 360541906
0 903384679
0 769283169
0 6990072
0 ...

output:

977291091
128984561
364900240
670134422
109312967
116219802
633246879
791832029
188822171
313954797
872698950
326842267
58045309
613915890
34453063
626081681
891712143
675586354
509834775
529836633
409512272
657071096
11862851
695651906
98170281
194125828
955037714
807908792
212191825
825295990
2244...

result:

ok 200000 numbers

Test #9:

score: 20
Accepted
time: 467ms
memory: 865940kb

input:

96880 200000
0 155849542
1 895865131 748889613
0 28666287
0 959676113
0 436568647
0 514279644
1 636928010 199253041
1 806543723 563843226
0 296862731
1 617330202 619480133
0 832224863
1 207080707 411689441
1 550833908 670195492
0 980814251
0 685006368
0 558249647
0 20614515
1 412246213 873717215
0 9...

output:

440357773
924848770
340312385
268399218
703705351
283032621
527143532
527723719
936920505
815914636
237227259
965189344
992799087
987559316
196769340
130556674
652234120
950203104
295087063
429164775
959998385
480555801
559603216
617304409
636888726
251764185
734722233
932706757
260865681
154570949
...

result:

ok 200000 numbers

Test #10:

score: 20
Accepted
time: 390ms
memory: 900412kb

input:

99119 200000
1 193445750 73279632
0 159943777
0 741212402
0 433101693
0 492169150
0 295804258
1 875516477 748591364
1 847628456 521055346
0 720470433
0 550284345
0 645519907
0 749938197
0 728894207
0 14951672
0 929957765
0 738265973
0 856320168
1 663420785 638700238
0 779605078
1 862023258 913300109...

output:

107826286
763543631
427034420
121557813
640560432
778202723
103828218
293968965
588012467
317760045
345087369
219212550
836926992
376387667
550043054
728607728
282292412
228698918
347936331
249473140
667006058
385530595
234024405
524452029
871686154
73351486
115718734
415219796
6724454
728022916
226...

result:

ok 200000 numbers

Test #11:

score: 20
Accepted
time: 514ms
memory: 847072kb

input:

91157 200000
0 391787528
0 128755192
3 417616809 157059090 109145241 105518767
4 168117201 184583673 611518413 449165163 785494567
0 335176806
0 767105706
6 197456690 26613590 508404062 688256680 114381875 509628059 822034065
1 134962121 111013253
0 273868329
0 995896690
0 727430687
4 52157529 93530...

output:

487041619
893275322
142402824
686731750
294920099
62183929
203079049
439067611
576528554
1804420
325046088
569012939
705848070
441856702
186405396
545740489
381312300
369454907
220000496
165233678
885597752
351769009
923484288
312188024
490873204
137214518
826339916
76816562
934429093
978384021
5417...

result:

ok 200000 numbers

Test #12:

score: 20
Accepted
time: 453ms
memory: 899716kb

input:

99054 200000
5 254591921 45593960 652041376 677254663 473209153 872993623
2 971834440 872618713 873774372
2 972786941 469418722 54936289
0 81056452
2 19714994 377576837 670989944
0 576526565
1 386619382 254596911
0 556584884
0 660262022
2 695328773 305942756 847812140
3 481581243 889943689 200600389...

output:

71125289
915873767
805882401
172961705
778575612
745456836
142968723
651540653
62367309
595540188
481360743
493180227
29659645
130302698
499160808
175915570
885742426
369665055
759536493
373302350
748795932
868454695
156649635
515858502
343254972
915736493
855732654
833555582
267541889
927511069
635...

result:

ok 200000 numbers

Subtask #4:

score: 20
Accepted

Test #13:

score: 20
Accepted
time: 215ms
memory: 479108kb

input:

50000 50000
1 610345459 691411093
1 476654936 529767753
1 8856530 640833948
1 961473497 456987897
1 462733802 114971681
1 662244461 415955667
1 717992437 907944693
1 346097988 176526535
1 805826501 182409272
1 33105050 971783530
1 45972429 258997374
1 964103067 796756441
1 958668755 735146502
1 9543...

output:

0
0
0
0
0
0
0
610268301
297428232
729194415
0
0
506964543
0
198345028
778136423
0
89695571
651093422
174709
799469987
0
0
0
0
374762615
64155221
0
644085102
355318236
625240586
0
0
0
0
611217681
0
246858712
0
946363040
766457000
0
0
0
0
0
0
0
885388926
324657374
0
0
608041499
0
0
0
595311003
0
0
790...

result:

ok 50000 numbers

Test #14:

score: 20
Accepted
time: 293ms
memory: 482312kb

input:

50000 50000
1 284188823 730123812
1 578529655 782975708
1 682107201 169640319
1 504919829 297067490
1 126340369 681480864
1 702290552 331608873
1 89823300 900339069
1 661791786 696739097
1 146107507 457302386
1 309885170 133384173
1 1601509 445278250
1 82308245 611577805
1 575317 145972663
1 3340187...

output:

118484783
20950737
827095992
192485904
949696395
760932709
0
827083836
737333618
0
0
936633428
869751868
21893026
0
0
700825516
0
0
140717292
495143473
757971245
71851829
758042728
168032853
336898224
82834617
0
50295595
473191194
0
603695852
88648030
191908163
0
0
347045240
304736441
10279888
28050...

result:

ok 50000 numbers

Test #15:

score: 20
Accepted
time: 221ms
memory: 477608kb

input:

50000 50000
1 908905842 879908939
1 69131120 893333490
1 766104239 502577285
1 598541702 20672714
1 19129534 562935613
1 17855501 931751363
1 817552765 924309216
1 601703730 928273412
1 280909912 198946276
1 259187488 350711225
1 460175073 829804287
1 142301100 182462131
1 440043596 503299121
1 4954...

output:

608336339
0
479640409
0
0
0
304101361
575455842
631421870
0
921143438
0
0
614891272
920725723
987924343
0
0
944939021
0
842440434
0
0
219630310
595973439
303974010
0
0
0
0
266178665
352670733
355014561
0
0
0
15870579
900144368
490797433
594447900
0
521603348
0
0
763764981
0
0
238461206
0
0
22187316
...

result:

ok 50000 numbers

Test #16:

score: 20
Accepted
time: 243ms
memory: 483480kb

input:

50000 50000
1 132666924 481468407
1 233104347 925423798
1 196520221 188340478
1 880316330 347865528
1 362038740 586184357
1 260977445 869456691
1 413836428 997205621
1 925267833 389145261
1 412474208 605923400
1 275275170 580329557
1 248067291 201190325
1 267032222 546518461
1 60371460 731907388
1 2...

output:

284858974
0
521392986
0
0
419555545
0
279474735
869174793
0
0
0
0
327341031
0
887506929
253382960
0
549720153
0
470223182
448985266
0
0
0
571599922
0
0
0
0
687095778
0
0
523720173
340816378
0
927700876
0
0
0
117671213
493623216
0
269849900
992438456
0
233002506
0
875191758
582797638
0
0
222273961
0
...

result:

ok 50000 numbers

Test #17:

score: 20
Accepted
time: 232ms
memory: 483396kb

input:

50000 50000
1 570249482 963041872
1 164483403 404765803
1 181145508 416450528
1 536381689 716629517
1 19355006 80481263
1 627992141 65443806
1 185587289 129800096
1 667577148 11179897
1 512133278 870239643
1 135475895 124891452
1 917154463 721424462
1 243207295 964207791
1 348452088 67572040
1 16668...

output:

76593910
267735832
0
0
379967837
128237686
782639460
0
0
155844091
934345203
666090547
241913187
0
0
884593508
0
199971361
0
876108660
362635493
0
0
0
0
93781856
635645613
903201788
0
794166948
108363160
0
0
937730015
0
641371731
0
836048882
0
584024075
0
0
0
0
169018859
0
0
0
0
984231395
0
0
102506...

result:

ok 50000 numbers

Test #18:

score: 20
Accepted
time: 258ms
memory: 481912kb

input:

50000 50000
1 374439028 76801984
1 198570918 279646664
1 738529796 230017198
1 93739509 610640325
1 525884738 858818589
1 949692556 761814293
1 235726510 7565628
1 45230953 841809717
1 624654181 697155421
1 56572048 898846486
1 181498104 803293558
1 123843798 593520342
1 590491409 791005242
1 888374...

output:

864276436
440159890
536780052
321076766
468541452
986423750
663920928
988866764
260419539
0
0
0
0
917177790
340374136
783267120
861409101
702416442
365736645
250814244
0
889464570
0
158883242
778105434
403578126
718091928
0
110804297
685559904
0
17649876
0
811219235
0
320574087
469972593
932031629
3...

result:

ok 50000 numbers

Test #19:

score: 20
Accepted
time: 220ms
memory: 475480kb

input:

50000 50000
1 33459023 378743148
1 649009512 322497285
1 4159024 354205478
1 635048826 663468389
1 822658913 27307310
1 195454131 803172665
1 875401287 11624886
1 289967362 733461614
1 251177354 546439677
1 600412174 876096433
1 230834162 878747260
1 269956920 918423510
1 254773805 746291985
1 29210...

output:

144329675
0
937010808
0
387987066
256520687
0
415222201
574050902
0
0
78330661
774146527
545659020
0
0
676856924
0
0
0
371281553
0
724389591
180883171
60120880
758706582
260395535
86733354
0
0
454943744
866940819
213813873
343349330
781027374
265021034
322573212
71290236
0
0
333346154
117482220
1005...

result:

ok 50000 numbers

Test #20:

score: 20
Accepted
time: 600ms
memory: 485548kb

input:

50000 50000
1 740199008 613475557
1 922880359 842126974
1 451019859 922790230
1 178429894 72393602
1 569458862 898768795
1 834271550 7640899
1 645877613 459724785
1 15126535 700620044
1 546332191 981494527
1 693370057 48191032
1 599613461 710991225
1 560674975 816111048
1 324902849 638444457
1 41924...

output:

874743447
472418696
893475459
768083962
844890219
0
491167288
0
662057644
33125578
0
0
0
380253379
790862397
453081406
0
0
64445999
613775426
0
0
0
669660760
597392638
0
37758869
0
11684083
11431232
0
827641705
191050687
39123082
0
821861901
0
658965581
0
107926632
720677708
0
0
240074723
949362284
...

result:

ok 50000 numbers

Subtask #5:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 71ms
memory: 214736kb

input:

19854 20000
1 150513542 240180212
0 987796281
0 90054116
1 191708494 438440429
0 192815969
0 867402303
1 531762469 210966860
2 95662022 345368425 199338548
0 269135053
0 816253511
0 66854944
0 319745952
0 202288549
0 492853777
0 410846691
0 824737426
0 821545014
0 72050044
0 534080091
1 542636124 52...

output:

913323334
0
0
0
0
0
0
0
0
0
0
0
901017606
0
0
0
0
0
954099396
0
0
432419999
0
0
0
0
0
0
0
761082946
259729654
0
0
0
0
790235355
933098570
356668385
125624181
0
0
0
0
917034405
0
321407524
0
671256345
39032345
0
0
676929142
0
0
0
0
0
0
0
0
910494481
0
0
0
733125978
0
0
835461650
0
154343024
690428959...

result:

ok 20000 numbers

Test #22:

score: 20
Accepted
time: 67ms
memory: 206844kb

input:

19416 20000
1 813812350 62928444
2 446931520 455152410 865811291
1 483245225 719509880
0 10630578
1 722267364 499990463
0 978295677
0 524126644
2 398577038 701788899 939255653
0 945953310
0 358029034
1 54632159 541649711
0 714215963
0 760637762
1 792667329 540131052
1 336329275 197811762
0 594815129...

output:

0
0
0
0
0
0
0
0
691960524
0
0
0
0
0
0
0
0
0
0
917519575
0
0
0
0
457906160
686627668
0
263875204
0
0
0
860458574
0
0
197732443
0
0
0
0
0
0
0
0
0
0
0
0
0
619069496
0
0
145464796
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
409777622
309523189
862407937
0
0
954411456
0
0
0
0
0
0
304719397
0
548777971
176155...

result:

ok 20000 numbers

Test #23:

score: 20
Accepted
time: 92ms
memory: 206516kb

input:

19645 20000
1 738216072 655062389
0 478261419
28 38522218 205802590 608351714 423733656 368037127 943951223 529243126 691493532 378826276 32699256 849862664 799709335 113704178 671006657 736000878 683394539 338518052 850384023 536423162 225738416 276528868 965415989 455460104 274736758 547583027 423...

output:

0
710035374
349663621
61124181
0
0
0
0
0
0
0
0
0
0
0
0
0
0
694466943
0
0
0
0
103025366
0
0
108158012
0
0
898653012
0
0
0
0
124734988
0
628306562
0
0
0
0
0
829055370
0
942321667
0
0
0
0
100614270
0
666765805
277413825
0
0
0
0
492192785
0
0
0
0
517011159
0
0
0
0
172598073
0
258513717
233404540
8590182...

result:

ok 20000 numbers

Test #24:

score: 20
Accepted
time: 67ms
memory: 210540kb

input:

19847 20000
4 815026590 930615671 256423615 192058090 553677398
0 854407447
3 121205405 14847480 141687199 287623506
2 379798536 291209656 593839232
1 352031200 841240984
0 295186159
0 841042115
0 679392127
0 420742492
2 891756622 260075296 417909411
0 645458804
0 681889229
0 29119165
0 99142741
3 7...

output:

470171472
213398321
0
0
55462715
0
338144412
0
0
0
0
0
0
0
698725184
0
0
0
0
47366191
0
317326831
0
0
0
239746199
214366720
0
0
0
0
0
279091720
0
86836316
0
0
0
35432299
0
308555884
0
319326811
0
0
0
305535605
0
358646410
0
0
131375996
0
0
0
0
0
0
0
0
570823027
0
0
80022023
0
954809219
0
0
0
0
26917...

result:

ok 20000 numbers

Test #25:

score: 20
Accepted
time: 75ms
memory: 210512kb

input:

19990 20000
3 575964327 889968526 762346953 464212918
0 91433877
0 762285092
1 703259059 61874142
2 130773960 696187633 280576635
1 163442506 294293968
0 134582456
0 525908094
2 981613234 494831823 871173319
0 320232487
0 951459253
0 725136632
2 48590419 631199232 992008959
1 860836891 867326137
1 6...

output:

90336621
0
741001438
326700634
0
0
0
0
0
0
925215064
0
0
863889195
0
0
0
0
0
576304546
0
0
0
0
583889751
0
0
0
0
0
0
813389361
0
0
0
0
0
0
0
108311310
0
0
653689603
0
0
0
91295650
0
347062400
0
0
0
0
620038417
846141331
99345412
0
581988923
0
0
0
0
365053652
29464872
917029396
788177507
288943414
0
...

result:

ok 20000 numbers

Test #26:

score: 20
Accepted
time: 74ms
memory: 210568kb

input:

19302 20000
1 140879209 815790450
0 263312184
2 357492390 407721624 927753023
17 329030216 687250506 904721674 66559073 150996400 582272412 140464848 806623151 989399143 916248414 596527559 964780629 802988469 182625819 764316767 594475067 203564894 275476377
0 547777698
0 34169169
0 93303556
0 5807...

output:

0
0
132910965
0
127962650
0
453633700
0
0
451482843
0
0
0
388743057
0
0
293560154
874329518
0
0
0
0
0
0
0
0
0
0
766081674
0
0
234642116
0
0
669563153
0
748448386
0
0
0
0
0
0
0
0
0
670410122
87350607
0
416323263
174794844
0
0
0
0
0
0
196859095
0
0
0
0
644332981
0
0
0
0
0
0
0
0
0
469599960
0
0
0
0
931...

result:

ok 20000 numbers

Test #27:

score: 20
Accepted
time: 72ms
memory: 206584kb

input:

19653 20000
1 906614788 500628713
0 988012762
0 284902421
0 704468047
0 872560811
1 907887753 600402772
0 767950811
0 118754288
0 290736011
0 217729487
1 190172852 683598286
0 723859834
0 220112811
0 448174595
0 39653265
0 770732977
0 458450918
0 438730398
0 183195813
0 191514564
0 2928127
0 3007322...

output:

0
244727120
0
0
132988676
354295625
0
667761790
0
0
0
0
0
822615931
0
0
0
0
0
0
504618092
0
973780962
0
0
0
0
737475269
0
0
0
383245743
0
0
10261578
551768502
0
835642191
0
0
69015099
0
0
773914454
0
0
0
0
0
193232063
0
0
0
0
0
230203189
0
0
0
0
0
0
0
0
120778708
0
949822563
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 20000 numbers

Test #28:

score: 20
Accepted
time: 68ms
memory: 198544kb

input:

19072 20000
0 910136763
1 809343877 577693489
0 805540439
0 728993500
0 234081004
1 891104112 210354669
0 262384318
0 568913493
0 376708574
1 145377149 421745582
0 108964429
0 697119989
0 615671424
0 697025092
0 222804661
0 927317484
1 66775292 771115618
0 405877157
1 977355316 502648356
1 218406564...

output:

0
0
0
558272462
0
0
0
0
0
0
0
328733917
446478844
0
0
0
0
0
0
848724549
0
0
980511070
0
0
597411269
0
127279175
0
0
0
0
0
739852501
0
0
0
0
0
0
568449517
589452941
0
0
0
0
791777304
0
0
0
0
114744131
322763812
613885875
52417149
0
0
0
0
149449664
0
0
644257795
0
725958460
276312482
499158209
8075964...

result:

ok 20000 numbers

Test #29:

score: 20
Accepted
time: 303ms
memory: 200572kb

input:

20000 20000
0 614936162
0 182986322
0 40697275
0 824161988
0 240412566
0 287310162
0 63000758
0 958628891
0 139827408
0 971860786
0 325782161
0 726800064
0 392930207
0 911604309
0 904980384
0 508941069
0 641836609
0 759719860
0 732767740
0 94630498
0 390558752
0 764408563
0 40013248
0 414628626
0 87...

output:

664811563
788614780
974744409
578158051
972633254
83874056
204528292
473798071
213046046
429307018
595958938
227031150
671368761
461998185
115917717
744731293
465171055
551785804
318236143
171800659
801541585
707676156
58721393
116249265
334321741
90511883
550891644
284752711
828872978
231691412
450...

result:

ok 20000 numbers

Test #30:

score: 20
Accepted
time: 81ms
memory: 212516kb

input:

19446 20000
1 701024899 61691599
0 459112272
0 605953973
0 852714844
0 174821235
1 313026866 19060724
0 553043793
1 837260834 209473757
0 445224261
0 18895399
1 976728020 509710102
0 332645932
0 661618262
0 204178386
0 269435005
0 736889829
0 397995492
0 866964923
0 132403278
0 596284173
0 958984850...

output:

534451823
0
0
607037735
558413343
0
0
0
0
0
0
0
0
0
0
0
673258724
0
869080507
506727857
9843331
0
85465239
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
398060444
882747749
0
0
0
0
0
0
214087586
0
0
0
0
0
0
0
0
0
0
0
0
733471287
0
636321624
0
351918892
0
0
856397457
0
0
0
0
0
0
0
0
91532953
0
0
0
0
0
237024413
63...

result:

ok 20000 numbers

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 #31:

score: 30
Accepted
time: 697ms
memory: 922628kb

input:

99594 200000
0 792083461
0 914312025
0 34350651
0 767686614
0 126625954
1 469369269 944342533
0 612174706
0 659144535
0 980769871
0 11719240
0 686570452
0 557384020
0 775725208
1 206987845 317493823
0 549993972
0 243134305
0 50842360
2 694278935 105006374 564812234
0 273854368
0 949758784
0 80244234...

output:

109399968
0
0
0
448463153
0
0
818361960
238762152
489879263
532197351
0
0
0
0
0
143357594
0
0
0
0
0
0
0
0
0
0
737808980
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
848155620
0
788868258
0
0
0
547711349
0
0
0
0
0
0
0
0
0
0
0
0
0
0
338269278
0
575775483
0
532938132
0
0
0
0
611122990
718119560
0
0
0
...

result:

ok 200000 numbers

Test #32:

score: 30
Accepted
time: 734ms
memory: 922868kb

input:

99035 200000
0 516279412
0 412939901
0 606838540
0 387878075
1 262965855 768053906
5 19202246 37691309 63031387 385686181 758382124 552090450
2 971931101 451423603 833655477
2 420564093 201427455 744193012
0 562042321
0 244312780
1 793149487 305896859
0 270808962
2 141955607 783349908 417999654
0 42...

output:

0
0
0
0
0
0
0
0
993301929
0
0
0
0
0
0
737055174
406546071
0
0
666458859
0
0
0
0
507321872
169036937
0
0
0
0
0
0
0
967598644
182481323
0
0
0
0
0
0
0
0
0
450225917
0
364239472
0
0
0
0
0
184083094
898158431
0
737677208
0
0
0
47593713
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
996953495
0
0
0
8084585...

result:

ok 200000 numbers

Test #33:

score: 30
Accepted
time: 623ms
memory: 912208kb

input:

99083 200000
9 812519718 737365909 60790048 110734972 345456242 716203655 119077807 648818873 468118712 147036529
1 297548567 794303861
5 641870110 181984618 69051204 758849582 714652096 396595861
1 560530303 275242004
0 574153100
0 317052463
0 480726959
3 110710840 830240927 248270237 978423303
0 5...

output:

0
0
567845892
29922025
0
0
0
0
134770615
0
0
0
0
0
0
0
0
0
471511799
0
0
0
0
0
0
0
0
0
0
0
0
0
85185078
0
0
581149537
0
540973163
0
0
0
747061501
751392383
0
0
594973285
0
123772660
0
0
0
0
0
0
0
0
304308252
260946625
121532287
0
340335526
0
0
0
0
0
0
0
0
0
0
0
148043643
0
0
0
0
575135327
0
54065753...

result:

ok 200000 numbers

Test #34:

score: 30
Accepted
time: 913ms
memory: 924996kb

input:

99785 200000
0 280332852
0 463734447
0 171818841
0 299075569
0 863711022
0 907616285
0 234302886
1 977699188 129280311
0 460473318
0 570409123
0 29676746
0 906924939
0 929635560
0 444520539
0 61650377
1 176555744 745995937
0 767706179
0 697499158
1 968035736 79077206
0 853004807
0 669726083
0 917877...

output:

0
480380633
100067255
0
0
736885183
0
0
960940710
0
579705665
0
0
0
0
598371980
0
0
0
0
0
693279318
0
0
22276414
0
0
0
0
0
806866513
990455994
585969490
381728870
0
428502384
890759743
0
0
0
0
0
797184734
0
0
914101649
0
442980166
0
0
699124593
0
0
226141455
0
765484286
156198071
0
0
0
723454355
0
0...

result:

ok 200000 numbers

Test #35:

score: 30
Accepted
time: 673ms
memory: 922500kb

input:

99006 200000
2 697598318 566784456 782231144
0 637183338
3 892921153 312022999 614093234 489700823
6 565253346 400806749 352924076 615575261 636132162 769385558 185304555
1 354998163 679380727
0 808808987
0 914852081
0 609747589
4 53572246 687372077 109442084 787697001 647385656
4 212951526 24244475...

output:

873398887
0
908891814
0
0
0
0
854361978
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
681498313
0
0
0
0
0
0
0
0
192671131
0
0
0
0
0
0
775815056
0
886750665
0
0
0
0
256584318
170858682
0
0
0
0
0
61850051
0
0
0
0
0
0
0
0
0
29520959
0
0
866066650
0
0
0
895412488
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #36:

score: 30
Accepted
time: 632ms
memory: 910436kb

input:

98985 200000
0 969193375
0 511357294
0 328085529
1 205258866 499880016
0 933319732
0 609835434
0 135107485
0 781419224
0 620351326
0 740789220
0 179692891
1 505604147 785232172
0 748252583
1 963799862 977536089
0 946638152
0 503453397
0 783885375
0 243538347
1 358016785 386995362
0 282713402
0 29462...

output:

0
0
0
0
0
401910156
0
0
0
0
0
0
0
0
0
0
601764437
0
0
0
0
0
0
753618471
0
0
305995424
0
0
0
0
0
0
0
0
0
0
0
431722758
0
0
0
0
798679245
773158656
0
0
0
0
0
0
0
0
0
0
0
0
0
0
170839700
0
0
0
0
0
0
0
0
0
0
0
0
0
0
156648441
0
0
0
0
0
0
0
439657527
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
347352285
0
0
0
0
0
...

result:

ok 200000 numbers

Test #37:

score: 30
Accepted
time: 627ms
memory: 920960kb

input:

99106 200000
0 536357478
1 248797118 129050430
1 106948594 292418714
0 510102794
1 133026708 722417074
0 180653240
0 446667653
0 287445048
0 661059497
0 594996611
0 819285540
0 783212723
0 210212100
0 693574734
0 112477560
0 674105046
0 248594760
1 158166781 850888375
0 497357910
1 640562644 6835468...

output:

0
0
0
0
0
0
0
0
957985443
0
0
0
0
0
0
0
966288616
0
520774584
0
0
0
321026238
0
0
0
0
0
513903889
162689619
0
0
0
0
0
265617770
0
97712317
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
953800844
0
0
0
0
0
0
0
0
0
0
424167855
0
0
0...

result:

ok 200000 numbers

Test #38:

score: 30
Accepted
time: 678ms
memory: 865272kb

input:

99337 200000
1 498475374 77807972
0 710939325
0 257489757
0 366384158
1 489698229 751337044
0 633357139
1 830049927 866194558
2 341614269 142470787 621653008
1 673980230 442738390
1 366325112 428366642
1 26626735 639931615
0 764633730
0 474395039
0 135657003
0 722380645
0 319814064
0 984404609
1 665...

output:

978464904
0
0
503368730
0
0
0
0
0
0
0
0
479532558
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
645577386
0
0
0
0
0
0
0
0
0
0
0
0
0
255376668
0
0
453568313
0
496966692
0
0
0
0
0
0
0
46766572
0
0
0
0
0
0
0
0
0
0
0
0
0
963187989...

result:

ok 200000 numbers

Test #39:

score: 30
Accepted
time: 652ms
memory: 920364kb

input:

99397 200000
1 908659187 39931868
0 672134567
2 102740510 36677225 150007181
2 471908611 266747812 357960206
0 136686904
1 551385776 27154055
6 897495677 293831234 982707521 723038522 356184574 855103517 336715204
0 60799780
0 77841372
3 798508674 561483859 147801908 665942476
0 545064278
1 19419329...

output:

0
0
0
0
0
0
0
347981445
556682855
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
708396072
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
209956118
0
0
0
0
0
0
0
0
606367784
0
0
0
0
0
0
0
0
0
0
368648402
0
0
0
0
0
65368737
634556670
0
0
0
467587270
0
877360716
0
0
0
518078588
0
0
0
0
0
476405426
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15193...

result:

ok 200000 numbers

Test #40:

score: 30
Accepted
time: 659ms
memory: 918612kb

input:

99251 200000
0 837618356
0 469241097
0 304116169
0 750862544
2 26173593 953672229 151599840
0 271279589
0 403113292
0 333427913
1 97867997 556460649
0 943168531
1 509903042 94841079
0 796070535
0 14009153
0 146895987
0 946947992
0 919251812
0 284637821
1 753226123 593010004
0 628694067
0 653161546
0...

output:

0
0
0
0
671158217
0
0
0
0
0
0
0
0
541497228
0
0
0
0
0
0
0
0
0
0
0
0
0
451481615
0
137067247
0
0
0
0
919959487
0
0
0
0
0
0
0
0
0
0
380863721
0
271452193
0
0
768517272
0
0
0
0
0
0
0
0
493731090
0
0
0
0
0
0
0
17031558
0
0
0
0
0
0
0
591218400
0
0
0
0
0
0
0
0
0
0
0
0
241982234
0
0
0
0
0
0
0
0
564614622
0...

result:

ok 200000 numbers

Test #41:

score: 30
Accepted
time: 598ms
memory: 927108kb

input:

99630 200000
0 5339176
0 183460101
0 78628974
0 71182183
1 821234975 144067318
0 956592536
0 82564025
1 334026285 237551854
0 154265800
0 260692099
0 260062211
1 456318703 276854147
1 587509429 4330857
0 381073041
0 675959015
0 965036457
0 283513233
2 316566027 40169150 897149637
2 770213563 2846924...

output:

309884962
263648364
548342103
189447330
403042313
0
164867241
51305764
463138099
0
0
63741792
0
42511729
0
486791755
0
102254495
0
0
0
0
656480709
0
0
0
680530049
686273532
998139721
0
0
0
783513253
720932489
0
812024439
938247438
847540531
669361421
0
601802190
0
990014943
517648770
672809095
96241...

result:

ok 200000 numbers

Test #42:

score: 30
Accepted
time: 700ms
memory: 924032kb

input:

99457 200000
0 520433982
0 600033942
0 597120011
1 131160787 64001098
1 573895343 649276549
0 195519651
0 475243851
0 289757468
0 804871132
0 666098884
1 231714454 628830730
0 890957706
0 83693875
0 301651579
0 291625927
0 404424239
0 181052960
1 536789543 288778943
0 166973270
1 345291754 449612874...

output:

0
0
0
0
304528688
0
0
766584610
0
0
0
0
656906535
777040558
0
269231403
0
757347049
0
0
447594777
0
881831292
914091245
0
0
0
403266514
741683002
526265855
0
0
0
0
967262076
0
856159414
0
0
0
782919249
327891282
0
572486461
0
0
179183639
735080713
682386725
0
0
0
0
0
0
0
8042811
82897394
446711502
1...

result:

ok 200000 numbers

Test #43:

score: 30
Accepted
time: 799ms
memory: 932848kb

input:

99862 200000
0 329513920
0 456692223
0 389322229
0 711051456
1 621965494 55887520
0 787567565
0 84446280
0 826368108
1 453561473 162705929
0 468696179
0 57014528
1 423197442 911428275
1 331659854 508452048
0 47732231
0 510804785
0 620213653
0 403025819
0 14580380
0 901519255
0 283742795
1 181801236 ...

output:

0
839931845
157764911
0
0
215894684
46271392
44093675
493597065
400043755
456226878
178843285
0
0
0
125583360
556511446
782225218
336159443
0
48437262
91755146
356318949
0
982396681
325921161
888415778
237790380
670546292
0
0
217544729
0
859956339
441975647
0
759366102
0
28623977
849837651
238938530...

result:

ok 200000 numbers

Test #44:

score: 30
Accepted
time: 666ms
memory: 930644kb

input:

99826 200000
1 323757533 870721963
2 904066510 788467099 240486432
2 180249005 71060394 53648532
0 164816460
0 468389437
0 258522341
1 182854620 988856023
0 139155677
0 858918287
1 578115690 581264910
1 848138916 498790873
0 817795940
1 629829076 517122055
1 131196258 513843426
0 281344156
1 5802285...

output:

510251661
322843343
253640725
175763102
708684462
0
0
0
309152124
420069658
913416863
0
38362214
0
263332631
642129577
0
0
871646207
298848615
0
329074227
301650376
0
0
394836751
0
0
0
0
0
293433700
0
0
0
0
0
800387736
13640879
738620452
923035045
0
626487991
973833608
0
830455251
0
316717789
0
0
56...

result:

ok 200000 numbers

Test #45:

score: 30
Accepted
time: 636ms
memory: 931232kb

input:

99664 200000
1 670597153 137196970
0 448037909
2 395548978 50888515 225301038
1 906680594 111745385
0 645929612
0 376568237
0 996010090
0 312802967
1 241662879 805185907
0 137707642
0 574859364
0 21632077
0 350124558
0 761906213
1 413353455 722297338
1 105639958 81668975
1 442545161 130820256
0 9458...

output:

0
13298333
796411980
717176960
427401440
859158010
0
0
554287565
0
6804644
0
837333422
850263412
749968216
21290770
716013140
0
0
0
609035567
419341980
574978215
229688216
205887830
173899597
79717147
620548356
156657047
0
0
549142000
7967802
0
744725557
381309597
0
0
152201862
191766672
0
870908035...

result:

ok 200000 numbers

Test #46:

score: 30
Accepted
time: 555ms
memory: 923100kb

input:

99936 200000
1 838410326 559781352
1 15519661 512473228
0 686587663
0 652469143
0 961809442
0 902588805
2 520910408 493321502 493526367
0 307197602
0 512061775
0 463074640
0 795071099
0 448849408
0 522272325
0 867669253
0 791911631
0 796271393
0 800296456
0 285955113
1 743247418 779908196
0 51017333...

output:

0
0
0
305107306
379150599
42011282
0
0
0
161166073
0
0
864848153
295413953
0
0
256383330
699111476
0
364923213
0
0
0
381145587
0
210879721
0
466483292
0
228632730
781776361
0
609583689
38035139
0
0
766392384
496307425
872071527
327088206
0
901406598
0
82575915
0
186066196
976518077
838408449
0
34449...

result:

ok 200000 numbers

Test #47:

score: 30
Accepted
time: 673ms
memory: 924988kb

input:

99088 200000
0 364832553
0 178745750
0 835029198
1 279742807 102370162
0 834347368
0 612774133
0 180761166
1 379950497 157310301
0 29363731
0 509494437
0 700030867
1 935402282 883975840
0 982734964
0 279823368
0 654117002
0 396925115
0 8330908
0 8204127
0 175734468
0 292209557
0 530551196
0 24939281...

output:

84290885
172473711
320359781
0
686175639
997982871
739107336
0
70395054
651442000
212364566
606189810
340398452
369355651
0
0
753033235
0
0
241596491
31250190
937363693
657293623
0
283648025
863116720
740290686
0
703070193
0
0
649865908
260970173
628279215
0
0
552350281
692378378
829193962
26701348
...

result:

ok 200000 numbers

Test #48:

score: 30
Accepted
time: 683ms
memory: 919076kb

input:

99145 200000
0 143560353
0 708439926
0 701452428
0 637315652
0 10858266
1 324024099 421464572
1 7867270 718774170
0 464413576
0 182983498
1 311377044 986639223
0 490148621
0 543909721
0 102531250
0 483589345
2 88597038 552846483 990387576
0 993560233
0 546852218
0 791201835
0 696249807
0 246306695
0...

output:

0
739694884
433769957
584558975
885259821
0
0
0
843472324
655955792
931400009
0
314207102
486068606
0
0
0
132839733
375394984
0
18557269
528832436
0
0
0
947710310
0
377197977
0
196747374
0
703143919
0
0
593537487
5538491
430096964
0
0
0
0
738126639
770283456
0
422226849
341610677
469499040
0
3008630...

result:

ok 200000 numbers

Test #49:

score: 30
Accepted
time: 762ms
memory: 932384kb

input:

99917 200000
1 606379853 230564505
0 861782624
1 166045839 446984409
2 262143347 271529930 75070248
1 764120674 560497036
0 493657528
0 60011341
0 384737505
0 485851690
0 59804027
0 272031503
0 101931073
0 887059536
0 202260726
0 777511966
0 834899633
0 27259216
0 449327211
0 45993148
0 460191658
0 ...

output:

605186308
597933348
865908650
0
494051001
833085633
765000024
317367680
231872632
80637105
0
114289353
0
945516164
0
668977591
549708654
300760382
0
194940063
0
0
0
149218300
0
0
627379931
0
421969276
181354550
0
0
0
943014191
0
0
0
206946838
0
0
751545512
840917385
0
455228946
0
0
295557208
0
40024...

result:

ok 200000 numbers

Test #50:

score: 30
Accepted
time: 653ms
memory: 927100kb

input:

99626 200000
0 543722507
0 832417757
0 634572868
0 523056298
0 604006305
0 105205567
0 642477632
0 273861057
0 159049568
0 278889755
0 534451219
0 215637712
1 496543777 850957896
0 527887191
0 797572231
2 351423761 279337124 419541603
0 138972236
0 742639412
0 727952849
0 810781862
0 249581579
0 536...

output:

112541029
161741932
287403817
0
438982353
0
31544875
936722186
751598883
597267944
328798533
745429287
419961835
165995330
576022299
231729203
0
0
0
686554191
0
0
399196180
984422139
580466621
0
0
752262932
529783655
68016352
0
649283329
0
837279914
162398064
160608005
0
0
0
142098038
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #51:

score: 30
Accepted
time: 445ms
memory: 895476kb

input:

100000 200000
0 613643917
0 835910163
0 418097458
1 813106042 240507736
0 563154711
2 915116833 242569780 645436195
1 983291419 722923451
2 275095780 639835018 487159272
0 363502753
0 864558407
0 52697997
1 99815226 844841329
0 174326710
1 806922141 55304067
2 804584045 470065735 376654165
0 3357850...

output:

0
314701272
301367246
0
0
0
307274596
0
979251102
0
0
0
0
0
0
0
0
0
0
429196314
0
0
0
0
105273277
0
0
950508916
306261739
247158638
0
0
443091520
0
0
0
778682554
0
0
0
149346952
0
871501201
0
0
0
127247196
0
0
0
0
0
198153970
893188252
0
841579618
24284813
537727232
616030760
0
0
0
860476381
5104688...

result:

ok 200000 numbers

Test #52:

score: 30
Accepted
time: 482ms
memory: 892112kb

input:

100000 200000
0 654076004
0 384031444
0 119374495
0 277579093
1 85876027 638148431
0 936480874
0 337004560
0 601574248
2 841095919 465239266 978449729
0 612063963
0 944928965
0 677239581
0 381653436
0 840246095
0 88260192
0 494499583
1 651377177 499867035
0 43926530
0 835699069
0 100921766
0 5710994...

output:

659159881
0
0
244713927
0
38053686
0
370345134
0
676351040
195874172
331050819
0
311975954
0
0
0
0
547003239
0
0
784593602
10749736
810352369
281275711
0
849350910
0
0
0
0
0
860912575
499058071
0
0
0
0
472871922
0
0
0
0
0
0
0
0
382020240
0
0
0
0
0
501714412
489877411
677514091
0
382886760
0
0
0
0
0
...

result:

ok 200000 numbers

Test #53:

score: 30
Accepted
time: 737ms
memory: 825200kb

input:

100000 200000
0 767950655
0 819206798
0 632776873
0 615458376
0 748952719
0 164743123
0 484317825
0 364077066
0 416857111
0 21162008
0 892795892
0 54757732
0 501046447
0 795792626
0 18991377
0 37548129
0 522283271
0 522400896
0 27035995
0 207431962
0 960915263
0 289342447
0 903308477
0 986811346
1 5...

output:

0
0
0
0
320911640
0
0
0
835380661
0
101129300
0
0
436510016
0
721709531
0
0
532297750
910683734
0
0
0
482614108
0
0
0
404027771
0
0
0
472509567
0
421942867
0
813473143
175018943
0
0
139332966
0
0
0
0
0
831264950
0
0
956587496
479700944
0
0
0
472306267
0
0
896405196
0
0
0
0
0
0
0
44420065
674247742
0...

result:

ok 200000 numbers

Test #54:

score: 30
Accepted
time: 401ms
memory: 892328kb

input:

100000 200000
80 975550954 194913535 93700686 603729067 514440779 5168754 493927441 225485222 367936123 66713098 693546661 995088484 849731735 241941370 756949641 477954618 773614993 153565165 321282091 75959417 436627529 864112020 870058819 110164879 875241154 473099607 381812633 879132931 95273234...

output:

0
421673387
618293885
0
569777033
761083826
0
0
143262552
0
252024071
168883593
625390897
0
0
885716630
446743153
0
748901923
0
0
958947377
381449865
0
0
0
0
0
0
338243090
0
0
306769426
0
492995267
642640342
0
625868541
0
264120975
0
601461549
528185255
762292312
0
0
0
193716429
0
235099016
0
0
9188...

result:

ok 200000 numbers

Test #55:

score: 30
Accepted
time: 688ms
memory: 912516kb

input:

100000 200000
1 370861671 597066317
1 279824219 835160176
2 890487447 312744954 293454271
0 256787799
0 525148622
0 310156426
1 30788965 106411304
0 860888126
0 13034841
0 91907701
0 96687299
0 448250210
1 316241974 721488419
2 317152672 491377577 192877359
0 830289753
0 769751867
0 119369072
0 2154...

output:

0
495342720
0
932168052
0
597533739
0
0
95979658
0
589148997
271163162
861440993
0
38549103
868360666
89387346
0
0
378468426
0
0
0
0
0
549989891
839865697
0
733467239
0
0
740630196
575730895
221141247
0
223984070
417737077
0
0
0
383572216
727210228
0
996006344
0
0
0
0
0
0
115192594
99462280
0
209476...

result:

ok 200000 numbers

Test #56:

score: 30
Accepted
time: 308ms
memory: 840696kb

input:

100000 200000
0 855935515
0 503029155
0 530279261
0 946473936
0 32581962
0 601598388
0 288273127
0 425515309
0 728814403
0 797556500
0 70386731
0 693458131
0 178352976
0 934593143
0 810333890
0 650702505
0 132404762
0 557444214
0 187801602
0 713129003
0 206777009
0 579160604
0 51113448
0 786951044
0...

output:

439964729
0
101250422
377604701
0
928328203
0
311197502
0
761687584
0
0
365258170
0
939530105
191412194
0
0
879112407
536002240
0
369080761
695996586
464890584
0
0
0
0
0
860862436
0
0
791830786
52010983
0
0
0
0
0
903621456
340505284
0
0
0
0
0
0
0
0
157762756
730657042
406293120
247221862
0
0
0
0
0
8...

result:

ok 200000 numbers

Test #57:

score: 30
Accepted
time: 578ms
memory: 901508kb

input:

100000 200000
0 957889022
0 214078695
1 483864879 225025140
0 272321791
1 186288580 21482959
0 837319618
0 63552234
0 124514667
0 266485699
0 681756899
1 73283727 713211035
0 208369034
0 527424469
0 853819875
1 318538042 411538896
0 238374843
1 401815602 35413471
0 679451288
0 721170212
0 237460435
...

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
29283727
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200000 numbers

Test #58:

score: 30
Accepted
time: 309ms
memory: 882924kb

input:

100000 200000
0 237677757
0 445038744
1 48499603 865005690
0 80453651
1 872325575 771904118
0 357606035
0 35698382
0 670168087
1 68812218 129958009
0 727178484
3 669452613 594874653 257476740 684536854
0 933422955
2 26415111 487769382 950606834
0 822838477
0 395410818
1 464093805 146648967
0 5402800...

output:

0
142431692
0
0
64525901
487482466
0
0
623335869
0
0
0
44757631
0
0
0
377565055
258331352
69775601
653608658
0
0
0
616970041
0
0
686456182
0
0
0
0
0
654294845
0
314063149
0
669527678
257486799
0
784911411
0
116961556
0
0
265128386
0
0
0
786118866
0
839678272
0
0
0
0
886976855
754239384
0
379664936
5...

result:

ok 200000 numbers

Test #59:

score: 30
Accepted
time: 569ms
memory: 915008kb

input:

100000 200000
0 564710724
0 208139081
84 824126092 287147669 859164352 91151335 630815103 51548342 878003285 701830355 258617205 894838138 961514745 511239843 848675884 55652377 908595648 210679303 878326125 349020875 810714103 246980554 33781344 344616238 841820124 279994891 579099712 812328036 667...

output:

33767043
0
114715016
0
0
689242238
0
0
0
0
29286069
249435181
0
0
0
111465282
830221170
0
571082250
0
0
710434908
0
0
0
820068292
562220327
0
233440294
0
0
0
0
0
289233587
0
102216699
0
557677325
0
629810979
0
0
0
670602664
0
626612356
0
0
0
0
975935882
937193482
791983888
560865529
0
171942466
0
0
...

result:

ok 200000 numbers

Test #60:

score: 30
Accepted
time: 575ms
memory: 916224kb

input:

100000 200000
0 158275260
1 287953086 578797831
0 474574496
0 190421636
1 828207062 780536839
0 73629262
0 127353181
0 399256593
2 581386154 715563215 268353972
1 387565681 225637914
1 640238681 118929274
0 297084940
1 557699324 177235182
0 25121062
0 722998173
1 597523931 149714293
0 108543196
1 72...

output:

931454750
0
741621372
0
508359232
0
0
0
268403560
0
317163570
0
0
0
0
417499296
0
857602890
0
0
769309753
712999564
0
243212495
169057700
405270682
0
456986014
0
0
0
0
0
253419485
0
703169565
17102526
0
611555671
607560013
0
458232888
0
0
0
0
0
0
15394385
0
137706560
334513057
0
0
0
633320663
129680...

result:

ok 200000 numbers