QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524031#8919. Рамазан и капустаDaiRuiChen007100 ✓1425ms92936kbC++173.1kb2024-08-19 08:45:362024-08-19 08:45:42

Judging History

This is the latest submission verdict.

  • [2024-08-19 08:45:42]
  • Judged
  • Verdict: 100
  • Time: 1425ms
  • Memory: 92936kb
  • [2024-08-19 08:45:36]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
struct info { int len,w,wc,wl,wr,wq,pr; };
struct tag { int w,mw,pr; };
info operator +(const info &x,const info &y) {
	info z{0,0,0,0,0,0,0};
	z.len=x.len+y.len,z.w=min(x.w,y.w);
	z.wc=(x.w==z.w?x.wc:0)+(y.w==z.w?y.wc:0);
	z.wl=max((x.w==z.w?x.wl:0),(x.w==y.w&&x.wl==x.len?x.len+y.wl:0));
	z.wr=max((y.w==z.w?y.wr:0),(x.w==y.w&&y.wr==y.len?y.len+x.wr:0));
	z.wq=max({(x.w==z.w?x.wq:0),(y.w==z.w?y.wq:0),(x.w==y.w?x.wr+y.wl:0)});
	z.pr=(x.w==y.w?(x.pr==y.pr?x.pr:-1):(x.w==z.w?x.pr:y.pr));
	return z;
}
info operator *(const info &x,const tag &y) {
	info z=x;
	if(x.w+y.mw==0&&~y.pr) z.pr=y.pr;
	z.w+=y.w;
	return z;
}
tag operator *(const tag &x,const tag &y) {
	tag z=y;
	z.mw+=x.w;
	if(~x.pr&&(x.mw<z.mw||(x.mw==z.mw&&z.pr==-1))) z.pr=x.pr;
	z.mw=min(z.mw,x.mw),z.w+=x.w;
	return z;
}
map <array<int,2>,array<int,2>> ANS;
void gans(int xl,int xr,int cnt,int mxq) {
	auto &z=ANS[{xl,xr}]; z[0]+=cnt,z[1]=max(z[1],mxq);
}
struct colu {
	info x; int sf; bool tg;
	void clr() { if(tg) gans(x.pr,sf,x.wc,x.wq); }
	void add(const info &y) {
		if(!y.w&&y.pr) {
			if(tg) x.pr==y.pr?(x=x+y):(clr(),x=y);
			else tg=true,x=y;
		} else clr(),tg=false;
	}
};
struct scl { int x,yl,yr; bool c; } a[MAXN];
int n,m,vals[MAXN];
struct SegmentTree {
	info tr[MAXN<<2]; tag tg[MAXN<<2];
	void adt(int p,tag k) { tg[p]=tg[p]*k,tr[p]=tr[p]*k; }
	void psd(int p) { adt(p<<1,tg[p]),adt(p<<1|1,tg[p]),tg[p]={0,0,-1}; }
	void psu(int p) { tr[p]=tr[p<<1]+tr[p<<1|1]; }
	void init(int l=1,int r=m,int p=1) {
		tg[p]={0,0,-1};
		if(l==r) {
			int z=vals[l+1]-vals[l];
			return tr[p]={z,0,z,z,z,z,0},void();
		}
		int mid=(l+r)>>1;
		init(l,mid,p<<1),init(mid+1,r,p<<1|1),psu(p);
	}
	void upd(int ul,int ur,tag k,int l=1,int r=m,int p=1) {
		if(ul<=l&&r<=ur) return adt(p,k);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) upd(ul,ur,k,l,mid,p<<1);
		if(mid<ur) upd(ul,ur,k,mid+1,r,p<<1|1);
		psu(p);
	}
	void qry(colu &c,int l=1,int r=m,int p=1) {
		if(~tr[p].pr||tr[p].w) return c.add(tr[p]);
		int mid=(l+r)>>1; psd(p);
		qry(c,l,mid,p<<1),qry(c,mid+1,r,p<<1|1);
	}
}	T;
void solve() {
	cin>>n,ANS.clear();
	for(int i=1,xl,xr,yl,yr;i<=n;++i) {
		cin>>xl>>yl>>xr>>yr,++xr,++yr;
		vals[2*i-1]=yl,vals[2*i]=yr;
		a[2*i-1]={xl,yl,yr,0},a[2*i]={xr,yl,yr,1};
	}
	sort(vals+1,vals+2*n+1),m=unique(vals+1,vals+2*n+1)-vals-1;
	for(int i=1;i<=2*n;++i) {
		a[i].yl=lower_bound(vals+1,vals+m+1,a[i].yl)-vals;
		a[i].yr=lower_bound(vals+1,vals+m+1,a[i].yr)-vals-1;
	}
	sort(a+1,a+2*n+1,[&](auto i,auto j){ return i.x==j.x?i.c<j.c:i.x<j.x; });
	--m,T.init();
	vector <int> cur;
	for(int i=1;i<=2*n;++i) {
		if(a[i].c) T.upd(a[i].yl,a[i].yr,{-1,-1,-1}),cur.push_back(i);
		else T.upd(a[i].yl,a[i].yr,{1,0,a[i].x});
		if(i==2*n||a[i+1].x>a[i].x) {
			colu c{{},a[i].x-1,0};
			T.qry(c),c.clr();
			for(int j:cur) T.upd(a[j].yl,a[j].yr,{0,0,0});
			cur.clear();
		}
	}
	cout<<ANS.size()<<"\n";
	for(auto o:ANS) cout<<o.first[0]<<" "<<o.first[1]<<" "<<o.second[0]<<" "<<o.second[1]<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	int Q; cin>>Q;
	while(Q--) solve();
	return 0;
}

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 222ms
memory: 9700kb

input:

200000
1
565778957 214885827 643631102 454354917
1
263101082 140849863 495025813 187319842
1
88613012 171540216 997203410 427032287
1
122323034 42830940 735807869 796456391
1
77613097 54027504 973250323 969381176
1
847142740 395047188 953109830 705625863
1
472126577 354277197 602563267 827774625
1
4...

output:

1
565778957 643631102 239469091 239469091
1
263101082 495025813 46469980 46469980
1
88613012 997203410 255492072 255492072
1
122323034 735807869 753625452 753625452
1
77613097 973250323 915353673 915353673
1
847142740 953109830 310578676 310578676
1
472126577 602563267 473497429 473497429
1
41553885...

result:

ok both cnt and k values are correct (200000 test cases)

Test #2:

score: 4
Accepted
time: 175ms
memory: 7704kb

input:

200000
1
154560 185774 999896526 999895042
1
5118 21584 999996924 999961195
1
2781 20150 999999968 999969452
1
19677 28358 999934643 999923144
1
12839 4048 999940429 999992705
1
55457 31057 999972310 999973714
1
50676 11995 999746876 999990131
1
143286 179252 999840647 999986791
1
685 46481 99999814...

output:

1
154560 999896526 999709269 999709269
1
5118 999996924 999939612 999939612
1
2781 999999968 999949303 999949303
1
19677 999934643 999894787 999894787
1
12839 999940429 999988658 999988658
1
55457 999972310 999942658 999942658
1
50676 999746876 999978137 999978137
1
143286 999840647 999807540 999807...

result:

ok both cnt and k values are correct (200000 test cases)

Test #3:

score: 4
Accepted
time: 199ms
memory: 7760kb

input:

200000
1
95713206 17057205 95753911 17216964
1
948737502 397597546 948813532 397696428
1
343347731 237747750 343472579 237826126
1
271259014 769141220 271367809 769229654
1
303510235 957327501 303668280 957359533
1
814653251 838216617 814690988 838325334
1
553349610 285946015 553443533 286003831
1
1...

output:

1
95713206 95753911 159760 159760
1
948737502 948813532 98883 98883
1
343347731 343472579 78377 78377
1
271259014 271367809 88435 88435
1
303510235 303668280 32033 32033
1
814653251 814690988 108718 108718
1
553349610 553443533 57817 57817
1
160021240 160042346 117112 117112
1
764861572 764908729 18...

result:

ok both cnt and k values are correct (200000 test cases)

Subtask #2:

score: 8
Accepted

Test #4:

score: 8
Accepted
time: 72ms
memory: 9972kb

input:

20000
13
10166867 1 997338381 1
682240 1 995463007 1
51318963 1 819209466 1
39298592 1 994333556 1
70440040 1 972033293 1
8773671 1 939207094 1
8216667 1 977351228 1
83210187 1 838599596 1
113696716 1 952264629 1
60385886 1 960352059 1
246537994 1 963808622 1
32311066 1 890559407 1
1055354 1 9420784...

output:

1
682240 997338381 1 1
1
26564604 903674492 1 1
1
18260841 984761698 1 1
1
1035698 998069808 1 1
1
17572 998814423 1 1
1
5655240 999185837 1 1
1
33851 997706739 1 1
1
6481621 968774293 1 1
1
3668165 993968173 1 1
1
812007 999488950 1 1
1
4400667 998363099 1 1
1
6854954 997780010 1 1
1
27502123 99425...

result:

ok both cnt and k values are correct (20000 test cases)

Test #5:

score: 8
Accepted
time: 64ms
memory: 9804kb

input:

1000
305
165610966 1 199040660 1
151011440 1 166894337 1
355623252 1 367432914 1
586810706 1 635520685 1
583580039 1 585490850 1
59073810 1 68448447 1
158215651 1 172566466 1
326197816 1 350862587 1
532192338 1 572030300 1
647071629 1 656810375 1
254555279 1 266412752 1
31831411 1 35183990 1
5719090...

output:

2
2648460 993695411 1 1
997472383 998498925 1 1
2
3713373 980552705 1 1
983536205 989704854 1 1
6
65756604 107635474 1 1
154459286 284420396 1 1
364420601 387906872 1 1
507655614 511711832 1 1
868754749 897504018 1 1
971995038 977791981 1 1
1
2449877 999482686 1 1
8
130061442 186743855 1 1
221943451...

result:

ok both cnt and k values are correct (1000 test cases)

Test #6:

score: 8
Accepted
time: 76ms
memory: 9800kb

input:

100
1008
572147251 1 572902915 1
141194602 1 141998514 1
303241767 1 304739551 1
620063336 1 620626233 1
379471467 1 379568285 1
304998057 1 307260652 1
916220170 1 917676654 1
68605846 1 69253764 1
286943498 1 286983311 1
616497081 1 616692368 1
240551904 1 240886869 1
445276973 1 446341016 1
55403...

output:

128
136054 2504968 1 1
2534028 6658223 1 1
6720526 15724253 1 1
15727550 15949204 1 1
16828856 17874877 1 1
17933275 19237232 1 1
19800759 20339303 1 1
21074110 21266876 1 1
21299882 28115198 1 1
28733354 47825485 1 1
48152681 50271885 1 1
51113054 63917444 1 1
64132098 65772807 1 1
66900854 7058759...

result:

ok both cnt and k values are correct (100 test cases)

Test #7:

score: 8
Accepted
time: 78ms
memory: 12008kb

input:

10
81
414153871 1 414321252 1
60133843 1 60248810 1
246970545 1 247405698 1
559334189 1 559390251 1
765588127 1 765648225 1
511270872 1 511628140 1
72300222 1 72348788 1
39508165 1 39922073 1
41062446 1 42149085 1
481564984 1 481987876 1
40330066 1 40582247 1
740952487 1 741338934 1
949745244 1 9499...

output:

79
10441553 10832064 1 1
12503898 12561562 1 1
28701336 29080789 1 1
30916126 31067456 1 1
39508165 39922073 1 1
40330066 40582247 1 1
41062446 42149085 1 1
60133843 60248810 1 1
72300222 72348788 1 1
104123412 104536968 1 1
116486409 116542078 1 1
125806509 125977346 1 1
140716110 140772891 1 1
145...

result:

ok both cnt and k values are correct (10 test cases)

Test #8:

score: 8
Accepted
time: 86ms
memory: 15232kb

input:

1
200000
316457453 1 316467104 1
835243680 1 835300437 1
87667626 1 87670934 1
765381650 1 765407926 1
875330649 1 875362446 1
528559162 1 528617241 1
50863721 1 50900784 1
109885149 1 109885817 1
690695508 1 690723541 1
480255493 1 480273801 1
901743297 1 901768468 1
76427630 1 76464651 1
669761542...

output:

3677
6882 283598 1 1
285700 287143 1 1
288549 314374 1 1
315039 871519 1 1
881700 2176876 1 1
2177205 2463342 1 1
2463432 2992947 1 1
2998586 3477899 1 1
3485903 3489361 1 1
3492298 3746677 1 1
3751260 3811315 1 1
3813492 3830346 1 1
3841474 3858830 1 1
3860703 4305113 1 1
4309665 5192554 1 1
519484...

result:

ok both cnt and k values are correct (1 test case)

Test #9:

score: 8
Accepted
time: 113ms
memory: 19084kb

input:

1
200000
877319873 1 877322987 1
180204233 1 180209178 1
592025399 1 592025590 1
595277898 1 595300217 1
893583566 1 893588250 1
510159591 1 510169046 1
610404644 1 610407970 1
760110050 1 760111253 1
516766174 1 516766628 1
873041931 1 873060920 1
489103021 1 489103246 1
39811125 1 39816102 1
90826...

output:

73689
7709 12929 1 1
20480 25120 1 1
59566 76806 1 1
78796 83178 1 1
83840 84099 1 1
86640 91777 1 1
109853 113189 1 1
118358 128042 1 1
134422 142219 1 1
144143 155367 1 1
166484 177335 1 1
182739 185350 1 1
196215 201639 1 1
205144 209719 1 1
216441 219541 1 1
227648 236126 1 1
239063 252586 1 1
2...

result:

ok both cnt and k values are correct (1 test case)

Test #10:

score: 8
Accepted
time: 155ms
memory: 26152kb

input:

1
200000
37265560 1 37265561 1
926610218 1 926610218 1
205021611 1 205021611 1
283833573 1 283833574 1
788763949 1 788763949 1
57166008 1 57166009 1
25026375 1 25026375 1
362266755 1 362266755 1
551613788 1 551613788 1
395719835 1 395719835 1
15724347 1 15724347 1
417011950 1 417011951 1
262260284 1...

output:

199936
18219 18220 1 1
19271 19271 1 1
26032 26033 1 1
28503 28504 1 1
33212 33214 1 1
36037 36038 1 1
36321 36321 1 1
37853 37853 1 1
41638 41638 1 1
46230 46230 1 1
49563 49568 1 1
54401 54401 1 1
56016 56017 1 1
57030 57032 1 1
58008 58008 1 1
59159 59159 1 1
61881 61882 1 1
70738 70738 1 1
73288...

result:

ok both cnt and k values are correct (1 test case)

Test #11:

score: 8
Accepted
time: 101ms
memory: 15080kb

input:

1
200000
200781722 1 368886943 1
100338339 1 885513848 1
256400077 1 934777836 1
41234371 1 420014301 1
34149093 1 821738221 1
15367066 1 138421365 1
34509837 1 873588323 1
679261 1 997200685 1
346018 1 999730184 1
110408498 1 965542596 1
203234793 1 936753702 1
9766704 1 984361609 1
773124288 1 832...

output:

1
59 999998918 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #12:

score: 8
Accepted
time: 177ms
memory: 26628kb

input:

1
200000
12181592 1 12181653 1
694883691 1 694884108 1
444914071 1 444921686 1
273965002 1 273966296 1
134232923 1 134233759 1
874404965 1 874408078 1
582910942 1 582918069 1
108214195 1 108218543 1
218116160 1 218127522 1
591821436 1 591822727 1
261515171 1 261520126 1
650836844 1 650837348 1
80919...

output:

200000
3933 4893 1 1
8412 11165 1 1
12878 15806 1 1
20541 22184 1 1
22739 28801 1 1
29251 29371 1 1
30330 31622 1 1
32203 33350 1 1
35708 36007 1 1
36039 37882 1 1
46173 48336 1 1
48837 52641 1 1
53858 59898 1 1
65423 66281 1 1
66691 66766 1 1
66963 72479 1 1
77525 80683 1 1
84931 85286 1 1
90853 92...

result:

ok both cnt and k values are correct (1 test case)

Test #13:

score: 8
Accepted
time: 116ms
memory: 21364kb

input:

1
200000
564035468 1 564044137 1
561071370 1 561077033 1
957740164 1 957751587 1
954077130 1 954078836 1
8460873 1 8463742 1
513708529 1 513710435 1
869042138 1 869049036 1
448561933 1 448571271 1
148786999 1 148805211 1
315620926 1 315627686 1
163909821 1 163911306 1
179648906 1 179661411 1
9752748...

output:

100000
8290 10333 1 1
14678 19281 1 1
21308 34215 1 1
35050 35810 1 1
36164 58146 1 1
60225 66054 1 1
68626 81870 1 1
85362 85641 1 1
86313 86743 1 1
91540 99170 1 1
99893 106002 1 1
108552 133991 1 1
135332 151442 1 1
153466 160920 1 1
161142 161258 1 1
161913 168240 1 1
173186 174405 1 1
176772 18...

result:

ok both cnt and k values are correct (1 test case)

Test #14:

score: 8
Accepted
time: 80ms
memory: 14896kb

input:

1
200000
210406218 1 210407392 1
871863989 1 871866844 1
16996548 1 17012449 1
893456596 1 893457871 1
141676570 1 141680557 1
893417535 1 893421941 1
175307673 1 175309344 1
919695241 1 919699282 1
948186479 1 948187759 1
704275135 1 704281418 1
257328973 1 257333959 1
175650081 1 175654082 1
56491...

output:

10
46 297041551 1 1
297046298 358036812 1 1
358036910 415365612 1 1
415371895 585755229 1 1
585760176 625553576 1 1
625557931 628758568 1 1
628761480 725627987 1 1
725628599 793223950 1 1
793228552 903186358 1 1
903187075 999993399 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #15:

score: 8
Accepted
time: 86ms
memory: 13904kb

input:

1
200000
292485409 1 292486763 1
330767493 1 330769296 1
378275354 1 378277890 1
516280512 1 516284247 1
538570578 1 538577246 1
34282482 1 34292161 1
887235270 1 887235753 1
558139716 1 558150753 1
854823930 1 854827033 1
251457280 1 251466576 1
878895705 1 878902944 1
530960086 1 530960651 1
16744...

output:

1
3845 999998953 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #16:

score: 8
Accepted
time: 85ms
memory: 14200kb

input:

1
200000
514786263 1 514790232 1
726660526 1 726670089 1
585322683 1 585335691 1
896731192 1 896735961 1
63644658 1 63649458 1
125990818 1 125996306 1
193991294 1 193996500 1
15964462 1 15977800 1
893005475 1 893020792 1
343580455 1 343581564 1
998437807 1 998453506 1
612879918 1 612882384 1
6346426...

output:

1
1663 999998501 1 1

result:

ok both cnt and k values are correct (1 test case)

Subtask #3:

score: 8
Accepted

Test #17:

score: 8
Accepted
time: 0ms
memory: 9804kb

input:

100
30
6 2 7 6
1 2 6 6
1 6 9 10
2 7 6 9
1 4 10 6
1 2 5 9
2 1 3 8
3 1 10 6
1 2 8 8
1 5 2 5
5 4 10 10
2 7 10 7
2 2 6 5
3 9 10 9
3 2 6 10
6 6 6 8
2 1 7 7
2 3 9 7
1 2 10 4
2 2 10 8
4 1 8 6
6 1 8 10
10 3 10 6
2 9 10 9
3 7 8 8
1 5 10 5
2 5 8 9
7 4 10 10
2 5 5 9
1 2 10 9
30
5 4 8 8
5 3 6 10
2 5 6 7
3 5 5 1...

output:

2
1 10 9 9
2 10 1 1
2
1 9 1 1
1 10 9 9
1
1 10 10 10
2
1 9 1 1
1 10 9 9
1
1 10 10 10
1
1 10 10 10
3
1 9 1 1
1 10 8 8
2 10 1 1
1
1 10 10 10
2
1 10 9 9
2 9 1 1
1
1 9 2 2
1
1 10 10 10
2
1 9 1 1
1 10 9 9
1
1 10 10 10
1
1 10 10 10
3
1 7 1 1
1 9 1 1
1 10 8 8
2
1 7 1 1
1 10 9 9
1
1 10 10 10
1
1 10 10 10
1
1...

result:

ok both cnt and k values are correct (100 test cases)

Test #18:

score: 8
Accepted
time: 4ms
memory: 10044kb

input:

100
30
4 3 7 5
10 6 10 6
2 4 5 4
1 3 6 5
10 4 10 5
8 1 8 2
6 5 6 7
3 5 4 8
1 2 4 2
7 4 10 9
5 1 7 1
6 6 9 6
5 9 9 9
5 4 6 5
7 5 9 9
6 5 7 5
1 5 1 10
6 8 7 8
5 9 7 10
7 3 7 4
2 3 6 6
1 1 1 5
1 1 2 1
9 5 10 9
1 4 7 6
4 5 7 7
1 3 2 5
10 8 10 9
4 5 5 8
4 9 6 9
24
2 4 3 9
2 5 3 9
6 4 7 4
2 1 9 4
1 2 1 4
...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #19:

score: 8
Accepted
time: 2ms
memory: 9844kb

input:

100
7
7 7 8 8
9 3 9 3
1 6 8 6
9 7 10 7
5 7 9 10
1 7 6 8
8 6 9 10
1
9 1 9 5
1
1 1 6 5
11
1 4 6 4
6 6 7 7
3 4 6 4
1 8 7 10
3 2 3 4
9 5 10 6
3 9 5 10
1 7 3 7
2 8 2 9
7 8 10 8
3 1 6 7
14
2 9 8 10
2 3 5 5
3 6 7 10
6 6 6 6
10 3 10 5
5 2 8 5
3 5 9 9
5 2 5 6
3 3 3 8
2 4 5 7
9 1 9 2
3 8 8 10
2 2 2 4
6 5 10 6...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #20:

score: 8
Accepted
time: 2ms
memory: 10008kb

input:

100
2
1 2 10 8
6 1 9 8
19
3 2 9 2
5 5 10 10
7 1 10 8
1 2 5 3
2 1 6 10
5 2 10 6
3 2 5 6
3 1 9 10
2 1 2 10
3 4 8 10
5 1 10 9
1 1 7 10
10 1 10 5
4 1 4 8
1 2 10 10
5 1 10 3
1 1 10 10
1 3 8 3
1 1 10 7
3
5 1 7 9
5 5 6 10
1 7 1 10
4
1 5 2 8
1 1 7 5
2 2 10 10
7 1 8 10
1
7 1 10 6
1
8 3 9 3
23
8 1 9 4
6 1 6 1...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #21:

score: 8
Accepted
time: 4ms
memory: 9740kb

input:

100
30
3 4 5 6
5 10 8 10
2 6 8 10
4 1 5 2
1 6 9 8
1 3 10 3
2 7 5 10
1 2 10 2
3 1 3 10
3 1 5 1
1 6 7 6
5 9 7 9
2 4 4 6
5 5 5 5
7 8 9 10
2 8 3 10
2 2 6 7
7 1 7 8
1 5 1 10
4 1 9 7
1 2 10 4
10 2 10 9
3 1 5 8
8 1 8 9
8 4 10 6
1 3 9 6
4 6 4 10
2 1 10 3
7 4 10 6
2 10 2 10
30
8 9 10 9
7 1 7 10
4 10 7 10
7 4...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #22:

score: 8
Accepted
time: 2ms
memory: 10044kb

input:

100
12
7 2 7 3
6 4 9 4
10 2 10 10
1 7 9 7
1 7 10 7
7 2 8 3
5 4 9 4
5 1 9 7
8 10 8 10
6 1 6 8
7 1 10 10
9 8 10 9
11
7 8 7 8
2 6 5 10
7 1 7 2
6 3 7 3
8 2 10 9
8 2 10 6
4 2 4 8
3 6 5 8
1 4 8 6
1 5 8 8
5 2 8 2
1
2 7 2 10
12
6 10 10 10
7 1 8 8
1 6 10 7
2 5 10 6
3 6 10 6
1 5 10 5
3 1 9 3
5 1 6 10
4 4 4 5
...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #23:

score: 8
Accepted
time: 0ms
memory: 9808kb

input:

100
4
3 4 10 5
7 2 7 10
3 7 10 8
4 2 5 10
8
1 3 10 3
1 7 10 7
1 5 10 5
1 9 10 9
9 2 9 10
2 2 2 10
4 2 4 10
6 2 7 10
6
1 2 10 2
7 1 8 10
1 7 10 7
5 1 5 10
1 5 10 5
3 1 3 10
8
1 3 9 3
6 2 6 10
8 2 8 10
1 9 9 9
2 2 2 10
4 2 4 10
1 5 9 5
1 7 9 7
4
5 2 9 8
1 3 10 3
1 5 10 6
2 2 3 8
2
2 3 7 4
4 1 5 10
5
2...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #24:

score: 8
Accepted
time: 0ms
memory: 9744kb

input:

100
3
1 2 4 5
2 3 6 8
4 5 7 10
5
2 2 7 6
3 3 8 7
1 1 6 5
4 4 9 9
5 5 10 10
5
4 3 8 8
5 4 9 9
6 5 10 10
3 2 7 7
1 1 6 5
3
3 7 10 10
1 2 3 7
2 5 7 8
5
5 4 9 8
6 5 10 9
3 3 8 7
2 2 7 6
1 1 6 5
5
1 1 6 6
3 2 7 7
6 6 10 10
5 5 9 9
4 3 8 8
2
5 4 8 6
2 1 6 4
4
1 3 5 7
2 4 7 8
3 6 8 9
5 7 10 10
5
5 4 9 8
6 ...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #25:

score: 8
Accepted
time: 2ms
memory: 10040kb

input:

100
3
1 2 7 2
2 2 6 8
4 2 4 10
5
3 2 9 6
5 2 7 8
4 2 8 7
2 2 10 5
6 2 6 10
5
4 1 8 5
5 1 7 6
6 1 6 10
3 1 9 4
1 1 10 3
3
2 2 10 6
3 2 8 9
5 2 7 10
5
5 2 5 8
1 2 10 2
4 2 7 7
2 2 9 3
3 2 8 6
5
5 1 5 9
1 1 10 3
4 1 6 7
3 1 7 6
2 1 9 4
2
3 1 3 9
1 1 7 6
4
5 5 5 10
3 5 7 7
2 5 8 6
4 5 6 8
5
6 1 6 10
1 1...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #26:

score: 8
Accepted
time: 0ms
memory: 9808kb

input:

100
30
4 2 4 2
5 2 5 2
5 1 5 1
4 4 4 5
1 3 2 9
6 5 6 6
1 10 1 10
5 10 5 10
8 2 8 2
10 2 10 2
9 10 9 10
4 1 4 1
3 1 3 9
5 7 5 8
4 9 4 9
3 10 3 10
7 3 10 9
7 10 7 10
2 10 2 10
8 10 8 10
5 3 5 3
5 4 5 4
4 3 4 3
5 6 5 6
6 10 6 10
5 5 5 5
9 2 9 2
4 10 4 10
4 8 4 8
10 10 10 10
30
2 2 2 3
10 5 10 5
3 6 4 6...

output:

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

result:

ok both cnt and k values are correct (100 test cases)

Test #27:

score: 8
Accepted
time: 4ms
memory: 7796kb

input:

100
30
8 2 8 10
7 1 7 9
9 6 9 7
2 2 2 4
8 1 8 5
4 6 7 6
6 2 6 5
5 5 5 5
1 6 7 6
2 6 2 6
2 1 2 8
2 2 2 7
2 1 2 1
6 10 8 10
4 6 9 6
1 7 2 7
10 2 10 5
5 5 7 5
10 6 10 6
1 5 1 5
1 2 1 5
8 6 8 6
8 4 10 4
8 8 8 8
8 3 8 5
5 1 5 6
1 10 7 10
1 2 1 8
6 1 7 1
1 1 4 1
30
7 6 7 6
1 1 1 3
3 5 6 5
1 8 6 8
5 5 5 5
...

output:

8
1 2 6 4
1 8 2 1
1 10 1 1
5 8 3 2
5 10 1 1
7 8 2 2
7 9 1 1
10 10 3 2
12
1 1 4 1
1 8 3 1
1 10 1 1
2 3 1 1
2 8 1 1
3 3 3 1
3 6 1 1
5 6 1 1
5 8 2 1
6 8 1 1
8 8 1 1
10 10 5 4
11
1 1 3 2
1 6 2 2
1 10 1 1
2 5 1 1
2 10 1 1
3 6 2 1
3 10 1 1
4 5 2 2
7 10 1 1
8 8 4 4
10 10 6 5
11
1 1 2 1
1 2 1 1
1 7 1 1
1 9 ...

result:

ok both cnt and k values are correct (100 test cases)

Subtask #4:

score: 4
Accepted

Dependency #3:

100%
Accepted

Test #28:

score: 4
Accepted
time: 227ms
memory: 10044kb

input:

40000
2
15 3 18 12
6 10 22 10
11
14 3 14 24
7 17 25 17
10 2 10 20
17 4 17 25
2 7 22 7
1 11 21 12
19 5 20 23
3 9 24 9
12 1 12 19
8 6 8 18
6 15 23 15
3
12 10 24 23
4 13 25 17
6 4 9 19
1
6 10 25 15
12
13 3 13 25
7 5 7 23
1 7 18 7
3 11 21 11
15 4 15 20
9 1 9 22
6 13 22 13
11 6 11 21
4 9 20 9
5 15 23 16
...

output:

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

result:

ok both cnt and k values are correct (40000 test cases)

Test #29:

score: 4
Accepted
time: 8ms
memory: 10608kb

input:

1
4998
1 3245 5000 3245
3936 1 3936 5000
1 2907 5000 2907
1 4137 5000 4137
228 1 228 5000
1 946 5000 946
1 300 5000 300
1 3297 5000 3297
846 1 846 5000
2310 1 2310 5000
1 4479 5000 4479
3532 1 3532 5000
1 4471 5000 4471
2096 1 2096 5000
1952 1 1952 5000
1 1936 5000 1936
318 1 318 5000
622 1 622 5000...

output:

2500
1 5000 2499 1
2 2 2501 2
4 4 2501 2
6 6 2501 2
8 8 2501 2
10 10 2501 2
12 12 2501 2
14 14 2501 2
16 16 2501 2
18 18 2501 2
20 20 2501 2
22 22 2501 2
24 24 2501 2
26 26 2501 2
28 28 2501 2
30 30 2501 2
32 32 2501 2
34 34 2501 2
36 36 2501 2
38 38 2501 2
40 40 2501 2
42 42 2501 2
44 44 2501 2
46 ...

result:

ok both cnt and k values are correct (1 test case)

Test #30:

score: 4
Accepted
time: 19ms
memory: 9744kb

input:

100
219
201 30 201 403
52 240 488 240
237 81 237 425
70 144 477 144
344 18 344 432
320 13 320 454
335 27 335 394
328 105 329 407
50 377 437 377
115 210 443 210
12 222 375 222
223 72 223 402
91 136 376 136
44 180 483 180
104 151 393 151
23 251 416 251
79 197 387 197
47 282 396 283
129 220 444 220
118...

output:

219
1 459 1 1
2 463 2 2
3 403 2 2
4 440 1 1
5 429 1 1
6 469 2 2
8 495 1 1
9 442 3 3
10 426 1 1
11 473 1 1
12 375 1 1
13 476 1 1
14 441 1 1
16 434 1 1
17 386 1 1
18 446 1 1
20 412 1 1
21 408 1 1
22 445 1 1
23 416 1 1
24 430 1 1
25 447 1 1
27 457 1 1
28 466 2 2
29 432 1 1
30 490 1 1
31 479 2 2
32 425 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #31:

score: 4
Accepted
time: 265ms
memory: 9700kb

input:

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

output:

5
1 44 5 5
1 45 12 12
3 50 7 7
7 45 3 3
37 44 15 8
5
1 50 44 44
2 50 2 2
3 49 2 1
3 50 1 1
5 49 1 1
2
5 49 16 16
6 49 32 27
5
2 50 43 43
3 46 1 1
3 50 3 2
13 50 1 1
17 50 1 1
6
1 41 9 5
1 42 4 4
1 49 29 15
1 50 1 1
11 30 1 1
12 26 4 4
5
1 50 41 41
2 49 3 3
2 50 4 4
3 49 1 1
9 49 1 1
6
1 45 1 1
1 49 ...

result:

ok both cnt and k values are correct (10000 test cases)

Test #32:

score: 4
Accepted
time: 411ms
memory: 9840kb

input:

100
2167
43 364 117 379
115 17 220 290
211 9 246 16
192 245 332 421
412 107 433 128
255 86 376 181
324 212 414 255
127 335 148 336
248 305 368 387
154 288 168 359
359 108 363 199
322 333 445 351
15 348 57 374
331 314 398 401
304 244 324 487
320 154 370 261
425 148 459 167
176 121 352 151
446 81 453 ...

output:

37
1 1 10 10
1 493 20 20
1 498 81 58
1 499 21 21
1 500 35 34
2 500 46 40
3 490 3 3
3 494 11 11
3 495 3 3
3 498 18 18
3 499 38 38
3 500 102 58
4 6 48 48
4 495 1 1
4 497 2 2
4 498 5 5
4 500 37 17
5 500 9 8
8 490 2 2
8 495 4 4
8 497 20 20
8 498 10 10
9 493 2 2
10 497 6 6
10 500 8 8
11 75 4 4
11 451 1 1...

result:

ok both cnt and k values are correct (100 test cases)

Test #33:

score: 4
Accepted
time: 581ms
memory: 15680kb

input:

1
200000
489 179 4507 1706
430 2144 4253 4307
683 57 3630 2423
2316 664 4478 1062
2761 688 3178 1462
1518 1687 2638 3654
215 1883 999 2397
3485 2418 3805 3798
310 37 623 4234
1028 746 2926 4922
2269 3671 4421 3671
175 1258 4875 3582
2815 101 3355 4662
595 826 2560 3144
1119 664 4044 4439
1057 2380 3...

output:

2
1 4999 1 1
1 5000 4999 4999

result:

ok both cnt and k values are correct (1 test case)

Test #34:

score: 4
Accepted
time: 531ms
memory: 23396kb

input:

1
200000
1982 4518 1998 4521
2643 1470 2644 1476
2106 278 2112 303
3464 72 3470 74
4958 4633 4962 4651
3862 1001 3866 1037
3706 77 3707 80
731 1907 733 1910
538 2891 559 2896
3126 649 3138 654
1053 2134 1054 2162
2997 3980 3007 4027
3637 1775 3649 1782
2227 1138 2229 1141
1823 1061 1834 1075
1764 23...

output:

124189
1 1 33 29
1 2 14 6
1 5 44 24
1 6 17 14
1 7 35 19
1 8 31 18
1 10 2 2
1 12 8 3
1 13 8 8
1 14 21 10
1 15 14 8
1 17 11 7
1 19 1 1
1 22 5 5
1 23 6 5
1 25 4 4
1 27 4 4
1 29 10 8
1 30 3 3
1 31 2 2
1 32 14 11
1 34 4 2
1 36 22 9
1 37 25 15
1 38 3 2
1 39 6 6
1 40 12 7
1 42 12 9
1 43 3 3
1 45 11 7
1 46 ...

result:

ok both cnt and k values are correct (1 test case)

Test #35:

score: 4
Accepted
time: 546ms
memory: 15756kb

input:

1
200000
2183 4518 3824 4521
1441 301 1441 3302
1679 1128 1685 4033
1257 936 1287 4058
4834 382 4856 4119
1767 459 1776 2073
4638 315 4640 3720
4731 1297 4734 4064
3 2891 4999 2896
3960 649 4835 654
1283 4217 1294 4946
367 3980 2037 4027
3331 1775 4166 1782
931 904 945 4262
1292 1061 4390 1075
2188 ...

output:

12
1 4999 68 18
1 5000 4826 4796
2 51 1 1
2 4987 4 4
2 4997 3 3
2 4998 16 10
2 4999 13 6
2 5000 60 27
3 4999 2 2
4 4999 7 7
56 95 1 1
100 4976 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #36:

score: 4
Accepted
time: 571ms
memory: 14488kb

input:

1
200000
1093 1645 3592 4144
2277 595 4776 3094
1580 495 4079 2994
738 1672 3237 4171
1528 268 4027 2767
1862 1705 4361 4204
605 320 3104 2819
9 1958 2508 4457
2214 1674 4713 4173
505 202 3004 2701
1458 1541 3957 4040
2218 2147 4717 4646
2451 27 4950 2526
242 1105 2741 3604
1433 2173 3932 4672
142 4...

output:

11
1 5000 4967 4967
2 4970 1 1
2 4991 3 3
2 5000 1 1
3 5000 13 13
4 4991 3 3
4 5000 8 8
15 4911 1 1
15 4967 1 1
15 4991 1 1
35 4970 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #37:

score: 4
Accepted
time: 572ms
memory: 14016kb

input:

1
200000
172 3018 671 3517
1673 2719 2172 3218
4251 364 4750 863
3396 3503 3895 4002
1993 3818 2492 4317
527 286 1026 785
940 3672 1439 4171
4151 1446 4650 1945
3686 1000 4185 1499
2747 3931 3246 4430
3957 1493 4456 1992
656 673 1155 1172
3488 4189 3987 4688
1785 2735 2284 3234
2428 3651 2927 4150
1...

output:

17
1 4999 295 295
1 5000 4499 2702
2 5000 98 98
3 5000 2 2
5 4984 3 3
5 4994 43 43
5 4999 34 34
27 4984 2 2
28 5000 9 9
29 4833 1 1
29 4984 3 3
29 5000 6 6
31 2900 1 1
31 4837 2 2
31 4911 1 1
31 4955 1 1
2907 4736 1 1

result:

ok both cnt and k values are correct (1 test case)

Test #38:

score: 4
Accepted
time: 460ms
memory: 16472kb

input:

1
200000
4307 898 4311 902
1830 2392 1834 2396
4207 405 4211 409
794 1950 798 1954
4925 2566 4929 2570
832 1421 836 1425
3217 2697 3221 2701
1966 1321 1970 1325
1074 4246 1078 4250
3258 2522 3262 2526
1313 1116 1317 1120
2693 2492 2697 2496
3267 1191 3271 1195
3630 4885 3634 4889
4873 1989 4877 1993...

output:

34230
1 5 141 12
1 6 7 2
1 8 9 5
1 9 6 4
1 10 1 1
2 6 167 7
2 7 1 1
2 8 7 3
2 9 12 5
2 10 5 3
2 11 15 5
2 13 3 3
2 16 1 1
3 7 154 8
3 8 7 5
3 9 5 3
3 10 4 4
3 11 3 3
3 14 4 4
4 8 124 5
4 9 10 4
4 11 9 4
4 12 2 2
4 13 5 3
4 16 1 1
4 17 1 1
5 9 137 5
5 10 8 4
5 11 8 3
5 12 7 4
5 13 2 1
6 10 131 9
6 11...

result:

ok both cnt and k values are correct (1 test case)

Test #39:

score: 4
Accepted
time: 7ms
memory: 12464kb

input:

1
2500
2980 806 3091 880
1617 2205 1722 2316
1483 3618 1584 3712
1419 4171 1517 4243
682 3594 750 3689
1349 1391 1445 1489
2860 3961 2972 4042
3225 158 3332 191
621 2303 686 2414
1553 4721 1656 4762
3784 1168 3872 1257
4993 1765 4998 1875
2808 3108 2919 3218
276 3974 320 4054
1737 3661 1846 3753
177...

output:

7400
1 3 61 61
1 8 25 25
1 13 13 13
1 23 13 13
2 6 61 61
2 13 13 13
2 20 13 13
2 32 13 13
3 8 37 37
3 16 24 24
3 36 12 12
5 11 61 61
5 20 13 13
5 29 13 13
5 43 13 13
6 13 37 37
6 23 12 12
6 47 12 12
8 16 37 37
8 27 23 23
8 51 12 12
10 18 61 61
10 29 13 13
10 39 13 13
10 55 13 13
11 20 37 37
11 32 12...

result:

ok both cnt and k values are correct (1 test case)

Test #40:

score: 4
Accepted
time: 4ms
memory: 12628kb

input:

1
2500
1917 1922 1922 1927
1854 1849 1859 1854
2475 2469 2480 2474
2782 2786 2787 2791
1781 1786 1786 1791
1246 1241 1251 1246
3567 3561 3572 3566
1397 1402 1402 1407
1065 1070 1070 1075
3394 3398 3399 3403
2719 2713 2724 2718
4798 4803 4803 4808
3055 3049 3060 3054
1498 1493 1503 1498
2670 2674 267...

output:

6248
1 3 2 2
1 6 1 1
1 11 1 1
1 15 1 1
2 6 2 2
2 10 1 1
2 19 1 1
3 7 1 1
3 11 1 1
5 10 2 2
5 14 1 1
5 23 1 1
6 11 1 1
6 15 1 1
9 14 2 2
9 18 1 1
9 27 1 1
10 15 2 2
10 19 1 1
13 18 2 2
13 22 1 1
13 31 1 1
14 19 2 2
14 23 1 1
17 22 2 2
17 26 1 1
17 35 1 1
18 23 2 2
18 27 1 1
21 26 2 2
21 30 1 1
21 39 ...

result:

ok both cnt and k values are correct (1 test case)

Test #41:

score: 4
Accepted
time: 7ms
memory: 10580kb

input:

1
2500
961 961 3461 3460
928 928 3428 3427
1238 1238 3738 3737
1393 1393 3893 3892
893 893 3393 3392
624 624 3124 3123
1784 1784 4284 4284
701 701 3201 3200
535 535 3035 3034
1699 1699 4199 4199
1360 1360 3860 3859
2402 2401 4901 4901
1528 1528 4028 4027
750 750 3250 3249
1337 1337 3837 3836
53 53 2...

output:

4999
1 2501 1 1
1 2502 1 1
1 2503 1 1
1 2504 1 1
1 2505 1 1
1 2506 1 1
1 2507 1 1
1 2508 1 1
1 2509 1 1
1 2510 1 1
1 2511 1 1
1 2512 1 1
1 2513 1 1
1 2514 1 1
1 2515 1 1
1 2516 1 1
1 2517 1 1
1 2518 1 1
1 2519 1 1
1 2520 1 1
1 2521 1 1
1 2522 1 1
1 2523 1 1
1 2524 1 1
1 2525 1 1
1 2526 1 1
1 2527 1 ...

result:

ok both cnt and k values are correct (1 test case)

Test #42:

score: 4
Accepted
time: 7ms
memory: 10136kb

input:

1
2500
961 1 4040 1907
928 1 4073 1847
1238 1 3763 2468
1393 1 3608 2767
893 1 4108 1765
624 1 4377 1218
1784 1 3217 3564
701 1 4300 1361
535 1 4466 1041
1699 1 3302 3385
1360 1 3641 2704
2402 1 2600 4794
1528 1 3473 3027
750 1 4251 1466
1337 1 3664 2661
53 1 4948 123
1306 1 3695 2596
2463 1 2539 49...

output:

2500
1 5000 3 3
2 4999 4 4
3 4998 2 2
4 4997 2 2
5 4996 2 2
6 4995 1 1
7 4994 2 2
8 4993 1 1
9 4992 5 5
10 4991 2 2
11 4990 6 6
12 4989 1 1
13 4988 3 3
14 4987 1 1
15 4986 2 2
16 4985 3 3
17 4984 1 1
18 4983 2 2
19 4982 6 6
20 4981 3 3
21 4980 1 1
22 4979 3 3
23 4978 5 5
24 4977 2 2
25 4976 3 3
26 4...

result:

ok both cnt and k values are correct (1 test case)

Test #43:

score: 4
Accepted
time: 366ms
memory: 16876kb

input:

1
200000
4859 165 4859 165
680 3701 680 3702
700 3082 700 3082
694 4994 694 4994
758 3298 758 3298
731 4573 731 4573
684 2738 684 2738
685 3623 685 3623
2472 71 2473 71
2407 72 2407 72
4553 257 4553 257
4541 356 4541 356
690 4076 690 4076
135 4005 135 4081
4126 415 4126 415
2463 2384 2463 2386
4868 ...

output:

9816
1 1 497 180
1 3 94 41
1 4 8 3
1 7 29 9
1 8 20 9
1 9 11 4
1 10 9 3
1 12 2 2
1 13 3 2
1 25 773 773
2 3 93 19
2 4 5 2
2 7 25 6
2 8 5 3
2 9 3 2
2 12 3 2
4 4 13 11
4 7 18 8
4 8 17 5
4 9 7 4
5 7 16 9
5 8 2 2
5 9 18 11
5 10 7 5
5 13 1 1
5 51 82 18
5 53 9 7
5 54 267 137
5 55 52 23
5 57 329 190
5 59 111...

result:

ok both cnt and k values are correct (1 test case)

Test #44:

score: 4
Accepted
time: 297ms
memory: 9828kb

input:

100
1621
266 27 267 28
34 33 35 33
333 35 333 35
202 34 204 34
321 73 322 73
34 34 35 34
202 2 204 2
321 21 322 21
65 2 66 2
62 34 64 34
217 1 219 1
318 407 318 407
334 2 337 3
333 32 333 32
328 49 332 49
496 476 498 476
240 34 240 50
333 38 333 38
321 387 322 387
490 122 491 134
67 2 69 2
342 97 34...

output:

226
1 9 112 112
2 3 103 103
5 5 185 185
7 10 26 26
11 11 27 13
20 21 13 13
20 23 34 24
22 23 44 44
24 26 41 21
27 31 8 8
32 36 1 1
32 46 2 2
32 60 1 1
34 36 83 44
34 37 19 19
34 71 1 1
36 37 9 9
37 37 88 88
38 74 1 1
42 49 1 1
49 64 2 2
53 58 14 7
61 61 13 13
61 64 2 2
65 83 1 1
71 71 1 1
75 77 1 1
...

result:

ok both cnt and k values are correct (100 test cases)

Test #45:

score: 4
Accepted
time: 9ms
memory: 10568kb

input:

1
2500
1187 1685 1187 4184
4675 914 4677 3414
1459 2185 1459 4684
4419 2363 4419 4862
1248 2396 1248 4895
4470 182 4470 2682
2901 1954 2901 4453
4795 2075 4797 4574
3156 2484 3157 4983
1487 1006 1487 3506
92 1352 92 3852
2201 2412 2201 4911
168 56 169 2556
2330 1202 2330 3702
1146 1632 1147 4131
249...

output:

4999
1 3 1180 1180
1 8 78 78
1 9 828 828
1 41 172 172
1 42 137 137
1 53 78 78
1 387 15 15
1 1702 5 5
1 2121 4 4
1 2128 2 2
1 3448 1 1
1 5000 1 1
4 5 985 985
4 9 194 194
6 6 99 99
6 7 421 421
6 8 466 466
7 9 99 99
8 9 420 420
9 9 544 544
10 10 288 288
10 13 806 806
10 25 203 203
10 40 169 169
10 41 6...

result:

ok both cnt and k values are correct (1 test case)

Test #46:

score: 4
Accepted
time: 5ms
memory: 10544kb

input:

1
2500
811 2127 4207 2903
2 2719 4998 2719
1731 1655 3257 3363
169 2426 4832 2590
2244 627 2246 4312
4797 560 4797 4125
2 3686 4998 3686
3020 1091 3020 4501
910 2080 4104 2954
3600 181 3600 4066
4996 1213 4997 3788
662 893 663 3752
2 2716 4998 2716
2058 1493 2948 3513
3004 982 3004 4140
2 3467 4998 ...

output:

1875
1 1 3607 1176
1 4999 626 1
5 5 3028 1082
5 4997 3 1
10 11 2111 243
10 4993 3 1
13 14 3288 912
13 4988 3 1
17 17 2729 797
17 4984 3 1
22 22 3618 1182
22 4980 4 1
26 26 3038 1170
26 4973 3 1
28 31 4145 1233
28 4971 3 1
35 36 3714 1047
35 4969 4 1
39 41 2179 286
39 4967 2 1
44 44 2848 881
44 4965 ...

result:

ok both cnt and k values are correct (1 test case)

Test #47:

score: 4
Accepted
time: 178ms
memory: 9752kb

input:

2500
50
11 52 11 84
90 54 90 97
1 26 22 26
65 35 65 38
76 63 76 77
8 28 8 82
80 11 80 44
5 12 21 12
67 58 73 58
6 99 6 100
48 20 48 32
71 40 71 73
16 95 33 95
56 14 78 14
84 9 92 9
14 4 14 74
97 51 97 72
24 19 24 99
30 5 30 83
54 37 54 40
2 31 95 31
36 86 94 86
42 38 42 61
60 48 60 93
28 55 61 55
44...

output:

50
1 22 1 1
2 95 1 1
3 86 1 1
4 63 1 1
5 21 1 1
6 6 2 2
8 8 52 44
10 28 1 1
11 11 31 24
13 91 1 1
14 14 67 25
16 33 1 1
17 69 1 1
18 18 30 15
20 20 1 1
24 24 74 17
26 85 1 1
27 84 1 1
28 61 1 1
30 30 72 26
32 32 23 23
35 81 1 1
36 94 1 1
37 67 1 1
38 38 53 9
40 40 28 28
42 42 20 8
44 44 1 1
46 93 1 ...

result:

ok both cnt and k values are correct (2500 test cases)

Test #48:

score: 4
Accepted
time: 9ms
memory: 10352kb

input:

1
2500
3105 4032 4518 4032
2191 491 4704 491
2144 2171 2144 2973
1360 4259 3367 4259
3949 131 3949 4404
1331 399 1331 1982
149 1383 1627 1383
343 891 4969 891
1345 2314 1345 3878
2397 1498 2397 3377
4581 68 4581 2520
2836 489 2836 2344
1716 3776 4715 3776
2639 2756 2639 3573
2882 4612 4209 4612
4194...

output:

2500
1 1156 1 1
2 2 532 532
4 4 3861 3832
6 6 2436 2436
8 8 3309 3309
10 10 2429 2429
12 2315 1 1
13 1189 1 1
14 3734 1 1
15 15 2858 2095
17 17 2922 1650
19 1848 1 1
20 4137 1 1
21 391 1 1
22 711 1 1
23 1024 1 1
24 799 1 1
25 2383 1 1
26 26 2715 733
28 341 1 1
29 29 2352 733
31 31 1191 707
33 33 221...

result:

ok both cnt and k values are correct (1 test case)

Test #49:

score: 4
Accepted
time: 524ms
memory: 16348kb

input:

1
200000
303 3855 2919 3855
781 314 781 766
3361 1089 3361 1491
4661 1453 4661 4133
1016 1859 3029 1859
369 775 3708 775
4304 2877 4304 4947
589 4104 1576 4104
165 1270 165 1675
44 10 3947 10
3528 2198 4516 2198
2342 1427 2342 1956
1839 2949 1947 2949
2475 1316 4812 1316
2181 2747 2703 2747
1424 420...

output:

9779
1 1 25 12
1 2 131 91
1 3 142 65
1 4 2 2
1 6 43 16
1 7 36 25
1 9 134 55
1 11 379 40
1 19 2208 50
1 24 275 21
1 25 1087 48
1 59 1 1
1 61 1 1
1 105 1 1
1 157 1 1
1 193 1 1
1 196 1 1
1 305 1 1
1 361 1 1
1 519 1 1
1 1350 1 1
1 1413 1 1
1 2807 1 1
1 3165 1 1
1 3466 1 1
1 3705 1 1
1 3801 1 1
1 3910 1 ...

result:

ok both cnt and k values are correct (1 test case)

Test #50:

score: 4
Accepted
time: 241ms
memory: 7768kb

input:

80
2500
2382 23 2470 26
3247 27 3274 28
4022 45 4115 45
2530 31 2611 31
4612 59 4768 60
4706 12 4796 12
97 31 147 31
3635 61 3704 61
3748 21 3850 21
1796 23 1844 25
2070 56 2114 57
2246 6 2443 6
2247 34 2248 37
4047 41 4125 41
3174 1 3179 3
656 54 665 56
2075 23 2122 23
752 3 777 3
4449 2 4491 4
233...

output:

995
3 31 1 1
5 13 1 1
5 121 1 1
6 182 1 1
6 820 1 1
8 139 1 1
8 147 1 1
8 474 1 1
8 627 1 1
10 265 1 1
10 455 1 1
10 531 1 1
15 34 1 1
16 20 1 1
17 84 1 1
20 114 1 1
20 350 2 1
20 382 1 1
20 388 1 1
23 42 1 1
23 127 1 1
23 208 1 1
23 341 1 1
23 744 1 1
26 29 1 1
27 72 1 1
45 56 1 1
51 454 1 1
52 82 ...

result:

ok both cnt and k values are correct (80 test cases)

Subtask #5:

score: 8
Accepted

Dependency #3:

100%
Accepted

Test #51:

score: 8
Accepted
time: 6ms
memory: 7768kb

input:

600
17
418541797 577680034 794999952 878382491
105004602 211185688 984902771 935493652
90376741 91289476 933420766 996246870
558946729 103138808 939638225 602606493
455608256 2469673 750343849 995314345
32812152 8480925 937684910 946828232
486498806 106996931 620811103 651644941
240644933 165407257 ...

output:

8
22842933 977715723 111433129 111433129
22842933 984902771 612492034 612492034
32812152 937684910 26472604 15138024
32812152 940608000 54129441 54129441
32812152 977715723 22004169 22004169
32812152 984902771 111815931 111815931
90376741 933420766 49418638 49418638
455608256 750343849 6011252 60112...

result:

ok both cnt and k values are correct (600 test cases)

Test #52:

score: 8
Accepted
time: 7ms
memory: 7704kb

input:

100
41
164471679 594663721 956038484 963512403
790222207 443981734 883656419 595443343
41976398 528225852 209034996 922983129
92091009 373944760 215144379 838721063
10047790 26867344 930066435 956836974
11965116 135400318 965175575 669129595
368279404 432022952 915025309 685238464
762467800 75599935...

output:

11
740608 789466432 10636402 10636402
740608 930066435 65237924 65237924
740608 997391887 5187568 5187568
1167089 997391887 174489249 174489249
1214997 998530226 49822362 49822362
1701070 997391887 122349359 84117500
10047790 997391887 512883169 246239696
10590845 978133159 2279222 2279222
10590845 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #53:

score: 8
Accepted
time: 9ms
memory: 10044kb

input:

10
238
827433368 455361468 931073143 563601246
695412598 51348550 774127521 90972787
413868960 288585848 529441784 435706642
75995447 488781026 238904858 510996539
553161642 787145041 941971547 816015404
695688946 270603529 717293951 273244339
545673970 627482813 663194435 731955805
53240795 5031594...

output:

162
1421265 422861224 5677942 5677942
1421265 968952128 26117020 22232505
6193753 86039503 16860101 16860101
12657185 48876069 74203212 74203212
13767241 232937517 34810125 34810125
13767241 315905533 30639975 30639975
13767241 452095572 37157227 37157227
13767241 888022619 10655705 10655705
1376724...

result:

ok both cnt and k values are correct (10 test cases)

Test #54:

score: 8
Accepted
time: 12ms
memory: 8588kb

input:

1
3000
779577246 113550692 796806802 144577371
555063665 168789612 556456022 208279836
989699791 915278787 993148233 935353583
71234844 784648743 73671161 788287576
386365412 1256289 391410967 32286737
557369341 902874707 580438528 916249525
902817951 39400010 905984218 70141132
353036272 551887085 ...

output:

2867
32002 26067471 29026108 29026108
32002 48133792 5926720 5926720
32002 53242839 1774454 1774454
89407 44596979 22634237 16952854
89407 60663723 20096295 20096295
89407 243460651 8774551 8774551
89407 255980438 1305278 1305278
131884 1122002 1283699 1283699
288234 6871527 6787706 6787706
606966 9...

result:

ok both cnt and k values are correct (1 test case)

Test #55:

score: 8
Accepted
time: 10ms
memory: 10340kb

input:

1
3000
902109757 74488828 909054417 75134209
168429059 187379984 171145779 187859645
267729284 38333291 269296881 39585780
815477940 133187834 817019136 133736922
463348149 746011165 466229532 750206017
196958192 282273581 199973184 283258040
245267764 441844812 247591640 443312999
19369450 42669194...

output:

3014
588267 1062775 6526881 6526881
1143030 1774644 2469173 2469173
2500062 8330698 127040 127040
2856143 4136494 1389198 1389198
2881169 5137827 1306400 1306400
4270255 5935491 383187 383187
4954453 5072129 871257 871257
5088635 6592831 485785 485785
5348090 6245078 3006217 3006217
5711962 5939541 ...

result:

ok both cnt and k values are correct (1 test case)

Test #56:

score: 8
Accepted
time: 6ms
memory: 9748kb

input:

600
1
501528377 159184115 517548802 416675300
2
429582490 460053006 451288014 497592547
211270635 348663233 298035362 942816967
16
367904247 129623700 504811760 936278049
18283111 527195899 934366007 606228577
669548433 31180264 701260246 973297717
182783844 19944463 262928264 811396997
299791482 64...

output:

1
501528377 517548802 257491186 257491186
2
211270635 298035362 594153735 594153735
429582490 451288014 37539542 37539542
16
6029045 939412523 37623343 37623343
6029045 988874143 247633221 247633221
18283111 934366007 79032679 79032679
37997791 875488366 19433874 19433874
74814641 284225486 835189 8...

result:

ok both cnt and k values are correct (600 test cases)

Test #57:

score: 8
Accepted
time: 5ms
memory: 9780kb

input:

100
124
696008948 406620926 760328046 486452854
145808382 19048427 344371386 671297983
219133863 309771326 560351057 315404114
487647387 32523240 741474072 212891113
27430250 825897431 700191359 848327939
72103314 100502055 632986937 112175907
146108093 199861173 181548807 492407247
820941950 248947...

output:

44
3038537 906575330 43173797 43173797
3645086 784177401 52120300 52120300
3645086 896431380 22687232 14323611
3645086 904487533 3940559 3940559
3645086 940236266 2666078 2666078
3645086 946341049 72656949 72656949
3645086 946932079 150493729 133194585
3645086 958754159 9615376 9615376
3645086 96333...

result:

ok both cnt and k values are correct (100 test cases)

Test #58:

score: 8
Accepted
time: 9ms
memory: 10172kb

input:

10
447
39090448 8145774 51490930 997777309
292212643 839479611 969731580 840183043
263643177 449201787 873263188 453892617
110809358 885203554 763112376 915253378
122217789 451787070 828691175 457066555
397076556 219134124 727302593 221734218
52292727 40188515 620299456 49072976
50483731 661334266 8...

output:

153
546986 999177048 24849160 24849160
546986 999229513 9082610 9082610
1647478 831347721 14462749 14462749
1647478 990442684 1363697 728643
2435187 999229513 15955691 15955691
4712403 988468966 9461354 9461354
4732054 916807426 4943053 4943053
4732054 919117533 375755 375755
5886705 11375170 160877...

result:

ok both cnt and k values are correct (10 test cases)

Test #59:

score: 8
Accepted
time: 11ms
memory: 10492kb

input:

1
3000
110119312 259026764 124431892 679200269
767052967 704218699 780056960 938684623
547278299 372841269 555642207 890080143
293168521 240459197 301803803 287905764
259041309 30814556 270503870 671494687
242861021 443932282 248000373 475267802
74274048 444781459 790236596 448009184
954942289 40769...

output:

82
27741 999957824 12925292 12925292
28665 999957824 1253290 1253290
90099 999957824 15170907 15170907
104837 999957824 20491965 20491965
124968 999586243 15881576 15881576
124968 999627848 555943 555943
343420 999627848 51053 51053
363717 999957824 10711235 10711235
439383 999957824 2551632 2551632...

result:

ok both cnt and k values are correct (1 test case)

Test #60:

score: 8
Accepted
time: 12ms
memory: 12168kb

input:

1
3000
971946336 668767541 974204808 881150816
570362913 863089378 665023751 863882876
516972851 73086602 522893868 980464375
729876516 199095021 733650449 353989029
507073429 130079407 510681878 892804000
429938221 452322512 686573829 453277528
844622582 623374461 844809594 796320131
36255405 32314...

output:

2352
151862 983897588 212780 212780
255990 999876318 2998553 2998553
503645 999316843 880398 880398
513707 908125768 1794000 1794000
829496 999180052 8039 8039
840080 998799793 1224306 1224306
878284 983423531 2925301 2925301
897242 983897588 1825418 1825418
908364 1266670 139738593 104709761
908364...

result:

ok both cnt and k values are correct (1 test case)

Test #61:

score: 8
Accepted
time: 10ms
memory: 12636kb

input:

1
2970
105923582 678052965 117335145 696929450
385350395 115466422 407700802 127413489
69439786 433349912 77432870 454709887
86730996 528257056 96712449 550345009
533821191 245957090 554387591 262497567
416278043 964462205 437929570 970260900
604496973 176842083 623347130 190029815
260505617 8765085...

output:

8801
135544 522568 11587394 11587394
135544 1242598 5201426 5201426
135544 1879861 2518280 2518280
135544 3832567 2957338 2957338
286307 854542 13166793 13166793
286307 1879861 3291715 3291715
286307 3401497 2447381 2447381
286307 4789862 2751893 2751893
400819 1242598 5897173 5897173
400819 2400920...

result:

ok both cnt and k values are correct (1 test case)

Test #62:

score: 8
Accepted
time: 12ms
memory: 10732kb

input:

1
3000
292291474 289036935 294062191 289813023
207772977 207365864 209009661 208253172
127195141 125293299 127433728 126965765
198517812 197240160 199501054 197924094
393971208 385872437 395225669 386584330
769011462 768665070 769872342 770006355
393028962 382891167 393701139 383486936
573529369 560...

output:

7498
135544 522568 599852 599852
135544 854542 780528 780528
135544 1514559 9803 9803
135544 2321301 134991 134991
286307 854542 547146 547146
286307 1455417 235167 235167
286307 3234485 119045 119045
400819 1142415 34117 34117
400819 1514559 126696 126696
725973 1455417 64986 64986
725973 2066115 9...

result:

ok both cnt and k values are correct (1 test case)

Test #63:

score: 8
Accepted
time: 3ms
memory: 10000kb

input:

1
3000
622151337 904250487 624327544 906751176
332357295 336203879 335396764 337636915
262174320 189577563 265153470 192102447
800127736 264535100 804780175 265994161
959063303 866156820 960823824 868854132
413103197 538652960 413973770 542406391
8693685 976801621 10410578 978409989
845801063 758524...

output:

1653
2351242 4928792 3911085 2371832
2761486 6352458 5472636 3034061
3047959 6445483 2757579 1665874
3198119 6695876 3786715 3786715
4325259 6728911 2720106 1924648
4928793 6911074 5461347 3454856
6352459 7150811 2581981 1433037
6445484 8693684 12823911 3641509
6695877 9217443 1027763 1027763
672891...

result:

ok both cnt and k values are correct (1 test case)

Test #64:

score: 8
Accepted
time: 11ms
memory: 8340kb

input:

1
3000
296245629 84966662 296246843 819941068
192122377 496998219 865857544 497138712
357650238 154226917 357699531 979571928
519566733 36478299 519581074 818075137
617301427 144260173 617530840 827624549
527504733 226032720 527567463 938021508
99434823 302014389 821051018 302065800
717623964 218996...

output:

3000
176922 913642568 281388 281388
186725 984975594 12112 12112
400819 967848601 43512 43512
854543 778954876 189701 189701
1242599 870337829 174207 174207
1455418 814380293 47415 47415
1514560 868566901 145559 145559
1578369 852334029 67747 67747
1879862 769244678 539098 539098
2249242 934840215 8...

result:

ok both cnt and k values are correct (1 test case)

Test #65:

score: 8
Accepted
time: 9ms
memory: 12540kb

input:

1
3000
150315423 146488966 651599268 646032536
107186318 103110579 612903730 600240624
67159089 62241392 569617307 556873920
102076584 97532926 608161993 596276632
197502856 193893433 701350208 696458461
386560432 380745307 884300335 885381995
197074993 192780164 700947555 695621790
285971830 284184...

output:

5999
135544 508215924 34117 34117
135544 508303448 126696 126696
135544 508459118 9803 9803
135544 508557842 509709 509709
135544 508703360 90143 90143
135544 508923981 134991 134991
135544 509048224 780528 780528
135544 509084973 272079 272079
135544 509087100 275067 275067
135544 509396079 119045 ...

result:

ok both cnt and k values are correct (1 test case)

Test #66:

score: 8
Accepted
time: 8ms
memory: 10388kb

input:

1
3000
150315423 176922 858097629 291163599
107186318 176922 895957005 212257949
67159089 176922 938114046 128041368
102076584 176922 899469961 201358880
197502856 176922 807382812 386338092
386560432 176922 621918658 774989807
197074993 176922 808612029 384447042
285971830 176922 719709856 56417180...

output:

3000
135544 999877008 9803 9803
286307 999599162 2062517 2062517
400819 999411306 119045 119045
522569 999272576 235167 235167
725973 998965389 50069 50069
817540 998826087 33480 33480
854543 998639333 135311 135311
1142416 998284629 138408 138408
1242599 998058783 116828 116828
1380640 997828184 25...

result:

ok both cnt and k values are correct (1 test case)

Test #67:

score: 8
Accepted
time: 6ms
memory: 9764kb

input:

300
3
412731850 762080506 447350261 995356798
692044403 305552026 809575693 631554118
611205314 749186027 808463865 978588447
3
167571887 57590827 195540178 943572063
195540179 168354502 440093613 652044667
568722191 640319784 580812853 943572063
8
214411380 376061512 261869523 583358129
551209559 4...

output:

3
412731850 447350261 233276293 233276293
611205314 808463865 229402421 229402421
692044403 809575693 326002093 326002093
3
167571887 195540178 402291071 291527396
167571887 440093613 483690166 483690166
568722191 580812853 303252280 303252280
8
155445006 190740538 151046051 151046051
214411380 2618...

result:

ok both cnt and k values are correct (300 test cases)

Test #68:

score: 8
Accepted
time: 10ms
memory: 10580kb

input:

1
3000
419966204 107588217 420675095 577095540
604052280 171694065 604550292 918959085
637355710 91006520 638740388 672019717
847628309 147902999 848107054 985616287
546377257 180999565 546884304 770617877
13200777 157585166 13384316 696800849
536727598 167451439 537722109 860975756
320443897 247703...

output:

5311
168083 232236 78219404 60207517
168083 573142 236826746 236826746
168083 2595984 24581916 24581916
168083 3663190 7270109 7270109
168083 3905268 103401267 103401267
168083 4227224 39975386 39975386
168083 8334109 11912702 11912702
168083 13067460 6538722 6538722
168083 14758306 11036423 1103642...

result:

ok both cnt and k values are correct (1 test case)

Test #69:

score: 8
Accepted
time: 10ms
memory: 10484kb

input:

1
3000
484488994 241313647 484978572 740151157
321923757 160209059 321933730 660957002
720702569 358787792 720778781 851436263
985660645 488274160 985696651 993080177
351338383 175709729 351462718 674223800
227695060 110914428 228410230 609040461
186990312 88644094 187184883 586703759
156199260 7519...

output:

3000
280744 320611 493999243 493999243
555213 908610 494200286 494200286
1585259 1670700 494574276 494574276
1903913 2090006 494571819 494571819
2744416 2801804 494562745 494562745
2880228 2965576 494744032 494744032
2998382 3084393 494805743 494805743
3322790 3361403 494984136 494984136
3432442 352...

result:

ok both cnt and k values are correct (1 test case)

Test #70:

score: 8
Accepted
time: 12ms
memory: 10440kb

input:

1
3000
554029310 322889864 555335996 363300476
618124950 515264390 619830606 539636481
945131341 678433343 946366015 801801046
321437175 197818238 999703786 207027423
178063128 978453107 180072749 999724846
550334552 326953822 553050446 367057606
207960856 78090693 208798754 79998732
976144132 67659...

output:

2974
280910 959805 1470384 1271776
280910 1981919 6908048 6908048
280910 3897916 710835 710835
280910 12333399 3406735 3406735
280910 13287742 768634 768634
280910 13573204 1276402 1276402
280910 15748145 443758 443758
280910 56128662 104451809 104451809
280910 58904570 33283621 33283621
280910 8628...

result:

ok both cnt and k values are correct (1 test case)

Test #71:

score: 8
Accepted
time: 15ms
memory: 10572kb

input:

1
3000
437711693 202880777 438214686 716814698
904915022 375460630 905438053 880160333
596291294 296121770 596894037 804984901
313716523 408950616 314420877 917557316
312107425 157342384 312299411 669632053
401458456 416701868 401771522 923775204
336958340 361334497 337265605 868573497
144605903 447...

output:

5999
94223 198023 177299972 177299972
94223 441193 5871230 5871230
94223 2619711 11860923 11860923
94223 3486088 91741986 91741986
94223 3926930 197718 197718
94223 4138539 63063586 63063586
94223 4899399 8736885 8736885
94223 5034381 27316455 27316455
94223 6133080 14399205 14399205
94223 6387466 1...

result:

ok both cnt and k values are correct (1 test case)

Test #72:

score: 8
Accepted
time: 15ms
memory: 12412kb

input:

1
3000
211798312 48831011 211901153 554218991
756022166 342077073 756064352 832618075
95994627 485343139 96025530 973237730
441237907 432058307 442129088 917717725
180594723 454740620 181153546 944671766
611215909 499561239 611465834 988758772
325106016 498725639 325464441 987761059
334402332 502183...

output:

5999
44602 530616 377709974 377709974
44602 586623 60725059 60725059
44602 2458327 32468201 32468201
44602 13279148 6381787 6381787
44602 31709989 5749993 5749993
44602 59420657 1561941 1561941
44602 63029484 1168438 1168438
44602 66069242 2411104 2411104
44602 754761369 160483 160483
44602 99996547...

result:

ok both cnt and k values are correct (1 test case)

Test #73:

score: 8
Accepted
time: 12ms
memory: 10384kb

input:

1
3000
168002679 419672715 828891381 584090794
887774474 179819612 887809459 925391095
442335 527314107 999087022 527510523
651817501 70116482 651886543 791497342
553050560 224864047 553524529 838276351
223936417 125913491 223965520 962740092
442335 326830257 999087022 326853668
442335 658496021 999...

output:

2250
287938 442334 591146264 131227765
287938 999260154 124738149 908211
594400 738665 554576689 173994188
594400 998929868 227813 112021
1904807 2374549 652984624 216891314
1904807 997425390 73083 57623
2564987 2795360 821833775 250572026
2564987 997286477 435673 406273
3509656 3800372 590787163 15...

result:

ok both cnt and k values are correct (1 test case)

Test #74:

score: 8
Accepted
time: 6ms
memory: 10448kb

input:

1
3000
244189659 583874952 717444194 583920538
142022436 897572234 142109930 919987591
896395318 201664208 896650292 550720852
800353592 253143872 800359323 994393070
515406999 447162848 515589092 906322784
44393642 124165444 69439785 124812543
245881985 138315052 245957089 581057310
263302919 34372...

output:

3000
16109 176921 497867942 497867942
186725 400818 236820868 236820868
921568 1242598 29938856 29938856
1455418 882779184 73142 73142
1514560 1578368 459565895 459565895
1702096 92346013 1619 1619
2249242 822352758 46363 46363
2368287 469908580 605607 605607
2603454 595970718 31908 31908
2653523 38...

result:

ok both cnt and k values are correct (1 test case)

Subtask #6:

score: 4
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #75:

score: 4
Accepted
time: 13ms
memory: 9808kb

input:

2000
7
215876127 470007458 613893220 911007147
284388053 203125736 665499619 725939612
7877071 193808040 984009136 748527668
273037808 520276027 967363938 843310023
453701723 710895382 518016796 905032221
201303578 315066618 942949854 763636396
111345967 23952559 386962869 93102197
1
46167999 308720...

output:

5
7877071 984009136 554719629 554719629
111345967 386962869 69149639 69149639
201303578 967363938 15108728 15108728
215876127 613893220 67697124 67697124
215876127 967363938 79673627 79673627
1
46167999 979243146 256345381 256345381
6
17732718 926653304 6591 6591
17732718 971322133 436680033 4366800...

result:

ok both cnt and k values are correct (2000 test cases)

Test #76:

score: 4
Accepted
time: 21ms
memory: 7728kb

input:

200
16
508834774 47858542 956984214 798001552
165996646 653524439 379959396 922739005
168777994 272227737 623118167 744752115
291560477 236885287 895022203 563354004
123660195 266306998 559788409 707973927
842461703 99502746 919982139 214457614
822606599 251779538 836594018 786496032
856619561 13209...

output:

10
616839 565774536 51683744 51683744
616839 734823397 12382483 12382483
616839 874563332 18334600 18334600
616839 886347341 91614890 91614890
616839 949562155 42894947 42894947
616839 956984214 96773582 48758584
616839 966680031 645433375 539814088
616839 998937315 7936054 7936054
73606400 94956215...

result:

ok both cnt and k values are correct (200 test cases)

Test #77:

score: 4
Accepted
time: 25ms
memory: 10036kb

input:

20
5
539873839 414195049 545901230 440457441
516123415 826384235 578023798 918505702
115258535 739341066 200324212 847284266
139940515 295604723 173784011 330208497
687285094 624702623 752105752 711936127
1
727264856 872075598 918660818 881627325
415
213590968 772256675 310940177 801475663
490198409...

output:

5
115258535 200324212 107943201 107943201
139940515 173784011 34603775 34603775
516123415 578023798 92121468 92121468
539873839 545901230 26262393 26262393
687285094 752105752 87233505 87233505
1
727264856 918660818 9551728 9551728
154
3487186 979826944 14493914 14493914
5239362 248833091 7629872 76...

result:

ok both cnt and k values are correct (20 test cases)

Test #78:

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

input:

1
10000
119486975 512501398 123124590 549355545
535340496 80005284 572874443 90794488
404338690 674521514 411180313 677882864
392344158 160116159 396379992 164795832
755990028 713464555 758790668 715654270
591543609 481313000 608012999 491591118
57522710 758844118 65471954 760833828
193554234 486105...

output:

2595
9778 165574026 4063686 4063686
9778 166974748 14702499 12850454
9778 167170194 236347 236347
9778 184458634 731401 731401
9778 191835839 1972761 1972761
9778 350854053 2029566 2029566
9778 357259024 227123 227123
9778 478969940 3279749 3279749
9778 484624471 2303478 2303478
9778 492425486 24658...

result:

ok both cnt and k values are correct (1 test case)

Test #79:

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

input:

1
10000
623792907 923860788 625488136 925182547
502415834 653228731 508365810 657548599
283951589 799919901 284945198 800949129
876973704 366069193 878990131 368333191
37836518 907786460 43637619 910574658
390544463 780389824 391930175 781388726
881275220 805667066 884908128 805952430
333013762 4469...

output:

10122
177158 1816037 4318094 4318094
274899 286917 5159763 5159763
344716 726105 941403 941403
493717 1161225 1343856 1343856
607919 1239427 2131513 2131513
620560 4871090 2349957 2349957
647559 6497928 221644 221644
658541 754692 447299 447299
711045 1494261 2203004 2203004
718574 2332570 2939111 2...

result:

ok both cnt and k values are correct (1 test case)

Test #80:

score: 4
Accepted
time: 11ms
memory: 10012kb

input:

2000
4
299533715 186073818 489954858 207737299
571883500 854829264 743016384 957702442
826713144 205559048 949844846 452353831
458166859 218445721 934548403 536280200
6
54642998 155686891 954261442 435943197
3157386 685418571 996292188 940719436
279268783 387507386 334025976 918930091
28193918 84992...

output:

5
299533715 489954858 21663482 21663482
458166859 934548403 83926369 83926369
458166859 949844846 233908111 233908111
571883500 743016384 102873179 102873179
826713144 949844846 12886673 12886673
5
3157386 996292188 255300866 255300866
28193918 195014583 320170190 249475373
28193918 954261442 280256...

result:

ok both cnt and k values are correct (2000 test cases)

Test #81:

score: 4
Accepted
time: 23ms
memory: 9808kb

input:

200
25
443715011 110860973 514809665 290340298
956340385 115849757 962917350 938548447
155346281 724894196 912756445 915252572
105831103 56849036 686422880 119318836
330729448 246899715 462123088 254464381
118519260 842207391 990242709 857329261
176780036 484965561 696820090 715181531
637328443 1358...

output:

21
1011405 144351498 137946907 53573219
1011405 226492020 46804473 31182287
1011405 681983984 8095766 8095766
1011405 696820090 51375120 33468075
1011405 796144565 38418462 38418462
1011405 912756445 137757276 79833965
1011405 935649677 231763002 231763002
1011405 940856772 37479230 37479230
1011405...

result:

ok both cnt and k values are correct (200 test cases)

Test #82:

score: 4
Accepted
time: 22ms
memory: 10056kb

input:

20
70
39598374 782765389 767351418 782797024
293568642 971231780 790927835 971697998
251675740 499943828 491166578 510083374
787852962 21335739 791957607 909977225
170600641 125082689 188296350 681683385
30637585 162298234 873139510 178689514
24600714 966409063 223971253 975677567
794720299 10639553...

output:

71
3202368 950921346 10779378 10779378
8144291 883661763 7631287 7631287
14689217 950921346 18436119 18436119
24600714 223971253 9268505 9268505
27426696 950921346 16567797 16567797
29540694 32609615 682607901 429327450
29540694 883661763 12907052 12907052
39598374 776739225 31636 31636
42974712 626...

result:

ok both cnt and k values are correct (20 test cases)

Test #83:

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

input:

1
10000
226719490 54444770 244007815 975134926
646679967 48193282 658183844 591369369
300378514 419347162 843443769 420054277
507357424 58454229 524803487 978028236
131823088 135622489 151539726 951766164
228886316 946694017 484880187 965009067
166155317 104890842 171253030 698883963
635908085 12497...

output:

123
1800 999409512 4692482 4692482
9502 999833528 1011101 1011101
16302 999279475 8782675 8782675
50039 999626231 5446846 5446846
57668 999612993 2140535 2140535
58695 999279475 2034258 2034258
72308 999818577 973380 973380
78107 999958326 9786044 9786044
100269 999853106 1618932 1618932
174715 9992...

result:

ok both cnt and k values are correct (1 test case)

Test #84:

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

input:

1
10000
183642806 713707235 963404138 714168414
341477220 549768516 398289301 550223898
887361450 178603489 889115107 996042560
401035134 698602445 618799322 699089832
70178521 314619224 73231530 495403017
234628085 605476847 931622270 606984637
136414660 2041378 141880522 919165373
23470335 9083361...

output:

706
33239 999113130 968089 968089
54726 260255003 1160486 720365
54726 797527337 215246 215246
54726 847148683 704487 704487
54726 885630189 15612 15612
54726 941076559 135128 135128
54726 973039215 1043061 834066
54726 986331884 1846164 1846164
54726 997373732 367481 367481
60297 999113130 3692259 ...

result:

ok both cnt and k values are correct (1 test case)

Test #85:

score: 4
Accepted
time: 35ms
memory: 13008kb

input:

1
10000
26760771 509525465 220407549 509999073
43997994 362425199 765020506 362564712
453241302 625749828 453273922 862606943
480108931 6925023 480350910 815073840
84029231 60424757 84076696 714326754
78595572 26886778 79116683 291807310
801469786 12653118 801518412 431383374
252192175 336225554 252...

output:

10116
70329 950624193 23823 23823
109867 949286328 54295 54295
129690 420839003 66298 66298
138633 999834156 171367 171367
167706 796901534 294 294
188893 749133637 69206 69206
188893 897122438 98792 98792
194344 211821 736077730 261347912
194344 965598432 1966 1966
223960 999486232 52764 52764
2564...

result:

ok both cnt and k values are correct (1 test case)

Test #86:

score: 4
Accepted
time: 48ms
memory: 17116kb

input:

1
10000
101956501 326248096 108377545 336979722
355601543 831873909 365596519 838309525
728466910 64277333 737757321 69011745
480260951 68233603 490833464 72445083
371745182 829950404 382298578 836792782
792416448 712540750 800711776 722373935
533669316 11574697 544714887 13750965
757329701 91777062...

output:

29800
63518 572384 6328327 6328327
63518 751138 2081370 2081370
63518 972640 1362465 1362465
63518 1429542 927736 927736
130752 592148 5388372 5388372
130752 972640 1402379 1402379
130752 1217525 760650 760650
130752 1925648 1039021 1039021
472324 751138 3711972 3711972
472324 1089534 2350315 235031...

result:

ok both cnt and k values are correct (1 test case)

Test #87:

score: 4
Accepted
time: 28ms
memory: 13548kb

input:

1
10000
116622525 114166382 117078096 114351291
599996708 593659256 600151591 593946826
380264483 374554415 380430258 374759910
221695201 214538999 222038396 214800023
610281203 604098594 610701004 604209147
815431681 808671314 815735989 808916656
160233425 155686327 160544574 155906519
939214443 93...

output:

24998
63518 572384 93975 93975
63518 592148 14660 14660
63518 904416 35930 35930
63518 1048312 32332 32332
130752 592148 276968 276968
130752 899283 13114 13114
130752 1211207 17316 17316
472324 593432 1287 1287
472324 904416 37982 37982
578703 899283 76022 76022
578703 984881 85216 85216
578703 142...

result:

ok both cnt and k values are correct (1 test case)

Test #88:

score: 4
Accepted
time: 21ms
memory: 8168kb

input:

1
10000
144806170 991372898 146723091 992376061
903821246 937173524 905520747 938728103
681650459 693772735 683241713 695679814
851048281 715291957 853719342 716519498
747236946 829231169 749270797 830347720
447133566 395066079 448450687 397243507
417668029 744858410 420216520 746056245
770204142 43...

output:

3382
9835 1587706 7029166 1667510
404016 2727369 4852587 2905720
545297 2831949 2552866 1737721
1294696 3982674 1006623 1006623
1386093 4222675 9519647 4197238
1587707 4333720 5763627 3353747
2727370 4466147 4259743 2699982
2831950 4709095 9304706 2482905
3982675 4787739 5725427 2454898
4222676 5413...

result:

ok both cnt and k values are correct (1 test case)

Test #89:

score: 4
Accepted
time: 32ms
memory: 12860kb

input:

1
10000
382944728 120986188 383043291 871090012
125318442 729710498 964784540 729761477
53265696 693163118 976005003 693191853
101428969 300104128 977422864 300156702
107174560 585443157 823644118 585537378
306482003 23521128 306483674 879047623
429102984 47002813 429129713 936155952
322125826 93840...

output:

10000
68174 979634239 18387 18387
104104 790430684 11774 11774
186277 805735628 16804 16804
198079 796711679 143263 143263
230411 917267193 4588 4588
472324 973839114 382 382
510388 802070594 22494 22494
522039 843085492 19236 19236
539355 825585132 77337 77337
587131 895921869 49760 49760
593433 82...

result:

ok both cnt and k values are correct (1 test case)

Test #90:

score: 4
Accepted
time: 46ms
memory: 16204kb

input:

1
10000
58574154 58927860 562666801 553328695
300749936 294057246 801700741 794597486
189892300 184401063 693330947 683527756
111704129 109623195 613602003 606214016
305995001 299085839 806638955 798916911
407244006 401355082 910116964 901787990
79629462 79694684 583237431 575170809
470707905 461075...

output:

19999
63518 501932560 1287 1287
63518 501933473 37982 37982
63518 502018984 35930 35930
63518 502060793 82173 82173
63518 502083549 11802 11802
63518 502192710 32332 32332
63518 502196922 14660 14660
63518 502200609 265317 265317
63518 502217706 11651 11651
63518 502318913 17316 17316
63518 50237011...

result:

ok both cnt and k values are correct (1 test case)

Test #91:

score: 4
Accepted
time: 22ms
memory: 12628kb

input:

1
10000
58574154 68174 944276093 114621634
300749936 68174 703391197 589595812
189892300 68174 811603513 370994377
111704129 68174 892726841 214065835
305995001 68174 698762737 599567003
407244006 68174 595237848 807596369
79629462 68174 922735292 155559681
470707905 68174 534806894 933153230
111551...

output:

10000
63518 999990812 35930 35930
130752 999986632 82173 82173
472324 999963542 11802 11802
572385 999958532 32332 32332
578703 999855132 279977 279977
587131 999854541 11651 11651
592149 999745627 17316 17316
593433 999716805 87387 87387
751139 999491688 36018 36018
884382 999484873 164618 164618
8...

result:

ok both cnt and k values are correct (1 test case)

Test #92:

score: 4
Accepted
time: 13ms
memory: 9836kb

input:

1000
13
180808647 405437034 418517856 448394373
249501753 474248873 418517856 541608158
833581705 399692047 864615804 454822373
457656419 133030389 616458945 181867472
9252818 84469378 113807258 417478628
568160570 320637592 622889068 853064904
830990630 425847966 832838536 853064904
261410126 83540...

output:

13
9252818 113807258 333009251 333009251
180808647 418517856 42957340 42957340
215282029 249501752 289335039 289335039
215282029 418517856 67359286 67359286
261410126 350132773 17656994 17656994
457656419 616458945 48837084 48837084
522618916 647279217 44335135 44335135
545787608 615979307 32792087 ...

result:

ok both cnt and k values are correct (1000 test cases)

Test #93:

score: 4
Accepted
time: 53ms
memory: 14472kb

input:

1
10000
821643826 145881451 821648751 917155797
510218656 445969910 510329983 595822101
233158152 170780587 233229532 728541790
554735301 95465681 554800586 754376850
804388427 322017402 804442434 847368876
591595701 26138691 591636992 957172945
118426528 63096733 118480994 934703779
531486304 23754...

output:

17471
175562 316418 60208195 60208195
175562 382627 103422738 103422738
175562 632317 10129062 10129062
175562 934250 20390835 20390835
175562 1912988 31428892 31428892
175562 3194560 10434797 10434797
175562 3464645 13132439 13132439
175562 5815613 2651062 2651062
175562 5831009 5309003 5309003
175...

result:

ok both cnt and k values are correct (1 test case)

Test #94:

score: 4
Accepted
time: 36ms
memory: 11860kb

input:

1
10000
314229974 910118172 316727684 941022872
530843321 198181317 650614213 199160453
88907588 25740697 90109431 29166060
176440317 589492533 177065325 599282407
295934990 861713973 300368509 894100970
548302951 308776447 662231523 309594329
933926271 774157340 937055925 819252436
422366103 530364...

output:

5145
42565 1610647 244390 244390
42565 1956201 4195348 4195348
42565 2329729 1616589 1616589
42565 2611572 16462083 16462083
42565 2911620 892857 892857
42565 3064588 972126 972126
42565 3905121 9086447 9086447
42565 4189847 1105622 1105622
42565 4774803 2245214 2245214
42565 5051938 215278 215278
4...

result:

ok both cnt and k values are correct (1 test case)

Test #95:

score: 4
Accepted
time: 49ms
memory: 16280kb

input:

1
10000
559502398 187684124 559672824 682681879
287569830 187999693 287749399 683083708
12868043 161801031 13006973 659034255
335875565 465967532 336151724 961836819
996251067 498769417 996496540 998267964
293745143 441144898 293841476 934355621
465270741 41757151 465456619 544228956
195198332 17722...

output:

19999
195443 202761 88438590 88438590
195443 457480 351686442 351686442
195443 1210901 14274723 14274723
195443 2460842 20702936 20702936
195443 5956258 10663144 10663144
195443 6096552 150045 150045
195443 14920279 1910951 1910951
195443 21715059 7838303 7838303
195443 60417280 1365792 1365792
1954...

result:

ok both cnt and k values are correct (1 test case)

Test #96:

score: 4
Accepted
time: 43ms
memory: 15492kb

input:

1
10000
150361680 423624410 846990556 575553734
148390 572255629 999816227 572311463
66902833 99689284 67003032 900880741
201816776 99816580 201857787 974917929
454900370 219355565 455127411 969473483
148390 475440349 999816227 475506152
308064260 348095077 690590758 649055903
71021269 32907585 7103...

output:

7500
65552 148389 755823160 245227978
65552 999912410 124569642 375112
223762 276658 508686824 75571496
223762 999643897 146150 55225
523715 561912 536214473 105044024
523715 999139632 41198 33602
648803 750222 624266730 201836447
648803 998955473 169515 74670
824389 910995 690720171 179323357
82438...

result:

ok both cnt and k values are correct (1 test case)

Test #97:

score: 4
Accepted
time: 25ms
memory: 9892kb

input:

100
39
673075390 35517264 687359034 751017655
714798907 511581145 840457700 530034413
902879898 33444143 905899408 760565503
277448704 450836711 700944988 492589600
690258259 537317632 693845019 562028735
289660877 503155682 290102566 611145599
580745014 368438581 628778111 939948247
823660989 26726...

output:

39
52718368 244940102 1554758 1554758
63742756 438646335 13131443 13131443
112348000 113443032 356600366 355851586
136900743 159551329 763055039 604737201
161510360 776228138 39806360 39806360
212501304 398713668 14372974 14372974
230948025 236109975 515419556 377538123
237878383 912254331 18202074 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #98:

score: 4
Accepted
time: 36ms
memory: 12728kb

input:

1
10000
383499069 44123516 383504878 980798372
755419079 367836562 755442323 913300122
332720689 2409965 332767454 170041154
290110665 123113763 290159291 843601333
490817673 680100475 490834257 813570788
475923516 760908497 537867972 760913186
2045831 216187072 587247261 216210660
329255674 8832264...

output:

10000
28905 30191 136054681 136054681
68174 768797539 11835 11835
104104 629323956 13519 13519
186277 683013746 186730 186730
198079 51876804 80995 80995
230411 857600166 67592 67592
472324 143187034 126141 126141
510388 766419983 125945 125945
522039 553348110 21102 21102
539355 490476191 120341 12...

result:

ok both cnt and k values are correct (1 test case)

Subtask #7:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #99:

score: 8
Accepted
time: 316ms
memory: 10020kb

input:

20000
6
173886237 353181314 449029916 798852950
120080534 335969056 826020605 969279947
162869623 384399321 828371995 535069141
180129351 505278254 946408768 518073931
230473571 88258844 408204299 349206116
379867689 241865855 937662092 374616584
11
73434832 94039910 770347171 461172247
102731809 17...

output:

6
120080534 826020605 443993542 434210806
120080534 828371995 137874143 120878933
120080534 937662092 38647529 38647529
120080534 946408768 12795678 12795678
230473571 408204299 153607011 153607011
230473571 937662092 94103201 94103201
8
17069148 951827495 215295045 215295045
17069148 963790676 1430...

result:

ok both cnt and k values are correct (20000 test cases)

Test #100:

score: 8
Accepted
time: 429ms
memory: 11940kb

input:

2000
55
241418510 54535907 682093792 629523011
434033850 623234767 896638645 962847495
149777619 349534842 548934602 625506193
447327366 449137668 558014189 906392965
219183093 655463108 992327359 841637218
228165390 295338457 887739142 970854481
364688919 145979006 638223007 724147825
432018923 301...

output:

14
7786053 960995550 230116390 135532177
7786053 980483527 300675037 300675037
7786053 982952108 105068592 105068592
7786053 992327359 91592783 91592783
28210835 992327359 23466333 23466333
28655223 976541537 58304042 58304042
28655223 992327359 71114995 71114995
46974115 976541537 28285035 28285035...

result:

ok both cnt and k values are correct (2000 test cases)

Test #101:

score: 8
Accepted
time: 565ms
memory: 12156kb

input:

200
516
465814817 791034948 800516281 976915304
291843458 80138384 666375012 393128262
288408742 175206116 588997253 661850969
353289970 268979197 676701271 749323006
103463193 599205175 530250304 767434665
8934195 742036 580179882 10821902
450079823 530657684 706163122 696277244
140910931 152450380...

output:

25
147063 984926620 5268144 5268144
147063 992771707 189782111 189782111
147063 994102964 178454338 178454338
147063 999139147 218016560 218016560
2829900 984926620 5309987 5309987
4959754 999139147 10214634 10214634
4959754 999340618 204877599 204877599
6953199 994102964 17316855 17316855
6953199 9...

result:

ok both cnt and k values are correct (200 test cases)

Test #102:

score: 8
Accepted
time: 724ms
memory: 16932kb

input:

20
12540
301353987 706214696 945169903 780479475
365888444 91592550 971730222 431087551
444216830 408713077 566797024 757226958
275296371 301834884 919296762 316430559
311571577 406059059 572027697 483953345
471569991 78769910 533538007 217325243
31797560 756056993 590609825 787768551
196065710 1106...

output:

38
27442 999823150 186996797 80443010
27442 999827953 64876097 64876097
27442 999925279 1826489 1826489
113943 999823150 94452070 94452070
129703 999823150 361627836 287615383
206531 999823150 66775139 46966641
377553 999823150 84333579 84333579
651573 999823150 49461676 49461676
1671335 992893759 2...

result:

ok both cnt and k values are correct (20 test cases)

Test #103:

score: 8
Accepted
time: 1066ms
memory: 57844kb

input:

1
200000
359179379 309962164 769369034 802265130
294331407 662518810 884480291 974301323
100360883 419154355 772560934 757140648
277615018 238821750 526698374 407658557
444794039 7894899 847757827 341022500
275055233 703072 733577589 65074751
298662524 270967635 850311240 757490616
401174738 7557491...

output:

40
1911 999942684 9947900 8720701
1911 999961790 2761121 2761121
1911 999995394 482657853 482657853
6488 999995212 89799815 89799815
6488 999995394 254120435 254120435
21123 999995212 31742683 31742683
44538 999936250 13992446 13992446
44538 999967190 3294415 3294415
44538 999995212 77831948 7783194...

result:

ok both cnt and k values are correct (1 test case)

Test #104:

score: 8
Accepted
time: 331ms
memory: 9820kb

input:

20000
17
661707893 455359399 726025145 958829240
560352967 214346317 783354532 594624977
178207621 514742703 708607464 656651817
557205452 26644427 675707759 692940789
660563502 64192690 735187088 272138839
527389941 26812779 663092653 937066900
391387089 83563321 892155943 566570597
290859600 27034...

output:

17
39156950 965928905 80406416 80406416
122987590 930763335 116975865 116975865
122987590 965928905 47551780 47551780
178207621 930763335 1620325 1620325
178207621 994097551 100813430 100813430
180640657 965928905 53680738 53680738
245189569 994097551 155508008 155508008
290139455 802669006 69753218...

result:

ok both cnt and k values are correct (20000 test cases)

Test #105:

score: 8
Accepted
time: 488ms
memory: 8112kb

input:

2000
468
164657186 252747321 805877716 310822073
397382271 190679634 567923170 238846939
205077640 198289170 777719886 543074314
450089855 63345833 575725215 411866802
200451749 205994203 783966951 635577964
290971085 112783870 669015383 193569535
17728995 712996651 985808140 721325373
199397537 317...

output:

354
306155 999149359 5719009 5719009
331091 999149359 4613174 4506981
331091 999405604 41515121 41515121
2045268 998502045 10707186 10707186
2246615 994679785 13532445 13532445
2246615 997417564 9221921 9221921
2246615 997659498 18355356 18355356
2246615 998502045 34342462 34342462
2981718 993132083...

result:

ok both cnt and k values are correct (2000 test cases)

Test #106:

score: 8
Accepted
time: 621ms
memory: 12304kb

input:

200
123
418469291 159242840 773794574 996946105
92842336 490432484 576432000 603770491
410584197 60329148 653518751 884078944
207429131 224033027 819004604 388894210
149379974 316438823 841664901 455779232
332059795 331814063 850856560 731914216
234671397 178870358 744684673 279458143
350882917 9550...

output:

109
6161470 988510546 2455898 2455898
6161470 989306289 11873208 11873208
20046686 994369626 15841375 15841375
34465391 982442753 10419768 10419768
34465391 982818378 17213348 17213348
34465391 988510546 27431358 27431358
34465391 989306289 35081779 35081779
34465391 994369626 83488435 79524647
3446...

result:

ok both cnt and k values are correct (200 test cases)

Test #107:

score: 8
Accepted
time: 797ms
memory: 17884kb

input:

20
6532
93673686 441163945 884755917 659467781
205763137 222201115 698796622 929897878
74327172 499670814 929311406 677190206
381863766 68660396 592887722 975385710
200555522 231080041 800986800 819362705
174928447 404979168 647046967 528541219
328690679 163006985 607779963 800971138
93059035 442180...

output:

4834
54816 998878000 739553 739553
72509 999652050 715439 715439
72509 999854044 4802658 4802658
133516 998380724 136465 136465
133516 998878000 2621922 1547826
133516 999448839 5908320 5908320
133516 999609592 1547845 1547845
133516 999652050 1344960 1344960
133516 999854044 3348033 3348033
188493 ...

result:

ok both cnt and k values are correct (20 test cases)

Test #108:

score: 8
Accepted
time: 1100ms
memory: 65080kb

input:

1
200000
152019990 313657093 679860216 654772502
82246204 578585184 951825273 650520825
402490595 123134733 701366711 469810396
142125372 560514786 676759897 942320227
369945830 383416783 828511385 695522914
19640586 720436240 980392911 729781003
468143163 60970590 624236470 269175829
84829701 46317...

output:

149924
2780 999993753 186659 186659
2780 999999153 792974 792974
3757 999993753 248491 248491
3757 999999153 774438 774438
4389 999989771 346843 249373
4389 999994088 937120 937120
4389 999999153 1454246 1454246
4658 999986465 208060 208060
4658 999989771 629510 388603
4658 999994088 456418 456418
6...

result:

ok both cnt and k values are correct (1 test case)

Test #109:

score: 8
Accepted
time: 1112ms
memory: 80480kb

input:

1
200000
329504270 327784370 829144276 828533486
81260778 81359901 582367912 580571190
349071334 347424571 848519316 848280229
80865912 80992922 581954350 580257151
339848627 338127372 839545443 839208098
134018067 134234402 635423207 633866502
472545174 470538507 972636347 972622663
158167667 15837...

output:

399999
3296 500114627 5771 5771
3296 500114901 987 987
3296 500121381 2562 2562
3296 500124428 3649 3649
3296 500126446 2859 2859
3296 500127996 143 143
3296 500132626 687 687
3296 500138217 485 485
3296 500140416 5126 5126
3296 500145368 1864 1864
3296 500145708 4107 4107
3296 500146005 345 345
329...

result:

ok both cnt and k values are correct (1 test case)

Test #110:

score: 8
Accepted
time: 623ms
memory: 49812kb

input:

1
200000
329504270 53 670960317 657276994
81260778 53 918324373 161244858
349071334 53 651597304 696636561
80865912 53 918700186 160606951
339848627 53 660411695 678191241
134018067 53 864992856 267139842
472545174 53 527819642 945098858
158167667 53 840351796 316506787
461637553 53 538737546 923398...

output:

200000
3296 999998433 5771 5771
5649 999995513 987 987
6693 999991952 2562 2562
13332 999988741 3649 3649
14341 999987930 2859 2859
14722 999983330 1315 1315
18623 999980688 5126 5126
19539 999974661 1864 1864
27457 999971330 4107 4107
28407 999971174 7686 7686
31154 999970367 229 229
32251 99996991...

result:

ok both cnt and k values are correct (1 test case)

Subtask #8:

score: 8
Accepted

Dependency #2:

100%
Accepted

Test #111:

score: 8
Accepted
time: 216ms
memory: 9848kb

input:

20000
17
82047827 1 579122002 290967735
146955747 1 786154187 528202919
285040469 1 687847131 804183670
511179528 1 817252362 924393587
102752572 1 636684528 623900655
375844037 1 885591258 337183695
220728877 1 827937470 786014580
344907350 1 769216344 40474719
257293967 1 483416094 825594821
50112...

output:

8
41135287 949313309 3363028 3363028
82047827 949313309 287604707 287604707
102752572 949313309 332932920 332932920
197600837 925662060 46166222 46166222
197600837 949313309 129273545 129273545
257293967 925662060 26254399 26254399
388725569 925662060 52405587 52405587
511179528 817252362 46393179 4...

result:

ok both cnt and k values are correct (20000 test cases)

Test #112:

score: 8
Accepted
time: 275ms
memory: 7776kb

input:

2000
62
626182256 1 669768446 727486940
62397245 1 697986309 69778830
832713591 1 991815781 871302693
450403090 1 723186148 868152924
5767854 1 906756620 3748899
199876095 1 281482811 468351213
147095487 1 827063723 249740968
454831524 1 478760129 197859256
536265753 1 660644097 706374085
493918933 ...

output:

38
5767854 998677462 3748899 3748899
47522709 998677462 57312972 57312972
56644936 998677462 53138116 53138116
57433975 998677462 14863993 14863993
58304730 991815781 46330470 46330470
84293050 991815781 57403504 57403504
129239841 991815781 12302371 12302371
147095487 991815781 4640643 4640643
1545...

result:

ok both cnt and k values are correct (2000 test cases)

Test #113:

score: 8
Accepted
time: 353ms
memory: 12288kb

input:

200
750
620330489 1 872375852 923323661
345612359 1 705756808 326422353
30275662 1 559748373 150114514
495509083 1 944204290 492746953
497318915 1 540091524 414306643
185893996 1 758745670 521916732
332642535 1 417234625 699848333
59592252 1 172668526 219705902
835590994 1 861264716 838568360
524522...

output:

376
48038 997641150 6890617 6890617
733043 997641150 9212092 9212092
2366310 997641150 10395119 10395119
3461525 997641150 2795636 2795636
5207214 997641150 8954970 8954970
5708927 997641150 21377207 21377207
6047947 997641150 711630 711630
7195016 997641150 7318145 7318145
11939581 997641150 179132...

result:

ok both cnt and k values are correct (200 test cases)

Test #114:

score: 8
Accepted
time: 430ms
memory: 12796kb

input:

20
8664
221313900 1 844201240 572074838
519602646 1 682602622 714018248
126136787 1 775478429 395693152
257569208 1 639206751 627698606
366852234 1 939136234 749450529
265313404 1 595446914 640989842
217302553 1 698458665 21575601
315606856 1 785996690 434098157
769251976 1 990910746 967942713
92238...

output:

4313
2158 999854534 178127 178127
13286 999854534 634283 634283
50688 999854534 2657894 2657894
130208 999854534 283028 283028
267261 999854534 359449 359449
341834 999854534 1527091 1527091
405501 999854534 1449977 1449977
472906 999854534 121290 121290
484087 999854534 144441 144441
517496 9998545...

result:

ok both cnt and k values are correct (20 test cases)

Test #115:

score: 8
Accepted
time: 593ms
memory: 43240kb

input:

1
200000
362120006 1 915991457 752010704
293477506 1 586616456 512699110
243348574 1 517560529 613560028
518395521 1 602283673 467349430
94532523 1 301833025 335453083
208460123 1 271649702 283545259
31221451 1 603161405 147804490
147703700 1 488240438 197427726
88055813 1 542402703 319290460
564696...

output:

99855
53 999990668 2504 2504
6811 999990668 24405 24405
13022 999990668 6774 6774
16024 999990668 89649 89649
16025 999990668 9322 9322
16711 999990668 30513 30513
22322 999990668 51879 51879
31195 999990668 66321 66321
39084 999990668 35177 35177
39556 999990668 19800 19800
40540 999990668 33923 33...

result:

ok both cnt and k values are correct (1 test case)

Test #116:

score: 8
Accepted
time: 154ms
memory: 7964kb

input:

40000
2
720190840 1 813742477 993012710
39143737 1 982578755 749985706
4
51224527 1 311907899 878606247
524923255 1 848849273 883355975
10404793 1 140952252 985667561
121203084 1 370396654 803696515
2
36002388 1 937075708 978543547
55486982 1 982078374 221253455
5
378562187 1 876003437 900812588
271...

output:

2
39143737 982578755 749985706 749985706
720190840 813742477 243027004 243027004
4
10404793 140952252 107061314 107061314
10404793 311907899 74909732 74909732
10404793 370396654 803696515 803696515
524923255 848849273 883355975 883355975
2
36002388 937075708 757290092 757290092
36002388 982078374 22...

result:

ok both cnt and k values are correct (40000 test cases)

Test #117:

score: 8
Accepted
time: 240ms
memory: 9800kb

input:

2000
50
197140952 1 684745363 817151254
125738861 1 852851634 877758063
720134700 1 831288734 659322600
522470888 1 983678710 983657039
11730934 1 945977535 981198408
153113406 1 835678318 865323927
635590534 1 824542235 880257996
422936086 1 891703605 987555469
780344187 1 800555891 886011109
18119...

output:

7
358284 983678710 22467763 22467763
358284 986747738 279002167 279002167
358284 988846475 521705597 521705597
5884985 983678710 134612936 134612936
9229697 981775489 10674831 10674831
9229697 983678710 25868576 25868576
488508072 595934107 593657 593657
6
93256 999693471 658283723 658283723
281905 ...

result:

ok both cnt and k values are correct (2000 test cases)

Test #118:

score: 8
Accepted
time: 353ms
memory: 12432kb

input:

100
772
110861939 1 147764720 119899543
875938173 1 967385245 544585698
635258693 1 683226497 286099091
550185860 1 569396674 661359192
37993693 1 41167924 260058828
113969868 1 173837937 424534227
842205489 1 851779335 683604304
747593719 1 952523176 840682247
693550740 1 801516926 440004661
903651...

output:

43
1090244 999172196 369432965 369432965
4836291 999172196 474042733 474042733
7913627 254470442 4094149 4094149
7913627 999172196 60596857 60596857
20214206 26323876 59491250 59491250
36221232 161090368 9102580 9102580
36221232 211803634 43559136 43559136
36221232 253759952 16303586 16303586
362212...

result:

ok both cnt and k values are correct (100 test cases)

Test #119:

score: 8
Accepted
time: 557ms
memory: 35260kb

input:

1
200000
341673126 1 744484171 849396388
86578762 1 829061156 539016427
352317979 1 888616942 879055647
325059538 1 794605665 847127802
228773183 1 673189045 992680170
39455769 1 900690911 773653816
410075322 1 690425342 621277268
93803090 1 354358395 883147504
312177383 1 700181559 839751662
141576...

output:

22
354 999999829 451132806 451132806
401 999999829 373106176 373106176
1566 999999829 108658970 108658970
1822 999998850 43807176 43807176
1822 999999829 15106921 15106921
39213 999997761 1654393 1654393
39213 999998850 4426170 4426170
42417 999997761 438692 438692
117761 999997761 1446944 1446944
1...

result:

ok both cnt and k values are correct (1 test case)

Test #120:

score: 8
Accepted
time: 443ms
memory: 19452kb

input:

10
5030
310483930 1 314753596 202131013
920997980 1 923100875 536344710
77169367 1 80042469 952315561
178358105 1 181680489 850089551
282942938 1 283803759 119894971
492730006 1 499096966 45409823
784879953 1 785895559 712087702
516601486 1 517497780 497103075
577665711 1 579587973 226842411
9173755...

output:

354
120324 998757626 148498800 148498800
1123795 998757626 101783805 101783805
1741159 998757626 147407965 147407965
1834749 997605268 64344510 64344510
1834749 998757626 173960592 173960592
1844354 182139548 2268102 2268102
1844354 182652587 64754599 64754599
1844354 389063287 11628919 11628919
184...

result:

ok both cnt and k values are correct (10 test cases)

Test #121:

score: 8
Accepted
time: 596ms
memory: 39404kb

input:

1
200000
123792556 1 123794056 351542201
633379782 1 633435045 769628604
118177834 1 118182994 453276107
432904613 1 432929457 772501261
919586374 1 919597919 79937842
117611179 1 117616015 686619052
167669524 1 167684654 789897722
583011586 1 583025077 930240484
553841458 1 553848263 11306134
41388...

output:

32919
1288 517551 105718755 105718755
1288 536801 30687163 30687163
1288 544168 69430732 69430732
1288 5881699 18134029 18134029
1288 8564999 69591034 69591034
1288 17469221 16732213 16732213
1288 22241297 161582564 161582564
1288 46533684 78622491 78622491
1288 123443531 115417738 115417738
15474 1...

result:

ok both cnt and k values are correct (1 test case)

Test #122:

score: 8
Accepted
time: 458ms
memory: 14776kb

input:

10
4183
368302030 1 368451634 220041666
124943681 1 125117360 42429715
586896574 1 588286899 27690005
448581796 1 451124720 107546618
267683161 1 268175795 819513302
790448976 1 791035447 608545039
508760907 1 510851022 541521060
98859919 1 101577510 229655608
99708760 1 100439056 436425252
20689273...

output:

1542
167000 14586870 232873650 232873650
489581 1091081 254430334 254430334
1042161 1091081 67971378 67971378
1065814 1085340 345464134 345464134
1140031 1223613 71844011 71844011
1881057 2015576 224425433 224425433
1881057 2099703 67105313 67105313
2123135 13051423 11185510 11185510
2123135 1458687...

result:

ok both cnt and k values are correct (10 test cases)

Test #123:

score: 8
Accepted
time: 651ms
memory: 42632kb

input:

1
200000
292682180 1 292683262 220726693
996048783 1 996049650 748333043
912941784 1 912957394 61521913
307709417 1 307724671 150202595
117744339 1 117752266 880706608
373695017 1 373705340 892518441
567157262 1 567171061 730730739
779912326 1 779915335 496187182
691040141 1 691043128 86099628
65484...

output:

121579
5010 5749 290235426 290235426
9872 52243 339311468 339311468
10188 52243 538633284 538633284
16294 40101 25149488 25149488
16294 52243 71895710 71895710
58338 64927 809287317 809287317
65894 83434 153773656 153773656
65894 129424 332498799 332498799
79035 83434 217565574 217565574
87519 99770...

result:

ok both cnt and k values are correct (1 test case)

Test #124:

score: 8
Accepted
time: 669ms
memory: 47536kb

input:

1
200000
356922016 1 645872341 711707086
377499306 1 625808633 750839392
250044366 1 753267487 496389229
199818459 1 802929457 396223913
202864248 1 799924787 402484669
293868431 1 708620126 585062818
194352604 1 808138965 385337476
141931185 1 859951995 280252985
210798158 1 792093799 418363754
269...

output:

200000
4057 999999071 12661 12661
5077 999998861 8456 8456
11287 999998129 2805 2805
15222 999996292 918 918
16443 999996147 7249 7249
18800 999995055 3771 3771
22958 999991252 424 424
25241 999983425 3216 3216
25989 999983351 14129 14129
26663 999981875 561 561
29396 999980039 1876 1876
32787 99997...

result:

ok both cnt and k values are correct (1 test case)

Test #125:

score: 8
Accepted
time: 698ms
memory: 47500kb

input:

1
200000
973720518 1 973725767 74987718
775479530 1 775482855 813398313
33319817 1 33330215 948258194
820828772 1 820833183 981289580
601653856 1 601660576 407242076
805975043 1 805986469 518168997
826600447 1 826601891 726189267
379716559 1 379724441 74626489
806603001 1 806606670 670777622
6840178...

output:

200000
977 10797 157980092 157980092
977 21276 544114581 544114581
977 29551 199169805 199169805
977 918467 7257771 7257771
977 12214464 136611 136611
977 31781244 274145 274145
977 31951215 176333 176333
977 74594068 234888 234888
977 145030996 54438 54438
977 164613844 18517 18517
977 261823350 14...

result:

ok both cnt and k values are correct (1 test case)

Test #126:

score: 8
Accepted
time: 698ms
memory: 49552kb

input:

1
200000
311756203 1 311759608 95990586
652447306 1 652447462 644406615
450478741 1 450483155 302720697
896194365 1 896200954 309434641
934509528 1 934515927 55979079
494624597 1 494629769 148908151
865227443 1 865235194 123670507
293132754 1 293137460 5211387
957409429 1 957410767 960399601
9446257...

output:

200000
3798 20258 212856083 212856083
3798 289854 787219 787219
3798 1075985 1887990 1887990
3798 3410797 368388 368388
3798 7359541 1140444 1140444
3798 9802224 697691 697691
3798 12707842 211726 211726
3798 16833236 80812 80812
3798 44861638 218994 218994
3798 57957237 3679 3679
3798 300739642 117...

result:

ok both cnt and k values are correct (1 test case)

Test #127:

score: 8
Accepted
time: 702ms
memory: 47500kb

input:

1
200000
504674024 1 504678236 778850980
217475985 1 217476040 371549468
864703167 1 864705624 896393687
407918560 1 591093603 270650466
497443943 1 497450482 475763486
124377277 1 124378883 747773480
329121272 1 329122464 815211468
496647703 1 501934135 329440470
956537889 1 956541924 501492170
993...

output:

200000
8214 8466 662249459 662249459
8883 12781 605413955 605413955
8883 999986831 6773 6773
13520 19928 365117919 365117919
13520 999966791 7560 7560
31315 39013 956357190 956357190
31315 999958369 3085 3085
39801 41199 900766901 900766901
39801 999946737 7121 7121
42885 52804 544318891 544318891
4...

result:

ok both cnt and k values are correct (1 test case)

Subtask #9:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #128:

score: 8
Accepted
time: 321ms
memory: 7656kb

input:

40000
5
283014244 277188849 348261909 999368079
140872916 642835006 283014243 746783920
348261910 110354575 378128800 948724980
622122411 630160994 924412015 863751297
378128801 713855738 622122410 773621958
5
447864058 83560808 465462998 461654602
465462999 442476339 469719431 690399156
775296156 6...

output:

7
140872916 378128800 71020732 71020732
140872916 924412015 32928183 32928183
283014244 348261909 50643099 50643099
283014244 378128800 540749179 365646157
283014244 924412015 26838038 26838038
348261910 378128800 166834274 166834274
622122411 924412015 173824083 90129339
7
257342301 447864057 38895...

result:

ok both cnt and k values are correct (40000 test cases)

Test #129:

score: 8
Accepted
time: 432ms
memory: 10056kb

input:

10000
16
751188652 518362104 754233994 758020825
633984411 249526887 672501788 807184401
873869680 378669359 941378033 516787478
754233995 87052327 805677469 621927220
226562732 765613779 253522940 934419598
348627055 425544096 465549298 763192146
672501789 85407596 751188651 359311092
266443672 298...

output:

27
13887367 226562731 669817453 607447496
13887367 253522940 10059086 10059086
13887367 256357859 110582848 110582848
13887367 266443671 48163886 48163886
253522941 266443671 191098542 191098542
253522941 348154640 186104922 186104922
253522941 348627054 46595317 46595317
256357860 266443671 1956292...

result:

ok both cnt and k values are correct (10000 test cases)

Test #130:

score: 8
Accepted
time: 869ms
memory: 12720kb

input:

100
285
991837892 9438739 995046459 997396987
810000407 558061680 815504536 857195356
979059478 227111282 979198567 741943445
682015658 143100446 686624288 382577652
470183218 236080896 473228155 878307841
647455294 380292051 653678073 893654030
727593398 416175208 727670671 691642796
587175166 2854...

output:

444
5092032 9614017 224076791 224076791
5092032 13325969 114262616 114262616
5092032 13596598 27728740 27728740
5092032 13763553 311335765 311335765
5092032 14728791 42572971 42572971
7007087 9614017 204482447 178338259
7007087 13325969 9063842 9063842
13325970 13596598 192144669 192144669
13325970 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #131:

score: 8
Accepted
time: 1342ms
memory: 76700kb

input:

1
200000
709124751 134600884 709134198 945164922
131399845 675511810 131416665 777047299
177336737 237279653 177342732 504194754
744387886 44130529 744388997 980813002
984912959 255141289 984914777 884737143
909113303 138838636 909114004 939689776
380832879 413710917 380835028 771943563
111929921 26...

output:

306812
1195 5815 553832627 502143580
1195 6520 40705962 40705962
6521 8344 246833962 246833962
6521 14468 350941833 350941833
8345 14468 297701209 233482947
8345 22419 30158922 30158922
22420 40561 146561265 146561265
30183 40561 634335491 251202154
30183 45991 67220625 67220625
45992 46078 31905292...

result:

ok both cnt and k values are correct (1 test case)

Test #132:

score: 8
Accepted
time: 1095ms
memory: 80428kb

input:

1
200000
749367400 374498079 749367678 874037814
60449465 29659661 60449714 529234615
280223744 139555707 280224568 638589687
606809386 303670434 606811259 802934057
39896452 19710794 39899197 518676214
725816343 362997017 725818573 862649866
481752196 240270401 481752575 739137815
635848346 3183449...

output:

399999
376 4232 19073 19073
376 4369 1722 1722
376 5633 923 923
376 9316 4034 4034
376 10320 3423 3423
376 13052 124 124
376 15471 1145 1145
376 20431 2298 2298
376 30333 5757 5757
376 32517 2959 2959
376 40473 2638 2638
376 48727 860 860
376 50538 532 532
376 53742 6675 6675
376 55282 199 199
376 6...

result:

ok both cnt and k values are correct (1 test case)

Test #133:

score: 8
Accepted
time: 1425ms
memory: 77416kb

input:

1
200000
639435081 182258416 639436112 877158155
334287756 272520424 334298632 621170403
830381930 413231465 830385540 587526189
179592176 247728530 179594341 876128617
21847729 77154910 21858341 604864028
345381206 290232985 345383620 912546211
763468971 278860393 763473916 989697563
553490525 4655...

output:

351027
1654 3052 260094098 260094098
1654 5354 192944147 192944147
1654 16424 48067014 48067014
1654 75887 43532980 43532980
1654 76912 7666761 7666761
1654 101895 38241001 38241001
1654 191429 17654763 17654763
1654 257281 5468695 5468695
1654 436073 6633224 6633224
1654 506630 15564198 15564198
16...

result:

ok both cnt and k values are correct (1 test case)

Test #134:

score: 8
Accepted
time: 1380ms
memory: 79352kb

input:

1
200000
342161405 368424380 342164432 834854201
53981374 279865618 54002947 673519770
426595711 483634918 426601981 659985045
301443350 268290644 301449572 925583332
11265132 241673271 11276804 867420738
56191399 442650208 56191617 850576624
186388929 317311811 186389117 628995278
369104580 9948416...

output:

349157
197 31557 41199245 41199245
197 64172 54208985 54208985
197 99522 4460478 4460478
197 131910 7198507 7198507
197 167514 12485437 12485437
197 267210 11959325 11959325
197 317838 9307740 9307740
197 659075 11827650 11827650
197 769260 7876745 7876745
197 858672 9720 9720
197 1287857 1435714 14...

result:

ok both cnt and k values are correct (1 test case)

Test #135:

score: 8
Accepted
time: 362ms
memory: 7724kb

input:

20000
13
13561068 157328923 54787963 579978177
300750182 238065905 457862252 508154206
720469551 357126745 832140682 398656447
520812982 108124013 562467236 797181667
505303838 192972262 520812981 560778785
224712851 240655833 239752379 522884710
61288752 512325715 123597167 540509995
158792096 2040...

output:

19
13561068 54787963 422649255 422649255
61288752 123597167 28184281 28184281
158792096 215510177 88008587 88008587
224712851 239752379 282228878 282228878
300750182 457862252 144396424 144396424
300750182 562467236 120612636 120612636
300750182 697024428 5079242 5079242
457862253 697024428 18802886...

result:

ok both cnt and k values are correct (20000 test cases)

Test #136:

score: 8
Accepted
time: 553ms
memory: 10052kb

input:

2000
24
422354444 835930946 519396812 967044902
389542759 437201675 409069404 618853962
979662377 383574133 992073899 622637227
834315879 400665892 839225886 530722330
381237901 97393121 387865885 143906506
189461617 167689556 219914846 331609572
252330605 624122820 313148106 965982590
692380402 582...

output:

34
5784217 24361304 26947933 26947933
5784217 66606804 228783948 228783948
5784217 94221389 65247718 65247718
5784217 143576855 103322821 103322821
24361305 143576855 53990955 53990955
24361305 156598859 128163416 128163416
66606805 156598859 15632952 15632952
94221390 140126497 3704189 3704189
9422...

result:

ok both cnt and k values are correct (2000 test cases)

Test #137:

score: 8
Accepted
time: 737ms
memory: 11056kb

input:

200
1057
128513001 924772299 128762020 970232871
702942920 141032784 704157713 168576011
77616330 681694325 80253764 895923990
481884033 725499062 482298950 762176932
250012533 252478091 250257649 694416959
621507212 646181738 622527852 840183088
605105667 803780399 608016755 808166513
101800817 139...

output:

1433
114722 2925869 10791570 10791570
114722 3296737 11352053 11352053
114722 3306680 11689108 11689108
114722 3845561 47977412 47977412
2081525 2759559 245523886 245523886
2925870 3296737 117321130 117321130
2925870 3845561 73916641 73916641
3306681 3845561 3528610 3528610
3306681 4897336 190112295...

result:

ok both cnt and k values are correct (200 test cases)

Test #138:

score: 8
Accepted
time: 1005ms
memory: 17760kb

input:

20
13038
971693807 192254104 971862343 754412294
809616184 285485180 809712788 597121527
154464677 707999443 154476449 736758362
819804315 324391438 819820560 535871050
598441617 148380755 598452493 384282455
62159193 570954557 62279315 805589589
647739417 134099219 647818102 487417054
471406100 151...

output:

17630
15739 99859 287016006 286911871
15739 101462 299228289 298027676
15739 137496 395069609 395069609
149073 231070 143529107 101047117
149073 314608 547493314 547493314
149073 337430 110430554 110430554
453502 585814 8066029 8066029
510901 772630 52509905 52509905
625422 772630 85784708 57181034
...

result:

ok both cnt and k values are correct (20 test cases)

Test #139:

score: 8
Accepted
time: 1291ms
memory: 74372kb

input:

1
200000
71733104 491622340 71733253 536071127
342165392 353599517 342169151 799053121
924145490 194198940 924146995 297523000
616880959 309503108 616891495 709549595
622101499 145748992 622115109 830601041
332071531 448196343 332074292 925828810
753686370 14004463 753690588 748827268
348782786 5133...

output:

270260
9069 12096 258390 258390
9069 14755 21210933 12435779
9069 16186 198693544 198693544
9069 16414 18350316 18350316
9069 19953 278197722 278197722
9069 25647 50953834 50953834
12097 14755 71296825 71296825
12097 25647 129510563 129510563
16187 25647 54333340 54333340
19954 25647 65239324 652393...

result:

ok both cnt and k values are correct (1 test case)

Test #140:

score: 8
Accepted
time: 301ms
memory: 7972kb

input:

20000
24
679582550 63262687 864568877 114406077
604187103 605619325 610678768 980955471
474324451 293316550 476465105 303106531
240382022 457316427 415843218 554596511
60708439 63262687 179794367 84236469
679582550 815569798 826345359 980955471
40796469 166044051 58218316 209871865
224628391 5545965...

output:

25
40796469 58218316 43827815 43827815
60708439 179794367 20973783 20973783
63879297 135978335 44429419 44429419
148985198 166130649 731651925 731651925
186657669 196764302 523639045 523639045
186657669 415843218 27359674 27359674
196764303 415843218 366694066 366694066
207164807 233878585 88276161 ...

result:

ok both cnt and k values are correct (20000 test cases)

Test #141:

score: 8
Accepted
time: 452ms
memory: 9980kb

input:

1000
52
169056984 950511912 232089464 990923087
393112191 808328427 416022246 877890318
64414653 5325434 64488143 944703330
668688166 642975830 702337790 990923087
883603541 200695400 887384363 269918976
258086136 924601436 278475636 942334741
308162031 5325434 310497490 94370112
128505745 778228666...

output:

53
17904811 19667975 543733663 543733663
32871007 46756440 536687706 536687706
64414653 64488143 939377897 939377897
79468346 85175445 202375879 202375879
85385360 106059579 219357882 219357882
107646342 230592725 86005630 86005630
109001330 110689365 51889291 51889291
125494255 126712935 2512824 25...

result:

ok both cnt and k values are correct (1000 test cases)

Test #142:

score: 8
Accepted
time: 597ms
memory: 11336kb

input:

100
284
776829026 1347122 828110276 214902960
454411238 137865693 462458532 423465157
124007302 1347122 127103774 994488826
51336756 239185737 54114816 308635542
415894080 586226573 417892867 994488826
84395355 610925633 86154506 875814311
539950468 905939327 546793989 906666071
241461928 289219955 ...

output:

283
104798 899419 993141705 993141705
4477147 5288045 30890449 30890449
4477147 6343979 28282680 28282680
5288046 6343979 445089466 445089466
7890609 8844750 236929350 236929350
7890609 18546369 644976316 644976316
14962135 16226774 34189733 34189733
15453583 18546369 274873715 274873715
24105261 24...

result:

ok both cnt and k values are correct (100 test cases)

Test #143:

score: 8
Accepted
time: 328ms
memory: 17196kb

input:

1
200000
86961618 592310421 87974088 592396460
851653444 903728300 851764439 904052483
25491978 998515592 27974367 999092857
840138133 843800473 840306416 843805675
985545763 502636631 985556457 502750777
30486055 843805676 30764533 844986161
179685959 559346256 180161383 559363376
193898853 8427822...

output:

9034
44734 383564 24898792 18772428
44734 469022 1387827 757007
44734 2359453 3283732 917220
44734 2571724 3352272 3109656
44734 2708008 2488947 1479635
44734 2885001 189554 122148
44734 3307536 8138948 4097071
44734 3547976 782045 782045
44734 3604338 12908 12908
44734 3953593 230812 230812
44734 4...

result:

ok both cnt and k values are correct (1 test case)

Test #144:

score: 8
Accepted
time: 810ms
memory: 63220kb

input:

1
200000
652462338 694112552 652490589 705687114
864527218 397784770 864533841 999999560
229586737 982563262 229598005 984519576
138190535 976742160 138216565 976743983
245556233 665630998 245557314 665631668
367928735 586411061 367950537 999999560
408194843 2446 408196837 486316534
289858094 124557...

output:

90530
9664 10406 630761194 630761194
18039 34614 151227343 151227343
26115 34614 848769772 493883244
38291 40085 999997115 999997115
56473 84007 999997115 999997115
94940 117870 279590642 279590642
129795 132918 703177636 703177636
147023 147683 424131851 371097078
147023 161701 575865264 575865264
...

result:

ok both cnt and k values are correct (1 test case)

Test #145:

score: 8
Accepted
time: 867ms
memory: 63324kb

input:

1
200000
414807608 700689227 414810394 700754470
331545818 497499901 331572635 999996561
540301609 21731746 540303732 77035947
391139594 447401907 391163700 447495049
450363757 262022649 450377238 295985131
2716528 799859618 2717448 999996561
35289459 854700682 35304170 933301027
463212621 111597092...

output:

91786
90 3875 306010 280197
8930 40811 8169086 7080235
45706 45921 999993856 999993856
77144 125960 73641391 73641391
86117 98294 350387239 350387239
99217 102606 262134412 262134412
143974 164715 999993856 999993856
165353 168444 49396290 49396290
171234 187075 5081886 3857267
189881 204685 3448037...

result:

ok both cnt and k values are correct (1 test case)

Test #146:

score: 8
Accepted
time: 771ms
memory: 67488kb

input:

1
200000
673443762 89011269 673443826 90662683
54753195 218982566 59657874 218987168
272380131 863491431 272380325 863773172
490530853 694418131 491325003 694457766
734921426 830078058 734928904 830088009
355419683 593542328 355421310 593546571
901966449 285932784 901966826 285933202
966505440 31728...

output:

192727
6186 16126 48332 37038
6186 87606 52755 52755
6186 133957 727647 727647
6186 163152 10987 10987
6186 230614 11217 11217
6186 267566 6479 6479
6186 411032 839 839
6186 450287 20272 20272
6186 487449 76928 76928
6186 495059 17215 17215
6186 551377 42889 42889
6186 569827 493139 493139
6186 6835...

result:

ok both cnt and k values are correct (1 test case)

Test #147:

score: 8
Accepted
time: 689ms
memory: 43152kb

input:

1
200000
558974657 481420098 559062667 481648704
6083416 993135701 6103751 993155571
440039091 58610135 440776752 59630606
970271751 616643243 970499640 616650177
412710108 695448757 421266094 696632038
388597995 847036644 388710057 847484996
756649456 703462938 756656339 703581109
924890508 7992686...

output:

96636
12313 42065 375721 375721
12313 45967 171412 171412
12313 103304 15579 15579
12313 325091 3562256 2371415
12313 341718 624346 624346
12313 347823 234567 234567
12313 367934 2032 2032
12313 378506 13796 13796
12313 413171 15110 14601
12313 464292 97488 97488
12313 507025 19383 19383
12313 54763...

result:

ok both cnt and k values are correct (1 test case)

Test #148:

score: 8
Accepted
time: 1114ms
memory: 70332kb

input:

1
200000
492514823 244174594 492519524 745570038
526378316 261381925 526380104 762535992
538504745 267602387 538507557 768676959
135156541 67222537 135158483 566824583
732636639 365235834 732638958 866126937
929476799 463839554 929477784 964727834
360759109 179115235 360761039 679954838
510980431 25...

output:

200000
327 8615 499252417 499252417
11549 12785 499251742 499251742
13439 13766 499258118 499258118
17122 23636 499257651 499257651
29434 35057 499257070 499257070
38250 44973 499254625 499254625
53181 55492 499255481 499255481
58374 61252 499262502 499262502
65153 68624 499261360 499261360
75885 76...

result:

ok both cnt and k values are correct (1 test case)

Test #149:

score: 8
Accepted
time: 1395ms
memory: 82792kb

input:

1
200000
966576574 377056529 966590295 877876876
353827576 222338716 353830506 721804303
131300514 342393866 131302040 842270628
955438794 71021208 955450253 569689609
36910245 19031776 36914316 517056624
141734724 116259088 141734744 615465232
969303396 274324975 969314831 774229302
880493158 20891...

output:

399999
2350 3149 68649829 68649829
2350 5957 258700408 258700408
2350 22540 5902285 5902285
2350 30076 50292170 50292170
2350 38501 689677 689677
2350 60253 2303298 2303298
2350 133794 77372211 77372211
2350 158930 1175732 1175732
2350 255663 9111994 9111994
2350 420068 13078457 13078457
2350 446004...

result:

ok both cnt and k values are correct (1 test case)

Subtask #10:

score: 8
Accepted

Dependency #1:

100%
Accepted

Dependency #9:

100%
Accepted

Test #150:

score: 8
Accepted
time: 356ms
memory: 9832kb

input:

20000
34
362931022 842074863 748007329 855571089
16702890 278427428 397610003 320022232
290031220 304435076 675825262 790080122
24251033 207771111 403192391 213980675
67590324 688383571 486154926 813951721
193610983 347301551 621189498 914768394
212511241 666458607 662352654 795288725
922643539 7693...

output:

17
1285349 370718596 51827943 51827943
1285349 817224239 169523249 169523249
1285349 826839391 321422512 165504793
1285349 945355738 197530070 197530070
64117488 110819004 55684401 55684401
67590324 817224239 23132303 23132303
70990108 817224239 22514749 22514749
145721769 817224239 5268829 5268829
...

result:

ok both cnt and k values are correct (20000 test cases)

Test #151:

score: 8
Accepted
time: 460ms
memory: 7860kb

input:

2000
20
365105426 639722360 644406474 803787208
743602722 240820567 932819625 673134953
344530041 147517905 561616369 255924034
131347238 84434255 455755978 886108277
28225559 826208892 324417348 845751012
370861644 40310991 656291993 703262774
259265 129798273 339210969 727866450
789532990 26370183...

output:

16
259265 644406474 24603676 24603676
259265 656291993 406516434 276966480
259265 932819625 90652284 90652284
259265 934337277 52602174 52602174
259265 953558542 23693610 23693610
9678388 638432870 75150831 75150831
97721351 414211968 21575351 21575351
97721351 480501063 20665800 20665800
97721351 6...

result:

ok both cnt and k values are correct (2000 test cases)

Test #152:

score: 8
Accepted
time: 586ms
memory: 12576kb

input:

200
199
592506196 34916652 708193481 662203307
525521669 613437107 685270564 741038787
389049036 352873826 550174357 615316926
734416721 69505510 879099391 318527378
109518561 565683851 195478394 933597212
548767612 823595163 663209332 897083927
278271588 170084555 409756829 975172008
460112250 6849...

output:

64
641249 1855004 20119911 20119911
1538571 5875051 361710037 361710037
10727057 13198164 120352254 120352254
19715588 30780548 124222659 124222659
19715588 46390787 19693886 14722606
19715588 54364980 161068507 161068507
25318142 46384217 207613882 207613882
30116510 46390787 71984191 71984191
4648...

result:

ok both cnt and k values are correct (200 test cases)

Test #153:

score: 8
Accepted
time: 758ms
memory: 15908kb

input:

20
13038
581155345 66022308 750268284 118637251
905446574 479037978 965252333 865488798
24528443 225798771 66556862 834646873
381906161 280072435 632820810 658382575
295742741 257246380 455964972 642454964
408377855 144630684 648316459 519909648
884319262 300609932 929816162 327015842
58513729 49547...

output:

154
30390 131823 493732200 493732200
92725 171955 59572846 59572846
92725 255611 2233394 2233394
136839 636028 2577384 2577384
144328 255611 521773620 521773620
161356 644774 167596735 167596735
338223 362168 99387557 99387557
369565 1172741 123063011 123063011
369565 6289365 254302298 254302298
515...

result:

ok both cnt and k values are correct (20 test cases)

Test #154:

score: 8
Accepted
time: 1113ms
memory: 55784kb

input:

1
200000
141254061 523283025 237455763 916208729
665203253 226338150 794894398 802666981
252642572 209363665 378292112 238052176
474566819 250772145 563190623 538033812
706909488 103780321 850330317 420752889
69687068 293492850 165374927 819738979
489064196 451486434 580190286 748926158
131081243 27...

output:

134
2505 16710 23061121 23061121
2505 20000764 215409210 215409210
2505 999990668 17500805 17500805
2505 999995740 379127308 214744678
2593 20000764 38635620 38635620
6811 13021 90114716 90114716
16024 20000764 1765134 1765134
20863 19786486 10295968 10295968
20863 19928945 127313434 127313434
20863...

result:

ok both cnt and k values are correct (1 test case)

Test #155:

score: 8
Accepted
time: 423ms
memory: 9808kb

input:

10000
4
256951991 807713593 726922879 983445163
493555893 468149231 784033393 834761292
25146771 567273838 279689727 924588479
38417859 268262051 654483225 756383956
16
284039929 7572338 443487368 111552867
472251059 599425483 705118385 898385087
676350786 358498651 891461764 612398371
303571473 454...

output:

7
25146771 279689727 51329636 51329636
25146771 726922879 89827187 89827187
25146771 784033393 216157819 189110119
38417859 654483225 199887180 199887180
38417859 784033393 99124607 99124607
256951991 726922879 58856684 58856684
493555893 784033393 51329636 51329636
40
1986130 93018991 134462161 134...

result:

ok both cnt and k values are correct (10000 test cases)

Test #156:

score: 8
Accepted
time: 780ms
memory: 15868kb

input:

100
1406
396029988 433829539 425667063 470161984
652717757 379581564 682318419 409707477
280970379 863642188 309003692 876873401
714115813 812877206 738853598 834196156
100836218 750900168 116943631 775172040
775290380 251399025 796304582 277113797
954438887 521295722 965789521 548969259
190882495 2...

output:

4143
32497 995694 14310849 14310849
32497 2437693 6902891 6902891
32497 4384744 3409001 3409001
32497 7600646 2773708 2773708
260958 2024368 16537457 16537457
260958 4384744 1592556 1592556
260958 6360807 5692862 5692862
260958 11217774 3069343 3069343
530299 2437693 13317671 13317671
530299 5410230...

result:

ok both cnt and k values are correct (100 test cases)

Test #157:

score: 8
Accepted
time: 1249ms
memory: 92936kb

input:

1
199809
551329675 746422730 553886285 748466643
492602651 21697928 495149798 22378877
856552754 362048223 858038628 364570479
88361154 471743425 89633300 474308864
311271546 958124527 313420577 958975600
161354204 524886579 163142200 527380287
637642019 987804356 640115333 988203853
156371838 63773...

output:

598533
184 6970 1378122 1378122
184 13238 561544 561544
184 25080 293183 293183
184 55906 256556 256556
1195 11603 1503688 1503688
1195 25080 273912 273912
1195 44169 245070 245070
1195 76777 288308 288308
5816 13238 786599 786599
5816 30751 565522 565522
5816 79636 265441 265441
10086 21855 1329596...

result:

ok both cnt and k values are correct (1 test case)

Test #158:

score: 8
Accepted
time: 793ms
memory: 82824kb

input:

1
200000
511595250 487424502 511618220 487446336
163083924 836528907 163098662 836550125
741128122 258938609 741140830 258945818
688422325 310997325 688429008 311006716
803683014 195794107 803692967 195813761
508566039 490279479 508582970 490294942
255552552 743969290 255562032 743974883
930440321 6...

output:

399999
1478 5955 408 408
1478 9605 1291 1291
1478 21727 3966 2407
2920 8806 539 539
2920 21727 219 219
2920 27479 6093 4425
4083 9605 1860 1860
6868 18907 54 54
6868 27479 9484 9484
6868 31956 5449 3900
7588 21727 408 408
11581 27138 2853 2853
11581 31956 2778 2778
11581 38950 2242 1660
11673 27479 ...

result:

ok both cnt and k values are correct (1 test case)

Test #159:

score: 8
Accepted
time: 899ms
memory: 91824kb

input:

1
200000
214726572 785528076 214811848 785559922
255055731 745685100 255133349 745746944
827224875 173279387 827309439 173334621
166733292 832967487 166826417 833020354
970594842 29169646 970650455 29239412
585040886 413607148 585114478 413664607
658651740 341185021 658729019 341225001
193768781 805...

output:

579990
6071 18458 23990 23990
6071 24430 17103 17103
6071 36515 4871 4871
6071 61660 12566 12566
16780 21781 16574 16574
16780 36515 10254 10254
16780 52893 2178 2178
16780 88877 12606 12606
18120 24430 17599 17599
18120 44177 11227 11227
18120 98600 544 544
18813 30162 21914 21914
18813 52893 11242...

result:

ok both cnt and k values are correct (1 test case)

Test #160:

score: 8
Accepted
time: 416ms
memory: 9796kb

input:

10000
18
497058813 233005118 622516767 374605808
410162982 178732088 516577787 275833846
705882924 884501750 862558905 993836335
819600476 665119464 998746793 893990148
87317304 23644919 288265098 162610639
721343938 605654964 893470573 714214569
29211691 112987472 158848456 228049489
623010740 6207...

output:

43
29211691 158848456 19998710 19998710
29211691 272180137 43364902 43364902
29211691 444222571 49623168 49623168
29211691 516577787 2075238 2075238
40984157 272180137 38261699 38261699
40984157 431502700 14040847 14040847
40984157 622516767 9522658 9522658
87317304 288265098 3946883 3946883
8731730...

result:

ok both cnt and k values are correct (10000 test cases)

Test #161:

score: 8
Accepted
time: 595ms
memory: 14784kb

input:

100
344
322982806 322949872 332743719 332327656
671146122 689551889 679158121 701428048
167632200 153946254 180228957 166618040
870334753 854632107 877748518 864293198
202457447 166739935 208910957 176393638
860429930 831531265 866546340 843041722
777839501 772303691 784751253 779415160
594184478 60...

output:

858
2649435 4384744 759587 759587
2649435 7075907 745671 745671
2649435 12151288 2402247 2402247
2649435 17731229 2078068 2078068
2719391 7075907 2058181 2058181
2719391 10067038 5054069 5054069
2719391 31451048 124183 124183
2847974 7294410 4719029 4719029
2847974 12151288 2167801 2167801
4806674 1...

result:

ok both cnt and k values are correct (100 test cases)

Test #162:

score: 8
Accepted
time: 815ms
memory: 88836kb

input:

1
200000
658676868 657360400 658688332 657375786
161952189 162123521 161961715 162145361
698069266 696717646 698076911 696739225
161115949 161349070 161125782 161363533
679632951 678276771 679651999 678289622
269755412 268583520 269775147 268603350
945301860 945221526 945311430 945238393
319389280 3...

output:

499998
3296 13331 6508 6508
3296 18622 687 687
3296 32250 2562 2562
3296 36503 143 143
5649 18622 5611 5611
5649 31153 4107 4107
5649 49557 1864 1864
6693 19538 5771 5771
6693 32250 987 987
14341 31153 7686 7686
14341 35102 677 677
14341 58712 229 229
14722 32250 3649 3649
14722 36503 2859 2859
2745...

result:

ok both cnt and k values are correct (1 test case)

Test #163:

score: 8
Accepted
time: 1408ms
memory: 80780kb

input:

1
200000
685035395 445065276 685039718 945046981
801880664 500005840 801885595 999815841
346159472 302102246 346164876 801697637
15817480 152420708 15833853 652179060
527073650 465436351 527079908 965097275
991689485 141430710 991695735 641441072
574706048 252209114 574712942 752268204
131269462 214...

output:

399999
10 1504 39891748 39891748
10 10562 209008855 209008855
10 26412 4447712 4447712
10 28130 61741763 61741763
10 35679 170728844 170728844
10 882791 1782522 1782522
10 1261593 3254685 3254685
10 1635183 491399 491399
10 1650286 5549293 5549293
10 1694010 2327641 2327641
10 2125309 389523 389523
...

result:

ok both cnt and k values are correct (1 test case)

Subtask #11:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #164:

score: 8
Accepted
time: 290ms
memory: 9748kb

input:

20000
23
494161954 150753410 588408181 812570786
54494825 249688519 70618578 771566170
807208549 253096103 990350470 760942681
351108171 249688519 379267510 771566170
860203287 155164308 923551866 797858098
5526115 511260001 993745521 571716529
534856804 99900181 582925048 841460960
712816244 293112...

output:

23
5526115 993745521 60456529 60456529
11848114 108645649 35376368 28107193
54494825 70618578 426044755 233464289
151161021 307489461 175655478 94762095
179523111 289654931 285765645 180678099
211820382 275048429 120816139 94524211
241801313 267378166 19123586 14712688
334188799 433608999 180054547 ...

result:

ok both cnt and k values are correct (20000 test cases)

Test #165:

score: 8
Accepted
time: 438ms
memory: 7868kb

input:

2000
12
216401032 145574617 423740788 850211193
103802783 394376553 465405544 761440714
13975665 490009537 617142969 661858710
368451806 1 391109068 944703115
181577317 152689001 458756021 810937074
170049071 177039419 464672169 790425002
44110538 426495519 598966816 731083969
288291115 66768788 407...

output:

12
13535600 930363443 78253169 78253169
13975665 617142969 93596005 72809122
44110538 598966816 132739277 69225259
55457449 538260003 23550354 22029672
103802783 465405544 38925357 28836063
170049071 464672169 246321422 217337134
181577317 458756021 44862490 24350418
216401032 423740788 46388503 392...

result:

ok both cnt and k values are correct (2000 test cases)

Test #166:

score: 8
Accepted
time: 714ms
memory: 13192kb

input:

100
1183
652711278 624319927 669868285 643739482
953438528 479346428 954037774 525866290
968641875 326782543 968664320 598198646
679240082 475810955 679864568 540383223
134096315 101068645 171958004 108369792
625186607 290482337 625619188 669997275
311047505 26263139 324106450 27734594
604030000 125...

output:

1183
13832 999862849 537472 537472
360012 999484455 920226 762403
475964 999150700 457758 404944
1726446 999094002 953012 668467
1847309 404254325 363008 284424
2292968 403649058 11907537 8162145
2389070 403118206 2898830 2353437
2642596 10453590 4660204 3344200
2671709 10436758 64884805 41416355
28...

result:

ok both cnt and k values are correct (100 test cases)

Test #167:

score: 8
Accepted
time: 640ms
memory: 19080kb

input:

10
13176
418736299 739051582 431840098 740768372
637612605 590345282 691111293 595368693
288083498 252936973 297084047 253081684
12067992 307705732 12077426 754118488
486920602 368479753 487007440 655491115
853160034 291500631 869131789 292746811
367575461 778074032 377194825 778604348
681790691 294...

output:

13176
17608 999996428 129302 129302
58140 999949916 296223 296223
83132 999851426 310185 310185
146034 999791453 2385936 2164252
201694 999759878 258465 258465
219414 999714348 157762 80358
268909 999706596 639899 427990
298232 999612371 439816 391893
304863 999566477 143519 109297
368288 999560764 ...

result:

ok both cnt and k values are correct (10 test cases)

Test #168:

score: 8
Accepted
time: 594ms
memory: 26468kb

input:

1
200000
603824667 716013203 604008267 716109234
790330951 302828024 790334800 660004031
563250161 774304937 563401394 775739764
775041914 310155786 775114331 659272762
907833026 325850138 907833514 675149258
536412892 260947890 536629239 262167657
179797577 232761444 179797976 716908978
337710294 2...

output:

200000
1277 999997825 503560 503560
1448 999992866 376972 212287
5658 999992786 827836 827836
7699 999990020 2411824 1652837
11744 999987313 1964201 1877852
18750 999985887 56580 56580
23175 999983885 632310 538530
23350 999981547 2463575 2463575
23361 999972638 242266 130387
27070 999968231 223378 ...

result:

ok both cnt and k values are correct (1 test case)

Test #169:

score: 8
Accepted
time: 662ms
memory: 28156kb

input:

1
200000
872667837 723773354 878124112 724091466
17298261 343340874 17299512 664050473
167008465 202907622 167014022 795101400
379567696 309675035 379569724 687017055
606940940 264355083 606946000 727923988
933361855 340192217 933362948 657294235
418956844 363437459 418957418 645729041
280861024 297...

output:

200000
6326 999999934 118667 118667
6335 999997754 99559 99559
9736 999997461 529783 304086
13580 999996342 218095 218095
15060 999990996 173748 108808
15308 999985330 37135 37135
21151 999982107 22630 22630
23517 999979762 161828 145627
26857 999979350 135589 100289
27727 999977764 692640 539177
32...

result:

ok both cnt and k values are correct (1 test case)

Test #170:

score: 8
Accepted
time: 695ms
memory: 28452kb

input:

1
200000
647425790 334750471 647427700 678629989
357454037 795021928 358482040 796327886
640462129 359660866 640462438 646776229
370963326 324564773 370963587 680762496
981210865 373407836 981211895 630038226
962442876 207025405 964666604 207351984
758825360 212672056 758827768 773641140
234453317 3...

output:

200000
2864 999997885 120875 120875
6093 999992843 81758 63609
6387 999980340 38574 38574
6713 999979166 1318 1318
7249 999975829 134718 81016
9885 999971283 37211 37211
11377 999968687 172060 137611
12661 999966681 135101 115419
12832 999966483 324205 296611
13562 999963092 15474 11629
13750 999958...

result:

ok both cnt and k values are correct (1 test case)

Test #171:

score: 8
Accepted
time: 1014ms
memory: 67916kb

input:

1
200000
828444486 412778595 855381251 412796472
93593674 21673867 100237429 21725397
258355698 598462531 315355723 598568560
975972174 513201224 985868992 513228143
918229290 237322402 930670513 237446194
628172945 679495069 634472154 679824074
8276414 508177439 991797173 508203756
149374109 339802...

output:

200000
1624 999995825 891 891
5671 999995020 9007 9007
8482 999990180 1051 1051
12279 999989018 6363 5177
13035 999988597 4377 2945
13248 999987768 7558 3948
13844 999984617 3670 3670
17648 999982510 1422 1422
24644 999982476 2447 2447
25038 999981307 903 903
31171 999981139 2523 2523
32346 99997859...

result:

ok both cnt and k values are correct (1 test case)

Test #172:

score: 8
Accepted
time: 772ms
memory: 33236kb

input:

1
200000
278616121 250591966 278616133 737813642
332577420 61799422 332578635 943604650
133688459 337175708 147217994 337236880
615120559 812711246 634657699 812801217
327224366 153760751 373281635 153778678
309345610 311499930 309346575 680226087
17361805 237862230 38003287 237982142
352065161 9621...

output:

200000
10951 999997564 1531 1531
17351 999994841 3359 3359
17975 999993292 33739 33739
18059 999991214 25567 25567
18202 999989883 6938 6938
20362 999989375 29423 29423
20651 999986586 96563 84111
27117 999981725 59191 39520
27513 999978172 6069 3187
37454 999976972 10988 10988
38162 999976090 57967...

result:

ok both cnt and k values are correct (1 test case)

Test #173:

score: 8
Accepted
time: 871ms
memory: 49552kb

input:

1
200000
589673818 115454511 652020564 115474957
65956667 216678342 266842201 216705415
81206545 179038890 251375834 179070571
641785689 56029875 641791650 946029614
628847975 68763796 628849386 933469704
310968939 98248598 310971387 901996433
161676151 4009961 161677906 995847889
838212221 39023901...

output:

200000
204 999994215 189 189
1395 999993650 10474 10474
5280 999992737 17652 9618
14701 999990676 11250 6417
15890 999987935 3169 3169
15899 999978762 1329 1329
16340 999977973 41683 20860
16383 999975479 10075 8747
17597 999969516 4259 4259
19607 999967153 3247 3247
24135 999959641 5747 4953
31276 ...

result:

ok both cnt and k values are correct (1 test case)

Test #174:

score: 8
Accepted
time: 239ms
memory: 10052kb

input:

40000
8
664088927 226439325 760547539 825493308
284077050 315964511 870325257 381770101
55920514 414449073 919806388 458629291
817280312 116742265 830597366 754222749
762613746 187912261 809216818 927414833
342193199 577278339 844324637 735320612
266013561 504698990 875547025 573837748
429827229 216...

output:

8
55920514 919806388 44180219 44180219
266013561 875547025 69138759 69138759
284077050 870325257 65805591 65805591
342193199 844324637 158042274 158042274
429827229 472881468 236043057 99708064
664088927 760547539 261887141 90172696
762613746 809216818 402335730 192094221
817280312 830597366 3003136...

result:

ok both cnt and k values are correct (40000 test cases)

Test #175:

score: 8
Accepted
time: 354ms
memory: 10020kb

input:

10000
4
634517246 200513980 635060595 983225607
144071704 394476576 930965737 736607404
256117152 255870142 727230617 342099382
709242037 56079129 717116901 991045458
46
204203051 712111548 831682942 714447701
216624343 685651065 822697916 707645749
508468707 78860791 514289121 810150110
110142237 4...

output:

4
144071704 930965737 342130829 342130829
256117152 727230617 86229241 86229241
634517246 635060595 354351558 246618203
709242037 717116901 506606260 254438054
46
9594472 982139335 12212760 12212760
30734501 959699726 6967418 6967418
35362143 937372465 6305559 6305559
38472925 932415926 813620 81362...

result:

ok both cnt and k values are correct (10000 test cases)

Test #176:

score: 8
Accepted
time: 638ms
memory: 12624kb

input:

100
1593
229188098 526993278 753882032 527864377
497371615 229284812 498214549 923205924
277303923 163811795 277837497 918312038
408989572 214484153 409183840 897962338
22052543 336826048 976083740 337795415
157064961 587637605 838254709 587664451
496917291 209099099 497131039 880350315
153839934 29...

output:

1593
229565 999723056 352321 352321
418781 999648426 295976 295976
629075 999003810 370063 370063
1395226 998973445 166663 166663
2371216 998572101 101278 101278
2375486 998194851 195173 195173
2451491 997925310 843 843
2673645 997375513 462958 462958
2826340 997228735 30468 30468
2826350 997001323 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #177:

score: 8
Accepted
time: 1026ms
memory: 68284kb

input:

1
200000
624590789 44975237 624593931 804852590
680213787 47717765 680216933 880088569
145968512 303256333 853353177 303257214
58734550 651991020 941164489 651994152
611407016 73441484 611409364 775984154
522735145 214475060 522744630 967698367
253339991 27037492 253340969 844695090
648913093 161532...

output:

200000
3263 999998845 1897 1897
3541 999997968 2919 2919
4329 999989747 1762 1762
7774 999987201 1739 1739
10264 999987020 431 431
13433 999980108 1612 1612
13452 999977394 1363 1363
13852 999969473 2184 2184
14656 999968381 3479 3479
18092 999967972 1758 1758
19294 999966980 257 257
21091 999960127...

result:

ok both cnt and k values are correct (1 test case)

Subtask #12:

score: 8
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #178:

score: 8
Accepted
time: 78ms
memory: 9788kb

input:

10000
1
12382530 185669825 302128769 747723745
2
143492319 197285983 970890412 946644561
245893540 70721806 823945083 950886281
3
32794373 164483677 832206990 885827426
101642244 27675271 428566998 963570816
357226601 107779816 832776926 983013548
2
2747130 150166610 591663156 975095134
105886119 11...

output:

1
12382530 302128769 562053921 562053921
2
143492319 970890412 749358579 749358579
245893540 823945083 130805897 126564177
4
32794373 832776926 721343750 721343750
101642244 428566998 80104545 80104545
101642244 832776926 134447251 77743390
357226601 832776926 19442732 19442732
3
2747130 591663156 1...

result:

ok both cnt and k values are correct (10000 test cases)

Test #179:

score: 8
Accepted
time: 102ms
memory: 7980kb

input:

1000
3
563970448 97855424 865186952 813641163
587511504 209317866 952754333 275636135
185532086 139165967 372477785 942650522
45
607693096 468508970 811400618 484683388
37778270 654321564 743002315 941831957
72486512 139948601 144130465 758463335
133681860 521233346 798995434 932962054
167749005 267...

output:

3
185532086 372477785 803484556 803484556
563970448 865186952 649467470 538005028
563970448 952754333 66318270 66318270
14
2297003 994498934 178326455 178326455
2297003 998027176 475844573 475844573
3806903 998027176 9143611 9143611
15737930 943010175 9790250 9790250
15737930 980466978 174484682 174...

result:

ok both cnt and k values are correct (1000 test cases)

Test #180:

score: 8
Accepted
time: 133ms
memory: 10508kb

input:

100
143
952459134 869810060 983279471 987167323
222478195 310783784 247126227 403621040
26313175 48945885 74260285 175305862
843970113 683300012 882140523 980024497
541343595 413944079 568445330 517494317
831951166 744741188 854414491 862850039
598889638 509032990 627068032 628315948
412784816 59870...

output:

139
8320205 95148994 57987744 57987744
8320205 101884995 47846901 47846901
8320205 445537846 36160646 36160646
26313175 74260285 10668516 10668516
26313175 133040695 39785759 39785759
26313175 154967753 3109510 3109510
26313175 242248059 72796193 72796193
45024137 242248059 1785436 1785436
45024137 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #181:

score: 8
Accepted
time: 209ms
memory: 20716kb

input:

1
50000
590596658 682793714 595886962 700446082
270604969 785402003 273020343 787984814
46889029 68781674 58595139 73047875
286655479 678383344 286981395 699454178
705798450 216708219 710464472 225359466
878208553 685215244 879709674 685326799
176811775 498681125 177223383 501271288
399830930 433322...

output:

5243
50380 33233281 1302413 1302413
50380 57983471 228429 228429
50380 100131672 4074472 2094543
59764 37431415 871898 871898
59764 120016595 323292 323292
59764 120606291 406857 406857
59764 171947675 310655 310655
59764 348944713 2298139 1338445
59764 350169779 1708451 1708451
59764 453774340 1193...

result:

ok both cnt and k values are correct (1 test case)

Test #182:

score: 8
Accepted
time: 216ms
memory: 27112kb

input:

1
50000
685754590 82037271 685851738 82147370
721461741 51066604 721994066 53756165
684940564 550255265 686797226 550843442
344436365 580978889 346260699 582455332
607986226 102110942 608498796 102211719
283217187 23014149 283276264 23090665
771404495 55299062 772875979 55469628
830319365 479840932 ...

output:

50533
2515 3100682 256162 256162
29154 339563 895565 895565
29561 183448 39941 39941
30722 1605770 977686 977686
39408 1892430 171632 171632
43710 1176008 1644479 1644479
66880 391153 966602 966602
67798 1576556 721018 721018
74667 2521976 1647468 1647468
109262 847738 1524615 1524615
137084 716375 ...

result:

ok both cnt and k values are correct (1 test case)

Test #183:

score: 8
Accepted
time: 81ms
memory: 10048kb

input:

10000
12
215666668 723501313 956508171 982136449
846501862 308182977 906753288 957779709
120158379 708251736 890322343 885549526
19426913 13729087 133278431 252234751
42236869 359582437 419518261 410566749
784904617 106274486 801748773 637628902
173886549 26562042 897345733 60267353
163578488 587610...

output:

13
19426913 133278431 122217791 122217791
19426913 754655431 116287874 116287874
19478156 754655431 110017494 110017494
42236869 649978771 48314504 48314504
120158379 906753288 15249577 15249577
120158379 956508171 162048214 162048214
163578488 906753288 8654486 8654486
173886549 897345733 33705312 ...

result:

ok both cnt and k values are correct (10000 test cases)

Test #184:

score: 8
Accepted
time: 110ms
memory: 10036kb

input:

1000
12
685803519 126238752 728855126 128174384
63983952 287603576 546305523 301831157
59633671 210293968 634523349 283485745
295673971 842741712 514809254 961689391
382121094 704813045 401945865 842857688
417568775 111142739 966816688 303856898
7240115 437122421 771040130 477832787
888073534 169096...

output:

12
7240115 771040130 40710367 40710367
59633671 966816688 69202831 69202831
59633671 994898802 3988947 3988947
63983952 994898802 14227582 14227582
295673971 514809254 118947680 118947680
328995998 994898802 97188587 93070757
382121094 401945865 137928667 137928667
417568775 966816688 99151229 99151...

result:

ok both cnt and k values are correct (1000 test cases)

Test #185:

score: 8
Accepted
time: 140ms
memory: 10208kb

input:

100
198
792311763 254120345 797162837 665217419
628595237 381144760 636091564 858880021
335029985 847893998 532754962 853910446
214773395 276055403 568932137 335487532
272326274 33560067 275923600 359132159
964315668 277227837 973065594 835308168
413136886 210559977 427092945 918111960
407764405 237...

output:

192
1210144 997796781 8333497 8333497
1702498 995445459 5875203 5875203
2558419 616549505 32369162 13951401
2558419 768384942 10883043 10883043
2558419 995445459 5488115 5488115
3870787 62648554 162993618 90159926
3870787 616549505 3087235 3087235
3870787 841060709 2970080 2970080
3870787 995445459 ...

result:

ok both cnt and k values are correct (100 test cases)

Test #186:

score: 8
Accepted
time: 256ms
memory: 23052kb

input:

1
50000
796593339 56511297 796640820 992205409
133193668 211418645 133277986 909797251
440870281 417142769 866117595 417181649
541361044 802078311 849846413 802151179
743810855 113120631 743888398 976129351
184822851 24466796 184871845 811841111
188290755 659483042 539181945 659543334
53495816 37398...

output:

43151
229 999929276 46842 46842
1660 986002313 1541 1541
2635 999951401 182602 182602
5909 984896949 50620 50620
7453 999997284 282660 282660
7898 600158491 497 497
7898 896122278 13741 13741
13933 999997278 209626 209626
19353 999778974 42118 42118
28675 996696513 100910 100910
29082 978185593 2614...

result:

ok both cnt and k values are correct (1 test case)

Test #187:

score: 8
Accepted
time: 265ms
memory: 23836kb

input:

1
50000
751671299 466040901 972430908 466046633
14175694 746183397 941808121 746213800
11879718 962059053 310015823 962115823
590153828 71979365 769454422 72038895
801695226 347394043 801739630 767299637
59100482 999191601 557950291 999227712
758691706 320595882 758736896 666806092
153023328 2686384...

output:

49548
5419 998798491 46981 46981
14050 992145213 134718 134718
22494 998952471 87311 87311
22777 996585431 32870 32870
25961 999430242 92183 92183
26069 537481267 38375 38375
27481 999384741 33139 33139
34228 999952075 69863 69863
36269 975244799 75205 75205
38611 999475472 14914 14914
43511 9999865...

result:

ok both cnt and k values are correct (1 test case)

Test #188:

score: 8
Accepted
time: 244ms
memory: 26624kb

input:

1
50000
211810463 794820877 959787106 794855991
696378656 162336060 701392861 162348429
977438664 258464097 977450037 429118421
495596748 506223490 495610380 712336922
695534449 206308800 695550528 832254446
28167498 26676056 945905932 26709442
451934381 48322454 846322316 48336902
546704409 3444748...

output:

50726
1091 995876812 30678 30678
7772 998908254 16833 16833
9914 868738666 30905 30905
11425 999881182 5174 5174
14413 354710973 800 800
14413 372395898 655 655
14533 979104326 8756 8756
15422 999923233 2957 2957
20171 45957 471256354 135707251
20171 47840 457226749 82254405
20171 941700345 43100 43...

result:

ok both cnt and k values are correct (1 test case)

Test #189:

score: 8
Accepted
time: 264ms
memory: 32896kb

input:

1
49952
298749988 141317978 303199882 144418107
568493074 107073341 573484274 110079049
861651096 359383858 864643660 364452104
858310428 543975859 861446086 549605636
256940843 80401274 261180965 82557835
713676231 782595330 718131862 786484218
668338532 914959930 673317437 917222341
939131832 5885...

output:

149409
3598 26559 2853946 2853946
3598 68192 1087102 1087102
3598 145871 729681 729681
3598 203410 609391 609391
12615 51385 2311775 2311775
12615 145871 670803 670803
12615 173905 480592 480592
12615 298663 628026 628026
18820 68192 1997603 1997603
18820 156427 1043904 1043904
18820 344515 477357 4...

result:

ok both cnt and k values are correct (1 test case)

Test #190:

score: 8
Accepted
time: 192ms
memory: 30168kb

input:

1
50000
167412864 169873190 167438766 169917456
316514353 318473248 316567428 318533720
700348811 703746884 700412233 703788124
785546562 789253989 785601001 789295973
81140516 83719040 81182797 83785704
786712397 790204343 786775619 790257213
859483948 862489380 859508766 862555719
910180128 912669...

output:

124998
3598 26559 36228 36228
3598 51385 736 736
3598 110274 3324 3324
3598 148879 3767 3767
12615 51385 20274 20274
12615 94044 16277 16277
12615 162117 3894 3894
18820 53903 1840 1840
18820 110274 9322 9322
33051 94044 29982 29982
33051 145871 14464 14464
33051 197861 405 405
45432 110274 16681 16...

result:

ok both cnt and k values are correct (1 test case)

Test #191:

score: 8
Accepted
time: 122ms
memory: 12804kb

input:

1
50000
430076044 192415638 432032232 193343299
295002371 943441425 295555498 944640540
475061156 467369775 475995858 468321451
289363613 360918936 291245659 361858036
380144492 104362224 381905611 104926698
473449716 211102288 474719975 212104078
232908342 111873896 233763493 112456497
578025521 14...

output:

8933
451836 926021 6671118 1411786
663195 1181713 5721297 1173043
676375 1183081 7960348 1868916
676375 1936283 925648 925648
730866 1367278 7777812 2270794
730866 2307491 796554 796554
746501 1462195 10384845 1593320
926022 1676259 8309014 1923054
1181714 1936283 7576411 1371868
1181714 2361532 822...

result:

ok both cnt and k values are correct (1 test case)

Test #192:

score: 8
Accepted
time: 217ms
memory: 26160kb

input:

1
50000
194838464 393415820 916846945 393428542
744814054 113091750 744838109 797816560
200031166 382768555 943870701 382770047
79429989 638541092 939370107 638544308
247048622 435619498 980201187 435651254
16359359 532920978 953848271 532936109
181555421 650664160 827579301 650665681
355715955 1657...

output:

50000
10130 876960021 9638 9638
66031 995972676 20593 20593
69665 881482625 2609 2609
76270 872147603 8920 8920
83973 817918167 7935 7935
92395 852882840 28259 28259
101240 851534722 24798 24798
103413 961041065 402 402
120086 968322850 1825 1825
122056 978672474 643 643
126328 938551637 22247 22247...

result:

ok both cnt and k values are correct (1 test case)

Test #193:

score: 8
Accepted
time: 212ms
memory: 22084kb

input:

1
50000
386692747 95294124 389220160 106944896
975268088 143161922 976468645 157622303
368115744 32591771 371312876 35146333
637726972 703319762 644869700 703735054
627199597 790621674 633825690 793974673
523167548 533346921 526860665 534755775
165342759 921636996 169513014 922290144
194392249 67983...

output:

22167
21769 1039990 726357 726357
21769 1071999 55755 55755
21769 1085535 247626 247626
21769 1137920 1287596 1287596
21769 1179021 744986 744986
21769 1237312 498784 498784
21769 1266448 75936 75936
21769 1320595 15567 15567
21769 1355402 1348874 1348874
21769 1370760 171565953 154986546
21769 1492...

result:

ok both cnt and k values are correct (1 test case)

Test #194:

score: 8
Accepted
time: 202ms
memory: 26800kb

input:

1
50000
242273042 176756787 243790219 178776506
767034071 875667575 767280470 877324113
603391029 500616553 605413028 500708551
854287440 774701052 854410372 774703271
373462169 207873397 373637371 209424157
779884419 507630834 779920429 517938308
362967837 326166169 363726097 326520987
755249065 90...

output:

50537
24968 530146 5648 5648
24968 604919 25374 25374
24968 689748 3129 3129
24968 876093 89751 89751
24968 1041081 15989668 15989668
24968 1068950 360558 360558
24968 1138237 5755 5755
24968 1140905 845726 845726
24968 1171110 371198 371198
24968 1212396 504397 504397
24968 1440620 47037 47037
2496...

result:

ok both cnt and k values are correct (1 test case)

Test #195:

score: 8
Accepted
time: 297ms
memory: 28432kb

input:

1
50000
812558725 221455975 812601339 720640631
506674362 147292956 506771754 646250054
497065920 386112440 497102092 885242410
331334709 135132694 331409123 634699753
432436178 28730202 432466379 528944718
9962370 224694645 10003336 723807368
16269770 276800159 16310358 774513414
916550019 37153758...

output:

99999
4519 32768 280718308 280718308
4519 95547 47794368 47794368
4519 320024 87032432 87032432
4519 399292 51323105 51323105
4519 1631746 3905341 3905341
4519 1745707 9036570 9036570
4519 3148684 5312936 5312936
4519 4694079 6989463 6989463
4519 5424737 757052 757052
4519 8817472 3410760 3410760
45...

result:

ok both cnt and k values are correct (1 test case)

Test #196:

score: 8
Accepted
time: 303ms
memory: 29636kb

input:

1
50000
467579201 175935353 467585407 676055514
234788510 391544387 234831015 892894570
781104502 267068265 781139982 767293756
366085424 62819894 366090271 563896889
575525262 178239839 575532211 678163183
161545969 385345862 161559406 886794186
739967452 157752574 739975555 657569585
530248555 442...

output:

99999
21222 48369 323357255 323357255
21222 190214 14148975 14148975
21222 210005 47707643 47707643
21222 225380 25351720 25351720
21222 248473 3517213 3517213
21222 330394 38096632 38096632
21222 608181 18370547 18370547
21222 642754 4718445 4718445
21222 929763 1952119 1952119
21222 1142598 899119...

result:

ok both cnt and k values are correct (1 test case)

Test #197:

score: 8
Accepted
time: 246ms
memory: 26356kb

input:

1
50000
324121297 336540278 678215009 658245449
106238467 444938626 894021342 550787105
17652 367983617 999968687 367987342
426338781 286576652 576659805 710141273
17652 587589229 999968687 587591449
17652 433991050 999968687 434017361
17652 334887828 999968687 334889988
17652 315956608 999968687 31...

output:

37500
518 17651 519213624 88041956
518 999996951 123675260 115577
33296 52372 756524841 241612580
33296 999914603 65259 41975
58941 70857 806603921 232468712
58941 999884277 42715 24463
152616 153250 626691328 181441751
152616 999821505 61972 41109
158259 253109 645976774 230167188
158259 999780755 ...

result:

ok both cnt and k values are correct (1 test case)

Test #198:

score: 8
Accepted
time: 128ms
memory: 7928kb

input:

200
62
261781449 944921366 569542727 946559953
849302708 36998806 858009870 344054392
383732304 394837239 571727548 395008084
154060221 976969399 186362047 986351657
431312015 164960171 436398933 691955261
13821302 78343825 22508133 231762536
578949234 147873646 579782986 806881650
169606867 3868425...

output:

62
5238887 7025969 451383408 451383408
9224536 10538690 338511247 338511247
13821302 22508133 153418712 153418712
24870212 37538528 148969358 148969358
41125112 341800515 4120564 4120564
46998441 48314381 449475026 342187726
53505402 60657905 429033082 333051971
71338576 427791017 25274 25274
913119...

result:

ok both cnt and k values are correct (200 test cases)

Test #199:

score: 8
Accepted
time: 245ms
memory: 27000kb

input:

1
50000
593485867 114500956 593488226 906188206
675965003 268727326 800330360 268742715
110674626 8864374 768971709 8869240
9530030 709683821 9539421 836933956
346288833 642485942 869375012 642518130
747463582 395205521 747463585 929204463
852077754 459481696 852082503 835725297
261634222 297023322 ...

output:

50000
43140 582428616 8037 8037
76270 101239 346307121 317036288
103413 76378138 6636 6636
120086 128607 135297022 72472249
132431 839598712 3493 3493
141526 149450 323236887 232843578
153580 402454626 1303 1303
157510 162739 29460637 29460637
168328 250363707 7650 7650
182141 50857516 9016 9016
198...

result:

ok both cnt and k values are correct (1 test case)

Test #200:

score: 8
Accepted
time: 185ms
memory: 26608kb

input:

1
50000
640877873 359379086 640987396 359492266
45960842 954688076 46060230 954794269
977446526 23620343 977526944 23674072
358739777 645142284 358809768 645183603
200279148 802586962 200316919 802656635
29489051 971171114 29567315 971264963
246220137 757343206 246250552 757391540
770730639 23023696...

output:

99999
8148 35328 12957 12957
8148 57788 3654 3654
8148 121541 9859 6490
16221 48680 6554 6554
16221 121541 12189 12189
16221 177916 5582 5138
29118 57788 4983 4983
36525 121000 1636 1636
36525 177916 16375 16375
36525 209520 24529 12509
40491 121541 12957 12957
83553 138065 2697 2697
83553 209520 56...

result:

ok both cnt and k values are correct (1 test case)

Test #201:

score: 8
Accepted
time: 211ms
memory: 29808kb

input:

1
50000
125026268 872723348 125280370 872950876
624325646 374331278 624682917 374530329
869119501 132710566 869452966 132994009
430379247 566717225 430687649 566942767
890974733 111133454 891351380 111303149
624472448 372380816 624752043 372633152
153706051 844493634 153962454 844686729
259865976 73...

output:

144990
690 24233 136833 136833
690 106240 37275 37275
690 148101 31157 31157
690 268519 23760 23760
8094 77064 115904 115904
8094 148101 25974 25974
8094 239400 33827 33827
8094 350404 1752 1752
12413 106240 82159 82159
12413 203064 37391 37391
12413 365739 17326 17326
52358 141220 111944 111944
523...

result:

ok both cnt and k values are correct (1 test case)

Test #202:

score: 8
Accepted
time: 212ms
memory: 24140kb

input:

1
50000
714469563 274565715 714473244 722892376
351055805 386286883 782457277 386303871
15576850 334701229 122613814 334856845
350048816 525285326 834556015 525408401
33755674 755487213 104565443 755628911
196711279 185091105 196718198 804518485
463271887 892180397 677441520 892208208
809558861 4226...

output:

50000
5249 999965732 6820 6820
7739 999965581 2846 2846
16770 999949490 4481 4475
37018 999939059 16447 12535
42499 999931473 3577 3577
56518 999925533 20576 15491
60291 999911421 15056 14224
70647 999910058 57595 48520
78943 999905960 4402 4402
82192 999895126 5073 4178
108558 999875336 779 779
116...

result:

ok both cnt and k values are correct (1 test case)

Test #203:

score: 8
Accepted
time: 194ms
memory: 17684kb

input:

1
50000
323787758 239708425 323789077 758598499
351080151 203887694 351089364 793627553
711105513 284908688 898000823 284919675
623450460 319805784 623456669 683152205
157586409 128017983 157589426 870257360
506686159 177947410 506691079 827345142
768998063 93324771 840317446 93446852
60860970 20771...

output:

50000
28136 999980906 86879 86879
37525 999964528 15172 15172
44915 999956678 39151 39151
59131 999950158 11133 11133
66428 999942549 34044 25047
80434 999930078 8840 8840
82530 999927206 3154 3154
87493 999914082 26919 26919
92261 999912694 87202 70021
97383 999908580 10712 10712
107995 999901497 2...

result:

ok both cnt and k values are correct (1 test case)

Test #204:

score: 8
Accepted
time: 152ms
memory: 20936kb

input:

1
50000
160915777 812284099 165076767 812298843
361598366 666553495 361623341 666556533
941833742 563855901 954602414 572402682
110682926 580718165 178588071 581146120
783773149 31701806 783815006 31710448
449562334 194659583 449571686 194662350
856730817 695148434 856777262 695177085
784081781 5459...

output:

25132
11164 254444 371000 371000
11164 362196 10877 10877
11164 468606 7668 7668
11164 587312 6476960 6476960
11164 660376 132062 124416
11164 1292986 5199935 5199935
11164 1336522 1776646 1776646
11164 1508404 4119133 4119133
11164 2100656 7106184 7106184
11164 2708711 3656901 3656901
11164 2788867...

result:

ok both cnt and k values are correct (1 test case)

Subtask #13:

score: 8
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #12:

100%
Accepted

Test #205:

score: 8
Accepted
time: 130ms
memory: 7700kb

input:

20000
2
448873073 561199394 861299476 748915645
16389288 14863376 545793993 935059078
4
119264287 323531140 419962431 827307421
21514037 82135563 113616954 484836990
396295950 8986299 966205320 817389172
490647537 130469426 838015733 943565242
2
44276726 103278215 438999937 861189426
498783259 21325...

output:

2
16389288 545793993 732479451 546336018
16389288 861299476 187716252 187716252
5
21514037 113616954 402701428 402701428
119264287 419962431 9918249 9918249
119264287 966205320 493858033 493858033
396295950 966205320 314544841 314544841
490647537 838015733 126176070 126176070
2
44276726 438999937 75...

result:

ok both cnt and k values are correct (20000 test cases)

Test #206:

score: 8
Accepted
time: 195ms
memory: 10096kb

input:

2000
110
220392558 5978824 766493698 741665120
88581745 178180230 633649263 871469474
574423506 315978276 849918149 832563195
687669445 254052550 874241067 913204244
587692914 9614657 845336338 984512862
68080502 829038151 929843267 948625658
457632815 199096502 570635321 969674587
390166021 2086736...

output:

25
1064064 994016018 34848267 34848267
1064064 997506822 94229729 94229729
1064064 997530113 32699333 32699333
2283323 994016018 8138097 8138097
2283323 995309127 264760 264760
2283323 997506822 378237288 378237288
2283323 997530113 83145183 83145183
3242335 916059441 314985 314985
3242335 964610734...

result:

ok both cnt and k values are correct (2000 test cases)

Test #207:

score: 8
Accepted
time: 269ms
memory: 10268kb

input:

200
188
63014878 676871895 67683062 792567711
564013481 888646925 660072313 940828072
337113400 964214369 445319577 970676078
369119071 876324279 383228275 916569350
566270165 273290005 591500437 311163130
595513722 318323227 611210645 330784422
67501567 515763503 127052360 539558780
363030573 59166...

output:

135
577256 349782204 982240 982240
577256 572341913 24991133 16362741
577256 637972217 47992101 38069466
577256 848479132 8857507 8857507
577256 959289944 39730514 39730514
2743969 87943988 92666529 92666529
15722017 357041671 20183767 20183767
26487487 153197532 38625473 38625473
30876787 357041671...

result:

ok both cnt and k values are correct (200 test cases)

Test #208:

score: 8
Accepted
time: 495ms
memory: 36308kb

input:

1
100000
456816308 907316371 461937839 909485614
277942963 299539451 283976286 300620231
47829088 61529218 51932183 68450483
463356845 198743985 466254975 200541967
505841863 858692421 514009991 866115767
342489258 765678982 345598582 766455906
771653616 619818297 774580334 626800636
416446448 63610...

output:

50376
1263 115123 55180 55180
7780 1171438 4096214 4096214
8346 1819808 1087397 1087397
8346 4049170 934371 934371
8346 6052360 264802 264802
8346 19556534 2394823 2394823
8576 21281059 175933 175933
8576 29513298 743865 743865
8576 34237752 903089 793749
8576 41416955 541235 541235
8576 53675826 51...

result:

ok both cnt and k values are correct (1 test case)

Test #209:

score: 8
Accepted
time: 485ms
memory: 42248kb

input:

1
100000
847211528 613032358 847791878 614436059
757950276 279767972 761116014 281042441
657658304 757681524 657952639 757871209
491414124 613587337 492337733 613726755
487769792 406350204 488312039 406604225
913515864 160183103 914256380 160603208
417961544 701239314 418525447 701871987
120978337 9...

output:

102479
8344 342411 834874 834874
28526 342663 115442 115442
49387 2179866 927566 927566
49524 280179 362614 362614
70727 836470 672497 672497
86884 203522 1971644 1971644
86884 299712 512295 512295
92681 1350284 702643 702643
126260 601573 24831 24831
154586 1247574 476131 476131
158155 160176 15311...

result:

ok both cnt and k values are correct (1 test case)

Test #210:

score: 8
Accepted
time: 148ms
memory: 7760kb

input:

20000
4
533868229 54283902 890903756 259357624
712903282 818587675 738525239 874130755
10550603 105690454 958489170 338648127
19100619 69608128 374065833 221525395
1
248057272 618715626 365821997 685464591
6
87710494 731498179 561543454 784944671
119482599 878735517 982093499 888906625
497669557 573...

output:

4
10550603 958489170 232957674 232957674
19100619 374065833 36082326 36082326
533868229 890903756 51406552 51406552
712903282 738525239 55543081 55543081
1
248057272 365821997 66748966 66748966
7
87710494 561543454 44933623 44933623
87710494 808609889 8512870 8512870
119482599 990744442 10171109 101...

result:

ok both cnt and k values are correct (20000 test cases)

Test #211:

score: 8
Accepted
time: 214ms
memory: 9864kb

input:

2000
30
671227267 477703247 790572673 647925249
717285441 12710544 893100100 959959488
586965016 160476494 703342490 559152549
333001670 125304673 994478279 296264312
328994613 119052928 348666969 513882509
43093003 384572726 47929584 448100770
769494423 233115763 867855723 988206533
213463196 24732...

output:

26
22720392 893100100 16422036 16422036
37525115 893100100 170243134 135432599
37525115 977172632 17269665 17269665
43093003 47929584 56953250 56953250
52608368 985428878 7882333 7882333
52608368 994478279 78384351 78384351
69424018 978202881 43537083 43537083
69424018 985428878 64833523 64833523
10...

result:

ok both cnt and k values are correct (2000 test cases)

Test #212:

score: 8
Accepted
time: 273ms
memory: 10204kb

input:

200
132
612051788 106797672 639297550 737402220
591233929 30687699 637663743 922531537
471351718 114297575 808366863 116812306
656007104 70360462 659267393 842963799
2362370 92207986 987687742 92892453
441693258 88959550 863629055 153888450
260335394 625018373 464858464 639620266
296907701 294061152...

output:

114
25060 999792908 28961423 28961423
2362370 987687742 684468 684468
6297713 931311101 13465711 13465711
7272887 76415680 488750582 182234639
7272887 502716583 20778242 20778242
7272887 639297550 4395723 4395723
7272887 757581291 6527738 6527738
7272887 832448518 13996401 13996401
7272887 892374481...

result:

ok both cnt and k values are correct (200 test cases)

Test #213:

score: 8
Accepted
time: 536ms
memory: 37784kb

input:

1
100000
62569100 816319097 298588959 816377142
690235108 610871746 690295257 673866461
563295213 15756866 563336853 856648370
23392288 202674436 994449318 202799228
519993513 585089096 520068494 858261610
413459062 676583667 811613247 676607833
738645293 478098822 844240105 478182184
215365008 2165...

output:

77292
870 999998642 128607 128607
2027 970801045 7911 7911
2027 983360194 35885 35885
4528 999998826 30 30
5927 900277038 16005 16005
5927 908784226 18244 18244
6460 900095379 51866 38176
6460 929145794 17343 17343
6460 993130284 8029 8029
7044 937280192 25045 18729
7044 974707140 38797 38797
7321 9...

result:

ok both cnt and k values are correct (1 test case)

Test #214:

score: 8
Accepted
time: 548ms
memory: 38748kb

input:

1
100000
502973888 520924227 637427229 520991054
775593763 517329064 775612954 999769743
343914153 15569648 343927069 979257284
797908759 471214570 797950917 497398336
554931176 108754284 554933735 446948261
392633904 24542414 392710286 866467327
698026650 69709194 698028819 868644203
875313746 2981...

output:

95654
2014 991672367 33857 33857
3109 999094964 18406 18406
3234 999937371 23277 23277
5043 879283872 9574 9574
5043 953449917 22518 22518
5376 998570451 83115 83115
7329 999557286 91470 91470
8063 999819432 120566 120566
8582 994348498 474 474
12188 999985419 72267 72267
16442 879946584 1091 1091
1...

result:

ok both cnt and k values are correct (1 test case)

Test #215:

score: 8
Accepted
time: 538ms
memory: 42120kb

input:

1
100000
885993011 703522473 885995575 986187907
210009068 960646 210009449 997186421
684783605 47413722 684789883 966852422
699368923 514893917 699412022 862556438
888689394 263815969 888691282 297807757
391625213 963577331 789088557 963588953
241836347 663263628 241875546 912292035
433599058 55079...

output:

101154
824 999693715 10961 10961
1442 999997340 14307 14307
2020 973192979 2805 2805
2310 999984075 1855 1855
2893 999970808 4118 4118
5136 740377523 2201 2201
5466 998652721 2594 2594
8210 801789804 3551 3551
8988 981366650 3294 3294
11358 902995294 5853 5853
11516 999999985 771 771
13745 995427068...

result:

ok both cnt and k values are correct (1 test case)

Test #216:

score: 8
Accepted
time: 578ms
memory: 51500kb

input:

1
99856
936741666 751974919 938179569 754865401
502281024 139742533 505830255 142053926
862132552 452185419 864319604 455402978
806012693 244549438 808518689 247489852
336511896 45255238 339873778 46538811
62662881 262956067 64175267 266065343
135737841 193571046 137789728 196155834
183390876 712639...

output:

298936
3731 21334 2087653 2087653
3731 45716 707257 707257
3731 68004 429210 429210
3731 94738 409229 409229
9305 32997 2075090 2075090
9305 68004 342935 342935
9305 88323 457712 457712
9305 124099 320050 320050
10135 45716 1455283 1455283
10135 75910 717751 717751
10135 135440 315160 315160
21595 6...

result:

ok both cnt and k values are correct (1 test case)

Test #217:

score: 8
Accepted
time: 394ms
memory: 48720kb

input:

1
100000
990166360 990552671 990200325 990598650
301895210 302188631 301922344 302228492
747358677 746896507 747410535 746915162
587211542 584546329 587244542 584578384
99707248 98580118 99733201 98607986
17731181 17690964 17784100 17731928
68843167 68547388 68869640 68601169
383393572 381840869 383...

output:

249998
3731 21334 17583 17583
3731 32997 9755 9755
3731 61584 7388 7388
3731 71413 1164 1164
9305 32997 11853 11853
9305 57344 510 510
9305 81360 3449 3449
10135 44953 11480 11480
10135 61584 2846 2846
21595 57344 21642 21642
21595 71349 6417 6417
21595 94738 4986 4986
32506 61584 3562 3562
32506 71...

result:

ok both cnt and k values are correct (1 test case)

Test #218:

score: 8
Accepted
time: 249ms
memory: 15464kb

input:

1
100000
358318887 343781180 359015796 345646229
13210996 655123905 15342809 655990177
914123599 292140251 916046880 292915442
102444020 343620158 103167701 344990896
692046738 966694209 692929352 967509602
78147097 549369043 79237565 550575114
861443306 437330156 862114661 439387467
312837961 68860...

output:

17758
717652 1439612 20904923 1592934
717652 2986935 130061 130061
717652 3140822 736438 736438
870186 2091172 23835023 2032856
870186 3140822 484802 428572
870186 3420037 199031 199031
1040760 2414101 18341135 1960741
1040760 3420037 134563 134563
1040760 3575240 1631286 1359762
1106509 2986935 872...

result:

ok both cnt and k values are correct (1 test case)

Test #219:

score: 8
Accepted
time: 503ms
memory: 39200kb

input:

1
100000
315241519 177276179 315241841 768634981
89194616 569375119 836805010 569381836
191667873 533639754 800643205 533640627
243292774 353020062 880931752 353022037
17639310 434902231 958991891 434910934
110573474 680492435 957130117 680494409
84661484 337250248 929955951 337273154
540307569 1868...

output:

100000
1630 980565232 2871 2871
9305 950405137 5095 5095
10135 858291425 5904 5904
13110 763368970 1062 1062
15956 810296305 3185 3185
21335 820767020 999 999
45717 944668912 1371 1371
48596 875884783 9150 9150
61585 810337736 1387 1387
66735 786244772 6355 6355
67148 837597465 6957 6957
67658 89768...

result:

ok both cnt and k values are correct (1 test case)

Test #220:

score: 8
Accepted
time: 435ms
memory: 37464kb

input:

1
100000
663141040 475390851 703366587 475812377
598827788 674022756 624285034 674714724
835374546 749237819 837284929 751126921
394023816 754750003 404534985 756044160
561637190 427244419 571494144 428728388
897845174 171780298 901575687 172902761
649196037 24555624 682943616 24896009
478949749 211...

output:

27837
4623 305646 543365 543365
4623 309206 2035806 2035806
4623 350382 1431871 1431871
4623 363275 607059 607059
4623 365628 132033 132033
4623 387490 953635 953635
4623 391198 2508485 2508485
4623 393125 355211 355211
4623 407858 1320517 1320517
4623 434296 381632 381632
4623 449393 1390904 139090...

result:

ok both cnt and k values are correct (1 test case)

Test #221:

score: 8
Accepted
time: 451ms
memory: 39328kb

input:

1
100000
533066754 790327414 533072254 791297148
570937388 681664822 570953783 739499351
243215196 447692040 243253639 448904822
267577411 947250535 267610405 947597049
957674266 960657160 957756101 961061336
419699111 915183193 419756713 915233420
670082079 698355044 670107459 740313677
633618062 7...

output:

108759
14276 1038047 14051735 12532179
14276 1178827 76518 76518
14276 1182942 72568 72568
14276 1207604 207630 207630
14276 1220522 1038430 1038430
14276 1246453 44262 44262
14276 1256215 8464 8464
14276 1272574 119573 119573
14276 1293550 1495106 1495106
14276 1359709 14961 14961
14276 1403089 340...

result:

ok both cnt and k values are correct (1 test case)

Test #222:

score: 8
Accepted
time: 635ms
memory: 45796kb

input:

1
100000
912937811 1697087 912957320 503403355
231047338 346322738 231065549 846331178
696085958 394518659 696102199 893886482
370258779 187022407 370275111 687316724
230973729 310852195 230985667 811434897
982464657 137085220 982468871 637941148
420794074 402844383 420831974 901659994
1183423 14658...

output:

199999
376 10504 214142616 214142616
376 24717 176836415 176836415
376 30089 35156430 35156430
376 73933 25890982 25890982
376 94912 31535602 31535602
376 134096 862098 862098
376 240369 3020448 3020448
376 305462 7398742 7398742
376 375670 3523207 3523207
376 640928 2458040 2458040
376 2032879 3840...

result:

ok both cnt and k values are correct (1 test case)

Test #223:

score: 8
Accepted
time: 521ms
memory: 40520kb

input:

1
100000
933697649 224512734 933711111 940768657
157399520 418910163 842490871 578585196
76073538 65203183 76080421 830484410
30387629 483558289 970638855 514408564
24412 452236963 999991570 452240352
498176039 248045398 500769005 749581478
24412 674936145 999991570 674940513
24412 464394162 9999915...

output:

75000
13949 24411 674151649 241244679
13949 999995999 124798403 53529
57345 61116 727472366 178842949
57345 999981367 4024 2014
78925 107746 588813601 126043946
78925 999951311 6262 4022
115588 118997 807303423 239118612
115588 999920927 21275 7512
122701 124270 596642195 182078477
122701 999904872 ...

result:

ok both cnt and k values are correct (1 test case)

Test #224:

score: 8
Accepted
time: 259ms
memory: 10076kb

input:

500
8
417320150 887553460 847543547 963081211
807264174 796555820 969616648 813065828
416459354 452809162 433037697 471672880
362161467 167176249 916252601 259640532
11776736 85170284 211750665 686455179
620818018 25160362 649040383 610099054
766792046 116313102 792795055 743914240
679552136 2988686...

output:

8
11776736 211750665 601284896 601284896
362161467 916252601 92464284 92464284
416459354 433037697 18863719 18863719
417320150 847543547 75527752 75527752
620818018 649040383 492474409 350458522
679552136 757815154 349807534 349807534
766792046 792795055 535136855 484273708
807264174 969616648 16510...

result:

ok both cnt and k values are correct (500 test cases)

Test #225:

score: 8
Accepted
time: 530ms
memory: 41744kb

input:

1
100000
41319580 30240027 265034939 30244690
792373759 322467110 854617183 322471099
258726754 486721522 718342864 486723635
627307105 620187823 887149364 620194998
85423024 657625428 947061449 657627972
731692857 338145638 875366912 338150116
224570919 646406206 224588081 892028888
147758667 44121...

output:

100000
1630 891865772 12146 12146
10135 13109 474602144 262553365
15956 811078495 1576 1576
21335 63698 305627601 147686300
66735 643478593 7997 7997
67148 7724898 4702 4702
67658 630666137 6705 6705
71350 71413 569908269 436325387
89300 93391 89507233 70678509
94286 446632554 2986 2986
100703 10514...

result:

ok both cnt and k values are correct (1 test case)

Test #226:

score: 8
Accepted
time: 368ms
memory: 45396kb

input:

1
100000
817313190 181338337 817351989 181345641
638686282 362120809 638700162 362128067
752704936 246750241 752722413 246780723
898485771 99618226 898518167 99654927
986505522 13002907 986528285 13013782
726713455 273198205 726737186 273213177
103349536 896563013 103370660 896583062
587606645 41320...

output:

199999
2195 14200 968 968
2195 24548 7061 7061
2195 31789 13718 10060
3667 18167 5013 5013
3667 31789 2224 2224
3667 71854 24181 22422
11438 24548 2615 2615
15859 30566 2882 2882
15859 71854 645 645
15859 89135 9502 4837
16897 31789 968 968
26086 71264 229 229
26086 89135 219 219
26086 119672 4959 3...

result:

ok both cnt and k values are correct (1 test case)

Test #227:

score: 8
Accepted
time: 433ms
memory: 52172kb

input:

1
100000
428517157 572764364 428700181 572870954
755975603 246372022 756133455 246493757
758178988 243906718 758318617 244005562
810027255 192993726 810135388 193094136
858727547 143007910 858891795 143128500
396037010 605694441 396157135 605810293
362802311 638533299 363014032 638662764
189408371 8...

output:

289990
8495 19699 58903 58903
8495 49739 31678 31678
8495 80040 4759 4759
8495 121210 8468 8468
14022 38839 73960 73960
14022 80040 26418 26418
14022 107001 25996 25996
14022 165387 26203 26203
17047 49739 30348 30348
17047 96564 8788 8788
17047 187831 15573 15573
21178 76812 66327 66327
21178 10700...

result:

ok both cnt and k values are correct (1 test case)

Test #228:

score: 8
Accepted
time: 484ms
memory: 40524kb

input:

1
100000
179616518 431048990 179619409 565466973
501879388 157053145 501891569 846986662
869844046 22896402 869847332 973619299
314992662 342487360 355534645 342565771
551437523 321766293 595454026 322075550
443847747 462821198 629745993 462877638
320707842 830606588 339687437 830718954
816313713 37...

output:

100000
5744 999991558 3783 3783
18826 999990488 4047 4047
20136 999961923 5874 5874
20190 999961106 2865 2865
23469 999959732 2759 2759
28821 999954037 9882 9882
30725 999945997 8227 8227
33762 999939029 10602 10301
37905 999935257 19424 19424
38805 999925619 9580 9266
42165 999922271 3780 3780
4680...

result:

ok both cnt and k values are correct (1 test case)

Test #229:

score: 8
Accepted
time: 385ms
memory: 27740kb

input:

1
100000
235141549 891937809 277045234 891982634
516805887 376813856 547552417 377062907
749727044 400181899 749733980 595990269
515727074 382816316 548411270 382827498
396386163 237821331 396386816 757783626
397767275 234901642 397769634 761431455
745573040 409371169 745582605 586592728
332650114 1...

output:

100000
8271 999998537 837 837
8687 999996029 45669 37258
13364 999990148 2320 2320
13370 999988487 26829 26829
17428 999980518 12893 7370
31185 999980018 58695 41661
32826 999958428 2048 2048
44314 999958255 71128 69558
45073 999956297 6163 6163
49755 999954417 31212 31212
59137 999952901 10378 7429...

result:

ok both cnt and k values are correct (1 test case)

Test #230:

score: 8
Accepted
time: 318ms
memory: 25948kb

input:

1
100000
588953784 508840978 588979861 509353302
753585226 907707776 756321022 907766685
957518286 389667280 967422979 389940540
483297832 225966227 483357809 227417078
39054103 938699598 39142926 938722011
605171452 581662092 605184460 581726663
851633231 818031929 851669237 818077106
136322398 897...

output:

50304
3839 12736 90139 90139
3839 201853 501935 501935
3839 275058 77320 39007
3839 290832 25901 25901
3839 319889 349718 349718
3839 325930 210928 210928
3839 448048 710051 521537
3839 563995 12841463 11550369
3839 572475 39058400 39058400
3839 583891 2875601 2875601
3839 712517 1032794 1032794
383...

result:

ok both cnt and k values are correct (1 test case)

Subtask #14:

score: 8
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Dependency #8:

100%
Accepted

Dependency #9:

100%
Accepted

Dependency #10:

100%
Accepted

Dependency #11:

100%
Accepted

Dependency #12:

100%
Accepted

Dependency #13:

100%
Accepted

Test #231:

score: 8
Accepted
time: 294ms
memory: 10048kb

input:

40000
1
182205422 131264829 797526511 254338280
4
74207180 6634303 802614415 461791523
425127024 52064700 875512077 126437635
71623800 7735674 736985615 981079330
546169607 137927425 884811982 183102560
2
175208394 474369527 891775850 855439423
105232526 255455997 511952415 566184384
7
579558280 263...

output:

1
182205422 797526511 123073452 123073452
5
71623800 736985615 519287807 519287807
71623800 802614415 334507778 278688963
71623800 875512077 74372936 74372936
71623800 884811982 45175136 45175136
74207180 802614415 1101371 1101371
3
105232526 511952415 218913530 218913530
105232526 891775850 9181485...

result:

ok both cnt and k values are correct (40000 test cases)

Test #232:

score: 8
Accepted
time: 391ms
memory: 9860kb

input:

4000
56
216835226 262723367 805570248 325275443
428913421 502236451 829243784 973956948
742390141 664978155 995257068 941529829
654032198 170497598 655137015 583577789
114722607 288783 294272870 731853574
299194553 173263881 457931303 655761748
206990189 165739648 997283182 861693720
302240029 14831...

output:

14
247636 994005112 49518489 49518489
247636 997283182 517261574 517261574
11500170 940916086 457762 457762
11500170 992635135 18949019 18949019
11500170 995257068 79836109 79836109
11500170 997283182 178692499 178692499
36058681 940916086 682744 682744
77963101 967701536 7389800 7389800
77963101 99...

result:

ok both cnt and k values are correct (4000 test cases)

Test #233:

score: 8
Accepted
time: 533ms
memory: 12196kb

input:

400
61
972527633 498271621 998146196 504860732
653225210 656252101 983172393 657198359
878069170 732299408 980751675 732847782
584358636 93129059 587421439 245265350
507477634 485436327 614050604 755089403
345861028 719452709 525434896 722412741
357393568 616467851 402322034 814021659
720379232 4712...

output:

67
4059282 38741086 52498638 52498638
9393864 84589422 29655170 16911119
9393864 354795587 26341308 26341308
9393864 487176918 14869730 14869730
9393864 550175802 6077893 6077893
14630204 173515292 24875669 24875669
20312885 51103873 74896652 72840990
27739090 129256350 73544102 73544102
29399645 18...

result:

ok both cnt and k values are correct (400 test cases)

Test #234:

score: 8
Accepted
time: 1099ms
memory: 68944kb

input:

1
200000
637566014 281980292 637813199 282132863
739107540 68502470 740849715 72798694
945097854 242248570 947688347 243582508
966811778 766752294 969370912 770092037
176102181 216539195 177720741 220185844
169769240 522426388 172649608 523062648
810825002 843118286 813578060 843693223
82311567 7055...

output:

182661
1660 190399 4111150 4111150
1968 425673 1842396 1842396
1968 703376 747266 747266
2804 2778111 747850 747850
6936 439826 1708241 1708241
8618 989444 1054513 1054513
8618 2053856 742974 742974
12347 154388 2685377 2685377
15761 302638 3179261 3179261
15761 1010336 1156333 1156333
23047 592854 ...

result:

ok both cnt and k values are correct (1 test case)

Test #235:

score: 8
Accepted
time: 996ms
memory: 68416kb

input:

1
200000
540505604 892833042 540834318 893618499
365064549 260997743 365272627 261185028
422396351 352832377 422712022 352859972
282591663 675335521 282637626 675574772
233356942 237504822 233942332 239063253
739272312 133836450 740031374 133924296
111696918 649168800 111881238 649554821
397349749 1...

output:

202229
80 795766 39535 39535
20191 569952 26860 26860
20451 235820 2152928 2152928
23157 89057 570392 570392
33444 167198 170475 170475
37041 1349882 211500 211500
45862 430481 2292054 2292054
46145 218745 411888 411888
46145 793192 21180 21180
55410 1496952 143145 143145
58631 892891 537419 537419
...

result:

ok both cnt and k values are correct (1 test case)

Test #236:

score: 8
Accepted
time: 291ms
memory: 9804kb

input:

40000
1
252936008 16237000 333589230 817592527
1
674870991 816199683 897565983 835607477
1
208089434 747666596 961820086 808179901
3
510743661 273561499 736840223 448330202
437012487 392061782 989472252 408225246
71037844 607429546 444670470 776670777
4
169676892 154448110 869273082 160189678
406947...

output:

1
252936008 333589230 801355528 801355528
1
674870991 897565983 19407795 19407795
1
208089434 961820086 60513306 60513306
3
71037844 444670470 169241232 169241232
437012487 989472252 16163465 16163465
510743661 736840223 158605239 118500283
4
169676892 869273082 5741569 5741569
272765552 692248093 9...

result:

ok both cnt and k values are correct (40000 test cases)

Test #237:

score: 8
Accepted
time: 420ms
memory: 9808kb

input:

4000
26
91358742 447302616 172236540 669700842
444095264 219936360 926494838 269196969
686334353 48629619 753441129 972889386
191270784 651764378 285081012 668388077
568458631 390906510 574933661 887844760
49461696 901625598 331385161 950438614
200648923 938586417 610541700 961221747
327629551 14873...

output:

25
3771421 973501451 41330862 41330862
9069796 982022685 80135873 80135873
22323225 966639681 159551765 159551765
30803873 898311211 20896224 20896224
49461696 331385161 36960819 36960819
49461696 610541700 11852198 11852198
91358742 172236540 201502003 141311956
108919734 627749567 23249826 2324982...

result:

ok both cnt and k values are correct (4000 test cases)

Test #238:

score: 8
Accepted
time: 543ms
memory: 10212kb

input:

400
87
9414608 633581355 948474998 702695350
704812935 138798294 740725843 363079166
150351251 712354722 354391268 716402132
161833438 445262056 930631557 472882669
496855218 291440408 503597923 917284767
126388173 97424737 140815544 846988429
66371796 771917558 914887338 801757227
759867651 5853746...

output:

80
514267 999142486 24753354 24753354
7952767 997980660 6507291 6507291
9414608 958386955 56459907 30897058
9414608 998695531 12654089 12654089
11709653 914887338 13832164 13832164
11709653 970721945 8146359 8146359
13557127 843789822 1871800 1871800
13592436 16786209 455989154 455989154
18406654 88...

result:

ok both cnt and k values are correct (400 test cases)

Test #239:

score: 8
Accepted
time: 1160ms
memory: 66416kb

input:

1
200000
813734216 6154435 813752570 985344114
22012003 19304236 998858254 19307525
123194876 51297168 622568977 51322167
907519415 150584449 907590403 994996968
100624053 865462027 732719233 865464699
162304062 298339209 162308794 731391151
247498763 26591525 247510206 997503734
440812808 101595053...

output:

140534
2218 970589065 14588 14588
2218 987906754 27618 27618
3504 935444271 6976 6976
4211 986805404 7443 7443
4461 999999894 40652 40652
4656 998975044 94978 94978
5139 975595473 132 132
5812 989266223 1808 1808
5812 998845282 8635 8635
5966 999999894 34473 34473
8133 969976298 4292 4292
8133 97704...

result:

ok both cnt and k values are correct (1 test case)

Test #240:

score: 8
Accepted
time: 1213ms
memory: 67172kb

input:

1
200000
78757012 333947322 900018284 333964941
160668550 472661311 179773079 472673536
982166166 141770484 982170762 993364176
449684687 749548923 473751250 749586928
903201657 565575504 932603079 565593334
269310483 586668076 746621069 586671946
347125694 178655341 347134051 891513642
581544468 71...

output:

185459
119 999998291 4184 4184
816 999991054 15747 15747
3425 7679 424805946 241724162
3425 996433358 5456 5456
3425 999977125 35290 35290
4017 330336398 21452 21452
4017 978759947 1530 1530
7604 999986351 1043 1043
7959 909749869 579 579
7959 927603063 15002 15002
9291 941120274 22434 22434
9429 65...

result:

ok both cnt and k values are correct (1 test case)

Test #241:

score: 8
Accepted
time: 1192ms
memory: 70448kb

input:

1
200000
258703096 322315550 258704259 415804735
320176550 934446888 918009527 934447097
252998179 183744254 317225105 183750427
9139764 305202543 844470871 305202869
717676299 420400847 717682611 923716715
2712742 953441793 996011598 953441829
898303538 651595723 898304205 657495661
693374231 21514...

output:

202483
376 999999496 7273 7273
798 999601988 1903 1903
1461 999872646 7427 7427
2999 999996399 6135 6135
4294 856843310 5599 5599
5299 934052298 5086 5086
5380 999697027 320 320
5502 998629471 4619 4619
7054 963445643 28621 28621
7054 973254880 72 72
9239 972241076 7396 7396
10524 623573692 1883 188...

result:

ok both cnt and k values are correct (1 test case)

Test #242:

score: 8
Accepted
time: 487ms
memory: 18092kb

input:

1
200000
203402060 804897444 204588815 805362607
413012207 930039911 414352894 930599252
57684579 64275532 58037451 64861768
577914220 638617913 578258408 639273926
9833091 544624098 10095201 545597241
383091300 207146729 384229612 208020533
411009817 719646191 411271556 720464377
371902486 60665490...

output:

34253
162508 657202 32266787 1783244
162508 740137 533858 504665
162508 1098829 3278496 1306534
162508 1252662 3109550 1663610
162508 1456392 991802 991802
162508 1711036 445069 445069
389677 740137 34140981 1804325
389677 789796 1793971 847235
389677 1098829 2080887 1058602
389677 1252662 905603 73...

result:

ok both cnt and k values are correct (1 test case)

Test #243:

score: 8
Accepted
time: 1074ms
memory: 68284kb

input:

1
200000
27058653 397112425 953865576 397115753
66900494 390972339 870790605 390972727
156255358 255602308 813710316 255609260
93160054 661005742 911388323 661006820
456417910 61445675 456419456 881019055
165773779 392655804 972723624 392656677
16731989 619431616 920809442 619432302
695879331 418595...

output:

200000
1195 798650565 2782 2782
1911 969325658 6812 6812
5816 791313445 188 188
6521 992393944 125 125
6971 926811789 120 120
8345 764205808 624 624
10086 825539175 400 400
11097 876527401 2407 2407
13239 805033257 1272 1272
14469 844639219 1766 1766
14555 883954266 689 689
15662 983934364 405 405
2...

result:

ok both cnt and k values are correct (1 test case)

Test #244:

score: 8
Accepted
time: 999ms
memory: 59772kb

input:

1
200000
880356019 838274591 881631352 841229219
271107857 335527776 280581550 336660155
612343088 601533343 612922688 620687899
969104183 58932244 969801524 59756558
8212563 358726049 13894114 359767053
189098234 241178834 195328856 242211438
175113386 112866602 181131667 114208134
374048785 113744...

output:

36697
2512 1113467 77729 43869
2512 1119869 110107 110107
2512 1121039 443827 443827
2512 1144553 1393863 1393863
2512 1157851 1995029 1995029
2512 1233069 32688 32688
2512 1253365 81608 81608
2512 1325470 66918 66918
2512 1373893 2804859 2804859
2512 1405335 402640 402640
2512 1422991 74405 74405
2...

result:

ok both cnt and k values are correct (1 test case)

Test #245:

score: 8
Accepted
time: 922ms
memory: 68116kb

input:

1
200000
452177690 663705340 452200205 664501814
939769521 446645 940048391 608970
724938148 350633773 725049010 354089074
442899289 529650572 442934699 531321758
229542770 84670423 229581695 84789485
228396372 703472129 228422452 708146722
651101876 692634370 651117027 692734195
219646770 716804169...

output:

201040
1138 632950 230 230
1138 654272 12117 12117
1138 684006 5189 5189
1138 687838 8083 8083
1138 698538 5081 5081
1138 701586 224980 224980
1138 703363 177 177
1138 707971 5700 5700
1138 708439 8768 8768
1138 710683 47307 47307
1138 724795 123202 123202
1138 728874 1729 1729
1138 729885 2985 2985...

result:

ok both cnt and k values are correct (1 test case)

Test #246:

score: 8
Accepted
time: 1136ms
memory: 67100kb

input:

1
200000
407935059 295919498 592841930 703937045
91091427 181727402 91095510 846302861
361940592 218442983 361943566 814168124
127063539 113908584 127069990 979705389
11252 706005783 999998428 706008321
11252 363782667 999998428 363785734
637530691 152134560 637536196 941169875
11252 502944916 99999...

output:

150000
8983 11251 597789702 143241408
8983 999999509 124779693 29641
13423 18829 666703914 173033067
13423 999994473 3197 1727
22905 24671 602358744 173789749
22905 999983625 8763 4321
26049 29847 453497241 65475128
26049 999980638 6438 2608
42468 43775 594522329 146998666
42468 999972234 2189 1469
...

result:

ok both cnt and k values are correct (1 test case)

Test #247:

score: 8
Accepted
time: 508ms
memory: 10108kb

input:

1000
290
133427442 209756399 135036415 996424260
441519821 910709684 442623943 911285921
16499460 195367554 17089635 258097896
333317157 530873600 522809396 534027556
451454245 497482237 451593038 499962782
220281936 63424222 221981393 304437557
655236672 513672850 655317374 797955801
973856021 6361...

output:

290
3809076 889089810 707458 707458
4145208 233042168 5186273 5186273
5916863 416322158 796101 796101
6150677 345295488 3150249 3150249
7031547 730704977 941790 941790
8965889 993835979 957532 957532
16499460 17089635 62730343 62730343
18744633 597362992 148386 148386
19744352 23800716 115686964 104...

result:

ok both cnt and k values are correct (1000 test cases)

Test #248:

score: 8
Accepted
time: 1130ms
memory: 68016kb

input:

1
200000
861789328 326160773 986685949 326168425
427090983 919565630 810510103 919566585
590730308 351303910 590732227 964518772
849652704 640934660 849655748 826502094
298911200 126846736 298912475 635377994
200755775 103724023 958592461 103726090
401780808 321716909 574683343 321720419
793150033 3...

output:

200000
53 726674266 2919 2919
5649 5823 101656221 101656221
6811 9372 70051968 70051968
13022 1983724 4014 4014
13332 503375329 259 259
14341 15880 235889394 150731145
16711 338217181 3177 3177
17196 686883883 180 180
22322 24185 307111167 307111167
28293 634554213 3354 3354
35979 894260729 794 794
...

result:

ok both cnt and k values are correct (1 test case)

Extra Test:

score: 0
Extra Test Passed