QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746914#8646. Card Collection275307894a71 915ms92920kbC++143.7kb2024-11-14 15:51:222024-11-14 15:51:23

Judging History

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

  • [2024-11-14 15:51:23]
  • 评测
  • 测评结果:71
  • 用时:915ms
  • 内存:92920kb
  • [2024-11-14 15:51:22]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,A[N],B[N],X[N],Y[N];
int flag[N];
struct ST{
	int mx[20][N],mi[20][N];
	void init(int *A){
		copy(A+1,A+n+1,mx[0]+1);copy(A+1,A+n+1,mi[0]+1);
		for(int i=1;(1<<i)<=n;i++){
			for(int j=1;j+(1<<i)-1<=n;j++){
				mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
				mi[i][j]=min(mi[i-1][j],mi[i-1][j+(1<<i-1)]);
			}
		}
	}
	int qrymin(int x,int y){
		int d=__lg(y-x+1);return min(mi[d][x],mi[d][y-(1<<d)+1]);
	}
	int qrymax(int x,int y){
		int d=__lg(y-x+1);return max(mx[d][x],mx[d][y-(1<<d)+1]);
	}
}a,b;
int pa[N],pb[N];
unordered_map<ll,vector<int> > f;
bool qry(int vx,int vy,int *A,int *B){

	auto check3=[&](int x,int y){
		if(x>y) return true;
		return (a.qrymax(x,y)>=vx||b.qrymin(x,y)<=vy)&&(a.qrymin(x,y)<=vx||b.qrymax(x,y)>=vy);
	};
	auto it=f.find(1ll*vx*n+vy);
	if(it!=f.end()){
		for(int i:it->se) if(A[i]==vx&&B[i]==vy&&check3(1,i-1)&&check3(i+1,n)) return true;
	}

	auto check1=[&](int x,int y){
		if(x>y) return true;
		return !(a.qrymax(x,y)<vx&&b.qrymin(x,y)>vy);
	};
	int i1=pa[vx];
	int d1=n+2,lim1;
	for(int i=1;i<=n;i++) if(A[i]>=vx&&B[i]<=vy&&check1(1,i-1)){d1=i;break;}
	lim1=max(i1,d1+1);while(lim1<=n&&!check1(d1+1,lim1)) lim1++;
	
	auto check2=[&](int x,int y){
		if(x>y) return true;
		return !(a.qrymin(x,y)>vx&&b.qrymax(x,y)<vy);
	};
	int i2=pb[vy];
	int d2=-1,lim2;
	for(int i=n;i;i--) if(A[i]<=vx&&B[i]>=vy&&check2(i+1,n)){d2=i;break;}
	lim2=min(i2,d2-1);while(lim2>0&&!check2(lim2,d2-1)) lim2--;

	gdb(d1,d2,lim1,lim2,i1,i2,A[12],B[12],check2(13,n));
	if(d1>=i1&&d2<=i2&&d1+1==d2) return true;
	if(d1>=i1&&d1+1<=lim2) return true;
	if(d2<=i2&&d2-1>=lim1) return true;
	return lim1+1<=lim2;
}
void build(){
	static int na[N],nb[N],dA[N],dB[N];
	copy(A+1,A+n+1,na+1);sort(na+1,na+n+1);
	copy(B+1,B+n+1,nb+1);sort(nb+1,nb+n+1);
	for(int i=1;i<=n;i++) dA[i]=LB(na+1,na+n+1,A[i])-na;
	for(int i=1;i<=n;i++) dB[i]=LB(nb+1,nb+n+1,B[i])-nb;
	for(int i=n;i;i--) pa[dA[i]]=i;for(int i=1;i<=n;i++) pb[dB[i]]=i;	
	a.init(dA);b.init(dB);
	f.clear();
	for(int i=1;i<=n;i++) f[1ll*dA[i]*n+dB[i]].push_back(i);

	for(int i=1;i<=m;i++){
		int nx=LB(na+1,na+n+1,X[i])-na,ny=LB(nb+1,nb+n+1,Y[i])-nb;
		if(na[nx]==X[i]&&nb[ny]==Y[i]) flag[i]|=qry(nx,ny,dA,dB);
	}
}
void Solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]);
	for(int i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]);
	build();
	reverse(A+1,A+n+1);reverse(B+1,B+n+1);
	build();
	for(int i=1;i<=n;i++) A[i]*=-1,B[i]*=-1;
	for(int i=1;i<=m;i++) X[i]*=-1,Y[i]*=-1;
	build();
	reverse(A+1,A+n+1);reverse(B+1,B+n+1);
	build();
	for(int i=1;i<=m;i++) if(flag[i]) printf("%d ",i);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

详细

Subtask #1:

score: 11
Accepted

Test #1:

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

input:

2 10
171631799 561094698
171631799 867698918
126573648 561094698
171631799 867698918
171631799 561094698
126573648 561094698
126573648 561094698
171631799 561094698
126573648 561094698
126573648 561094698
126573648 561094698
171631799 561094698

output:

2 3 6 10 

result:

ok 4 number(s): "2 3 6 10"

Test #2:

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

input:

3 10
713180371 43103927
713180371 136832929
853543805 251852293
892623928 251852293
713180371 136832929
713180371 43103927
853543805 43103927
892623928 136832929
713180371 43103927
853543805 43103927
892623928 136832929
713180371 43103927
892623928 251852293

output:

2 3 6 9 

result:

ok 4 number(s): "2 3 6 9"

Test #3:

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

input:

4 10
254412080 855555783
254412080 534954259
610506813 184822793
804271098 233942602
804271098 233942602
536633825 184822793
254412080 855555783
804271098 233942602
536633825 233942602
254412080 855555783
804271098 534954259
610506813 534954259
536633825 184822793
536633825 855555783

output:

1 3 4 6 7 8 

result:

ok 6 numbers

Test #4:

score: 11
Accepted
time: 3ms
memory: 26460kb

input:

5 10
148547041 170447714
617759855 170447714
617759855 963162312
148547041 948767426
423489361 460053818
423489361 460053818
817714720 948767426
617759855 673099807
617759855 963162312
617759855 673099807
423489361 460053818
423489361 460053818
817714720 948767426
817714720 170447714
148547041 67309...

output:

1 4 6 7 

result:

ok 4 number(s): "1 4 6 7"

Test #5:

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

input:

6 10
452189481 369706489
974106249 369706489
152471743 55874110
152471743 7767562
623180600 783682263
116778263 783682263
974106249 369706489
452189481 7767562
623180600 7767562
116778263 783682263
330861484 7767562
452189481 640079581
974106249 640079581
623180600 783682263
974106249 7767562
116778...

output:

1 4 8 

result:

ok 3 number(s): "1 4 8"

Test #6:

score: 11
Accepted
time: 3ms
memory: 24392kb

input:

7 10
546365360 29458595
459505526 682968936
892069847 113227141
892069847 682968936
459505526 895773339
436538726 29458595
892069847 29458595
892069847 21442381
200908509 682968936
84249914 782064261
691849455 682968936
691849455 682968936
691849455 21442381
691849455 682968936
691849455 21442381
84...

output:


result:

ok 0 number(s): ""

Test #7:

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

input:

8 10
53884460 816621582
931458006 534340303
53884460 621933704
317941616 487589985
53884460 793793344
831491668 487589985
53884460 816621582
53884460 417129074
831491668 417129074
317941616 534340303
395845824 793793344
395845824 417129074
317941616 166559933
100528187 487589985
83144683 816621582
8...

output:

2 10 

result:

ok 2 number(s): "2 10"

Test #8:

score: 11
Accepted
time: 2ms
memory: 26640kb

input:

9 10
703128946 628411749
703128946 876135124
678057110 783023566
563107567 908344997
255577987 177945114
703128946 177945114
519769912 951772210
678057110 470396423
703128946 470396423
563107567 783023566
813952930 470396423
230207898 177945114
230207898 628411749
519769912 555485281
703128946 78302...

output:

1 6 

result:

ok 2 number(s): "1 6"

Test #9:

score: 11
Accepted
time: 2ms
memory: 26536kb

input:

10 10
411828800 587312736
368564282 297078085
368564282 265187364
287645241 405039514
368564282 535066135
368564282 265187364
701629305 581674146
894581821 581674146
600278299 347261251
368564282 390901645
633230417 151902557
287645241 297078085
1782717 405039514
287645241 587312736
894581821 587312...

output:

2 5 7 

result:

ok 3 number(s): "2 5 7"

Test #10:

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

input:

11 10
594865443 637250974
223004376 637250974
785025296 887146590
120666718 887146590
31665956 652873089
594865443 887146590
1682073 112213166
31665956 121276446
785025296 121276446
28305142 652873089
28305142 661968377
1682073 120498688
938018458 887146590
120666718 112213166
28305142 112213166
223...

output:

10 

result:

ok 1 number(s): "10"

Test #11:

score: 11
Accepted
time: 3ms
memory: 30756kb

input:

12 10
39186066 168002748
671722214 32295292
39186066 469855569
442075770 469855569
689698028 968471023
3489285 168002748
671722214 968471023
182809077 689539890
481317320 742954502
265274602 32295292
265274602 26013512
481317320 742954502
976556207 168425358
689698028 32295292
749415058 545907259
24...

output:

10 

result:

ok 1 number(s): "10"

Test #12:

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

input:

13 10
527355089 377970728
552459003 455747923
709625462 510634723
552459003 377970728
731571039 951161417
232811148 951161417
552459003 658700181
232811148 377970728
518940837 455747923
455586174 378372201
219157258 378372201
219157258 377970728
709625462 385691279
455586174 510634723
915002219 1039...

output:

1 4 7 8 10 

result:

ok 5 number(s): "1 4 7 8 10"

Test #13:

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

input:

14 10
118092342 284486250
927338949 433938384
402661724 978896809
647730583 672355271
31848729 951232518
735207774 379785691
647730583 976797409
118092342 976797409
16895438 951232518
266079358 317991591
402661724 759687663
927338949 672355271
384578818 379785691
927338949 675446949
647730583 672355...

output:

1 2 9 

result:

ok 3 number(s): "1 2 9"

Test #14:

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

input:

15 10
180664786 545082798
348151122 545082798
945365791 568927334
87112728 22695274
969050024 993697033
76897725 568927334
946081941 721317554
736012091 124380018
76897725 993697033
969050024 297352406
87112728 22695274
477303819 152140956
497190005 127179215
477303819 957952273
946081941 297352406
...

output:

2 3 

result:

ok 2 number(s): "2 3"

Test #15:

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

input:

16 10
950185079 359470460
717527338 766264034
950185079 464367361
702133494 562464640
47221737 933850433
804214161 68526353
835127535 923127189
663871966 429877028
663871966 933850433
663871966 860592052
717527338 159513156
817202184 970491880
835127535 475614319
519002985 475614319
109565532 137441...

output:

5 9 

result:

ok 2 number(s): "5 9"

Test #16:

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

input:

17 10
785164241 654900960
360828785 824839755
439791874 641288092
577364156 862808499
668131950 862808499
893897612 712643610
893897612 596494049
736363695 306279255
668131950 262689126
141356696 306279255
141356696 559915287
785164241 712643610
785164241 862808499
785164241 91314622
657093012 89959...

output:

1 2 4 7 8 

result:

ok 5 number(s): "1 2 4 7 8"

Test #17:

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

input:

18 10
634436200 539568435
939344787 325688918
488541626 821095697
430879210 182007328
634436200 676635380
863100947 105320937
634436200 259039153
155697449 650750783
863100947 290661066
904360323 275647130
148773803 836392810
155697449 275647130
904360323 325688918
242889289 395936619
863100947 8363...

output:

4 5 8 10 

result:

ok 4 number(s): "4 5 8 10"

Test #18:

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

input:

19 10
643978171 286398879
496772316 971744093
955019965 629209809
874944857 162312003
813096582 680350320
973954693 690315188
387049024 971744093
817521662 629209809
17782710 227578391
308611155 855159132
817521662 286398879
222858816 971744093
222858816 532541541
704414451 629209809
17782710 227578...

output:


result:

ok 0 number(s): ""

Test #19:

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

input:

20 10
339497023 613254335
277080109 869002717
498404000 182716214
838620251 613254335
774235215 599908689
321477480 52537358
406499846 787324761
498404000 867048589
339497023 265303890
653823018 594937507
277080109 856711907
774235215 150629026
339497023 613254335
845764830 867048589
339497023 85671...

output:

5 9 

result:

ok 2 number(s): "5 9"

Test #20:

score: 11
Accepted
time: 3ms
memory: 20364kb

input:

2 1
573537298 133184345
819019960 446972624
573537298 133184345

output:

1 

result:

ok 1 number(s): "1"

Test #21:

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

input:

2 10
215463781 963544789
417194171 381706359
215463781 381706359
417194171 963544789
417194171 381706359
215463781 381706359
215463781 381706359
215463781 381706359
417194171 963544789
215463781 381706359
417194171 963544789
215463781 381706359

output:

1 2 4 5 6 7 8 9 10 

result:

ok 9 numbers

Test #22:

score: 11
Accepted
time: 2ms
memory: 22424kb

input:

2 10
347064832 492954369
276208042 238639351
347064832 492954369
276208042 492954369
347064832 238639351
276208042 492954369
276208042 238639351
276208042 492954369
347064832 492954369
276208042 492954369
347064832 238639351
347064832 492954369

output:

1 5 7 10 

result:

ok 4 number(s): "1 5 7 10"

Test #23:

score: 11
Accepted
time: 2ms
memory: 24620kb

input:

2 10
59424469 214378961
467302957 920237929
467302957 214378961
467302957 920237929
467302957 214378961
467302957 920237929
467302957 214378961
467302957 214378961
467302957 920237929
467302957 214378961
467302957 920237929
467302957 920237929

output:

2 4 7 9 10 

result:

ok 5 number(s): "2 4 7 9 10"

Test #24:

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

input:

3 10
199016579 737474160
269172900 902060853
363682951 999857037
199016579 999857037
363682951 737474160
363682951 737474160
199016579 737474160
363682951 999857037
363682951 902060853
363682951 737474160
199016579 737474160
269172900 902060853
269172900 737474160

output:

4 5 8 9 

result:

ok 4 number(s): "4 5 8 9"

Test #25:

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

input:

3 10
546485825 847511917
181508698 729251744
262746395 577803673
546485825 729251744
546485825 577803673
262746395 847511917
546485825 729251744
546485825 577803673
262746395 577803673
546485825 847511917
262746395 577803673
181508698 847511917
181508698 577803673

output:

6 7 8 10 

result:

ok 4 number(s): "6 7 8 10"

Test #26:

score: 11
Accepted
time: 2ms
memory: 22364kb

input:

3 10
237380807 513263480
564217004 186570115
980960156 646344876
980960156 646344876
237380807 646344876
980960156 646344876
980960156 513263480
980960156 513263480
564217004 513263480
980960156 186570115
237380807 513263480
237380807 513263480
980960156 186570115

output:

1 3 6 8 9 

result:

ok 5 number(s): "1 3 6 8 9"

Test #27:

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

input:

15 10
624534653 795252871
948654092 55283897
925850942 516359844
291755097 717356990
550592491 128816565
821582441 517445939
994534468 342358076
26658991 396148487
649608935 585141111
323180864 608811044
265317796 85810941
124933870 521198693
547685531 600579720
271150336 559571739
242219192 7700636...

output:

1 2 3 4 8 9 

result:

ok 6 numbers

Test #28:

score: 11
Accepted
time: 3ms
memory: 32640kb

input:

16 10
83190470 209266752
880371594 540332431
77621971 311011586
207583928 515840494
210164058 16324657
557379175 66621069
583090455 503874482
155148044 798469757
997210630 599613989
425284838 540392415
814293641 704949575
371097849 755590192
748854182 185159646
764105570 723184963
281807551 22356411...

output:

1 2 3 4 5 6 7 9 10 

result:

ok 9 numbers

Test #29:

score: 11
Accepted
time: 2ms
memory: 28548kb

input:

17 10
335815281 733974183
996064097 204520072
806805395 978835797
278538265 788397455
993251528 550268353
598157139 171152822
752267659 708459589
720836211 683278789
104083774 172399908
396138427 816227937
454892965 632042288
630038886 668199869
907561802 996410213
244931242 610519539
474601248 7303...

output:

1 6 8 

result:

ok 3 number(s): "1 6 8"

Test #30:

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

input:

18 10
461958391 283363776
820708759 240820111
809183522 564946300
274367350 887675067
808876603 652655193
242336368 71989816
35682865 592736787
598975260 11034644
432130229 841406481
617636775 764446022
39223975 938369951
608686441 406829225
979705068 458377101
609019396 321322678
993501055 30534219...

output:

1 2 3 5 6 7 8 9 10 

result:

ok 9 numbers

Test #31:

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

input:

19 10
935306669 629155511
75497873 924414411
568314611 976194131
623493055 355890466
492224421 999834286
553317256 546504008
409428707 857511314
933067983 202850910
458115220 344652086
144924200 447572677
301600067 34784059
519123285 847853731
447663066 411079314
846416609 480411419
22568709 1531818...

output:

1 2 3 4 5 6 7 9 10 

result:

ok 9 numbers

Test #32:

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

input:

20 10
847175920 439365704
473215562 166583238
625362454 43314630
918168962 805367197
669794952 141443774
551725106 388869509
256958552 6665321
795177606 869847992
903617816 725384164
355322010 664242041
828642286 886444867
100880811 648469308
357482546 290363154
804925144 953197840
600535575 1891279...

output:

2 3 4 6 7 8 

result:

ok 6 numbers

Test #33:

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

input:

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

output:

1 2 3 4 7 8 9 10 

result:

ok 8 numbers

Test #34:

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

input:

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

output:

1 2 4 6 8 10 

result:

ok 6 numbers

Test #35:

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

input:

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

output:

1 4 5 6 7 8 9 10 

result:

ok 8 numbers

Test #36:

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

input:

20 10
647485976 833063145
962065068 658413630
729055030 89008090
552814579 367567398
962065068 658413630
57744310 463674984
962065068 658413630
190454651 801934060
57744310 463674984
190454651 801934060
647485976 833063145
962065068 658413630
729055030 89008090
57744310 463674984
57744310 463674984
...

output:

1 4 6 8 9 

result:

ok 5 number(s): "1 4 6 8 9"

Test #37:

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

input:

20 10
7 9
6 10
7 9
8 8
7 9
6 9
6 9
7 9
7 10
6 9
6 10
5 9
7 9
6 9
5 10
6 11
5 11
5 10
6 11
7 9
8 8
8 9
8 10
9 8
7 9
7 10
10 8
10 7
10 6
11 8

output:

2 3 5 6 

result:

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

Test #38:

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

input:

20 10
9 7
10 5
9 5
8 8
10 6
9 6
10 6
10 7
9 5
10 6
11 7
9 6
10 5
11 7
9 6
10 7
11 7
9 7
10 6
10 5
8 8
8 9
8 6
9 8
7 9
7 6
10 8
6 7
10 6
5 8

output:

3 4 7 9 

result:

ok 4 number(s): "3 4 7 9"

Test #39:

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

input:

20 10
5 10
6 9
8 7
6 11
6 11
6 11
6 9
5 11
5 9
6 11
5 10
5 9
6 11
7 11
5 10
7 10
7 11
7 8
5 11
6 9
8 8
8 9
8 10
7 8
9 9
7 10
6 8
6 7
10 10
5 8

output:

2 3 6 7 8 10 

result:

ok 6 numbers

Test #40:

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

input:

20 10
11 7
10 5
8 7
10 7
10 5
10 5
11 7
10 6
9 7
9 7
10 7
11 7
11 7
11 5
11 5
10 7
11 6
7 8
10 7
10 6
8 8
8 9
8 6
7 8
7 7
9 10
6 8
10 7
6 10
11 8

output:

3 5 8 10 

result:

ok 4 number(s): "3 5 8 10"

Test #41:

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

input:

20 10
11 5
9 5
11 5
8 9
9 7
9 7
11 5
11 5
11 6
11 6
9 8
9 6
11 6
11 6
9 7
10 6
9 5
11 5
9 5
10 7
8 8
8 7
8 10
9 8
7 7
9 6
6 8
10 9
6 10
11 8

output:

4 6 8 10 

result:

ok 4 number(s): "4 6 8 10"

Test #42:

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

input:

20 10
7 11
7 11
7 10
6 9
6 10
7 10
6 10
7 11
7 9
7 11
8 9
7 9
5 9
6 10
5 9
7 11
9 8
5 10
5 10
6 10
8 8
8 7
8 6
9 8
7 9
9 10
10 8
6 9
10 10
5 8

output:

5 6 8 10 

result:

ok 4 number(s): "5 6 8 10"

Test #43:

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

input:

20 10
8 7
7 11
6 10
6 9
7 11
5 11
7 11
5 11
6 10
5 9
6 10
7 9
5 9
7 10
7 10
5 10
7 10
6 11
7 8
7 11
8 8
8 7
8 6
9 8
7 9
7 6
10 8
10 7
6 10
11 8

output:

1 5 9 

result:

ok 3 number(s): "1 5 9"

Test #44:

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

input:

20 10
9 8
9 7
11 5
11 6
9 7
9 7
10 6
10 6
10 7
10 7
9 5
11 5
10 6
9 6
10 6
10 5
10 6
11 6
11 5
8 9
8 8
8 9
8 6
9 8
9 7
9 6
6 8
6 9
10 6
5 8

output:

1 3 4 5 6 9 

result:

ok 6 numbers

Test #45:

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

input:

20 10
9 7
10 7
10 5
8 9
9 8
5 11
7 10
5 10
6 10
7 9
6 11
5 11
7 10
6 10
7 10
6 11
6 11
6 11
6 11
7 10
8 8
8 9
8 6
7 8
9 7
9 6
6 8
10 7
6 10
11 8

output:

1 2 4 5 7 8 9 

result:

ok 7 numbers

Subtask #2:

score: 38
Accepted

Dependency #1:

100%
Accepted

Test #46:

score: 38
Accepted
time: 3ms
memory: 47076kb

input:

1500 10
401134743 898594342
739681625 898594342
842492194 569404274
888451796 685104441
945772067 221545383
142276409 691220027
618847410 643831161
16003964 98459610
713370318 64857580
724642432 4634850
273681220 854797105
989430408 833800077
514271483 906536506
13011218 464186337
807512695 78088298...

output:

1 2 6 

result:

ok 3 number(s): "1 2 6"

Test #47:

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

input:

1600 10
933582191 336495008
461620436 186999808
345579872 988069086
49626704 262546280
559588074 252137392
130131997 356874602
657557603 314943383
724926365 743965763
522148738 216365207
821938460 254227453
189386460 336987142
813625232 402587899
320823882 973493831
150859871 634285383
849379382 411...

output:

1 3 4 7 9 10 

result:

ok 6 numbers

Test #48:

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

input:

1700 10
268825522 651445219
372394758 520736010
780878865 355459372
938320730 570235537
837012553 542718246
510360226 969805444
398385643 822868917
504655413 237794042
134892998 792841787
619617894 353138044
984056476 90070486
513541687 20525207
477511733 505399428
761217858 342975394
8421166 573348...

output:

4 7 8 9 

result:

ok 4 number(s): "4 7 8 9"

Test #49:

score: 38
Accepted
time: 6ms
memory: 53300kb

input:

1800 10
642029300 233564193
976887706 478822967
206490042 850155848
830711038 257938544
509981940 859622254
559517681 797058592
776971561 648160301
904506037 357109149
863152696 712844141
260274145 737977711
573464951 212703203
859270067 289430998
743922492 723209573
970279967 301446178
153687709 50...

output:

1 5 9 10 

result:

ok 4 number(s): "1 5 9 10"

Test #50:

score: 38
Accepted
time: 4ms
memory: 51264kb

input:

1900 10
825602635 52650151
866650293 727151834
49970867 108190581
13700700 44510906
523083830 529933163
26634435 443037805
884549435 226492038
801694700 765008610
268700778 649920259
695492705 106305760
811980644 153846947
286037407 173408838
300631179 615831679
287137514 534905521
866650293 5843593...

output:

2 4 7 9 10 

result:

ok 5 number(s): "2 4 7 9 10"

Test #51:

score: 38
Accepted
time: 4ms
memory: 47196kb

input:

2000 10
239583537 194327848
337276200 579167831
992971115 457681310
58153709 766984625
550429831 187200521
996697473 470499583
155778433 438120690
533747714 200223673
975344767 298446236
103906926 242700826
249895157 548765582
722315242 109127349
344697959 235943941
28562418 62676666
162165971 67455...

output:

1 2 5 6 7 8 

result:

ok 6 numbers

Test #52:

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

input:

1800 10
387536330 209721826
390894731 521823087
809287255 680079590
32777165 904875615
254122498 871233040
607735338 185518803
671331222 237888347
339733785 626965936
307580555 777288206
939253725 633227531
683074471 462711578
774046201 219351683
236081441 60275595
316485055 244506122
294823876 1030...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #53:

score: 38
Accepted
time: 4ms
memory: 51380kb

input:

1900 10
911052008 447447389
841021022 634688035
944651890 258709859
891462897 212006838
320199172 642400574
964244188 78652971
19662495 819526836
376348174 126274974
434815998 403531920
125513839 480582509
749811755 103403256
602271080 529686970
837439174 859905304
492206478 615500105
263102272 9536...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #54:

score: 38
Accepted
time: 6ms
memory: 49212kb

input:

2000 10
291372897 886276819
365700003 411818987
812168540 840073013
236393171 345978194
962726876 937608906
16160423 876553748
397527240 504410188
60792581 194840261
200753455 379090975
19569269 769967083
234055148 695874581
365844083 551392738
8092323 814228473
820199547 603797811
431679259 2125871...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #55:

score: 38
Accepted
time: 6ms
memory: 51160kb

input:

1800 10
9392404 27366426
14926966 25464186
8220166 18925563
29861131 19353882
13199167 13488760
19078396 8799243
15151232 25337562
15308250 18800050
12606562 24228468
19522150 1455491
9802828 12238344
19078396 19401726
30505419 3500873
139870 3500873
29212036 3500873
22961661 15860516
13199167 19950...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #56:

score: 38
Accepted
time: 3ms
memory: 51364kb

input:

1900 10
11069544 28569259
8395730 30739947
6275579 11245309
9881932 24855559
1072682 26048411
9881932 8957646
14426606 20337971
4231078 29477784
12042125 4479426
1254044 2734368
18676525 25238150
11710597 27500225
2719991 17677835
5034634 19105854
13403700 5019656
11640220 15622836
8609815 10486774
...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #57:

score: 38
Accepted
time: 3ms
memory: 53212kb

input:

2000 10
29396400 19629084
18481165 12429158
8289863 27196133
5829188 26716056
13537663 779169
27259859 23223525
30086089 24980633
30048604 29006956
8880221 29267180
16216915 23673507
186517 12871012
18761618 21367329
24774599 14882865
4041254 21367329
27064670 14882865
5829188 15480518
8289863 30607...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #58:

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

input:

2000 10
937 193
730 1452
657 76
404 974
1919 1798
1605 1922
99 703
1578 1678
1912 1104
584 1587
1043 1296
831 583
375 562
690 1989
1565 502
693 1199
1243 1079
34 982
437 36
1479 1334
859 1011
1299 672
316 1022
1330 837
627 1068
268 1055
1118 345
346 1968
1574 1138
7 1089
641 362
417 381
1256 1155
19...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #59:

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

input:

2000 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 5...

output:

1 2 4 6 8 10 

result:

ok 6 numbers

Test #60:

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

input:

2000 10
1 2000
2 1999
3 1998
4 1997
5 1996
6 1995
7 1994
8 1993
9 1992
10 1991
11 1990
12 1989
13 1988
14 1987
15 1986
16 1985
17 1984
18 1983
19 1982
20 1981
21 1980
22 1979
23 1978
24 1977
25 1976
26 1975
27 1974
28 1973
29 1972
30 1971
31 1970
32 1969
33 1968
34 1967
35 1966
36 1965
37 1964
38 19...

output:

1 4 5 6 7 8 9 10 

result:

ok 8 numbers

Test #61:

score: 38
Accepted
time: 4ms
memory: 49220kb

input:

2000 10
591792934 616105615
752818974 143716789
293153789 672666291
591792934 616105615
148779494 570184902
499291018 343041370
752818974 143716789
148779494 570184902
379319777 549323017
293153789 672666291
156511112 814161446
499291018 343041370
752818974 143716789
293153789 672666291
499291018 34...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #62:

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

input:

2000 10
6 10
5 9
7 9
6 11
6 9
7 10
6 10
6 11
6 10
7 9
5 10
6 9
7 10
7 10
7 9
7 10
6 11
6 10
5 9
7 10
7 9
6 10
5 10
6 11
7 11
6 11
6 10
7 11
6 9
6 11
7 11
6 11
5 9
6 10
5 10
7 11
6 9
6 9
6 9
6 9
6 9
5 9
6 11
5 10
7 9
7 9
5 10
6 11
7 11
6 10
6 9
5 10
6 10
5 11
7 11
6 9
6 9
7 11
7 11
6 11
5 10
7 9
6 11...

output:

7 8 10 

result:

ok 3 number(s): "7 8 10"

Test #63:

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

input:

2000 10
10 5
9 6
10 7
9 6
10 7
9 5
11 5
10 6
11 7
11 6
11 7
11 6
10 7
9 7
9 6
11 5
10 6
10 6
11 7
9 5
9 6
10 7
10 5
9 6
11 6
11 7
11 6
9 6
11 7
10 7
10 6
9 7
10 6
9 7
10 6
10 6
10 5
10 6
9 7
10 5
9 7
9 5
10 6
10 7
9 5
11 6
9 6
11 7
9 5
11 5
10 5
9 6
9 7
9 6
10 7
10 5
9 6
11 6
9 5
9 7
10 6
9 6
10 7
9...

output:

2 3 4 7 8 

result:

ok 5 number(s): "2 3 4 7 8"

Test #64:

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

input:

2000 10
7 9
6 9
5 11
7 11
7 11
7 9
6 9
7 11
5 10
6 10
6 10
5 10
6 9
7 9
5 9
5 9
7 10
5 9
5 11
5 11
7 11
6 10
6 9
7 11
6 11
5 9
6 9
7 10
5 10
6 11
6 11
6 11
7 11
7 9
6 10
5 11
7 9
6 9
7 9
6 10
5 9
5 10
6 9
7 10
7 11
7 10
5 9
5 9
7 9
7 9
7 11
6 10
5 9
7 10
7 9
6 10
7 9
6 11
7 10
5 10
5 11
5 10
5 11
7 ...

output:

2 4 5 6 7 8 10 

result:

ok 7 numbers

Test #65:

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

input:

2000 10
10 7
10 5
11 7
9 6
10 6
9 6
11 6
10 6
11 7
9 5
10 6
10 7
11 6
10 7
9 7
11 6
10 7
10 6
10 7
10 6
11 6
11 6
10 7
10 6
9 6
10 7
10 5
11 7
11 7
10 5
10 7
10 7
10 7
11 5
11 6
9 5
11 6
9 7
9 5
9 7
10 7
9 6
10 5
11 7
9 5
9 5
11 5
9 5
9 6
11 7
10 5
11 6
11 6
9 5
9 7
11 6
11 7
9 6
11 5
10 6
9 7
10 7
...

output:

3 5 6 9 

result:

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

Test #66:

score: 38
Accepted
time: 2ms
memory: 51052kb

input:

2000 10
10 7
10 7
9 6
11 7
11 5
9 5
10 5
9 6
9 7
9 5
9 6
10 7
11 5
11 6
11 6
10 5
11 5
9 5
9 5
10 7
9 5
10 7
10 7
11 6
9 5
11 5
10 6
11 5
10 5
11 6
11 6
11 5
11 6
11 5
11 6
11 7
10 5
9 5
10 5
10 6
11 6
10 6
11 5
9 7
9 5
11 7
9 5
9 6
9 5
9 7
10 7
11 5
10 5
10 6
9 7
9 5
11 6
9 7
9 5
11 6
9 5
11 7
9 5
...

output:

2 5 

result:

ok 2 number(s): "2 5"

Test #67:

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

input:

2000 10
6 11
5 9
6 10
6 9
6 9
7 9
7 10
7 11
6 11
6 11
7 11
7 10
5 9
7 10
6 11
6 11
6 9
6 10
6 10
5 9
7 11
6 9
6 11
6 9
6 10
5 9
7 10
5 11
5 11
7 10
6 10
5 10
5 11
5 9
7 11
6 10
7 10
7 10
7 11
7 10
7 9
7 9
5 9
5 11
7 9
5 11
5 11
6 9
7 10
5 10
5 11
5 11
6 9
6 10
7 10
7 9
7 11
7 11
5 11
6 11
6 10
5 10
...

output:

7 9 10 

result:

ok 3 number(s): "7 9 10"

Test #68:

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

input:

2000 10
8 7
7 9
6 11
6 10
5 9
7 11
7 9
6 9
6 11
5 10
7 11
6 11
7 9
7 11
5 9
5 10
7 11
6 10
7 9
5 10
5 9
6 11
6 10
7 10
7 9
5 9
5 9
7 10
7 9
6 11
7 9
7 11
6 10
6 11
6 9
6 9
5 9
7 11
7 11
7 10
7 9
7 9
7 11
7 9
5 11
6 10
5 11
6 11
7 9
7 10
5 10
6 9
6 11
5 10
6 9
5 10
7 11
7 11
6 10
7 11
6 9
6 11
5 11
5...

output:

1 3 5 8 9 10 

result:

ok 6 numbers

Test #69:

score: 38
Accepted
time: 4ms
memory: 51064kb

input:

2000 10
9 8
11 7
10 7
9 7
9 7
9 7
10 6
9 7
9 7
9 5
11 6
9 5
11 5
11 6
11 5
10 7
11 7
9 7
10 5
11 6
11 6
9 7
11 6
11 7
11 5
11 7
11 5
11 7
11 6
11 5
10 7
10 7
9 6
9 7
9 6
10 5
10 5
9 6
10 5
11 7
9 7
10 6
10 7
9 5
9 7
11 7
11 6
11 5
10 6
10 6
11 7
10 5
9 6
11 6
10 6
11 5
9 6
10 7
11 6
10 5
11 5
9 7
11...

output:

1 3 4 

result:

ok 3 number(s): "1 3 4"

Test #70:

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

input:

2000 10
9 7
11 5
9 6
10 7
10 7
11 6
11 7
9 6
9 5
9 7
10 7
11 5
10 5
11 6
9 7
10 5
9 5
10 7
10 6
11 6
11 5
11 6
11 6
9 5
10 6
10 5
10 6
10 6
9 6
10 5
11 5
11 5
9 5
11 5
10 6
10 7
10 6
9 6
10 7
9 6
9 6
11 6
10 6
9 6
9 7
11 6
9 6
9 7
11 6
11 6
11 5
10 6
10 6
9 7
10 6
9 5
11 7
9 6
10 6
10 5
10 7
9 6
11 ...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Subtask #3:

score: 22
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #71:

score: 22
Accepted
time: 302ms
memory: 85008kb

input:

150000 10
429397615 196539042
253788191 786385159
144814364 368410247
539186750 28998265
709395946 451949901
747504119 217288628
144253456 723931313
409006764 432647953
437137800 953770352
820178730 437810411
764271627 211460452
398777508 23054037
786701950 571743764
647382230 691039687
581509166 87...

output:

1 2 4 5 6 

result:

ok 5 number(s): "1 2 4 5 6"

Test #72:

score: 22
Accepted
time: 325ms
memory: 87940kb

input:

160000 10
815907773 688556533
328193051 354132109
827858861 377690093
606686130 166700159
105782643 296723364
433067299 766816876
46328628 653442171
95893505 135770019
864026570 20065385
812537395 24412688
893123904 281579324
858556559 31052476
15758169 945446076
737774519 827098173
672856895 755779...

output:

1 3 4 9 

result:

ok 4 number(s): "1 3 4 9"

Test #73:

score: 22
Accepted
time: 355ms
memory: 86756kb

input:

170000 10
577425468 532104445
393636494 54188066
944175537 931626116
946999048 218816681
83619102 387111374
42324322 407586148
286432180 910853680
836807251 263763936
380037161 913210452
622601268 881378296
180483719 757146083
768794144 33646285
859035020 847983937
833796622 857876972
174059290 2930...

output:

1 4 5 7 

result:

ok 4 number(s): "1 4 5 7"

Test #74:

score: 22
Accepted
time: 385ms
memory: 91916kb

input:

180000 10
475449178 536652311
13236240 927707504
352850653 574131835
733963494 218296379
992484526 74251001
36304702 874096048
207551492 981866035
133384436 478757128
332470246 680778451
111277156 613511114
671188149 146249372
459270983 109741174
401668496 248862246
822586685 814830370
710626076 304...

output:

4 9 

result:

ok 2 number(s): "4 9"

Test #75:

score: 22
Accepted
time: 401ms
memory: 91908kb

input:

190000 10
830905815 44014497
421588331 448655984
533648186 992504321
277350365 72896812
734292348 301183805
560049292 932174014
282759917 410938145
903972142 807487397
488314688 348056158
929887890 209513806
635536089 721199099
153995028 837135944
96379496 728688258
856027422 701370764
396696237 476...

output:

1 3 5 8 9 10 

result:

ok 6 numbers

Test #76:

score: 22
Accepted
time: 427ms
memory: 92752kb

input:

200000 10
241073146 208017712
268082755 540439555
217348135 258620577
76808365 937382350
405035548 767085695
331041252 254573432
152417600 436471572
210176530 134663636
886530614 788137616
528726989 884899837
80450105 299587307
253775314 803874611
627205073 704819192
945659901 670074798
815883219 69...

output:

6 8 

result:

ok 2 number(s): "6 8"

Test #77:

score: 22
Accepted
time: 371ms
memory: 91192kb

input:

180000 10
727989653 693467729
763471589 972775031
404642863 195502920
810050715 611503869
518494613 166944605
646043942 398513248
361266603 627686995
947613903 727998298
949309802 930401045
120355149 367012634
175865210 547751861
658054774 937406637
638824696 395864703
158770562 855345550
695024337 ...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #78:

score: 22
Accepted
time: 407ms
memory: 91908kb

input:

190000 10
233033058 540777749
768510667 517425682
362893106 706416233
158565149 374356967
718320676 778931970
339908 879450446
935893133 136134412
696733657 427326241
669405898 915436694
347204950 375776784
1815820 168596578
780543211 293599992
415341105 939673703
364677928 811197595
48951703 932447...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #79:

score: 22
Accepted
time: 428ms
memory: 92916kb

input:

200000 10
498879289 466255565
875371002 149246931
553841836 548734993
136206384 934412381
34826056 322444571
788740476 494405939
183017696 990153853
207494663 511777783
572053681 440922722
698927938 146928337
869671213 555066746
820270918 577959395
60907566 579849474
489408308 255272842
485146461 32...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #80:

score: 22
Accepted
time: 331ms
memory: 82124kb

input:

180000 10
2477044 994331
2038800 1994212
2280830 479535
474762 1407636
467952 1695532
1223614 2024015
864038 1847045
1755882 2006894
863122 852036
362566 1997713
1517745 413857
2323569 1701979
1354801 955627
1468185 2246010
203170 1034918
1695039 156305
1281639 2168943
445778 1449803
1179794 763923
...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #81:

score: 22
Accepted
time: 346ms
memory: 84828kb

input:

190000 10
2093815 185418
660014 10234
448501 1617838
1696567 324278
369451 1377312
1696567 2013412
369409 442854
930226 686558
1637438 645788
2019600 2210347
2121483 1826538
332659 1324453
1749341 1836431
8204 1459842
8690 558818
1696691 1675261
615602 760824
77306 2200787
1470121 139070
2101080 441...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #82:

score: 22
Accepted
time: 362ms
memory: 85552kb

input:

200000 10
2319433 511179
595920 525574
1687127 1521152
2378746 87014
1318855 1135756
1079319 249872
930170 2269205
214789 1538313
292194 1297763
536974 590539
405021 1733070
1332087 2053177
715059 2178057
1828519 2053177
2165762 861980
704124 1980513
1732214 926871
2312406 861980
169406 949288
50308...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #83:

score: 22
Accepted
time: 418ms
memory: 92736kb

input:

200000 10
140090 60947
194178 91826
69049 83912
13519 101086
46062 14454
134926 180499
56113 86844
199883 95212
160298 108285
198533 46105
173152 65313
22780 71012
131980 150830
6189 181689
144397 61361
68366 155549
10128 122321
149224 98667
196727 120722
50469 101558
110508 25907
141343 74610
14020...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #84:

score: 22
Accepted
time: 173ms
memory: 92876kb

input:

200000 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52...

output:

1 2 4 6 8 10 

result:

ok 6 numbers

Test #85:

score: 22
Accepted
time: 189ms
memory: 92820kb

input:

200000 10
1 200000
2 199999
3 199998
4 199997
5 199996
6 199995
7 199994
8 199993
9 199992
10 199991
11 199990
12 199989
13 199988
14 199987
15 199986
16 199985
17 199984
18 199983
19 199982
20 199981
21 199980
22 199979
23 199978
24 199977
25 199976
26 199975
27 199974
28 199973
29 199972
30 199971...

output:

1 4 5 6 7 8 9 10 

result:

ok 8 numbers

Test #86:

score: 22
Accepted
time: 145ms
memory: 75544kb

input:

200000 10
38693490 592863320
116437328 728326914
349472146 186110376
122626131 196584755
122626131 196584755
940356736 53742497
672585370 493027203
116437328 728326914
122626131 196584755
774943154 667172326
199331396 378136030
38693490 592863320
767639780 322322842
116437328 728326914
122626131 196...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Test #87:

score: 22
Accepted
time: 122ms
memory: 75560kb

input:

200000 10
7 9
6 10
5 9
6 10
6 10
6 10
7 9
6 10
6 11
5 10
5 10
6 11
5 11
7 11
7 11
7 9
6 10
6 9
5 10
5 10
5 9
7 11
6 10
6 10
6 11
5 9
6 9
6 11
5 9
6 11
5 10
6 9
6 11
6 11
5 10
6 10
6 9
5 9
7 11
7 11
7 10
5 10
6 10
7 11
6 10
5 9
5 10
5 10
7 11
6 9
6 9
5 11
5 10
7 9
6 9
5 11
5 9
7 10
5 10
5 10
6 9
7 11...

output:

2 4 6 7 8 10 

result:

ok 6 numbers

Test #88:

score: 22
Accepted
time: 113ms
memory: 74972kb

input:

200000 10
9 6
11 6
10 5
9 7
11 6
10 7
11 6
10 5
10 6
11 7
9 7
9 5
10 5
10 5
11 7
10 7
9 6
10 5
11 7
9 7
10 6
9 6
9 7
11 7
9 6
9 7
10 7
9 5
11 7
10 5
10 5
10 6
9 5
11 6
11 6
10 6
10 7
10 5
9 7
9 6
10 6
10 7
9 5
9 7
10 5
11 6
9 7
11 7
10 7
11 5
10 5
9 6
11 5
10 6
11 7
9 6
10 7
10 5
9 6
9 5
11 5
10 5
1...

output:


result:

ok 0 number(s): ""

Test #89:

score: 22
Accepted
time: 125ms
memory: 74336kb

input:

200000 10
7 11
6 11
7 9
7 9
6 9
5 9
7 11
7 10
5 11
7 11
7 9
7 10
7 10
7 11
6 9
6 11
5 11
5 10
7 9
7 10
7 9
7 9
5 11
7 9
5 9
7 9
6 11
6 11
6 11
6 9
7 11
7 11
7 9
6 11
6 10
6 11
6 10
5 9
7 11
6 10
7 9
6 10
6 10
7 9
5 9
6 10
6 10
5 11
5 10
7 11
5 11
6 11
5 10
6 9
7 9
6 9
6 11
6 9
7 11
7 10
6 10
7 10
5 ...

output:

3 4 6 

result:

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

Test #90:

score: 22
Accepted
time: 120ms
memory: 74520kb

input:

200000 10
11 5
11 6
11 6
10 5
10 7
9 6
9 6
9 7
11 5
9 6
11 5
10 7
9 7
11 6
9 7
9 6
11 5
11 7
11 6
9 6
10 7
11 7
11 5
11 7
11 7
10 7
11 5
9 7
11 6
9 6
10 7
9 6
10 7
9 7
9 7
9 5
11 7
10 5
10 7
10 5
10 7
11 7
9 7
10 7
11 6
11 6
9 6
10 6
11 6
9 7
10 6
10 5
11 5
10 5
10 5
10 5
9 6
10 5
9 5
9 5
11 7
11 7
...

output:

3 5 7 

result:

ok 3 number(s): "3 5 7"

Test #91:

score: 22
Accepted
time: 127ms
memory: 74540kb

input:

200000 10
10 7
10 6
9 7
9 6
11 6
9 5
9 7
9 6
11 7
11 7
11 7
10 5
10 6
11 7
9 7
11 7
10 6
9 7
11 6
10 5
10 5
9 6
11 7
9 7
9 5
10 6
10 7
9 6
11 7
10 7
9 7
10 5
9 7
11 6
11 6
9 7
10 7
11 6
11 7
11 6
10 5
10 6
10 7
10 5
10 7
9 7
10 7
9 5
11 6
11 7
9 7
9 5
11 6
9 7
11 7
9 6
9 6
11 5
9 7
9 5
11 7
9 5
9 6
...

output:

2 3 4 7 8 

result:

ok 5 number(s): "2 3 4 7 8"

Test #92:

score: 22
Accepted
time: 129ms
memory: 74396kb

input:

200000 10
7 9
7 11
5 9
7 9
6 9
6 9
6 11
7 10
7 10
5 11
5 11
7 9
5 9
6 10
7 9
6 10
6 10
5 10
6 10
7 10
7 11
5 9
5 10
5 9
5 10
7 10
6 11
6 9
7 9
6 9
7 11
7 10
5 11
7 9
5 11
6 11
6 9
5 11
5 10
6 11
6 10
7 11
5 10
6 11
6 11
7 10
7 11
7 9
5 9
7 10
7 11
6 10
7 9
5 10
7 11
6 9
5 11
6 9
7 10
5 11
7 10
6 10
...

output:

3 4 7 10 

result:

ok 4 number(s): "3 4 7 10"

Test #93:

score: 22
Accepted
time: 135ms
memory: 74280kb

input:

200000 10
8 7
6 11
6 9
5 9
5 9
7 10
7 11
5 10
6 11
5 9
6 11
5 9
7 11
5 11
5 10
7 9
6 9
7 9
7 9
7 9
7 9
5 9
7 9
5 9
7 10
6 9
7 9
5 10
7 10
7 11
5 10
6 10
5 10
6 10
7 10
5 10
7 10
6 9
7 10
7 11
5 10
6 10
7 10
7 10
7 10
6 11
6 9
6 9
5 10
5 10
5 11
5 11
6 9
6 10
6 11
5 9
5 10
5 11
7 10
5 11
5 11
7 9
7 9...

output:

1 5 7 9 10 

result:

ok 5 number(s): "1 5 7 9 10"

Test #94:

score: 22
Accepted
time: 117ms
memory: 75544kb

input:

200000 10
9 8
10 7
11 6
10 5
11 5
9 7
11 7
9 6
9 6
11 6
11 5
11 6
11 6
10 7
11 7
11 5
10 6
11 6
9 5
9 7
11 7
10 7
10 7
9 5
10 7
9 5
11 5
11 6
9 6
9 5
9 5
10 7
9 7
11 5
9 6
9 6
9 5
9 6
9 7
11 6
11 6
10 6
9 6
11 7
11 5
11 6
11 5
10 6
11 6
10 7
9 7
11 6
9 5
11 5
11 5
11 6
9 6
11 7
11 6
10 6
11 7
11 5
1...

output:

1 2 5 8 10 

result:

ok 5 number(s): "1 2 5 8 10"

Test #95:

score: 22
Accepted
time: 126ms
memory: 74656kb

input:

200000 10
10 5
9 5
11 7
9 7
11 5
11 7
10 7
10 7
9 5
9 6
11 6
11 5
10 5
9 5
10 7
10 7
11 5
9 5
10 7
11 7
11 6
10 5
10 7
9 6
9 6
10 5
9 6
9 6
11 5
11 5
9 7
11 7
11 5
11 6
9 5
10 7
9 5
9 6
10 7
11 5
9 6
9 7
11 7
11 5
11 6
9 7
9 7
11 6
9 7
11 7
9 7
9 5
10 5
9 6
11 5
11 6
9 5
9 7
9 6
10 7
11 6
9 5
11 6
1...

output:

1 2 3 4 5 6 7 8 9 10 

result:

ok 10 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #96:

score: 29
Accepted
time: 609ms
memory: 86496kb

input:

150000 200000
554840280 450180271
129755190 936539702
636029974 100931595
347482033 941182758
424159440 989863886
696730935 668647576
963026851 795393731
584491123 313196560
272517468 169799915
695813985 399916082
208857226 922765084
533199689 430981114
166699253 374247795
578418513 419435154
294227...

output:

5 8 9 12 15 16 17 19 20 21 22 23 25 26 27 32 33 40 43 46 47 48 50 51 52 55 61 63 66 70 72 76 79 82 83 85 86 88 91 94 95 97 98 99 102 103 109 111 114 115 118 119 125 126 127 130 132 138 142 144 147 148 149 150 154 156 157 158 160 162 164 166 167 171 176 179 180 181 185 187 189 192 194 196 200 209 211...

result:

ok 80181 numbers

Test #97:

score: 29
Accepted
time: 625ms
memory: 87436kb

input:

160000 200000
964840689 890753281
28316914 630883814
522451989 871899608
147921988 415914644
84486619 796686598
432858799 754790681
255645216 438676341
970549535 928815871
603919592 610653655
597931265 410394132
802945872 291781420
343730460 768366788
726574223 921938712
295943849 562181199
16490787...

output:

1 2 4 5 12 13 17 19 23 28 35 36 37 38 39 41 47 48 55 57 63 64 67 69 73 74 75 76 77 78 83 84 86 87 94 95 99 100 101 102 104 105 107 110 119 121 125 126 130 131 132 139 140 143 150 155 156 157 161 162 164 168 169 170 173 176 177 182 184 185 187 188 190 196 198 199 200 201 202 206 210 211 213 216 224 2...

result:

ok 79953 numbers

Test #98:

score: 29
Accepted
time: 608ms
memory: 88948kb

input:

170000 200000
350061411 338756662
174393043 463310349
308708027 113337455
894989479 530862424
571052926 471872475
1354742 490057071
709901823 821816883
454860980 400426503
344089837 713612263
927373930 505959529
351923669 999161852
258127224 592159637
19031106 512430211
737965619 277517786
144266339...

output:

2 5 7 8 9 11 14 15 16 17 18 21 25 26 27 33 34 35 38 39 40 44 47 49 50 53 55 58 59 61 63 64 65 69 70 71 74 76 78 79 80 81 82 83 85 89 90 95 97 99 100 104 106 112 113 114 115 116 119 120 122 124 126 128 131 132 134 142 147 149 150 151 152 155 157 160 164 165 168 171 172 174 175 177 180 183 186 188 190...

result:

ok 79521 numbers

Test #99:

score: 29
Accepted
time: 688ms
memory: 91648kb

input:

180000 200000
875233799 499154419
972804050 290613340
792919392 304353712
553321687 600710811
983836536 822296197
671773344 192874307
983638205 457051611
491811123 109956990
226306259 795272169
897569919 609275644
13896724 252275363
718205786 557657489
755589814 377967362
939165761 947994416
9928179...

output:

3 6 8 10 15 17 18 20 26 29 33 35 37 43 45 47 50 51 54 55 57 59 60 61 62 67 68 71 75 77 78 84 86 90 91 94 96 98 102 104 106 107 108 109 112 116 117 118 121 123 124 125 130 131 132 134 138 139 140 146 148 150 152 156 159 160 162 164 165 166 169 171 173 176 178 180 182 183 184 186 187 188 189 190 191 1...

result:

ok 79510 numbers

Test #100:

score: 29
Accepted
time: 662ms
memory: 91848kb

input:

190000 200000
917780169 337976184
377059645 574122000
571339970 247074015
592346314 719513000
1341479 285704240
90474409 826677871
775123160 325719776
446074818 477133510
575775843 280043143
726369091 468708661
143152658 587048680
392058297 840967330
29965745 544923386
9159246 31162616
746362267 983...

output:

4 10 13 14 17 18 23 26 29 32 34 39 42 43 44 45 50 51 52 53 54 56 61 64 67 69 70 71 72 74 80 83 85 88 91 94 95 97 98 100 109 111 113 118 126 127 130 135 141 142 143 145 148 150 152 153 154 156 157 162 163 171 173 176 177 180 181 182 184 186 191 195 198 200 205 207 208 209 210 211 213 214 217 218 219 ...

result:

ok 79654 numbers

Test #101:

score: 29
Accepted
time: 694ms
memory: 92716kb

input:

200000 200000
207195955 162377530
972394896 167558257
770815185 73410472
227526784 948293116
117434463 324106529
505671534 182003692
724337591 782151916
684152386 10834894
754253529 403170449
902049520 637178731
854546342 812285084
518272205 837853391
462104188 715290933
131116914 835654250
29911181...

output:

2 4 6 8 12 13 14 15 16 19 21 23 27 29 30 32 34 40 49 55 57 58 61 63 65 66 67 69 74 75 76 77 78 79 81 84 88 89 93 96 97 98 105 106 107 109 110 111 118 120 121 122 124 125 127 128 130 135 136 142 143 145 147 151 152 155 156 159 162 165 169 170 173 174 177 180 181 183 185 186 189 196 197 198 201 206 20...

result:

ok 80117 numbers

Test #102:

score: 29
Accepted
time: 823ms
memory: 91796kb

input:

180000 200000
682897139 358054774
684771011 142168053
405832352 901800509
160344235 716611251
987824028 38612710
751635697 93033988
282943203 775574016
792971142 186751384
264439580 717766103
94282689 554052633
916308401 886689138
523240726 972537810
747214916 525225675
387991157 750385122
360192471...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199979 numbers

Test #103:

score: 29
Accepted
time: 827ms
memory: 91928kb

input:

190000 200000
268005404 170850831
948931227 544405132
185276179 60341282
949553143 646951442
950072109 440344719
455928326 155833918
633682979 60660744
52084126 340784020
404501591 150882430
61943857 497380285
758132714 869365538
759145712 925684338
927126715 630268607
580777182 774126488
359162748 ...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199972 numbers

Test #104:

score: 29
Accepted
time: 915ms
memory: 92920kb

input:

200000 200000
745783133 407431967
417064914 906296581
819201570 475896545
593514802 696179975
509402546 312075966
755342400 801503044
21065172 198617456
560678716 397844051
855246813 102096144
597481677 182730027
430597246 749002215
733675601 937821633
704417532 878516168
459571150 534310290
4249108...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199978 numbers

Test #105:

score: 29
Accepted
time: 642ms
memory: 84180kb

input:

180000 200000
1582785 985427
2054914 2221684
2038650 2359431
1146235 1043733
2153806 297663
306761 577964
2081704 2249295
1112397 1994248
284798 66713
1563787 460788
809908 1057520
1178278 1343460
1802724 353868
1580055 1727595
563565 702045
3913 1578762
1430890 1620740
1660237 1508702
671840 461821...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 200000 numbers

Test #106:

score: 29
Accepted
time: 643ms
memory: 85208kb

input:

190000 200000
547267 1255728
33298 2250962
1991659 1348780
33298 490075
1522153 587997
1978445 1679557
864776 880450
2187386 2225454
717316 1751971
2072263 1574429
942355 655620
1573348 929405
1626153 1199363
87630 621894
121152 1622209
1166279 1202377
1944544 1724524
1271385 152637
1759941 2094081
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199997 numbers

Test #107:

score: 29
Accepted
time: 691ms
memory: 83692kb

input:

200000 200000
1182321 1022445
1899018 1163780
767294 2238821
586232 2036174
2095246 1778759
877592 476275
406003 2014284
913923 1977317
1038989 1510060
1691991 591019
1936598 1905117
1066507 163244
14611 103525
621156 522915
766116 166996
110270 768697
1492892 1247415
658514 1163216
584903 1829579
3...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199999 numbers

Test #108:

score: 29
Accepted
time: 806ms
memory: 92708kb

input:

200000 200000
52274 130656
91938 187848
146519 187513
2775 30215
119453 144745
188029 115046
167165 196661
190442 78787
143923 176153
2306 151544
177848 43243
179425 7091
54855 128487
84645 175845
9072 8701
128557 169685
193752 171369
163409 140825
175395 71058
167744 83599
191198 119401
164252 4266...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 199993 numbers

Test #109:

score: 0
Time Limit Exceeded

input:

200000 200000
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 5...

output:


result: