QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547115#7777. Intro: Dawn of a New EraskcAC ✓392ms46516kbC++143.1kb2024-09-04 18:22:072024-09-26 21:18:51

Judging History

你现在查看的是测评时间为 2024-09-26 21:18:51 的历史记录

  • [2024-10-13 20:51:30]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:393ms
  • 内存:45744kb
  • [2024-09-26 21:18:51]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:392ms
  • 内存:46516kb
  • [2024-09-26 21:17:57]
  • hack成功,自动添加数据
  • (/hack/919)
  • [2024-09-26 21:14:27]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:408ms
  • 内存:46412kb
  • [2024-09-26 21:11:59]
  • hack成功,自动添加数据
  • (/hack/918)
  • [2024-09-04 18:22:07]
  • 评测
  • 测评结果:100
  • 用时:393ms
  • 内存:46464kb
  • [2024-09-04 18:22:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=100000,M=200000;
constexpr int tN=N*3+1,tM=N+M+N*3+N*2;
vector<int> vec[N+10];
int n,val[N+10],vtop;
int getid(int x){
	int rv=lower_bound(val+1,val+1+vtop,x)-val;
	if(val[rv]==x) return rv;
	return -1;
}
struct EDGE{
	int to,next,w;
}e[tM*2+20];
int head[tN+10],etop,headc[tN+10];
void adde(int u,int v,int w){
	e[etop].to=v;
	e[etop].next=head[u];
	e[etop].w=w;
	head[u]=etop++;
}
void add(int u,int v,int w){
	adde(u,v,w);
	adde(v,u,0);
}
int dis[tN+10],vis[tN+10];
deque<int> q;
void bfs(int x){
	memset(dis,63,sizeof(dis));
	dis[x]=0;
	q.push_back(x);
	int i;
	while(!q.empty()){
		x=q.front();
		q.pop_front();
		for(i=head[x];~i;i=e[i].next){
			if(!e[i^1].w) continue;
			if(dis[e[i].to]>dis[x]+1){
				dis[e[i].to]=dis[x]+1;
				q.push_back(e[i].to);
			}
		}
	}
}
int dfs(int s,int t,int w){
	if(s==t) return w;
	vis[s]=1;
	int b=w,tmp;
	for(int &i=head[s];~i;i=e[i].next){
		if(!e[i].w) continue;
		if(vis[e[i].to]) continue;
		if(dis[e[i].to]!=dis[s]-1) continue;
		tmp=dfs(e[i].to,t,min(w,e[i].w));
		w-=tmp;
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		if(!w) break;
	}
	vis[s]=0;
	return b-w;
}
int Dinic(int s,int t){
	memcpy(headc,head,sizeof(head));
	int sum=0,flow;
	while(1){
		bfs(t);
		if(dis[s]>=1e7) break;
		sum+=flow=dfs(s,t,(int)1e9);
		memcpy(head,headc,sizeof(head));
	}
	return sum;
}
int b[N+10],btop,abab[tM*2+10];
void dfs(int x){
	if(1<=x&&x<=n) b[++btop]=x;
	if(x==tN) return;
	for(int&i=head[x];~i;i=e[i].next){
		if(abab[i]!=1){
			if(!e[i^1].w) continue;
			if(vis[e[i].to]) continue;
			if(i&1) continue;
			if(abab[i]==2) continue;
		}
		--e[i^1].w;
		dfs(e[i].to);
		break;
	}
}
int nxt[N+10],vval[N+10],vvis[N+10];
int main(){
	memset(head,255,sizeof(head));
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int i;
	for(i=1;i<=n;++i){
		int k;
		cin>>k;
		vec[i].resize(k);
		for(int j=0;j<k;++j) cin>>vec[i][j];
		sort(vec[i].begin(),vec[i].end());
		val[++vtop]=vec[i].back();
	}
	sort(val+1,val+1+vtop);
	vtop=unique(val+1,val+1+vtop)-val-1;
	val[vtop+1]=1e9;
	for(i=1;i<=n;++i){
		add(i,n+getid(vec[i].back()),1);
		for(auto j:vec[i]){
			int o=getid(j);
			if(o!=-1&&j!=vec[i].back()){
				add(n+vtop+o,i,1);
			}
		}
	}
	for(i=1;i<=vtop;++i){
		add(n+i,tN+2,1);
		add(tN+1,n+vtop+i,1);
		add(n+i,n+vtop+i,n);
		abab[etop-2]=1;
		abab[etop-1]=2;
	}
	for(i=1;i<=n;++i){
		add(0,i,1);
	}
	for(i=1;i<=vtop;++i){
		add(n+vtop+i,tN,1);
	}
	add(tN,0,n);
	int tmp=Dinic(tN+1,tN+2);
	assert(tmp==vtop);
	tmp=e[etop-1].w;
	vis[tN+1]=vis[tN+2]=1;
	e[etop-2].w=e[etop-1].w=0;
	tmp-=Dinic(tN,0);
	cout<<n-tmp<<'\n';
	for(int i=0;i<n;++i){
		dfs(0);
	}
	static bool vvis[tN+10];
	static vector<int>V[tN+10];
	for(int i=1;i<=btop;++i){
		vvis[b[i]]=1;
	}
	for(int i=1;i<=n;++i)
		if(!vvis[i])V[getid(vec[i].back())].emplace_back(i);
	for(int i=1;i<=btop;++i){
		cout<<b[i]<<' ';
		auto&v=V[getid(vec[b[i]].back())];
		for(int x:v)cout<<x<<' ';
		v.clear();
	}
	for(int i=1;i<=vtop;++i)
		for(int x:V[i])
			cout<<x<<' ';
	cout<<'\n';
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

3
4 2 3 1 5 

result:

ok correct!

Test #2:

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

input:

3
1 1
1 2
1 3

output:

0
3 2 1 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 5ms
memory: 24036kb

input:

9
2 1 2
2 3 4
2 2 5
2 4 5
2 5 6
2 6 7
2 6 8
2 2 8
2 8 9

output:

7
2 4 3 5 6 1 8 7 9 

result:

ok correct!

Test #4:

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

input:

20
2 17 18
2 19 20
2 3 4
2 11 12
2 20 21
2 14 15
2 4 5
2 12 13
2 7 8
2 13 14
2 1 2
2 8 9
2 15 16
2 6 7
2 5 6
2 18 19
2 16 17
2 10 11
2 9 10
2 2 3

output:

19
11 20 3 7 15 14 9 12 19 18 4 8 10 6 13 17 1 16 2 5 

result:

ok correct!

Test #5:

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

input:

20
2 1 12
2 1 3
2 1 4
2 1 21
2 1 15
2 1 10
2 1 19
2 1 17
2 1 9
2 1 5
2 1 8
2 1 18
2 1 2
2 1 20
2 1 14
2 1 6
2 1 7
2 1 16
2 1 13
2 1 11

output:

0
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 

result:

ok correct!

Test #6:

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

input:

20
2 20 21
2 6 20
2 11 20
2 13 14
2 18 21
2 15 21
2 10 16
2 7 8
2 1 12
2 12 18
2 7 20
2 5 12
2 18 21
2 4 14
2 12 17
2 12 16
2 16 19
2 7 12
2 10 18
2 11 14

output:

14
20 4 14 19 10 18 9 12 16 7 17 15 11 2 3 1 5 6 13 8 

result:

ok correct!

Test #7:

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

input:

20
2 9 10
2 1 17
2 11 12
2 20 21
2 1 4
2 6 7
2 15 16
2 1 18
2 1 5
2 1 13
2 5 21
2 7 21
2 1 2
2 2 21
2 1 19
2 19 20
2 14 21
2 10 11
2 13 14
2 8 21

output:

10
15 16 4 11 12 14 17 20 13 10 19 9 8 7 6 5 2 1 18 3 

result:

ok correct!

Test #8:

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

input:

20
2 4 6
2 11 16
2 9 15
2 10 14
2 20 21
2 10 20
2 8 10
2 3 19
2 3 18
2 16 18
2 4 14
2 14 18
2 20 21
2 13 21
2 19 21
2 15 21
2 7 12
2 4 16
2 20 21
2 20 21

output:

13
18 2 10 9 12 17 11 4 8 7 6 20 5 13 14 15 16 19 3 1 

result:

ok correct!

Test #9:

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

input:

20
2 10 12
2 5 7
2 4 11
2 14 15
2 10 12
2 17 20
2 14 15
2 12 13
2 12 15
2 15 18
2 18 20
2 14 16
2 16 21
2 7 20
2 7 14
2 12 19
2 3 15
2 5 6
2 16 17
2 7 8

output:

12
18 17 4 7 9 10 11 6 14 15 12 19 13 8 5 1 16 3 2 20 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 5ms
memory: 20644kb

input:

20
2 8 21
2 7 20
2 15 21
2 18 21
2 17 19
2 10 15
2 8 14
2 5 19
2 16 21
2 3 8
2 5 8
2 7 11
2 12 21
2 6 13
2 10 13
2 16 21
2 7 14
2 12 15
2 18 20
2 19 21

output:

14
19 2 18 6 15 14 12 11 10 7 17 8 5 20 1 3 4 9 13 16 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 4ms
memory: 21080kb

input:

20
2 13 20
2 16 20
2 20 21
2 4 5
2 16 21
2 11 13
2 5 7
2 16 19
2 18 19
2 12 18
2 1 16
2 11 17
2 11 20
2 2 19
2 6 20
2 19 20
2 4 13
2 17 20
2 14 17
2 15 17

output:

15
20 12 19 17 6 11 10 9 8 14 16 1 2 13 15 18 3 5 4 7 

result:

ok correct!

Test #12:

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

input:

20
2 15 17
2 10 19
2 9 11
2 19 20
2 2 17
2 15 17
2 17 18
2 1 13
2 16 17
2 4 13
2 4 9
2 11 21
2 8 17
2 8 21
2 16 17
2 5 21
2 1 2
2 2 6
2 8 20
2 18 21

output:

15
17 18 15 1 5 6 9 13 7 20 12 14 16 11 3 10 8 2 4 19 

result:

ok correct!

Test #13:

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

input:

20
2 4 16
2 11 18
2 16 18
2 20 21
2 18 21
2 13 18
2 15 17
2 3 13
2 16 19
2 3 19
2 13 20
2 9 19
2 19 21
2 8 12
2 10 14
2 12 18
2 11 20
2 11 16
2 16 20
2 17 20

output:

15
18 1 9 10 12 15 14 8 6 2 3 16 7 20 11 17 19 4 5 13 

result:

ok correct!

Test #14:

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

input:

20
2 7 20
2 5 18
2 12 19
2 3 12
2 13 19
2 1 2
2 11 19
2 19 21
2 5 16
2 12 14
2 3 20
2 17 19
2 20 21
2 1 2
2 3 18
2 14 16
2 2 11
2 12 13
2 10 14
2 3 19

output:

15
19 10 16 9 15 2 14 6 17 11 1 13 8 4 18 5 3 7 12 20 

result:

ok correct!

Test #15:

score: 0
Accepted
time: 5ms
memory: 22200kb

input:

20
2 7 11
2 11 17
2 9 21
2 1 2
2 15 19
2 9 21
2 1 10
2 7 19
2 17 21
2 15 17
2 7 9
2 20 21
2 1 5
2 14 17
2 14 21
2 10 21
2 6 20
2 7 9
2 4 6
2 17 18

output:

13
19 17 12 3 6 9 15 16 18 11 13 8 5 7 4 1 2 10 14 20 

result:

ok correct!

Test #16:

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

input:

20
2 10 17
2 11 21
2 4 13
2 17 20
2 18 20
2 1 21
2 4 19
2 11 21
2 1 20
2 20 21
2 7 15
2 1 3
2 18 21
2 20 21
2 15 16
2 14 18
2 8 14
2 6 16
2 17 21
2 10 16

output:

14
17 16 5 4 9 14 2 6 8 10 13 19 12 11 15 18 20 7 3 1 

result:

ok correct!

Test #17:

score: 0
Accepted
time: 5ms
memory: 23348kb

input:

1000
2 926 927
2 660 661
2 142 143
2 43 44
2 199 200
2 80 81
2 132 133
2 614 615
2 500 501
2 173 174
2 804 805
2 22 23
2 358 359
2 553 554
2 974 975
2 31 32
2 969 970
2 847 848
2 857 858
2 284 285
2 244 245
2 649 650
2 84 85
2 890 891
2 382 383
2 575 576
2 936 937
2 858 859
2 921 922
2 211 212
2 327...

output:

999
248 712 884 682 508 455 916 411 403 992 128 828 690 628 959 497 324 639 898 272 960 12 542 760 663 709 596 998 95 963 16 815 900 745 374 664 243 896 700 832 77 448 4 333 568 829 49 308 679 420 984 479 490 133 487 680 186 659 395 811 290 797 199 307 350 718 620 742 874 314 426 294 886 518 351 972...

result:

ok correct!

Test #18:

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

input:

1000
2 1 23
2 1 983
2 1 460
2 1 171
2 1 34
2 1 516
2 1 437
2 1 823
2 1 546
2 1 37
2 1 914
2 1 609
2 1 757
2 1 96
2 1 39
2 1 646
2 1 574
2 1 443
2 1 651
2 1 257
2 1 557
2 1 533
2 1 213
2 1 611
2 1 787
2 1 238
2 1 896
2 1 552
2 1 850
2 1 714
2 1 61
2 1 218
2 1 179
2 1 192
2 1 836
2 1 568
2 1 279
2 1 3...

output:

0
1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 9...

result:

ok correct!

Test #19:

score: 0
Accepted
time: 6ms
memory: 24076kb

input:

1000
2 322 639
2 960 978
2 28 258
2 891 900
2 121 546
2 768 792
2 330 497
2 290 711
2 752 932
2 145 148
2 978 1000
2 96 644
2 326 892
2 292 961
2 285 348
2 312 858
2 222 509
2 342 944
2 305 361
2 266 831
2 521 906
2 701 908
2 238 473
2 345 589
2 899 932
2 4 490
2 780 905
2 786 790
2 952 956
2 170 55...

output:

759
998 240 435 250 234 997 732 990 988 253 979 714 551 577 644 724 464 973 249 463 921 763 776 909 961 975 966 695 45 632 760 972 963 111 958 596 957 675 840 956 204 594 549 590 663 346 834 984 373 160 232 618 749 820 779 281 296 678 503 188 195 265 334 701 954 952 377 178 212 568 950 967 282 458 6...

result:

ok correct!

Test #20:

score: 0
Accepted
time: 3ms
memory: 23156kb

input:

1000
2 1 534
2 628 1001
2 498 1001
2 1 107
2 355 1001
2 1 313
2 756 1001
2 800 801
2 816 1001
2 972 1001
2 793 794
2 1 484
2 653 1001
2 1 664
2 920 921
2 992 993
2 1 931
2 1 576
2 1 761
2 1 682
2 835 1001
2 196 1001
2 1 608
2 790 1001
2 1 424
2 1 9
2 901 902
2 77 78
2 907 908
2 1 700
2 1 59
2 1 379
...

output:

541
998 903 994 991 286 990 858 739 116 989 212 1000 988 986 983 71 981 980 979 977 975 973 971 968 966 963 962 611 960 959 459 123 958 707 956 935 625 954 522 553 948 946 696 945 572 944 128 869 942 393 941 939 937 114 734 936 934 933 930 929 928 466 927 604 923 423 920 950 783 919 917 914 912 722 ...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 6ms
memory: 21644kb

input:

1000
2 507 536
2 995 999
2 447 844
2 673 963
2 236 608
2 621 897
2 622 748
2 984 991
2 219 719
2 40 994
2 643 717
2 642 754
2 812 867
2 42 369
2 659 998
2 307 359
2 366 816
2 270 441
2 86 216
2 918 929
2 433 651
2 622 927
2 162 416
2 422 593
2 329 575
2 925 948
2 841 869
2 339 576
2 178 342
2 548 79...

output:

749
997 649 318 993 990 332 989 984 60 835 880 983 455 972 32 657 742 982 12 516 572 980 286 961 688 245 744 979 274 978 412 976 723 146 824 975 151 325 379 974 578 644 966 962 953 652 759 949 427 204 414 707 738 947 462 944 938 743 935 422 559 636 933 303 588 658 469 616 932 156 352 896 954 113 78 ...

result:

ok correct!

Test #22:

score: 0
Accepted
time: 6ms
memory: 22452kb

input:

1000
2 9 630
2 20 209
2 886 910
2 229 395
2 775 876
2 53 785
2 116 539
2 541 947
2 440 878
2 348 541
2 62 72
2 185 207
2 457 478
2 876 943
2 289 828
2 199 569
2 750 866
2 350 859
2 449 1000
2 614 919
2 159 576
2 860 863
2 523 640
2 90 673
2 678 695
2 195 297
2 952 968
2 755 932
2 551 884
2 585 778
2...

output:

742
996 520 942 994 701 350 750 397 991 104 482 106 354 937 680 90 99 258 776 884 990 989 160 985 281 238 982 138 978 975 973 865 126 772 76 972 545 968 967 239 893 72 509 962 511 592 439 959 645 955 374 196 215 902 667 46 742 833 953 951 88 316 390 923 789 297 70 688 135 673 613 140 837 445 947 940...

result:

ok correct!

Test #23:

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

input:

1000
2 122 559
2 498 582
2 639 837
2 162 165
2 322 953
2 304 435
2 769 823
2 407 841
2 885 901
2 5 453
2 991 996
2 191 824
2 418 614
2 233 251
2 76 850
2 762 988
2 45 265
2 810 932
2 14 546
2 152 731
2 901 980
2 426 761
2 120 555
2 414 940
2 919 931
2 30 622
2 217 814
2 897 979
2 197 879
2 567 923
2...

output:

748
1000 344 926 999 673 996 562 388 836 947 992 488 202 990 500 886 927 987 984 67 981 967 88 278 638 739 513 559 664 972 464 875 971 282 770 970 993 322 514 965 309 634 92 182 211 597 705 578 607 905 961 957 946 757 942 52 940 457 711 468 591 862 212 425 938 518 455 968 998 615 171 542 937 936 806...

result:

ok correct!

Test #24:

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

input:

1000
2 512697359 512774760
2 648164742 651715810
2 87626639 88106897
2 23746611 24188540
2 612369762 612453612
2 657545784 658170997
2 356463524 356849621
2 183720601 183734922
2 638606521 639379351
2 368881937 369615994
2 267253191 267995026
2 20605282 22822236
2 412174893 413053221
2 44459170 4470...

output:

999
535 176 467 282 495 466 353 550 470 604 906 568 710 19 868 748 701 57 334 849 656 636 128 587 873 622 459 146 12 76 692 4 108 159 659 314 996 826 967 920 551 411 624 973 192 431 812 225 25 553 647 227 573 687 594 752 390 613 274 536 558 725 841 330 888 53 420 988 629 59 951 14 252 58 468 190 97 ...

result:

ok correct!

Test #25:

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

input:

1000
2 689110 123618662
2 689110 377706241
2 689110 336058146
2 689110 420597240
2 689110 601454368
2 689110 217406459
2 689110 480517810
2 689110 123853154
2 689110 512642478
2 689110 434665274
2 689110 147499673
2 689110 502900373
2 689110 512082915
2 689110 528921552
2 689110 485324937
2 689110 4...

output:

0
1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 9...

result:

ok correct!

Test #26:

score: 0
Accepted
time: 3ms
memory: 20832kb

input:

1000
2 13182656 97097493
2 534040646 686390939
2 15317349 798031669
2 12527965 844489633
2 571878710 942801249
2 209452489 642245523
2 309202234 665709291
2 452019901 817215335
2 213188968 660531281
2 236377020 719458791
2 885520813 929279023
2 789242396 954981032
2 728381185 905330516
2 930178744 9...

output:

629
1000 304 517 863 991 999 110 935 317 347 521 998 990 688 988 987 970 986 732 981 979 721 977 976 974 972 971 967 163 964 961 784 891 930 424 28 159 278 550 962 959 226 358 563 128 451 495 275 239 958 476 530 957 524 544 952 653 788 492 953 151 357 951 466 950 108 745 948 844 946 125 945 944 124 ...

result:

ok correct!

Test #27:

score: 0
Accepted
time: 4ms
memory: 20608kb

input:

1000
2 234530151 645041705
2 541508343 541790009
2 475415737 477831954
2 403318 414196892
2 201373810 202813283
2 403318 101085488
2 249234594 645041705
2 403318 77381550
2 361905218 645041705
2 403318 46490445
2 126508755 645041705
2 403318 155549446
2 173971388 645041705
2 604500868 607164086
2 40...

output:

540
1000 999 998 664 86 997 187 996 994 992 724 986 904 984 982 981 976 974 971 969 980 968 446 124 966 965 964 823 963 958 955 949 945 942 941 938 934 933 931 89 930 929 927 925 680 494 657 924 923 922 921 87 920 915 913 397 63 911 910 908 907 906 282 905 451 903 902 901 900 844 897 896 790 895 353...

result:

ok correct!

Test #28:

score: 0
Accepted
time: 5ms
memory: 23228kb

input:

1000
2 617243117 868238738
2 581179245 814192846
2 601381485 694795618
2 492520629 928681111
2 36607223 342636773
2 465170385 744208961
2 894226642 917965440
2 955758812 971948546
2 228214222 610889618
2 232507617 601381485
2 471311352 693868162
2 501068095 832083539
2 876843796 981863378
2 47083364...

output:

630
1000 999 654 993 901 512 306 836 992 769 991 988 38 986 984 420 983 980 276 979 978 891 75 347 751 977 668 549 974 971 439 970 969 966 792 774 204 963 705 961 959 953 799 801 952 951 64 134 41 950 324 949 773 890 187 562 948 762 918 243 530 947 86 325 945 116 943 265 721 940 939 937 934 932 930 ...

result:

ok correct!

Test #29:

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

input:

1000
2 920901423 974010612
2 815808463 828407660
2 481347895 556221528
2 182460512 634505113
2 831483943 976133598
2 105815699 379285207
2 674221624 905477702
2 399113592 620489963
2 62016516 214067254
2 527579867 955151402
2 830675962 883173856
2 948490774 964039399
2 173305694 213392181
2 30615226...

output:

646
999 998 610 993 992 991 836 612 568 250 636 990 989 988 986 101 114 23 311 980 979 155 819 738 977 903 545 182 962 661 457 973 492 315 139 677 970 966 580 606 978 965 129 164 964 958 956 782 212 739 954 158 35 952 480 56 145 196 441 25 410 563 755 908 950 383 948 381 579 947 925 601 598 720 944 ...

result:

ok correct!

Test #30:

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

input:

1000
2 335179329 834946514
2 283244947 828406291
2 194193951 833817416
2 228853987 645842676
2 535125948 537666192
2 535369179 561139451
2 694701107 855227705
2 937751529 996625109
2 58635182 83954819
2 337719556 499663115
2 805571812 881156579
2 449637409 904707632
2 853294998 898929900
2 19747035 ...

output:

633
998 408 428 539 997 27 996 637 716 272 990 447 193 902 988 509 986 125 299 981 697 376 43 241 796 396 514 980 979 978 972 971 381 221 966 400 748 45 817 903 230 726 784 965 333 827 963 590 123 923 833 890 491 628 900 907 935 973 960 969 958 957 567 880 989 953 951 946 32 942 941 461 563 913 615 ...

result:

ok correct!

Test #31:

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

input:

100000
2 48459 48460
2 21895 21896
2 6640 6641
2 47086 47087
2 83937 83938
2 52096 52097
2 82721 82722
2 88798 88799
2 11916 11917
2 7382 7383
2 35078 35079
2 33960 33961
2 53910 53911
2 43673 43674
2 63314 63315
2 80238 80239
2 67146 67147
2 91456 91457
2 22355 22356
2 51033 51034
2 26479 26480
2 7...

output:

99999
76245 10773 13043 32899 88895 46371 81501 62284 4343 84490 94666 85913 12895 73843 51288 52503 8144 94154 30812 38356 91034 7625 28753 58842 5341 39356 93437 86033 53541 15209 43076 71407 81913 26821 46869 6551 89893 92879 88841 76700 54831 31493 42533 29537 48441 8495 21655 94082 39405 20952 ...

result:

ok correct!

Test #32:

score: 0
Accepted
time: 90ms
memory: 44124kb

input:

100000
2 1 81053
2 1 16517
2 1 90983
2 1 99752
2 1 85811
2 1 25069
2 1 93076
2 1 53744
2 1 53964
2 1 76157
2 1 60365
2 1 72282
2 1 86306
2 1 30379
2 1 50838
2 1 3764
2 1 75120
2 1 90708
2 1 2490
2 1 43799
2 1 77311
2 1 82055
2 1 8538
2 1 54162
2 1 56356
2 1 47484
2 1 9616
2 1 71534
2 1 68712
2 1 945...

output:

0
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 999...

result:

ok correct!

Test #33:

score: 0
Accepted
time: 235ms
memory: 38492kb

input:

100000
2 12000 54652
2 28351 79538
2 94360 94937
2 61977 85064
2 86167 86510
2 72079 81388
2 27376 95608
2 86518 89067
2 40238 45556
2 14542 19339
2 15897 35460
2 48661 50646
2 14032 44400
2 64328 70815
2 25376 99199
2 91299 95405
2 14847 99126
2 10716 70170
2 40377 72895
2 55068 87277
2 93035 95045...

output:

74529
99998 59834 99997 87754 99996 94784 17687 99993 80224 26365 51836 99992 6188 99991 5959 99989 93007 45410 13178 23388 67252 99986 99985 86573 13656 40547 73049 99982 98793 43993 50463 63818 84178 37766 67496 71358 86937 60119 99979 63111 12714 17599 23995 32151 79712 84572 99977 23303 95137 99...

result:

ok correct!

Test #34:

score: 0
Accepted
time: 78ms
memory: 41076kb

input:

100000
2 1 12317
2 23106 100001
2 1 33767
2 47015 47016
2 74948 74949
2 1 27200
2 11084 11085
2 73463 100001
2 97529 97530
2 61168 100001
2 21246 21247
2 88781 100001
2 93455 100001
2 1 56715
2 1 59545
2 1 6644
2 61725 100001
2 37111 100001
2 1 59337
2 1 27135
2 42453 42454
2 5800 5801
2 22556 10000...

output:

55541
99999 99995 32907 99993 99984 99982 41444 99981 99979 99977 99976 99975 99972 19162 99970 99969 50409 67779 46653 99968 99965 2841 63589 95913 96965 75449 99963 74083 99960 99959 61913 99958 99954 99953 55661 62463 99952 99949 99947 44508 36018 38037 99944 99942 99939 62566 99034 99938 99936 9...

result:

ok correct!

Test #35:

score: 0
Accepted
time: 221ms
memory: 37796kb

input:

100000
2 42752 67631
2 97619 99412
2 64028 86492
2 60998 70996
2 71786 93438
2 74951 96860
2 78201 95252
2 51711 99890
2 5829 50791
2 79409 96439
2 70369 80364
2 95323 98450
2 23734 79022
2 49533 88776
2 63407 97283
2 10732 57041
2 5829 74062
2 61731 64329
2 10911 94555
2 41146 50147
2 91823 98918
2...

output:

74424
99994 99983 47488 80446 99979 90141 99973 78513 67239 99970 55227 9443 21286 98795 50777 99969 41202 99968 69233 75332 36082 2061 48497 99967 43257 97641 69867 2874 86130 99965 99964 713 73977 79337 32612 19842 82223 92848 51811 34912 55781 99961 1830 87812 99954 11709 99944 83527 98193 18437 ...

result:

ok correct!

Test #36:

score: 0
Accepted
time: 220ms
memory: 37024kb

input:

100000
2 13580 57952
2 88073 92336
2 40003 60273
2 37350 75834
2 33426 77751
2 44240 70645
2 4562 89897
2 79260 84075
2 11747 41473
2 27445 62209
2 67647 82594
2 64358 83057
2 56322 85247
2 63242 78982
2 91834 98455
2 66044 82898
2 73126 79954
2 54564 90545
2 36449 43667
2 53768 82955
2 33846 77078
...

output:

74529
100000 82671 99999 21351 96804 41818 99996 99995 30155 99994 99991 7235 54665 43337 7862 43620 72735 90460 29226 99990 99528 75151 15727 26956 69281 99989 34353 36172 99987 4710 8354 71132 97997 16777 38997 74705 99986 691 22089 26359 33742 76725 82049 30674 50454 78223 81395 1316 13218 18641 ...

result:

ok correct!

Test #37:

score: 0
Accepted
time: 216ms
memory: 38520kb

input:

100000
2 40228 81714
2 99713 99721
2 7259 32553
2 18515 59727
2 98969 99914
2 46923 54347
2 79489 99191
2 15790 28131
2 48637 70550
2 96452 97070
2 24912 25734
2 64363 77764
2 44429 68433
2 34796 74713
2 15622 35045
2 68822 73956
2 66344 93338
2 92871 97507
2 23587 80300
2 17611 74039
2 40450 94231
...

output:

74416
100000 75128 6917 99998 99997 99995 99215 99994 99988 94809 57000 99984 95311 88138 49737 49117 3744 7855 21484 35330 61722 96217 12248 18580 99982 99976 90177 88436 94338 73984 3888 39041 57602 99971 86331 99967 99115 9661 42654 83932 53958 54283 76417 94099 87104 5058 89502 99962 18992 25244...

result:

ok correct!

Test #38:

score: 0
Accepted
time: 120ms
memory: 46516kb

input:

100000
2 596401419 596405347
2 31587562 31592900
2 253158848 253160067
2 654443478 654446953
2 260834303 260852020
2 461648137 461649937
2 61561195 61577827
2 116053155 116061032
2 476740816 476745660
2 598420085 598429594
2 453346816 453350408
2 494568528 494573032
2 487089527 487095168
2 247840352...

output:

99999
51068 49529 80796 86045 80411 33244 38458 29503 99284 34822 55740 34760 95335 97116 6336 44896 19267 38031 7300 36825 16575 53904 65563 72640 97880 35536 2904 84368 80065 15652 79218 85718 22663 83261 73079 51728 39760 3809 23097 58070 19815 23192 97961 81937 27021 72968 22487 70564 97702 2065...

result:

ok correct!

Test #39:

score: 0
Accepted
time: 88ms
memory: 41928kb

input:

100000
2 3142 140849999
2 3142 486848036
2 3142 99305595
2 3142 369542113
2 3142 130549827
2 3142 230567267
2 3142 114486183
2 3142 324385142
2 3142 523190768
2 3142 182822411
2 3142 287473472
2 3142 174863271
2 3142 418615430
2 3142 465179581
2 3142 5921085
2 3142 88494543
2 3142 279235795
2 3142 2...

output:

0
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 999...

result:

ok correct!

Test #40:

score: 0
Accepted
time: 198ms
memory: 38940kb

input:

100000
2 237338344 652431151
2 773245782 995378876
2 524649543 738613984
2 366725068 885223820
2 810051474 872050776
2 972414208 992417952
2 883113760 888004022
2 155856635 723951012
2 421288306 886375493
2 5941848 229186961
2 416886098 673867373
2 157517412 371117347
2 849355506 895553328
2 2439590...

output:

63743
99999 99998 99996 99995 7460 24930 30049 44364 99994 99993 1786 99990 91152 9533 93266 99987 99985 15911 92269 99982 19886 81596 2834 21426 99980 13431 20082 72119 99979 15124 99977 87127 99976 79095 13620 70095 39735 85279 93972 99975 68276 62793 99974 43608 52148 99973 99972 96619 50 22365 2...

result:

ok correct!

Test #41:

score: 0
Accepted
time: 80ms
memory: 42376kb

input:

100000
2 43890701 43901592
2 568 218118988
2 206823285 206829134
2 568 205642395
2 500741974 666071483
2 202032425 202033556
2 515527059 666071483
2 622229455 666071483
2 568 582113592
2 568 262721376
2 587512551 666071483
2 568 577191215
2 445248200 445248571
2 352847796 352857605
2 249588493 24959...

output:

55511
100000 99999 99997 99995 31884 99994 99988 99986 99980 99979 99977 76552 99976 99975 45610 99974 99972 60564 99971 1221 42010 99966 10341 99965 99963 99962 99961 61520 94855 99959 99954 99952 99950 99945 55477 72518 99942 99941 99939 99936 41749 2677 7475 99935 75233 99934 97962 99933 58603 99...

result:

ok correct!

Test #42:

score: 0
Accepted
time: 205ms
memory: 41380kb

input:

100000
2 686849852 746248482
2 732526813 779294820
2 376786021 843151433
2 269957600 973473231
2 320069829 505476437
2 249208181 260879541
2 61651079 246358579
2 608000514 842597830
2 261154673 733548353
2 774471763 954541503
2 108045354 975764876
2 864725035 945036602
2 161286600 912396559
2 548794...

output:

63820
100000 96483 1136 54212 99999 69412 92423 12805 31101 60111 99995 60849 99994 93789 99992 99990 20460 29220 50954 15878 46578 99986 3396 67719 95020 99985 99982 99980 99977 28307 64400 2785 40985 78588 39398 99975 99973 99972 99969 36914 48293 75962 89688 99968 44514 99967 69045 86033 29148 40...

result:

ok correct!

Test #43:

score: 0
Accepted
time: 193ms
memory: 39292kb

input:

100000
2 702221799 829527113
2 594154243 730679644
2 698097756 958906217
2 790137799 913317707
2 301657172 552073583
2 337536232 371059060
2 389715331 682048619
2 988326494 993053331
2 159833625 861127609
2 652183344 821304427
2 679559260 807716233
2 380854425 911557959
2 292910660 384678167
2 11975...

output:

63840
99998 99997 34559 99991 2745 91831 61164 98536 99988 11445 21059 17943 99986 40208 81386 91416 99983 52809 99982 99980 99978 99977 74730 99976 99975 99973 83708 99971 99966 8913 23661 43358 61091 65840 99965 99961 21041 17767 99959 99958 79563 99951 8866 23756 57913 99949 17496 58047 88602 699...

result:

ok correct!

Test #44:

score: 0
Accepted
time: 197ms
memory: 41568kb

input:

100000
2 485070748 880630415
2 149909829 181582017
2 518889351 802876478
2 629244207 950379261
2 334862810 720985874
2 926637129 977914386
2 18740461 57165062
2 536638895 620961118
2 340803355 728643217
2 305158581 748948117
2 814938104 903197336
2 580779830 683888210
2 553576170 584700111
2 2906157...

output:

63859
100000 99998 98470 28290 99992 82524 30407 99991 20246 55352 51320 99990 41321 45644 99988 99987 26730 53197 67521 99986 15300 18167 30340 99985 99981 79578 34309 38572 11661 99980 74298 99979 24657 52583 94373 47105 8551 60302 99974 9468 90863 99565 99973 99972 71210 96275 99969 99967 25050 9...

result:

ok correct!

Test #45:

score: 0
Accepted
time: 54ms
memory: 30284kb

input:

50000
4 45 60 36 68
2 18 29
3 78 27 73
2 17 37
5 39 49 45 68 74
3 45 88 36
5 77 70 38 28 1
4 71 0 40 18
6 91 49 27 7 38 31
3 73 45 47
3 8 21 65
1 98
6 42 70 9 41 62 0
5 42 79 39 37 31
3 74 100 17
3 95 31 87
5 51 48 32 72 69
2 92 87
1 72
5 98 33 13 28 18
3 98 42 33
5 93 85 100 5 69
3 94 6 88
4 87 81 ...

output:

49998
49478 219 1337 2521 5982 6868 10825 12339 15801 16796 21308 22119 22737 24890 25932 27909 29890 30043 30841 32546 33275 33970 34783 35547 36525 40809 41651 44275 11717 4005 5130 5188 6921 7075 7528 9484 10579 13008 16381 18532 18695 20715 20933 21041 21751 23917 24140 27396 27727 27954 31092 3...

result:

ok correct!

Test #46:

score: 0
Accepted
time: 114ms
memory: 31396kb

input:

50000
4 207 607 880 135
3 484 438 759
4 192 317 598 811
3 912 107 838
5 245 981 121 849 634
7 920 599 638 85 830 673 162
1 465
4 597 436 704 81
5 634 900 844 898 527
4 899 920 435 234
2 523 581
3 6 126 182
7 904 163 90 973 794 369 390
3 207 868 74
7 884 259 79 169 559 547 49
2 427 435
2 313 812
4 68...

output:

49934
49869 13536 49594 21038 3368 12195 15457 38107 38947 38153 276 2727 9580 21169 27919 30096 31460 41401 42059 37567 11667 25981 39367 43758 36350 1293 1727 2272 25453 28820 28830 30221 31457 34419 27562 13937 18781 19173 29336 34500 35058 20103 5078 8031 10470 17633 27617 30040 35829 37566 4919...

result:

ok correct!

Test #47:

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

input:

50000
3 1113 774 1032
3 1637 849 1523
2 1291 1960
5 737 376 438 1907 844
2 1657 1636
5 1252 1128 336 174 417
3 438 1645 364
5 1541 1594 821 1060 439
3 878 1043 1632
7 1506 1023 1734 1918 904 340 1213
2 1769 1778
5 1053 463 381 1348 395
3 323 1324 382
3 177 664 201
1 285
2 17 1159
3 1398 5 1465
4 834...

output:

49807
49921 9840 49027 7103 12015 22165 26823 34950 35577 49731 26509 40501 627 1794 26253 27200 30146 40415 44361 2982 9563 9758 12194 26281 29782 31063 41958 45451 2275 2313 10528 10547 21149 22775 29977 34972 35081 36638 41966 42479 44033 25908 17232 22228 31869 36846 39814 39824 42356 48515 4976...

result:

ok correct!

Test #48:

score: 0
Accepted
time: 149ms
memory: 30732kb

input:

50000
6 1932 2335 319 1627 1276 903
1 1074
4 3418 1963 2015 1396
3 423 2262 439
4 3261 1799 1742 854
4 2511 561 2598 1938
1 1609
4 2106 1519 3801 699
4 3822 2210 1792 2063
6 159 2986 2128 1072 3137 2632
4 1520 3179 2927 2523
6 549 1587 1568 3324 2096 1463
2 2671 1427
5 387 3441 1333 1212 2766
4 779 ...

output:

49508
49919 19731 26197 36175 16417 11155 16645 3735 7114 15145 33953 26468 3392 6305 20370 49760 32686 9966 26835 27079 20508 49476 17310 11543 27218 43225 4298 4512 9477 12325 13688 20919 26571 33986 42671 47325 37723 2514 4860 19403 22142 22486 32383 38313 49980 46453 4742 9119 11064 20104 21589 ...

result:

ok correct!

Test #49:

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

input:

50000
3 2180 4273 1595
1 2283
6 4115 4886 4931 5988 298 3993
6 2726 75 1258 5026 109 3702
5 4249 355 4095 4737 1812
7 5354 1250 1052 1931 4396 418 2218
3 791 1744 3896
3 1067 520 5278
2 1206 5518
6 4755 4598 3417 4111 4792 3796
3 2658 4809 27
5 1258 1959 2520 2410 1625
4 2772 3311 1798 111
5 2752 11...

output:

49185
49892 11040 47387 16393 48316 49857 34286 42589 8806 24247 25955 26475 34638 7287 34100 40369 44182 44357 40860 2368 3935 10666 12390 12829 13025 14532 15023 18042 23335 35278 44647 20520 5820 7432 8052 11141 16097 16262 20863 25212 35235 35515 36640 40373 41558 45794 49672 7569 32032 785 2651...

result:

ok correct!

Test #50:

score: 0
Accepted
time: 169ms
memory: 30952kb

input:

50000
3 4868 1966 2385
4 2121 6317 2935 2319
3 5761 3025 6058
6 5262 7486 7357 6772 6784 1105
2 965 1435
4 2526 2549 1034 1014
4 7770 4679 1031 1226
6 976 7443 5675 3183 3319 1526
5 4613 5237 1010 7973 2692
1 3384
3 2999 406 1835
6 7582 3141 3671 1740 3375 5057
4 3165 2014 5380 4642
6 1824 174 6914 ...

output:

48824
49981 1505 2971 36186 31996 47184 5673 24044 49957 42825 27745 23438 29089 31930 40778 41257 47829 49081 23169 49905 5074 31288 5446 13676 33780 42771 3064 6187 6786 18739 41680 49871 39976 37462 7971 22995 2232 2328 7034 11325 49856 12262 49855 31501 49029 13290 38724 2426 16630 33662 36190 7...

result:

ok correct!

Test #51:

score: 0
Accepted
time: 173ms
memory: 31832kb

input:

50000
4 7593 1614 9605 3123
3 3673 2818 30
2 3293 200
3 6148 3152 5348
6 1284 5233 1818 447 473 8712
4 963 4638 4061 2896
4 3079 6749 1264 9590
1 6966
3 285 8991 6853
3 6009 4660 5257
4 1667 1080 2569 4683
6 8720 9357 1826 4842 6282 1412
3 8047 3801 6251
4 892 7729 691 1327
7 9382 3872 5153 6802 236...

output:

48495
49989 11952 10893 20195 20546 22508 41767 15888 49973 35289 5033 43816 1934 10512 33583 47264 33563 6365 34514 42198 73 49941 49917 1813 18429 48098 28296 6291 13935 15719 17797 20030 21553 4880 25249 27150 42633 4938 6705 23055 27222 27931 42577 43682 3566 3819 8607 9472 14218 19326 25269 296...

result:

ok correct!

Test #52:

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

input:

50000
5 9084 8425 11202 11358 7066
3 5889 618 3445
5 73 8742 13869 14172 9580
3 2723 10630 5226
2 12195 70
6 12891 7338 5390 12082 5651 12757
5 8214 13218 334 3783 10040
5 11050 3018 14446 1828 2438
4 4179 5438 69 4249
5 2570 141 4446 5177 5018
5 10577 1120 3074 8618 8751
4 1847 11695 10989 8132
3 1...

output:

47582
49990 27571 36208 2203 25351 34082 39917 25826 13512 6019 13541 17119 49596 13259 6146 7737 22388 30147 47876 203 2378 4507 9794 11355 19929 46266 47414 49946 6701 1887 27860 49411 22843 258 11653 27066 42308 43634 28781 3001 16224 20849 49941 11432 40848 16416 12980 20250 23391 30259 47368 46...

result:

ok correct!

Test #53:

score: 0
Accepted
time: 166ms
memory: 31076kb

input:

50000
4 347 9390 17911 5940
8 2485 523 15473 602 15622 18596 15924 2713
3 3418 18845 5746
4 17377 16407 15812 16142
4 6843 7050 4642 12056
4 17662 6811 19686 17426
7 4423 2905 17326 6735 12999 17264 18134
4 6381 529 12432 5042
8 4812 8415 2342 436 2646 7294 7391 9015
3 16712 13743 9802
3 19946 19519...

output:

46601
49990 49976 22299 36894 16455 49935 10667 12350 18126 32182 35272 41623 48976 43289 21480 23099 31721 44034 49967 36095 49371 14776 37281 45757 49950 40272 3251 3145 13456 36495 43070 32762 49939 7107 7649 18066 12953 25128 43081 49938 19855 48049 22477 45942 22726 27506 48296 8807 13614 38986...

result:

ok correct!

Test #54:

score: 0
Accepted
time: 182ms
memory: 31480kb

input:

50000
2 13646 8405
2 11353 10469
5 16080 22235 16681 23739 22080
2 12689 19542
4 10243 20288 22506 12090
3 12047 2856 456
2 17457 24668
6 5713 11086 22103 5218 19806 11314
4 11073 11885 13373 8871
5 4885 1937 16779 20998 23320
3 2832 9351 22420
4 9767 21633 22557 3387
4 6274 1841 2801 472
4 15542 11...

output:

45651
49998 36233 42210 36511 12209 27947 45294 48890 8054 201 5555 8119 20734 31529 39469 39771 17998 11968 32307 38424 48669 49991 21571 27562 44815 49331 29190 30605 1706 14259 15000 20271 15953 10857 16904 18281 21506 22782 37190 49973 49953 44680 49935 15011 41221 44158 45705 15980 20588 25367 ...

result:

ok correct!

Test #55:

score: 0
Accepted
time: 56ms
memory: 33516kb

input:

100000
2 95 57
2 94 7
2 81 18
2 29 24
1 15
2 11 1
2 0 59
3 82 83 88
2 24 40
2 90 23
1 8
2 36 57
3 88 7 18
1 64
2 68 28
2 57 13
1 88
1 82
2 71 87
2 99 6
1 15
4 54 45 83 71
3 98 89 100
2 65 93
1 72
3 16 99 45
5 65 36 8 95 68
1 96
1 19
2 25 95
2 12 8
2 5 0
1 70
2 25 94
2 20 85
2 87 4
3 66 21 79
2 65 54...

output:

99999
99798 361 1014 1131 1252 1506 1733 1769 1953 2117 2351 2692 2931 3106 3153 3157 3173 3350 3528 3697 3999 4039 4439 4495 4809 4968 5035 5136 5191 5574 6459 6492 6818 6928 7305 7366 8633 8670 8697 8758 8821 9140 9268 9380 9513 10124 10302 10412 10643 10661 11007 11056 11330 12222 12282 12551 126...

result:

ok correct!

Test #56:

score: 0
Accepted
time: 186ms
memory: 35332kb

input:

100000
1 728
2 570 779
1 204
1 319
1 179
2 168 49
3 553 200 148
3 333 915 526
2 211 399
1 53
1 940
3 472 465 554
1 631
2 607 76
2 895 5
1 717
1 402
1 803
2 248 879
2 316 232
1 790
1 101
3 365 657 458
2 893 540
1 420
2 842 237
3 299 433 84
2 374 380
4 554 823 764 37
3 546 350 602
3 70 493 885
2 896 8...

output:

99977
99873 2659 4550 12861 15208 17065 17417 21883 25477 26410 26840 29439 31090 37857 38893 40590 41410 42805 48116 48190 49414 59720 60782 63383 67533 70245 73363 73801 77399 77527 81526 85042 87125 89043 84974 70 3145 7458 9687 11523 14794 15370 18778 20123 21047 24475 29164 31081 32980 42414 51...

result:

ok correct!

Test #57:

score: 0
Accepted
time: 294ms
memory: 34088kb

input:

100000
3 1673 1760 1959
3 1587 1262 1196
1 1692
2 685 333
1 1266
1 1726
1 150
2 562 455
2 1753 1222
3 94 1828 987
1 1581
1 1122
5 1172 1656 1619 1050 92
3 346 1421 1836
2 1726 315
3 174 1111 1716
2 460 1974
1 545
1 1772
3 397 1146 228
1 862
3 1658 1564 623
1 7
4 578 1344 190 1038
1 699
2 621 292
2 1...

output:

99920
99947 8347 13927 17154 22581 28909 32448 35665 57412 59084 59317 74763 79211 86500 90574 95065 785 18702 21976 38126 51668 51746 58022 58437 59488 60323 69799 93638 58298 7002 7299 15937 30764 32452 41406 53862 56501 57878 72411 76608 78283 82014 83890 84814 85172 90658 93164 93318 90062 732 4...

result:

ok correct!

Test #58:

score: 0
Accepted
time: 367ms
memory: 35180kb

input:

100000
2 552 714
1 3933
4 432 2843 3596 2928
2 3538 1583
2 1030 3587
1 1403
2 485 3658
1 2496
3 1508 368 1426
2 629 704
1 892
2 3519 1658
3 1180 248 550
3 3367 1677 3703
2 3237 1548
4 678 283 3588 2431
1 3497
1 1423
3 1838 1657 935
4 1660 3924 431 1151
4 2507 1607 284 2371
1 2430
2 782 2666
1 3109
3...

output:

99719
99977 928 13238 25604 31315 33642 39233 50999 59821 83206 87722 97429 91690 2042 3794 12767 23994 37465 45789 47243 53069 66155 80065 95137 23004 4620 5667 6193 8603 9602 9867 22375 26621 27391 33856 95413 70089 5055 7918 21280 21765 32378 33523 34372 35272 49931 60078 66218 67657 72990 73455 ...

result:

ok correct!

Test #59:

score: 0
Accepted
time: 391ms
memory: 34124kb

input:

100000
1 2296
3 3934 3474 786
2 5866 5102
2 4440 1792
2 1259 869
2 3023 4842
2 3170 3000
2 413 2099
1 3773
1 4185
2 4726 5597
2 3898 5395
1 4124
1 1832
3 3915 501 4385
1 3790
1 2743
2 592 3352
1 744
1 5392
1 4274
1 4680
2 3719 2854
1 5368
1 4483
1 3742
1 3389
1 5183
1 3906
1 1687
1 2795
3 5557 5988 ...

output:

99411
99979 5304 12364 17035 28440 29065 74205 86585 86821 10401 3000 10539 19296 22629 23346 30995 33976 40868 53608 77062 90908 59389 4124 5787 14319 21896 30816 36410 44215 46693 72162 82527 95574 73272 61 502 18090 32409 32549 45246 45488 53682 58811 60067 63399 67631 78857 82265 82922 87401 924...

result:

ok correct!

Test #60:

score: 0
Accepted
time: 392ms
memory: 34108kb

input:

100000
2 865 6108
1 293
3 4957 7211 1105
2 1737 4288
1 7618
5 3380 6343 4662 3171 900
1 3940
2 7205 2620
2 7834 300
1 5447
1 1760
2 2046 2779
2 4550 509
1 966
1 7574
2 1127 5323
2 3662 2363
1 6609
5 6609 6120 2847 678 2649
2 6709 943
2 5439 3024
2 5502 4555
1 4127
2 1482 1692
4 2284 6117 5244 652
1 ...

output:

99035
99990 39482 56637 80008 70251 2587 3959 8573 38742 76714 87703 91158 99994 28450 9523 12593 18889 33328 51437 74562 82302 89896 33110 3469 6710 11297 65373 65723 85337 71841 3586 13133 17319 19855 23758 24497 56350 95700 7333 21607 30428 35959 61644 71166 96566 94777 336 3911 14833 19985 29331...

result:

ok correct!

Test #61:

score: 0
Accepted
time: 370ms
memory: 36668kb

input:

100000
2 5762 6767
2 8537 2102
2 607 6367
3 7112 7745 6439
4 4620 3044 6364 1337
3 8350 5196 3138
3 6950 1884 9531
2 229 5292
2 1327 2119
1 7918
1 5152
3 72 3285 7124
3 9899 4001 7613
3 4298 1244 4791
1 7457
1 28
5 951 9662 4572 3502 9680
1 2138
2 5651 9154
1 9360
3 1813 6018 9794
3 4245 4824 5268
1...

output:

98540
99983 8537 13350 39133 92588 97115 7996 34467 35830 47637 60387 64944 93844 59623 13227 30877 38296 41116 43115 48168 54424 70492 89169 1003 14295 18737 35496 36374 39487 49542 53992 56171 56672 73703 73774 98714 85473 1837 4674 8186 10449 20268 29450 35387 35393 37356 39916 47022 53734 58132 ...

result:

ok correct!

Test #62:

score: 0
Accepted
time: 371ms
memory: 35140kb

input:

100000
1 11286
1 785
2 2239 7078
2 6616 8372
3 11324 13456 1784
1 7848
3 7628 474 3006
1 13935
3 12019 9631 4317
3 7682 4312 6157
2 11651 529
1 9630
1 13221
2 13870 5539
4 2192 164 14807 4346
5 9155 7210 13841 13429 13449
2 5021 4936
1 8822
2 12434 7739
2 5123 8562
3 1017 13118 9476
2 8039 4817
2 89...

output:

97114
99995 18909 39277 94601 99289 65601 72000 24467 1800 13683 75470 2799 9462 19334 25433 25689 31905 53493 80846 99368 89940 3773 33978 37949 93467 94988 49534 8539 9842 23023 51952 76575 45189 5855 12496 12903 30565 65602 66426 69856 79493 94335 97205 12706 9247 22191 53745 59424 63365 70612 80...

result:

ok correct!

Test #63:

score: 0
Accepted
time: 336ms
memory: 37380kb

input:

100000
1 3339
2 12542 1582
3 11876 1621 19577
3 3136 13480 6209
1 3391
1 15068
1 4363
1 16390
1 2717
2 11036 9644
2 19887 18032
1 17014
4 17213 9715 12377 19774
2 9019 3019
1 11718
3 19104 11059 18186
1 10481
2 13743 5146
4 17640 10057 19995 1096
1 749
3 5711 14461 10198
3 5238 12665 17485
1 4715
2 ...

output:

95363
99990 17611 19115 28819 38763 39881 62222 86300 51558 22868 30571 87362 95231 86055 28270 56007 82603 83188 78263 23580 24921 32308 35066 50800 59818 70519 75457 78396 94074 94921 16655 29805 68239 91633 99981 15254 42450 56405 61907 4114 63663 99967 75464 97996 99923 40775 83616 93248 7101 58...

result:

ok correct!

Test #64:

score: 0
Accepted
time: 362ms
memory: 37276kb

input:

100000
1 22372
2 807 5345
1 1726
1 18351
1 18404
2 18059 21614
4 15502 10174 20082 19736
3 12777 11132 23474
3 21325 14585 6839
5 11249 2371 14077 1481 8214
2 10996 4408
2 12787 13372
2 11639 10240
2 19955 13988
2 18061 7646
2 18513 947
2 3721 5607
1 957
1 2616
1 23054
2 24206 247
2 10037 24755
2 30...

output:

93514
99990 70074 40155 66353 88488 95352 8768 25517 72102 85132 17955 15994 28737 44789 65305 68007 92719 2905 12796 17401 26873 45962 46726 62743 90532 18514 10260 54871 92592 83267 268 1803 42124 57226 78706 83925 98907 38463 3393 30296 32305 33726 41963 60356 62392 46223 14648 21121 23100 35939 ...

result:

ok correct!

Test #65:

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

input:

2
199999 999936325 999932716 999907239 999936208 999842617 999852700 999975976 999934549 999950109 999989471 999836186 999912739 999898154 999941223 999804199 999930540 999981113 999969089 999802349 999906832 999873865 999939686 999927906 999921840 999878431 999866873 999935847 999964030 999950381 9...

output:

1
2 1 

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed