QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124232#5439. Meet in the Middle___WA 44ms53976kbC5.8kb2023-07-14 14:06:502023-07-14 14:06:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 14:06:53]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:53976kb
  • [2023-07-14 14:06:50]
  • 提交

answer

#include<stdio.h>
#define ll long long
#define N 200010
#define M 500010
#define int long long 
int maxx(int x,int y){return x>y?x:y;}
int minn(int x,int y){return x<y?x:y;}
ll maxl(ll x,ll y){return x>y?x:y;}
ll minl(ll x,ll y){return x<y?x:y;} 
int read(){
	char ch;int zf=1,res=0;
	while((ch=getchar())<48||ch>57)if(ch=='-')zf=!zf;res=(ch^48);
	while((ch=getchar())>=48&&ch<=57)res=(res<<3)+(res<<1)+(ch^48);
	return zf?res:(-res);
}
struct node1{
	int y,nxt;ll s;
}ea[N<<1],eb[N<<1];int staa[N],stab[N],cnta,cntb;
struct node2{
	int s,nxt;int id;
}ask[M];int stas[N],cnts;ll anss[M];
int lg2[N<<1];
int dfsa[N],dfsb[N],dcta,dctb;
ll adda[N],addb[N]; 
int sizea[N];
int oulaa[N<<1],oulab[N<<1],pcta,pctb,fstoulaa[N],fstoulab[N];
int depa[N],depb[N];
struct node3{
	int s,id;
}sa[N<<1][25],sb[N<<1][25];
struct node{
	int x,y;int xid,yid;ll ax,ay;ll d,flag;
}a[N<<2];
int n,q;
int dy[N],ndy[N];
int pbsta(int x){
	oulaa[++pcta]=x;
	sa[pcta][0].id=x;sa[pcta][0].s=depa[x];
	return 0;
}
int dfsa1(int x,int fa,ll S){
	adda[x]=adda[fa]+S;
	dfsa[x]=++dcta;
	dy[x]=dfsa[x];
	 ndy[dfsa[x]]=x;
	depa[x]=depa[fa]+1;
	pbsta(x);
	sizea[x]=1;
	fstoulaa[x]=pcta;
	for(int i=staa[x];i;i=ea[i].nxt)if(ea[i].y!=fa){
		dfsa1(ea[i].y,x,ea[i].s);
		pbsta(x);
		sizea[x]+=sizea[ea[i].y];
	}
	return 0;
}
int pbstb(int x){
	oulab[++pctb]=x;
	sb[pctb][0].id=x;sb[pctb][0].s=depb[x];
	return 0;
}
int dfsb1(int x,int fa,ll S){
	addb[x]=addb[fa]+S;
	dfsb[x]=++dctb;
	depb[x]=depb[fa]+1;
	pbstb(x);
	fstoulab[x]=pctb;
	for(int i=stab[x];i;i=eb[i].nxt)if(eb[i].y!=fa){
		dfsb1(eb[i].y,x,eb[i].s);
		pbstb(x);
	}
	return 0;
}
struct node3 mergest(struct node3 x,struct node3 y){
	if(x.s<=y.s)return x;
	else return y;
}
int finda(int x,int y){
	x=fstoulaa[x];y=fstoulaa[y];
	if(x>y){int p=x;x=y;y=p;}
	int p=lg2[y-x+1];
	return mergest(sa[x][p],sa[y-(1<<p)+1][p]).id;
}
int findb(int x,int y){
	x=fstoulab[x];y=fstoulab[y];
	if(x>y){int p=x;x=y;y=p;}
	int p=lg2[y-x+1];
	return mergest(sb[x][p],sb[y-(1<<p)+1][p]).id;
}
int yclst(){
	lg2[0]=-1;
	for(int i=1;i<=n+n;i++)lg2[i]=lg2[i>>1]+1;
	for(int h=1;(1<<h)<n+n;h++)
		for(int i=1;i+(1<<h)-1<n+n;i++){
			sa[i][h]=mergest(sa[i][h-1],sa[i+(1<<(h-1))][h-1]);	
			sb[i][h]=mergest(sb[i][h-1],sb[i+(1<<(h-1))][h-1]);	
		}
	return 0;
}
ll cala(int x,int y){
	return adda[x]+adda[y]-adda[finda(x,y)]*2;
}
ll calb(int x,int y){
	return addb[x]+addb[y]-addb[findb(x,y)]*2;
}
struct node merge(struct node x,struct node y){
	struct node res=x;
	if(y.d>x.d)res=y;res.flag=0;
	if(calb(x.x,y.y)+x.ax+y.ay>res.d){
		res.d=calb(x.x,y.y)+x.ax+y.ay;
		res.x=x.x;res.y=y.y;
		res.ax=x.ax;res.ay=y.ay;
		res.xid=x.xid;res.yid=y.yid;
	}
	if(calb(x.y,y.x)+x.ay+y.ax>res.d){
		res.d=calb(x.y,y.x)+x.ay+y.ax;
		res.x=x.y;res.y=y.x;
		res.ax=x.ay;res.ay=y.ax;
		res.xid=x.yid;res.yid=y.xid;
	}
	if(calb(x.x,y.x)+x.ax+y.ax>res.d){
		res.d=calb(x.x,y.x)+x.ax+y.ax;
		res.x=x.x;res.y=y.x;
		res.ax=x.ax;res.ay=y.ax;
		res.xid=x.xid;res.yid=y.xid;
	}
	if(calb(x.y,y.y)+x.ay+y.ay>res.d){
		res.d=calb(x.y,y.y)+x.ay+y.ay;
		res.x=x.y;res.y=y.y;
		res.ax=x.ay;res.ay=y.ay;
		res.xid=x.yid;res.yid=y.yid;
	}
	res.flag=0;
	return res;
}
int pushdown(int,int,int,int);
int build(int k,int l,int r){
//	printf("A%d %d %d\n",k,l,r);
	if(l==r){
		a[k].x=a[k].y=ndy[l];
		a[k].ax=a[k].ay=adda[ndy[l]];
		a[k].xid=a[k].yid=ndy[l];
		a[k].flag=0;
		a[k].d=0;
		return 0;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	a[k]=merge(a[k<<1],a[k<<1|1]);
	return 0;
}
int change(int k,int l,int r,int x,int y,ll S){
	if(x>r||y<l||x>y)return 0;
	if(x<=l&&y>=r){
		ll p=S;
		a[k].ax+=p;
		a[k].ay+=p;
		a[k].d+=p*2;
		a[k].flag+=p; 
		if(l==r)a[k].d=0;
		return 0;
	}
	int mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	change(k<<1,l,mid,x,y,S);
	change(k<<1|1,mid+1,r,x,y,S);
	a[k]=merge(a[k<<1],a[k<<1|1]);
	return 0;
}
struct node find(int k,int l,int r,int x,int y){
	if(x<=l&&y>=r)return a[k];
	int mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	if(y<=mid)return find(k<<1,l,mid,x,y);
	if(x>mid)return find(k<<1|1,mid+1,r,x,y);
	return merge(find(k<<1,l,mid,x,y),find(k<<1|1,mid+1,r,x,y));
}
int pushdown(int k,int l,int r,int mid){
	if(a[k].flag){
		change(k<<1,l,mid,l,mid,a[k].flag);
		change(k<<1|1,mid+1,r,mid+1,r,a[k].flag);
		a[k]=merge(a[k<<1],a[k<<1|1]);
		a[k].flag=0;
	}
	return 0;
}

int mergea(int x,int y,ll S){
	ea[++cnta].y=y;
	ea[cnta].nxt=staa[x];
	staa[x]=cnta;
	ea[cnta].s=S;
	ea[++cnta].y=x;
	ea[cnta].nxt=staa[y];
	staa[y]=cnta;
	ea[cnta].s=S;
	return 0;
}
int mergeb(int x,int y,ll S){
	eb[++cntb].y=y;
	eb[cntb].nxt=stab[x];
	stab[x]=cntb;
	eb[cntb].s=S;
	eb[++cntb].y=x;
	eb[cntb].nxt=stab[y];
	stab[y]=cntb;
	eb[cntb].s=S;
	return 0;
}
int merges(int x,int s,int id){
	ask[++cnts].s=s;
	ask[cnts].nxt=stas[x];
	stas[x]=cnts;
	ask[cnts].id=id;
	return 0;
}
int dfs2(int x,int fa){
//	printf("B%d %d\n",x,fa); 
	for(int i=stas[x];i;i=ask[i].nxt){
		struct node p=find(1,1,n,1,n);
		anss[ask[i].id]=maxl((cala(x,p.x)+calb(p.x,ask[i].s)),(cala(x,p.y)+calb(p.y,ask[i].s)));
	}
	for(int i=staa[x];i;i=ea[i].nxt)if(ea[i].y!=fa){
		int y=ea[i].y;
		change(1,1,n,1,n,ea[i].s);
		change(1,1,n,dfsa[y]+1,dfsa[y]+sizea[y]-1,-2*ea[i].s);
		dfs2(y,x);
		change(1,1,n,1,n,-ea[i].s);
		change(1,1,n,dfsa[y]+1,dfsa[y]+sizea[y]-1,2*ea[i].s);
	}
	return 0; 
}
signed main(){
	n=read();q=read();
	for(int i=1;i<n;i++){
		int x,y,s;x=read();y=read();s=read();
		mergea(x,y,s);
	}
	for(int i=1;i<n;i++){
		int x,y,s;x=read();y=read();s=read();
		mergeb(x,y,s);
	}
	for(int i=1;i<=q;i++){
		int x,y;
		x=read();y=read();
		merges(x,y,i);
	}
	dfsa1(1,0,0);dfsb1(1,0,0);
	
	yclst();
//	puts("!!!");
	build(1,1,n);
	dfs2(1,0);
	for(int i=1;i<=q;i++)printf("%lld\n",anss[i]);
	return 0;



}
	
 





详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 22004kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 24032kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 24016kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

647838384844
626539793176
514273941704
637066393138
472546379596
645842915960
641537859258
573604504956
644081575470
803875451466
674370549986
734764046916
744862815441
763778393516
553499885160
526743824759
610373719514
689550247042
549161302822
726811438160
653134244120
666761991962
701575393972
6...

result:

ok 50000 numbers

Test #5:

score: 0
Accepted
time: 36ms
memory: 51976kb

input:

10000 50000
5314 8843 137901358
5314 4153 459134340
5314 8667 933926892
4153 6504 330487798
4153 8880 750362377
4153 5990 874275912
4153 546 563436331
5990 6216 902348875
8843 3101 669215553
6216 8138 732343176
8667 8675 581114294
6504 7416 127778711
546 4239 282695908
6504 9455 549237168
5314 8340 ...

output:

464564968641
331633000004
565299667784
484694871646
570451097836
417492802442
372302349684
638725688107
386235986078
355738655551
462027769535
558485994764
524714144289
450157947013
432701214095
494566741391
529031758638
637683369382
415646847933
344894296260
390294136162
527685175763
575151290175
3...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 28ms
memory: 48204kb

input:

10000 50000
2808 2490 757309564
2808 9601 312271047
2808 4046 119325897
2808 4894 466822371
4894 1507 498399554
2490 5982 84088145
9601 1251 149019541
2808 6681 416590999
2808 6583 357757899
1251 3192 889947539
6583 9762 350572496
6681 22 597479070
5982 8744 263208242
8744 5281 49894126
1507 8806 30...

output:

1501072697023
2058806276380
2017086500812
2044250452467
1543567245539
1695101693278
1765462307870
2576423082091
2302805133490
2090282734929
2375783476943
1954788661090
2056530503168
2453153202726
1978028047409
2106220371212
2210163378358
2015714406862
1555876274751
2122832986951
2102262624814
169085...

result:

ok 50000 numbers

Test #7:

score: 0
Accepted
time: 26ms
memory: 50292kb

input:

10000 50000
4064 7188 81750473
7188 8466 310631946
8466 2276 154981798
2276 7347 162965456
7188 464 806245243
464 2250 849189978
8466 641 734602751
8466 9246 225800419
4064 5267 191524437
2276 5292 192776095
2276 9036 414997994
9246 5470 362146726
2250 473 98496385
4064 7726 700294189
473 9503 42824...

output:

3589143478793
5241855728342
3397106617685
3432843859461
4544481241003
3649934075137
3020107625030
3297847713344
3894730366667
3030559097282
4824131552194
4821302024170
4471510161493
3291683748595
4954639576578
2961243269520
3659899432127
3421183608349
5262802614761
4408705330639
5203984107670
500158...

result:

ok 50000 numbers

Test #8:

score: 0
Accepted
time: 35ms
memory: 51984kb

input:

10000 50000
8676 4714 406191383
8676 5040 603960140
5040 9715 635348098
4714 9483 594267326
9483 5451 409058229
8676 8913 909259106
9715 1399 320185961
9715 4857 180234031
4714 8888 585099487
5040 1244 645347755
5451 7736 479423492
9483 1038 272038574
1399 3970 638817231
8888 3314 55726955
8888 2295...

output:

447424387353
491327570749
614052040822
384218910068
429859933145
356174725430
609432604118
465420084327
472632020898
382647454960
343751681021
441874503695
463199624732
610943875286
563031986601
566780763247
346991783125
601234775562
619765985074
357316826763
495874578271
526431260851
331681020073
4...

result:

ok 50000 numbers

Test #9:

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

input:

10000 50000
30 8765 730632293
8765 4245 897288335
30 4974 965971295
4974 9464 585377707
9464 744 157095406
744 6387 969328235
744 235 905769171
744 912 989443452
744 1341 273641834
744 9933 802952118
4974 8348 248881694
8765 9127 36706230
912 6136 324362270
4974 8517 411159721
8348 1941 672019024
94...

output:

260285187513
334448828465
448073136303
349497881882
360969017248
402078622370
390257279014
308648100196
320994952264
289449337583
393159064851
453034865550
283828471834
446349617896
380894281657
408838602752
363824724502
420964873388
362606539223
391080537186
304570333981
245848347318
310973758007
3...

result:

ok 50000 numbers

Test #10:

score: 0
Accepted
time: 23ms
memory: 46408kb

input:

10000 50000
2152 8278 350040498
2152 3058 895649234
3058 2264 151370300
8278 6118 576488088
8278 7313 464941095
3058 6966 884173172
6966 9779 786319677
9779 9796 943877064
6118 929 517473780
6118 2651 550491074
7313 662 313307192
7313 8043 506406589
7313 1698 864683116
6118 5060 766592488
6966 1903 ...

output:

652477746679
597325264627
539318490039
597048004752
421646977029
649309274459
506349020540
429554460108
462828559625
593933122751
543584884281
652286846854
654020863570
717938057245
431237695994
601883634488
731084254857
588856926225
399175030875
575410680840
526320427336
494819850806
529049784844
5...

result:

ok 50000 numbers

Test #11:

score: 0
Accepted
time: 28ms
memory: 53976kb

input:

10000 50000
7747 7582 379514112
7582 4607 188977429
7582 5317 187026200
7747 8600 712822661
8600 4262 212978273
7747 827 649275004
827 8014 76935591
7747 6641 753086484
7582 8582 206016126
8014 8460 708095438
8014 9211 377732689
8582 4450 416298437
827 9208 699971259
9208 6823 416992550
8582 186 770...

output:

746737735180
498470031337
630778245801
714337715073
566315588400
809241414480
668680437815
575990359534
612421079786
631355089285
534254563162
566879359756
667087033615
650377712872
669587743650
611030906118
593248384501
735077133684
585253655611
595113935966
519628983099
603281284099
529926712130
5...

result:

ok 50000 numbers

Test #12:

score: 0
Accepted
time: 34ms
memory: 51988kb

input:

10000 50000
3472 122 628742395
3472 3867 379635964
3867 1902 749838600
3867 7438 305533780
122 6633 278565996
122 1661 208291710
7438 3819 677928429
1902 7425 657683150
1661 5239 676247552
1902 2756 448261111
7438 7365 97063037
3819 6763 371040229
6633 8865 356148629
6763 5581 863369674
6633 1551 46...

output:

608697605604
482134269787
577721966634
628074778968
445000575297
484814952220
511586460160
374153126368
469519128844
602443844531
619658782918
385417337773
345965815878
620132139546
609655051154
537845187251
622122602447
436588599524
531403283302
587074749895
441226010189
421564270566
406700017163
5...

result:

ok 50000 numbers

Test #13:

score: 0
Accepted
time: 33ms
memory: 49700kb

input:

10000 50000
1160 9231 559787863
9231 4770 299521320
9231 9192 876373929
4770 3107 498755345
1160 5830 724175215
3107 9464 281278611
5830 3611 15139105
4770 7601 642740087
9464 910 538577221
9464 8134 554493711
7601 5225 259081456
9192 4493 741155925
5225 7756 789054604
5225 9044 160953940
7601 6104 ...

output:

44163199908
36544889589
45890256673
36776414195
37333219129
39650732470
43389306319
38148496085
42684423989
37470526473
42398992970
40710607327
42271798904
40981602830
42083787825
41411720865
39511748870
39133821656
42107800923
40131700757
38159799832
39161288828
43514631246
38415055107
37202416831
...

result:

ok 50000 numbers

Test #14:

score: 0
Accepted
time: 32ms
memory: 51596kb

input:

10000 50000
4350 9200 67344024
4350 3516 652031480
9200 9124 852386373
3516 3291 174252855
9124 6162 531615996
3516 3512 591430394
9124 1486 34243545
9200 6098 389999654
6162 3831 371706900
3512 4570 438513693
6162 312 142582166
3512 2336 718583156
4570 7409 610288335
2336 7420 1537001
7420 7842 827...

output:

1281632463885
1210271183079
1237017380491
895833426340
1283280064455
942224768023
892689065199
798697911014
751216197267
758455784557
1141824774281
820909870575
1014030803803
957938689064
1219651503682
771983156874
1178424399518
788435609430
1077287342681
1093062283731
946704599027
893784573061
1275...

result:

ok 50000 numbers

Test #15:

score: 0
Accepted
time: 32ms
memory: 42148kb

input:

10000 50000
9863 2086 776561351
2086 3631 126823773
9863 3392 474209454
3631 9001 149307847
9001 9522 263109666
3392 5761 187746709
9001 3767 870963783
3631 3788 726791
9522 4896 223271095
5761 1160 858678197
5761 543 58975325
3767 9995 875487770
1160 7361 101433507
4896 8325 954009430
8325 3351 894...

output:

3639977233620
3530907756332
2675379129344
4448022048643
2573190330483
4499414931784
3266309481456
3096703943537
2626858162069
3705044120135
3214988142418
3607045075418
2855013843207
4100248201012
2944552371007
3467914981358
4012578656847
4011860831951
5010047454262
4258401519515
4612650790910
498761...

result:

ok 50000 numbers

Test #16:

score: 0
Accepted
time: 28ms
memory: 47704kb

input:

10000 50000
4049 3217 948325921
4049 5052 335875847
5052 1077 805501667
1077 5617 791326096
3217 6795 341938001
1077 1687 296345105
6795 4846 592548551
5052 605 480047794
1687 1641 278347154
5617 4357 204297995
605 314 916793543
605 2278 379707422
2278 1593 345641808
1687 8644 903411591
1593 4760 76...

output:

22692370014
26671995767
23223650964
25037938894
24746389474
23697688458
23151041959
23816855885
23838338206
24834553266
26196330065
24533366219
26308807100
27248674922
25552842773
26570165114
22870797629
23557706389
26691697989
25265417363
24630757806
26415052596
25655335960
24347193370
26001962880
...

result:

ok 50000 numbers

Test #17:

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

input:

10000 50000
6523 4998 683131495
4998 935 871371995
6523 9691 163318078
9691 8916 578451344
9691 9874 961103371
8916 685 208189809
685 8871 368173207
8916 6734 382636596
685 5383 69823504
8871 5902 340803834
4998 587 182084912
935 8296 327702300
5383 4787 216764061
5383 2603 471182122
587 7372 923681...

output:

24346279878
24159724129
19056689759
21329886740
23717511632
21152471010
22089148390
19124036591
20347315967
22739779159
21892965420
21733073800
20715327790
19193604096
20429859569
23181805930
23345539065
21847491691
20610795206
20970932375
20066420900
25367510483
25843830881
20702116769
20515076455
...

result:

ok 50000 numbers

Test #18:

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

input:

10000 50000
8136 1635 842124659
8136 2446 96949099
1635 3483 867846492
1635 7944 589014022
2446 207 229225727
7944 1395 875428514
7944 312 711917988
3483 4069 668199427
4069 2891 305479784
4069 4426 368431680
3483 1607 247762956
1395 7960 213299897
1607 6273 261862409
207 8056 602952
7960 2331 89834...

output:

221805361345
344330244834
301417460297
196121116177
222185764926
269532557170
198254727612
342514611011
271623778301
249627562926
352800786311
318085376117
259654080926
283228181375
306204031853
331174503459
236933657251
189132469039
318214396178
200056424582
246470661905
244719493308
274008065442
3...

result:

ok 50000 numbers

Test #19:

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

input:

10000 50000
334 352 60206968
352 305 837992380
305 8581 842844833
334 8942 264051201
352 6003 382159029
8942 5537 30427164
8581 5969 913354403
6003 905 682266733
5969 1403 303476090
5969 7464 32917776
6003 2070 859897901
2070 3467 234241345
3467 8698 320427414
8581 7873 37110524
1403 8517 185370301
...

output:

581969194691
514453676470
390553242144
398767185182
396307411698
584378802405
654841477333
639529239848
655418442247
730832203542
400197481561
640310612327
591358565895
582685012783
649766947177
653842132618
655829106256
632258804246
648019844537
634680579467
592078061031
629280869021
403624822082
6...

result:

ok 50000 numbers

Test #20:

score: 0
Accepted
time: 33ms
memory: 52052kb

input:

10000 50000
2912 1663 153488050
1663 350 727308826
350 5343 783761508
5343 4104 46303186
4104 4018 493469519
4018 7659 338930839
7659 7533 245268135
7533 7193 290715498
7193 1634 377621959
1634 4211 94097273
4211 8929 767914581
8929 9758 539944169
9758 5342 960382115
5342 9418 972428758
9418 7598 33...

output:

1190970395145
1233073741726
1371353640922
1331841332961
1378285681669
1293803818492
1686098601566
1618705136059
1050063891251
1662210882776
1448886276816
1832119288597
1763213206091
1156731099316
1524816455948
1335795776622
1633864615670
1516179736541
1415679696558
1438625445786
1615887718882
189147...

result:

ok 50000 numbers

Test #21:

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

input:

10000 50000
1582 4135 838497045
4135 3442 702336909
3442 375 533282097
375 7146 882775805
7146 7807 86813140
7807 2263 859334122
2263 4883 392374535
4883 764 848075477
764 8723 793741265
8723 7925 470473887
7925 9112 861905098
9112 9330 805905723
9330 1010 229417453
1010 1029 642466213
1029 9335 709...

output:

1127922564814
1281785466573
973255728311
1332854046538
1161797930892
807045830722
1425252079799
1039233881246
980497481096
1216098061633
1476646339263
1533948111753
1212122907197
1332660079468
955677153525
1259815716640
1086329148065
909766639115
1338471739010
939166362772
1340194437028
104118973954...

result:

ok 50000 numbers

Test #22:

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

input:

10000 50000
4451 9061 799400506
9061 1178 240231790
1178 5175 327625710
5175 2065 504597872
2065 7467 395771348
7467 4338 90256163
4338 7909 39263862
7909 6047 959079033
6047 4521 939635800
4521 1781 570412122
1781 7114 41842045
7114 9567 538188744
9567 6660 479347504
6660 5084 475415876
5084 7759 2...

output:

2612835250496
2316736477624
2309048258185
2157172758992
2377745518491
2409756133919
2272336592611
2053957710271
2157940052734
2055432584295
2389859879140
2584767884856
2084451671595
2691085170630
2552358316415
2117293003432
2601352641000
2038665655976
2262026232194
2883248280386
1930369024422
263238...

result:

ok 50000 numbers

Test #23:

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

input:

10000 50000
2406 3956 170266249
3956 4278 617152977
4278 9621 802573824
9621 7235 499787802
7235 7940 556199678
7940 5712 268451785
5712 8272 380260179
8272 9454 312873112
9454 37 928734978
37 8494 918251253
8494 2702 909777424
2702 2897 511382005
2897 2473 650541982
2473 8739 540826760
8739 1318 57...

output:

3688449984397
3506033630019
3926985837670
4985948471880
5772244887821
5602256960659
4730388411655
5141144647115
3882620480043
5244011267795
6180288345261
4561619240491
4424170939376
4452089542635
5272350745707
5067654692782
4316283105320
6103750854868
4951431868818
4953378642955
4369957992172
502862...

result:

ok 50000 numbers

Test #24:

score: 0
Accepted
time: 33ms
memory: 50052kb

input:

10000 50000
9430 4862 90250453
4862 5092 294400353
5092 2612 484501098
2612 8881 932929771
8881 7630 665290950
7630 6880 197581047
6880 6106 295913729
6106 3182 888334009
3182 2764 687623650
2764 7330 955188014
7330 5888 105599141
5888 5128 827517314
5128 9673 626535422
9673 9500 218347441
9500 4501...

output:

1442822272365
1249968437919
1368459443408
925425673049
1371626107255
1501244260337
1123727805409
1434888268789
1537663432781
1199117283837
1547928613605
899524679128
1495714480795
1196591493368
981733389269
1184663866396
937249971220
1217636880799
1567605094467
1392243948541
1496701724063
9117555121...

result:

ok 50000 numbers

Test #25:

score: 0
Accepted
time: 25ms
memory: 48036kb

input:

10000 50000
1967 9497 461820510
9497 1178 319298273
1178 7445 145202113
7445 3034 902583404
3034 7501 928151869
7501 2487 459727120
2487 1927 411855531
1927 4807 105006725
4807 1992 299690675
1992 4558 246562304
4558 115 348147838
115 2218 732412173
2218 6098 36029103
6098 8912 215264673
8912 5974 7...

output:

1452728960259
1069309140104
1088859970692
1601829914205
1600074448672
918801493758
1556713604025
1468991923254
1032000884525
1120479986989
1584995341955
1225820113142
1115386685568
1125849996370
1624310125094
1042043642274
1642673371715
921569447932
1114209021067
1175110907921
1674220487453
13608173...

result:

ok 50000 numbers

Test #26:

score: 0
Accepted
time: 28ms
memory: 45928kb

input:

10000 50000
3687 1957 195328472
1957 9618 819445162
9618 5708 301381464
5708 7804 803748477
7804 5784 159651491
5784 9477 191830173
9477 2828 651065074
2828 3288 442904132
3288 2676 145220818
2676 9753 442305164
9753 9303 898437452
9303 6960 700689716
6960 6964 284360517
6964 5387 355920548
5387 392...

output:

998503404363
1604845265983
1423320672434
1230166630000
1629093161212
1665524577805
1017436418144
1379079551940
1215814978854
1525080888607
1336110438270
1391978947901
1224078797078
1337273479620
903411009592
1032160619737
1450865947593
1270702155713
1123901183324
945302264234
1621388543791
137770393...

result:

ok 50000 numbers

Test #27:

score: 0
Accepted
time: 20ms
memory: 44248kb

input:

10000 50000
4619 4672 632374577
4672 1485 151596478
1485 7570 520803323
7570 5035 589315332
5035 6454 972688563
6454 3178 4455903
3178 7452 655255761
7452 8817 290358997
8817 7446 894564176
7446 2400 391187907
2400 8212 447745441
8212 1041 225735660
1041 6146 3273699
6146 2076 501450580
2076 7017 60...

output:

1466430398410
1374962852333
1167346426504
1568616290332
1583434370235
1567260274522
1342605268196
1110985837416
1424545379723
1198723544468
1440457693462
1113663184800
1717040026662
1319981119405
1547625088972
1818262100762
1438147538696
1732361643736
1514518231328
1800320095828
1235395372966
167798...

result:

ok 50000 numbers

Test #28:

score: 0
Accepted
time: 28ms
memory: 50944kb

input:

10000 50000
3815 2108 109828605
2108 8246 871433724
8246 1773 499617397
1773 4982 529444916
4982 5565 125348820
5565 4927 295865627
4927 3617 274708402
3617 4621 934061476
4621 5864 71331083
5864 7163 41553354
7163 1864 139708757
1864 4821 408177604
4821 406 762686163
406 3802 554564727
3802 6097 45...

output:

4179645608801
3621222799118
5069122128753
3107489850826
3725609402691
4197146513097
3863763537601
4425810625162
5271230619388
3622077291893
5587359863687
3216144157381
4585048602299
4823522488441
4961364199893
3633725603053
4304942220163
5515944410576
4837662880499
3818831769794
3063292200970
371425...

result:

ok 50000 numbers

Test #29:

score: 0
Accepted
time: 44ms
memory: 47172kb

input:

10000 50000
1026 9411 807865599
9411 8477 114914385
8477 4630 117894471
4630 2583 431079789
2583 7986 776448300
7986 218 457926255
218 8900 397346917
8900 8767 218388952
8767 5843 913534371
5843 3742 618503504
3742 3319 492252659
3319 2455 830110630
2455 5201 394003558
5201 2347 119358741
2347 3095 ...

output:

4150620273258
4900011741668
4510937083926
4507537640062
4335426504350
3076847988438
3179824212142
4281208959293
4022540671475
3575917949129
4047096988755
4242394553346
3429528629662
2907131856245
3234879589233
2830253794403
3038747350850
3062740673985
3527280377144
3688356427678
2849861354167
286902...

result:

ok 50000 numbers

Test #30:

score: -100
Wrong Answer
time: 40ms
memory: 53380kb

input:

10000 50000
5676 3304 360678401
3304 9671 208651942
9671 5808 291461144
5808 7195 332714662
7195 6117 132580484
6117 2475 325019586
2475 2202 665209625
2202 9459 357492236
9459 4541 490896443
4541 102 755262166
102 480 549829265
480 2980 957076360
2980 7927 880096760
7927 6507 829376947
6507 5875 48...

output:

4053816166902
5274942110119
6621667205076
5262572259524
6375870430343
5009263574832
4550206351153
5992896905952
6725177648919
5751273937319
5957109474664
5698292166429
4651310779201
5295950230806
5540686673728
5227296374669
5403703339688
6532799126832
5515803622733
4945763113888
6142127823783
456305...

result:

wrong answer 7344th numbers differ - expected: '3681069419849', found: '3680861947624'