QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#685045#9373. Query on TreewyxqwqAC ✓1456ms97560kbC++147.6kb2024-10-28 17:17:312024-10-28 17:17:32

Judging History

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

  • [2024-10-28 17:17:32]
  • 评测
  • 测评结果:AC
  • 用时:1456ms
  • 内存:97560kb
  • [2024-10-28 17:17:31]
  • 提交

answer

#include<bits/stdc++.h>
#define vectorwyx maze
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define gtc getchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline ll llread(){signed ch=getchar();ll x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
template<typename T> void out(T *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=2e5+5,K=9;
const ll inf=1e18;
vector<int> e[N];
int bfn[N],tb,bod[N],dod[N],bL[N][K+2],bR[N][K+2],fa[N][K+2],dL[N],dR[N],td,n;
ll a[N];

void init(){
    fo(i,1,K) fa[1][i]=0;
    fo(i,1,n) e[i].clear(),fa[i][0]=i;
    fo(i,1,n) fo(j,0,K) bL[i][j]=n+1,bR[i][j]=0;
    tb=td=0;
}

void dfs1(int x){
    for(int i:e[x]) if(i!=fa[x][1]){
        fo(j,1,K) fa[i][j]=fa[x][j-1];
        dfs1(i);
    }
}

void bfs(){
    queue<int> q;q.push(1);
    while(!q.empty()){
        int x=q.front();q.pop();
        bfn[x]=++tb;bod[tb]=x;
        fo(i,0,K) if(fa[x][i]) sml(bL[fa[x][i]][i],bfn[x]),big(bR[fa[x][i]][i],bfn[x]); 
        for(int i:e[x]) if(i!=fa[x][1]) q.push(i);
    }
    // cout<<"bfn:";out(bfn,1,n);
}

void dfs2(int x){
    if(!bR[x][K]) re;
    dL[x]=++td;dod[td]=x;
    for(int i:e[x]) if(i!=fa[x][1]) dfs2(i);
    dR[x]=td;
}

struct Seg{
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
struct Node{
    ll mx,tag;
    Node(){mx=-inf,tag=0;}
    void upd(ll &k){mx+=k,tag+=k;}
}tr[N<<2];
void ps(int x){tr[x].mx=max(tr[ls].mx,tr[rs].mx);}
void pd(int x){
    ll &k=tr[x].tag;
    tr[ls].upd(k);
    tr[rs].upd(k);
    k=0;
}
void build(ll *a,int x,int l,int r){
    if(l>r) re;
    // printf("build(%d,%d,%d)\n",x,l,r);
    if(l==r){
        tr[x].mx=a[l];
        tr[x].tag=0;
        re;
    }
    tr[x].tag=0;
    build(a,ls,l,mid);
    build(a,rs,mid+1,r);
    ps(x);
}
void update(int x,int l,int r,int L,int R,ll v){
    if(L>R) re;
    // printf("update(%d,%d,%d,%d,%d,%lld)\n",x,l,r,L,R,v);
    if(l>=L&&r<=R){
        tr[x].upd(v);
        re;
    }
    pd(x);
    if(L<=mid) update(ls,l,mid,L,R,v);
    if(R>mid) update(rs,mid+1,r,L,R,v);
    ps(x);
}
void set(int x,int l,int r,int aim,ll v){
    if(l==r){tr[x].mx=v;re;}
    pd(x);
    if(aim<=mid) set(ls,l,mid,aim,v);
    else set(rs,mid+1,r,aim,v);
    ps(x);
}
ll ask(int x,int l,int r,int L,int R){
    if(L>R) re -inf;
    if(l>=L&&r<=R) re tr[x].mx;
    pd(x);
    if(R<=mid) re ask(ls,l,mid,L,R);
    if(L>mid) re ask(rs,mid+1,r,L,R);
    re max(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
}
};
ll tmp[N];

namespace Tree_b{
Seg b;
void build(){fo(i,1,n) tmp[i]=a[bod[i]];b.build(tmp,1,1,n);}
void update(int l,int r,ll v){b.update(1,1,n,l,r,v);}
ll ask(int l,int r){
    re b.ask(1,1,n,l,r);
    // ll ret=-inf;fo(i,l,r) big(ret,b[i]);
    // printf("Tree_b::ask(%d,%d)=%lld\n",l,r,ret);
    // re ret;
}
}

namespace Tree_d{
Seg tag,mx;
void build(){
    fo(i,1,td) tmp[i]=0;
    tag.build(tmp,1,1,td);
    fo(i,1,n) tmp[i]=-inf;
    fo(i,1,n) if(bR[i][K])
        fo(j,bL[i][K],bR[i][K]) big(tmp[dL[i]],a[bod[j]]);
    mx.build(tmp,1,1,td);
    // cout<<"Tree_d::mx:";out(mx,1,n);
}
void update(int l,int r,ll v){
    // printf("update(%d,%d,%lld)\n",l,r,v);
    // fo(i,l,r) tag[i]+=v,mx[i]+=v;
    tag.update(1,1,td,l,r,v);
    mx.update(1,1,td,l,r,v);
}
ll ask(int l,int r){
    re mx.ask(1,1,td,l,r);
    // ll ret=-inf;fo(i,l,r) big(ret,mx[i]);
    // printf("ask(%d,%d)=%lld\n",l,r,ret);
    // re ret;
}
void clr_tag(int x){
    Tree_b::update(bL[x][K],bR[x][K],tag.ask(1,1,td,dL[x],dL[x]));
    tag.set(1,1,td,dL[x],0);
    // tag[dL[x]]=0;
}
void reset(int x){
    mx.set(1,1,td,dL[x],Tree_b::ask(bL[x][K],bR[x][K]));
    // mx[dL[x]]=Tree_b::ask(bL[x][K],bR[x][K]);
}
}

void gao(int l,int r,int v){
    // printf("gao(%d,%d,%d)\n",l,r,v);
    if(l>r) re;
    
    int x=bod[l];
    assert(fa[x][K]==fa[bod[r]][K]);
    x=fa[x][K];
    if(!x){Tree_b::update(l,r,v);re;}
    Tree_d::clr_tag(x);
    Tree_b::update(l,r,v);
    Tree_d::reset(x);
}

ll nbor(int x,int k,int v){
    // printf("nbor(%d,%d,%d)\n",x,k,v);
    if(!fa[x][1]){
        ll ret=-inf;
        fo(i,0,k){
            if(!bR[x][i]) break;
            gao(bL[x][i],bR[x][i],v);
            big(ret,Tree_b::ask(bL[x][i],bR[x][i]));
        }
        re ret;
    }
    // puts("qwq");
    gao(bL[x][k],bR[x][k],v);
    // puts("qaq");
    if(k==0) re Tree_b::ask(bfn[x],bfn[x]);
    gao(bL[x][k-1],bR[x][k-1],v);
    ll ret=max(Tree_b::ask(bL[x][k],bR[x][k]),Tree_b::ask(bL[x][k-1],bR[x][k-1]));
    re max(ret,nbor(fa[x][1],k-1,v));
}

void solve(){
    cin>>n;int q=read();init();
    fo(i,1,n) a[i]=llread();
    fo(i,2,n){
        int x=read(),y=read();
        e[x].pb(y),e[y].pb(x);
    }
    dfs1(1);
    bfs();
    td=0;dfs2(1);
    // fo(i,1,n){cout<<i<<":";fo(j,0,K) printf("[%d,%d] ",bL[i][j],bR[i][j]);HH;}
    // fo(i,1,n) printf("[%d,%d] ",dL[i],dR[i]);HH;
    // fo(i,0,K) printf("[%d,%d] ",bL[5][i],bR[5][i]);HH;printf("[%d,%d]\n",dL[5],dR[5]);
    Tree_b::build();Tree_d::build();
    // cout<<"mx:";out(Tree_d::mx,1,td);
    while(q--){
        int o=read(),x=read();
        if(o==3){
            int v=read();
            ll ans=-inf;
            fo(i,0,K-1){
                if(!bR[x][i]) break;
                gao(bL[x][i],bR[x][i],v);
                big(ans,Tree_b::ask(bL[x][i],bR[x][i]));
            }
            if(bR[x][K]) Tree_d::update(dL[x],dR[x],v),big(ans,Tree_d::ask(dL[x],dR[x]));
            cout<<ans<<'\n';
            co;
        }
        int k=read(),v=read();
        if(o==1){
            ll ans=-inf;
            if(bR[x][k]) gao(bL[x][k],bR[x][k],v),big(ans,Tree_b::ask(bL[x][k],bR[x][k]));
            fo(i,1,k){
                if(!fa[x][i]) break;
                int l=bL[fa[x][i]][k-i],r=bR[fa[x][i]][k-i];
                if(!r) co;
                if(i==k){gao(l,r,v);big(ans,Tree_b::ask(l,r));break;}
                int L=bL[fa[x][i-1]][k-i-1],R=bR[fa[x][i-1]][k-i-1];
                if(!R){gao(l,r,v),big(ans,Tree_b::ask(l,r));co;}
                if(l<L) gao(l,L-1,v),big(ans,Tree_b::ask(l,L-1));
                if(r>R) gao(R+1,r,v),big(ans,Tree_b::ask(R+1,r));
            }
            if(ans==-inf) puts("GG");
            else cout<<ans<<'\n';
            co;
        }
        cout<<nbor(x,k,v)<<'\n';
    }
}

signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    int T=read();
    while(T--) solve();
    return 0;
}
}
/*
1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1
-------------------------------------------------

*/










signed main(){re vectorwyx::main();}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 58212kb

input:

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

output:

3
6
1
5
4

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 42ms
memory: 58140kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...

output:

GG
42972228579460
GG
42972483129988
-91734812202809
42973182938297
-91733557508933
GG
-91733875882986
77264056182933
77263506444530
7065382376488
7065749360235
7066534912965
-85115611272570
-85114714781312
96492412785032
-20428913156111
-20428197540063
96491742171666
-14945310996805
96491180203461
-...

result:

ok 200000 lines

Test #3:

score: 0
Accepted
time: 31ms
memory: 58092kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
1 3
1 2
3 4
3 1 -82365883
1 2 9 -730670945
2 4 2 -618745828
2 1 2 774032949
3 3 6733210
3 3 -843683844
3 1 327410390
3 1 -865685600
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3...

output:

74427674582310
GG
74427055836482
74427829869431
74427836602641
74426992918797
74427320329187
74426454643587
GG
-93292817648557
-93292095778370
74425923795990
-1057589620769
-93291944298803
74425228504438
74425430401539
-93291936231808
74425906008467
GG
-1058067327518
74424997886529
74424370598990
74...

result:

ok 200000 lines

Test #4:

score: 0
Accepted
time: 38ms
memory: 58076kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
3 2
1 5
1 4
1 2
3 5 865538081
3 4 551893736
2 3 9 797578233
1 3 0 -657534941
3 4 -507570975
1 1 2 352656478
3 5 951666995
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707...

output:

-41384368776733
-13731103953662
15340876041469
15340218506528
-13730813946404
15340571163006
-41382619531505
15341095622616
-13729470333069
-13728514744440
-41382546320208
15340844183861
-13729221899958
15340255675017
-13729490336654
-13729529150761
-13729624738248
15341124008689
15341173814500
GG
-...

result:

ok 200000 lines

Test #5:

score: 0
Accepted
time: 47ms
memory: 58080kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
2 1
3 1
4 6
1 5
7 1
2 4
1 6 4 -614276625
3 7 -430532617
3 3 -970301980
1 1 4 767992650
2 1 4 88036223
2 3 5 -930151770
3 3 -816226996
1 2 1 -696978838
2 1 1 -877781309
2 5 2 58619...

output:

-20711859007500
-20712289540117
-77588031854580
GG
65913690653467
65912760501697
-77589690197123
37911124737345
65911882720388
65912468916628
65911745912774
-29967336843362
65911988615088
GG
37910494006281
65912545393218
-49259038263999
GG
65913255260627
GG
GG
65912963550828
-24029074909413
65912862...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 63ms
memory: 58148kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
5 8
5 1
1 2
4 7
7 10
2 4
5 6
3 9
3 2
3 7 -830615007
1 2 6 637860195
2 7 7 -843886558
3 8 273999944
10 8
-33479821641433 91082116968197 -34...

output:

39452464479236
GG
96743943304642
662466765309
91246631814706
-29877405744477
GG
GG
91081604757708
GG
91246614330784
-29877381879548
-4361386733251
89595437158302
-4360828297147
19337184792075
89595109336295
89594748412265
19336971357477
89594978989869
86993545918633
-84286253125550
GG
GG
52174855696...

result:

ok 200000 lines

Test #7:

score: 0
Accepted
time: 48ms
memory: 58088kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
2 3
2 1
3 1 -988613092
1 2 0 308890489
1 1 0 472776476
2 2 2 -122992202
2 3 1 831940219
3 3 -612896282
3 3 -536438981
1 1 0 161104440
2 1 1 354965461
3 2
77441670935132 -63158159333100 77264362049163
3 1
2 1
1 3 4 -20585631
1 1 6 747193249
3 5
...

output:

42972056839450
34993819163787
42972529615926
42972406623724
34994528111804
-91734288358912
-91734824797893
42972567728164
42972922693625
GG
GG
GG
7064655135811
-61568732738930
7065157020537
-61568593058530
80122234728388
80122047274326
80122140239806
80121956639200
80121963373184
80121401404979
9259...

result:

ok 200000 lines

Test #8:

score: 0
Accepted
time: 27ms
memory: 58364kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
3 2
4 1
1 2
1 2 8 639477246
1 4 0 510694922
2 1 0 421373363
2 3 4 -843809269
3 1 -620938865
3 3 -933234989
1 3 3 458028025
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3 1 -69529...

output:

GG
74428267643115
-1056623075128
74427423833846
74426802894981
-24215336531480
74427260923006
GG
-24215228767974
-1057365953075
74426730075409
-1057445771381
-24215077288407
74426034783857
74426236680958
-24215069221412
74426712287886
74427585548383
74427327526258
-24215759758547
-24216387046086
744...

result:

ok 200000 lines

Test #9:

score: 0
Accepted
time: 43ms
memory: 58140kb

input:

10000
5 21
-17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814
1 2
4 1
5 1
1 3
3 4 -183603675
1 1 6 750831651
2 4 2 -112044052
2 5 0 487266103
2 4 7 623494631
2 3 6 -758745863
2 5 3 524459610
3 4 819153725
2 4 0 955588629
3 5 -451248313
1 3 0 -251438755
1 4 0 -707155518
3 ...

output:

-13731839451073
GG
15339966419184
-41384859092763
15340589913815
15339831167952
15340355627562
-13730743133022
-13729787544393
-41384921132698
15340104188807
-13730494699911
-49544113109053
-13730763136607
15340065374700
-13730897538201
-17118548613921
15340115180511
GG
-41384542096059
1534095454059...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 42ms
memory: 58364kb

input:

10000
7 53
-49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875
6 5
6 7
3 6
5 4
5 2
1 7
1 2 1 -902483856
2 2 0 -166019888
1 2 6 773740058
1 7 4 332162805
3 4 483966804
2 1 8 -161176455
2 6 2 999609920
2 2 1 575504367
1 2 2 -125436309
1 7 6 -85...

output:

-29966653943726
65913436597356
GG
GG
37913147798534
65913275420901
65914275030821
65914850535188
37913860795690
GG
65915321019354
65915455681128
65915560380329
65915183127659
65914812218108
65915548812492
65916224155305
65915243014798
-20710396693949
GG
65915329685860
65915917517754
65915625807955
6...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 62ms
memory: 60252kb

input:

10000
10 4
71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201
3 4
3 8
5 10
8 1
6 2
7 6
10 3
8 9
5 7
3 10 272721546
2 10 4 618153907
3 8 763987349
1 9 7 870230974
10 8
-13468051963531 -33479821641433 9...

output:

49372466325069
96745405345107
96746169332456
-54231506787020
91247244061845
91246513437933
-33254303623674
-34062728633884
38205426400070
91082413811192
-13468602472782
GG
86995519872619
10278075155744
86995188030179
86995444966527
19338147521978
86995117144520
86994756220490
19337573163350
-9437093...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 678ms
memory: 76296kb

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

99730096363045
-53142619895885
62633703474374
91065884890424
95913832039203
71963014593268
-73718672703414
88512243346245
95865153100847
20076236503631
-34284711719410
39055157031710
89757297384484
10950553757520
74269720205379
-9148723701106
-8854522652340
30148659190315
43163551215290
403669992467...

result:

ok 200000 lines

Test #13:

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

input:

2
200000 23147
-97882461219103 4406360045230 -36834806355299 -23973944052222 67113212265469 11669200972710 -6141709659817 -49560474741369 -18057145741204 -44040958119516 3611153759432 -22756796992893 65910580696453 -78071204736196 25214500077730 -40055869810099 52016133250624 24245766969509 -8573710...

output:

-84299253303082
91895293630648
98660521022574
99046915140773
96940400761168
-80640388829817
62170787931699
80755385476426
87313515284587
58038098598906
58552202132101
69717429372059
50840268036882
49052127297522
30321746138445
57233008189011
-26057525271228
98121546101640
88622027455733
621912032228...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 586ms
memory: 66536kb

input:

10
50000 1687
36077001037650 -28672159307004 -49567820178173 -66598809699217 51717647349268 40388708770673 -41615842513164 20640893046085 55244284371739 -12659258787859 -57804698295568 -1343921361566 -31490537070370 87398926700957 6369486949134 29314854271472 87863569527089 713709747605 -57348496935...

output:

99530565733478
52005604713243
95506513999163
99658832110191
99907096903163
97154724606255
81337070881934
58949958650580
99715077145772
85133043445758
74581069634085
50184582656147
69809426118622
70927902639147
-91729966293446
17060316600613
-10509867546560
-87583239449605
65152989953561
700189739274...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 245ms
memory: 58236kb

input:

500
1000 92
-34961255282319 -28048065121777 48403085782275 59825930674807 -81890804792913 -3718001248779 -16547933440271 86250915241917 86924443194023 -9735258000336 -91234968422024 -28592966984694 52777768205476 -93185139144600 5318140881411 -56116796281200 9179306895895 -22296214888774 -9108202485...

output:

4668320585308
88059957249898
71176226537037
93851532152750
-32706642031920
99121476057172
79602129082988
84325004453053
86250139584500
98672885845344
45802895326473
68661280872768
97371517369487
93616500614156
27589386746356
88059626048731
99121271376424
68093790136715
99361085683130
98488054170870
...

result:

ok 200000 lines

Test #16:

score: 0
Accepted
time: 993ms
memory: 75992kb

input:

5
100000 10278
-33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...

output:

-12749974258479
84017004006248
-89539813077621
-80338381552172
82312582262422
98103687339070
94560175951271
93134724507461
58620904163291
81867438963191
-400987364342
63575768373779
90005411398068
-98825155078969
67966851202993
98296098861174
-24807695936092
96949416015307
-34263626970319
8507072303...

result:

ok 200000 lines

Test #17:

score: 0
Accepted
time: 1087ms
memory: 85148kb

input:

2
200000 23147
-97882461219103 4406360045230 -36834806355299 -23973944052222 67113212265469 11669200972710 -6141709659817 -49560474741369 -18057145741204 -44040958119516 3611153759432 -22756796992893 65910580696453 -78071204736196 25214500077730 -40055869810099 52016133250624 24245766969509 -8573710...

output:

-16293954011041
62741995621901
-15125520384148
-25704572286872
90860743450740
84695269973325
97944190355983
94735633468742
98145063030824
49413787538754
23053417111812
95872648137173
98013065972849
81312129572281
41406152110373
86973126919367
1937367791719
72403580564416
61555358324125
9332704669248...

result:

ok 200000 lines

Test #18:

score: 0
Accepted
time: 905ms
memory: 66220kb

input:

10
50000 1687
36077001037650 -28672159307004 -49567820178173 -66598809699217 51717647349268 40388708770673 -41615842513164 20640893046085 55244284371739 -12659258787859 -57804698295568 -1343921361566 -31490537070370 87398926700957 6369486949134 29314854271472 87863569527089 713709747605 -57348496935...

output:

99705414543107
90806884059450
-99065023764916
44502201885685
41965846324836
57927754525268
97154724606255
2207419427510
58949958650580
15979464387860
88027385456934
85066188731388
88003516748338
13807676343737
70927902639147
24810733685067
56036888868844
96304109192530
-87583239449605
90227083493459...

result:

ok 200000 lines

Test #19:

score: 0
Accepted
time: 435ms
memory: 58180kb

input:

500
1000 92
-34961255282319 -28048065121777 48403085782275 59825930674807 -81890804792913 -3718001248779 -16547933440271 86250915241917 86924443194023 -9735258000336 -91234968422024 -28592966984694 52777768205476 -93185139144600 5318140881411 -56116796281200 9179306895895 -22296214888774 -9108202485...

output:

92216518632988
65868387025923
33144669107606
90675422377591
87484153022845
91564811156334
-5939805691954
83606924569797
99360070397247
65441546475283
26095689215894
46536466844928
-65116611524340
99120414657699
52778214899359
62494041600873
49995963180845
96529740597360
-54602314642631
7240589818753...

result:

ok 200000 lines

Test #20:

score: 0
Accepted
time: 1258ms
memory: 80036kb

input:

5
100000 30356
48732517027966 -75485069283129 79926511452338 84737548208340 -4063689333444 -26064561034096 -5005593549244 -95015983578570 10773641083693 -1369584002862 -34611806567262 -34483324181269 -30834965692363 -21880618264420 38559052468666 22423312348992 24568192973798 -13169262615879 -329176...

output:

97391716846671
99997980645062
30363999518777
86065373774365
99962498031641
7011826103833
-22297614542099
99998413612399
99979353430562
99999083146947
84004577167487
-7553435675487
70855712832395
63489365860544
-56474750228298
65160481873948
99998096092826
99979872838791
39551692313382
99997181558805...

result:

ok 200000 lines

Test #21:

score: 0
Accepted
time: 1456ms
memory: 93668kb

input:

2
200000 4305
-35839858780510 -46340026955793 37290215973337 80439860209880 20880856686867 -85932911276377 847927507119 -25873222730914 -61911623227205 42020136332179 81542533339184 92745718522666 -80863450472631 -11887947308601 -6381745719346 -69069821378657 47096674055998 52971672631109 -366178775...

output:

91018645888774
74883402138788
-28436304848899
18127535521648
42973158308750
99998204131500
99997253356073
-13562791387157
99997545578369
62122930670385
99997794312654
99980343230633
11154221017513
99997042972467
92453170630725
82368818609736
90737436684970
-74749161406722
99996959128481
100599775673...

result:

ok 200000 lines

Test #22:

score: 0
Accepted
time: 174ms
memory: 75712kb

input:

5
100000 30356
48732517027966 -75485069283129 79926511452338 84737548208340 -4063689333444 -26064561034096 -5005593549244 -95015983578570 10773641083693 -1369584002862 -34611806567262 -34483324181269 -30834965692363 -21880618264420 38559052468666 22423312348992 24568192973798 -13169262615879 -329176...

output:

97391716846671
77351038474533
GG
99998256803865
-15146272575566
-32750777413539
-22297338383296
22265017995574
-64598600433400
-47045637573054
99998010723226
GG
99998126203876
99998742114800
-56475203908623
99999299818876
-85166984669993
-77375884503100
GG
-82405014168855
99998704532460
-72447842377...

result:

ok 200000 lines

Test #23:

score: 0
Accepted
time: 209ms
memory: 86956kb

input:

2
200000 4305
-35839858780510 -46340026955793 37290215973337 80439860209880 20880856686867 -85932911276377 847927507119 -25873222730914 -61911623227205 42020136332179 81542533339184 92745718522666 -80863450472631 -11887947308601 -6381745719346 -69069821378657 47096674055998 52971672631109 -366178775...

output:

99998592345164
99998764545131
GG
18127715594642
GG
46442750960466
1022495102935
GG
59018282934551
44044068449359
-5987218825801
-79867246423671
GG
21624395408438
99999563573152
100000011613229
GG
GG
71358189655199
GG
99116913919110
44046341975160
99999393789334
51129573040929
GG
74638433068527
99999...

result:

ok 200000 lines

Test #24:

score: 0
Accepted
time: 1219ms
memory: 81884kb

input:

5
100000 8942
30458351123984 -99291229852141 -12865463827821 -83559403577043 92297941669257 8067426302599 -88895214250465 83183072958553 -25073421109417 45660440845857 -58057584616805 47484458290408 61708022567561 28814976199142 94628071168194 -15807248370007 93545485294215 1243357546563 -9196309138...

output:

65879476626569
99989633073528
66303827239421
99984371305602
95865415598928
99989310079348
99997668669178
-16907130669278
99984617141815
99989489782071
74485247336569
99985369764508
99997311926878
-5956160456002
-21765410597614
68567642793011
68677126686853
99984583928940
79104813328415
1021092151973...

result:

ok 200000 lines

Test #25:

score: 0
Accepted
time: 1221ms
memory: 97300kb

input:

2
200000 124275
-6879990256550 60408566804944 -50503758407226 62165694305898 -2929598849441 21266523508873 32559565656329 42533852936069 -27779635890511 -41860894434449 59737294909010 56898656329556 -61796570894221 -7366285120539 75590331719627 23477461848562 69824828281955 81081841027624 9718412147...

output:

99999875598025
38014274172543
19157038935943
100000499940321
78315646562854
97523365791916
59225090909834
98353403062524
99999935579570
99992614942578
96105950235889
99999182210608
4834072987300
99998985800528
83377118181946
99998348651461
60577299564581
87786309108168
97441531873570
99998549050424
...

result:

ok 200000 lines

Test #26:

score: 0
Accepted
time: 199ms
memory: 75400kb

input:

5
100000 8942
30458351123984 -99291229852141 -12865463827821 -83559403577043 92297941669257 8067426302599 -88895214250465 83183072958553 -25073421109417 45660440845857 -58057584616805 47484458290408 61708022567561 28814976199142 94628071168194 -15807248370007 93545485294215 1243357546563 -9196309138...

output:

GG
-70779814384280
99997372441323
17779357805951
95865624269236
-90986547238247
-10094765247418
GG
-46623517458178
91819362246340
GG
74407623137004
-86903864238755
GG
GG
GG
68677478648618
-67822554365124
99996901354949
71715176348130
99997157575410
88645863656523
99997510986843
GG
GG
99997771800549
...

result:

ok 200000 lines

Test #27:

score: 0
Accepted
time: 196ms
memory: 86160kb

input:

2
200000 124275
-6879990256550 60408566804944 -50503758407226 62165694305898 -2929598849441 21266523508873 32559565656329 42533852936069 -27779635890511 -41860894434449 59737294909010 56898656329556 -61796570894221 -7366285120539 75590331719627 23477461848562 69824828281955 81081841027624 9718412147...

output:

-76948297162391
99998843704425
GG
25539009685810
78313402006443
99999675797053
99999143912115
99999977186679
-84264461510704
-1475430852988
100000556597644
7436013470306
GG
65819614051075
100001100786150
90385255705471
60578568766344
GG
GG
-29435752577264
59701374392570
GG
7546502632576
715472283501...

result:

ok 200000 lines

Test #28:

score: 0
Accepted
time: 1240ms
memory: 82084kb

input:

5
100000 115776
40147330490310 -95142835085437 -77702883772263 -51847765427833 -11331837393452 42208003573885 27219460015612 61377834528379 -60920483302527 64727320424267 -53540217396039 -42580319000311 -17781548934912 51538835457804 -77261760435292 -82000954359314 -65440367655677 15655977709006 489...

output:

81089598145574
-359652955813
-36199741317021
99998823725350
99998876972715
8544540236587
88477345603618
87957673439423
69760046284360
99912643387436
20136756415746
99968528351135
52446307977076
-89921191060443
99999875777368
26383421673828
-2944507079937
72850138595282
99402096197554
100000865297440...

result:

ok 200000 lines

Test #29:

score: 0
Accepted
time: 1298ms
memory: 97560kb

input:

2
200000 55475
22075583300113 -4879694164010 61697972244915 71854673672224 1227385851856 -43562306500976 64262613870947 -61095926126639 6356646413479 74253779831627 37936351446132 21047299169150 -14762251078205 -30816358137378 -14474445571092 -56016404621206 92552982507912 -90816580510454 5895356076...

output:

64288263600081
99998876606275
86539576766665
81973701593672
-94471283737696
92754026314725
30907518120970
93679300573324
99999720947131
99999044877195
-38640691420730
12600303111357
99950021706111
-23618350035024
82591239213970
30525453074981
87494736660036
36914806502244
99126197222474
842905699749...

result:

ok 200000 lines

Test #30:

score: 0
Accepted
time: 172ms
memory: 75632kb

input:

5
100000 115776
40147330490310 -95142835085437 -77702883772263 -51847765427833 -11331837393452 42208003573885 27219460015612 61377834528379 -60920483302527 64727320424267 -53540217396039 -42580319000311 -17781548934912 51538835457804 -77261760435292 -82000954359314 -65440367655677 15655977709006 489...

output:

99999566824152
GG
GG
-60538807500834
-12000357948222
99998606117217
11128788546068
GG
99998873112618
-20414104116358
20136752555649
-68022736401730
GG
-89921194920540
-14440656424153
GG
GG
99999546157622
99999646564055
-37598252587929
100000485587365
39531455692908
82582038700364
-91066212605104
GG
...

result:

ok 200000 lines

Test #31:

score: 0
Accepted
time: 195ms
memory: 86956kb

input:

2
200000 55475
22075583300113 -4879694164010 61697972244915 71854673672224 1227385851856 -43562306500976 64262613870947 -61095926126639 6356646413479 74253779831627 37936351446132 21047299169150 -14762251078205 -30816358137378 -14474445571092 -56016404621206 92552982507912 -90816580510454 5895356076...

output:

99998359783559
-7342008572744
99997903766164
99996978819680
-94473181524291
99997867094751
GG
99997309038990
-74854045294033
24026977180383
99997214647071
GG
-61241913012764
-23619904867060
99996480075963
GG
99996363454305
GG
99996813700641
99996073739904
99995581952333
48677870033156
99996520419372...

result:

ok 200000 lines

Test #32:

score: 0
Accepted
time: 480ms
memory: 86472kb

input:

1
200000 200000
99519641094072 -40654974871 -71153464621408 62277179738497 -70172272577857 41880207232311 29648392987509 32236984712341 50058235277102 29777595052170 -740177683573 -77327192504215 48009267804747 113594583419 42315050747865 14592685243669 -46712558712577 -19551272106622 64419167695937...

output:

95626436877251
99998843794666
93542193700111
99999273533566
-23028211064226
-33788658436809
11755141585206
99999765334955
99995175326153
94876145388442
99999926112437
99630684022754
-47660793216868
29294417847863
99999193559730
99999632738211
97836929937971
61545075765554
-58298676130530
94856549966...

result:

ok 200000 lines

Test #33:

score: 0
Accepted
time: 475ms
memory: 86380kb

input:

1
200000 200000
-71524785349266 -93292061214135 41048266030733 44003013834514 -93978433146869 -50916063015144 61355736169423 -71397089317663 84194517581092 -54107730681755 -50504266416760 58858305065071 95043587620762 4630961804185 -47749726542854 -64896886258803 -23984404486620 8558896289893 261886...

output:

27550843302470
-63558851725447
100000515010219
23551014465391
99828101242823
97898580866134
99542977509131
60393366669648
99110710359228
53554195045543
100000010904680
99885614900678
99999480465998
99462866822004
99999389901888
65143714791525
100000274877151
98918112943692
98621030451804
-7470979528...

result:

ok 200000 lines

Test #34:

score: 0
Accepted
time: 461ms
memory: 86936kb

input:

1
200000 200000
-42569211792602 13456532546603 -46741413382534 53691993200841 82211111316824 56283371770106 93063079351337 -2990013650680 -81664905147622 62002648617026 -72309504846934 23011242871961 -85893827768125 -18814816245358 34222350896119 27646102001120 26706895009646 36669064686408 -1204624...

output:

-34780400254627
99975429705936
99999768648371
-59723683528790
99956435187995
99856019410161
99999770105960
99030509773007
99727611358099
-76344059498272
86708265736958
99999472938699
99554556561180
31083382258100
99999540916671
99999593279614
12529665168758
14238323780355
99999785474001
-99986970660...

result:

ok 200000 lines

Test #35:

score: 0
Accepted
time: 456ms
memory: 86472kb

input:

1
200000 200000
-13609343268643 -51836023389647 65460317269607 35422122264155 86363801050824 -8545458239743 -75229577466750 93380207286613 -47532917810928 -21882677116898 -94114743277109 -12835819321148 -38859507952109 -42260594294901 -83809866632204 -51843469501352 49435049235604 64774938115627 -78...

output:

100000209466246
99596203270325
100000951276291
99707460611739
66847220709179
100000955244912
-68852617565183
-9317950326728
100000392227315
77274216723126
100000487195529
99582923002966
100000037821268
100000586235480
99113252074877
-46260821058316
98915216142418
19491295558945
-50544142608075
-6569...

result:

ok 200000 lines

Test #36:

score: 0
Accepted
time: 460ms
memory: 86116kb

input:

1
200000 200000
15346230288020 54912570371090 -22333657110956 45106806663185 62557640481812 98653976545507 -43517939317540 -10253866743392 -13396635506938 94227702181882 84080018292718 -48682881514258 -19792628373699 -37743227074134 -1837789193231 40699518758571 -99877946235427 92885106512143 835251...

output:

-60371659646694
33686951708332
99998519528610
-31343672088504
99908469362097
69381388099556
99490421604883
-97780248085938
99998780964079
-40734176392537
-56670681247697
99809976928903
99997903045934
99998485064414
48086054308563
-93203045645041
99817967780207
54545211982081
13023628528314
-20114064...

result:

ok 200000 lines

Test #37:

score: 0
Accepted
time: 435ms
memory: 86948kb

input:

1
200000 200000
16338658574375 -10375690597864 -82168781188506 54795786029512 38747184945504 33820851568361 -11814891102922 86112059226605 20743941764348 10346671415254 62279074829840 -84529943707368 27241691442316 -61189005123677 80134288245742 -38790052743901 -77154086976766 -79004725091343 173271...

output:

99620448726511
99663797403475
99999322005228
34159112664841
38356366167035
-12401590863918
99998351716634
99976243828231
99998915869472
99499878973121
-35958659744192
99999513391277
51991646216630
99530035291767
100000044977014
99346251825236
99709788684660
100000969782919
100001484058828
-532333368...

result:

ok 200000 lines

Test #38:

score: 0
Accepted
time: 448ms
memory: 86592kb

input:

1
200000 200000
45294232131038 96372903162874 30037244430931 36521620125529 42899874679505 -58971123711797 19892452078992 -17517719836104 54875929101043 98498200411021 12510691129356 79622994099523 46308571020726 -56671637902911 -9930489044977 53757230483318 -26462787480500 -50903146629420 -20903372...

output:

100000170040969
-8952798175361
99554039311890
99864717629874
99917975416002
68298475964208
70719780022462
-82038526403118
99873162169261
100000507444608
100000928812037
99250819728185
-23454389568720
-75258746098700
38386470299208
99559996586464
100000171617496
99829998789729
99498022475938
99763855...

result:

ok 200000 lines

Test #39:

score: 0
Accepted
time: 456ms
memory: 86368kb

input:

1
200000 200000
74249805687702 31076052259327 -57756729949632 46210599491856 19089419143197 76191456343762 79562940531215 78852501101189 89012211405033 14608579709801 -9290252333522 15808491668809 93342890836742 -80117415952454 72041588393996 -25732341019154 -3738928221838 -22792978232905 -591382277...

output:

99999282305772
99922798087563
100000270375274
100000839068333
100001596244807
-36901065281983
98565378817990
99056959792738
23583313624647
100002011810623
-57186049793987
-82493004637416
-77772632809651
99587674622414
100002173431115
100002753756312
100003245100330
2851962682863
98663746801132
10000...

result:

ok 200000 lines

Test #40:

score: 0
Accepted
time: 426ms
memory: 86084kb

input:

1
200000 200000
-96794620755636 -62175353979936 54445000702509 55903873825478 -4721036393112 -16604813903693 -88729716286872 -24781572928816 -76851506290978 -69276746024123 -31099785730992 -20038570524301 -87590229584849 -75600048731688 -45986334167032 66810647240769 46952371274428 5312895196314 746...

output:

-61242558199370
98870000746915
96973074904019
99998648269011
85693024157791
5510353570074
99998305726122
99653865087137
33228062752232
32713860286417
-96964506411536
99998401230210
-70684226995485
99997503739023
99997144467835
99997533346944
-98384320126483
99996740178088
99743487109292
-61699665788...

result:

ok 200000 lines

Test #41:

score: 0
Accepted
time: 434ms
memory: 86076kb

input:

1
200000 200000
-37196289589304 31594180920019 -66919502932677 79334124900919 78056293774935 10869587247396 49340174204745 43916207044850 38089626646890 15694762117168 -10737717059002 11676453988694 13330113379524 94339695279216 -53201489294223 -88794792138147 -34461912203310 -72118892571085 2986086...

output:

99773620383857
-6319310660135
99651434373713
99997555418316
96853219172599
99510365468365
99920146943932
99862841956641
31540367965116
99997247802345
99929658936969
99959321562058
99957255167398
30062375151140
99998133486648
39283470080640
99693909053786
-68120439985095
99998624926803
99818183600913...

result:

ok 200000 lines

Test #42:

score: 0
Accepted
time: 990ms
memory: 85056kb

input:

1
200000 200000
99519641094072 -40654974871 -71153464621408 62277179738497 -70172272577857 41880207232311 29648392987509 32236984712341 50058235277102 29777595052170 -740177683573 -77327192504215 48009267804747 113594583419 42315050747865 14592685243669 -46712558712577 -19551272106622 64419167695937...

output:

71896197448832
99998843794666
93542193700111
99999273533566
91939153364462
99377330724005
94633664659329
99999765334955
99995175326153
62369507666493
99999926112437
99630684022754
-43689584789635
80204866841743
99999193559730
99999632738211
97836929937971
88397723255457
17622029176211
94856549966308...

result:

ok 200000 lines

Test #43:

score: 0
Accepted
time: 999ms
memory: 84892kb

input:

1
200000 200000
-71524785349266 -93292061214135 41048266030733 44003013834514 -93978433146869 -50916063015144 61355736169423 -71397089317663 84194517581092 -54107730681755 -50504266416760 58858305065071 95043587620762 4630961804185 -47749726542854 -64896886258803 -23984404486620 8558896289893 261886...

output:

-59578742059337
98227552580096
100000515010219
15980865554055
99828101242823
94802770426498
25686763102078
60393366669648
99110710359228
53554195045543
100000010904680
98349693302860
99999480465998
99462866822004
99999389901888
65143714791525
100000274877151
98918112943692
98621030451804
-1898475034...

result:

ok 200000 lines

Test #44:

score: 0
Accepted
time: 996ms
memory: 85124kb

input:

1
200000 200000
-42569211792602 13456532546603 -46741413382534 53691993200841 82211111316824 56283371770106 93063079351337 -2990013650680 -81664905147622 62002648617026 -72309504846934 23011242871961 -85893827768125 -18814816245358 34222350896119 27646102001120 26706895009646 36669064686408 -1204624...

output:

99346310438086
99975429705936
99999768648371
51802389323485
87569983823912
95315276283352
99999770105960
99030509773007
99727611358099
77860030953908
97976973068934
99999472938699
99554556561180
99724398878704
99999540916671
99999593279614
-68274264108813
6866817703147
99999785474001
99440872081397
...

result:

ok 200000 lines

Test #45:

score: 0
Accepted
time: 987ms
memory: 84964kb

input:

1
200000 200000
-13609343268643 -51836023389647 65460317269607 35422122264155 86363801050824 -8545458239743 -75229577466750 93380207286613 -47532917810928 -21882677116898 -94114743277109 -12835819321148 -38859507952109 -42260594294901 -83809866632204 -51843469501352 49435049235604 64774938115627 -78...

output:

100000209466246
99596203270325
100000951276291
99707460611739
99414003177693
100000955244912
95515692375788
99406130557517
100000392227315
98637875697380
100000487195529
99582923002966
100000037821268
100000586235480
99113252074877
99292951997901
-35731455692105
98268097460894
19103529889749
4040187...

result:

ok 200000 lines

Test #46:

score: 0
Accepted
time: 984ms
memory: 84944kb

input:

1
200000 200000
15346230288020 54912570371090 -22333657110956 45106806663185 62557640481812 98653976545507 -43517939317540 -10253866743392 -13396635506938 94227702181882 84080018292718 -48682881514258 -19792628373699 -37743227074134 -1837789193231 40699518758571 -99877946235427 92885106512143 835251...

output:

99514172915019
52829440306910
99998519528610
99820204789330
74084896070718
99097922189630
99490421604883
12217451692042
99998780964079
63703022206178
88207284622436
99809976928903
99997903045934
99998485064414
78543208802180
99078917990296
99817967780207
87921794134290
13023628528314
43105234935686
...

result:

ok 200000 lines

Test #47:

score: 0
Accepted
time: 995ms
memory: 84980kb

input:

1
200000 200000
16338658574375 -10375690597864 -82168781188506 54795786029512 38747184945504 33820851568361 -11814891102922 86112059226605 20743941764348 10346671415254 62279074829840 -84529943707368 27241691442316 -61189005123677 80134288245742 -38790052743901 -77154086976766 -79004725091343 173271...

output:

99620448726511
99663797403475
99999322005228
62346941220538
71344903440247
-11301678805384
99998351716634
99976243828231
99998915869472
99499878973121
99964630255035
99999513391277
51991646216630
98002530763561
100000044977014
99346251825236
99709788684660
100000969782919
100001484058828
57951024614...

result:

ok 200000 lines

Test #48:

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

input:

1
200000 200000
45294232131038 96372903162874 30037244430931 36521620125529 42899874679505 -58971123711797 19892452078992 -17517719836104 54875929101043 98498200411021 12510691129356 79622994099523 46308571020726 -56671637902911 -9930489044977 53757230483318 -26462787480500 -50903146629420 -20903372...

output:

100000170040969
99686601798847
99554039311890
99864717629874
99917975416002
18280935234585
72296535041661
97499360110464
99873162169261
100000507444608
100000928812037
81995936287544
-23454389568720
96718044042268
99440881219467
43714056054198
100000171617496
99829998789729
99498022475938
9976385530...

result:

ok 200000 lines

Test #49:

score: 0
Accepted
time: 990ms
memory: 84984kb

input:

1
200000 200000
74249805687702 31076052259327 -57756729949632 46210599491856 19089419143197 76191456343762 79562940531215 78852501101189 89012211405033 14608579709801 -9290252333522 15808491668809 93342890836742 -80117415952454 72041588393996 -25732341019154 -3738928221838 -22792978232905 -591382277...

output:

99999282305772
97036902447316
100000270375274
100000839068333
100001596244807
99692177782292
99886379526426
99056959792738
47705450196605
100002011810623
98471401332456
-82493004637416
-77772632809651
99587674622414
100002173431115
100002753756312
100003245100330
98347599842724
98663746801132
100002...

result:

ok 200000 lines

Test #50:

score: 0
Accepted
time: 972ms
memory: 84988kb

input:

1
200000 200000
-96794620755636 -62175353979936 54445000702509 55903873825478 -4721036393112 -16604813903693 -88729716286872 -24781572928816 -76851506290978 -69276746024123 -31099785730992 -20038570524301 -87590229584849 -75600048731688 -45986334167032 66810647240769 46952371274428 5312895196314 746...

output:

98664790140453
70837255632444
99634447175030
99998648269011
15218553375682
-68447116358988
99998305726122
99653865087137
23440674794725
93888969075773
99357269552187
99998401230210
18604149148456
39846503530302
99997850753757
99998239632866
99838985429398
99997446464010
26324681470621
99973300765964...

result:

ok 200000 lines

Test #51:

score: 0
Accepted
time: 989ms
memory: 85004kb

input:

1
200000 200000
-37196289589304 31594180920019 -66919502932677 79334124900919 78056293774935 10869587247396 49340174204745 43916207044850 38089626646890 15694762117168 -10737717059002 11676453988694 13330113379524 94339695279216 -53201489294223 -88794792138147 -34461912203310 -72118892571085 2986086...

output:

99773620383857
-6319310660135
99651434373713
99997555418316
99863255961682
99510365468365
99920146943932
99862841956641
98499460378674
99997247802345
99929658936969
99959321562058
91781123548987
98827041527475
99998133486648
7533857370932
87694973954744
17513054707953
99998624926803
99818183600913
9...

result:

ok 200000 lines

Test #52:

score: 0
Accepted
time: 500ms
memory: 86328kb

input:

1
200000 200000
-61653499922223 -29880690661524 -82947741522639 56821039534144 -27976006312594 -7358072195529 -24672763142646 56358727712057 -69230150633415 -56096090257095 -34835898011571 17018777760138 2732168942095 76843454019406 -6408995110970 -82694108185536 34797751169690 -7960384030214 -39038...

output:

95461465449831
-32415860955138
99203342729152
97564319519681
94431808122451
99999504603093
100000358357830
95066080989125
99993025377986
91916140911850
78519369371147
92817901080986
99189824814403
100001186872174
100001999516694
8749982492809
52072217523968
-33143762309412
-56603196627158
1000010774...

result:

ok 200000 lines

Test #53:

score: 0
Accepted
time: 968ms
memory: 84880kb

input:

1
200000 200000
-61653499922223 -29880690661524 -82947741522639 56821039534144 -27976006312594 -7358072195529 -24672763142646 56358727712057 -69230150633415 -56096090257095 -34835898011571 17018777760138 2732168942095 76843454019406 -6408995110970 -82694108185536 34797751169690 -7960384030214 -39038...

output:

95461465449831
-32415860955138
89010041592432
97564319519681
94431808122451
99999504603093
100000358357830
66036381337626
99993025377986
91916140911850
76285309440970
92817901080986
99189824814403
100001186872174
100001999516694
83999431627294
98864753368188
94591922781738
96396831585496
10000107743...

result:

ok 200000 lines

Test #54:

score: 0
Accepted
time: 29ms
memory: 58304kb

input:

10000
1 69
75111229681286
1 1 0 -107639262
1 1 0 787234797
2 1 1 324243128
1 1 0 133781650
1 1 7 929015899
1 1 0 580874096
3 1 -799558087
3 1 331527339
2 1 6 725087735
2 1 0 -287241548
2 1 0 914517300
1 1 3 -400194525
1 1 9 490814455
1 1 7 140069158
2 1 8 -513150929
3 1 -68238294
2 1 0 22368227
3 1 ...

output:

75111122042024
75111909276821
75112233519949
75112367301599
GG
75112948175695
75112148617608
75112480144947
75113205232682
75112917991134
75113832508434
GG
GG
GG
75113319357505
75113251119211
75113273487438
75113013380798
75113247954189
75112396513318
75113139847187
75112167285038
75111936151274
751...

result:

ok 200000 lines

Extra Test:

score: 0
Extra Test Passed