QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#428653#8640. Fish 3JohnAlfnov100 ✓368ms49088kbC++142.2kb2024-06-01 20:50:172024-06-01 20:50:21

Judging History

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

  • [2024-06-01 20:50:21]
  • 评测
  • 测评结果：100
  • 用时：368ms
  • 内存：49088kb
查看
  • [2024-06-01 20:50:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
long long c[300005],s[300005],a[300005];
int sc[300005];
vector<pair<int,int>>g[300005];
long long ans[300005];
long long sm[1200005],lz[1200005];
void pushdown(int l,int r,int o){
	if(lz[o]==-1)return;
	int mid=(l+r)>>1;
	sm[o<<1]=(mid-l+1)*lz[o];sm[o<<1|1]=(r-mid)*lz[o];
	lz[o<<1]=lz[o<<1|1]=lz[o];
	lz[o]=-1;
}
vector<pair<pair<int,int>,int>>vc;
void add(int l,int r,int o,int ll,int rr,long long z){
	if(l>=ll&&r<=rr){
		vc.emplace_back(make_pair(l,r),o);
		sm[o]=(r-l+1)*z;lz[o]=z;
		return;
	}
	pushdown(l,r,o);
	int mid=(l+r)>>1;
	if(mid<rr)add(mid+1,r,o<<1|1,ll,rr,z);
	if(mid>=ll)add(l,mid,o<<1,ll,rr,z);
	sm[o]=sm[o<<1]+sm[o<<1|1];
}
long long query(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr)return sm[o];
	pushdown(l,r,o);
	int mid=(l+r)>>1;long long ans=0;
	if(mid>=ll)ans+=query(l,mid,o<<1,ll,rr);
	if(mid<rr)ans+=query(mid+1,r,o<<1|1,ll,rr);
	return ans;
}
int mx[1200005];
void build(int l,int r,int o){
	lz[o]=-1;
	if(l==r){
		mx[o]=sc[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);build(mid+1,r,o<<1|1);
	mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
int qmax(int l,int r,int o,int z){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(mx[o<<1|1]>z)return qmax(mid+1,r,o<<1|1,z);
	return qmax(l,mid,o<<1,z);
}
int st[300005];
int main(){
	int n;
	long long d;
	scanf("%d%lld",&n,&d);
	for(int i=1;i<=n;++i)scanf("%lld",&c[i]);
	for(int i=n-1;i>=1;--i)sc[i]=sc[i+1]+(c[i]%d>c[i+1]%d);
	for(int i=1;i<=n;++i)s[i]=s[i-1]+(a[i]=c[i]/d+sc[i]);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		int l,r;
		scanf("%d%d",&l,&r);
		g[r].emplace_back(l,i);
	}
	build(1,n,1);
	int tt=0,ls=0;
	for(int i=1;i<=n;++i){
		while(tt&&a[i]<=a[st[tt]])--tt;
		vc.clear();
		add(1,n,1,st[tt]+1,i,a[i]);
		st[++tt]=i;
		for(auto pii:vc){
			int o=pii.second;
			if(mx[o]>a[i]){
				int l=pii.first.first,r=pii.first.second;
				ls=qmax(l,r,o,a[i]);
				break;
			}
		}
		for(auto pi:g[i]){
			int l=pi.first,wz=pi.second;
			long long he=s[i]-s[l-1]-query(1,n,1,l,i);
			if(l<=ls)ans[wz]=-1;
			else ans[wz]=he;
		}
	}
	for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

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

input:

1 1
684133708065
1
1 1

output:

0

result:

ok single line: '0'

Test #2:

score: 9
Accepted
time: 0ms
memory: 10856kb

input:

1 5
922528093559
1
1 1

output:

0

result:

ok single line: '0'

Test #3:

score: 9
Accepted
time: 2ms
memory: 10992kb

input:

10 3
558103292241 930416975101 878795845384 804480358330 767898782842 927334443478 767423599302 776338370164 666494289968 823066426292
5
6 7
4 9
1 5
1 5
8 9

output:

53303614726
237001368097
103332276763
103332276763
36614693399

result:

ok 5 lines

Test #4:

score: 9
Accepted
time: 0ms
memory: 11172kb

input:

2999 2
910702609990 771959295198 631713940606 723519904787 964465009855 589336853658 570529304452 677181103776 829388017677 615422452777 832072560651 949712644950 621686593519 620107188218 588008578663 771134678307 881088604010 630837395048 942542093526 816092813704 526760463705 966907267801 6380490...

output:

153267304332767
88210429847688
251073763892516
120498585857360
269647060516126
181655809626706
28744824361327
212696506328096
28938088535006
161900364003182
192266190540855
85782185067648
162456411997002
113328101043704
91937879477447
77391229958272
34192773485302
123898620434484
16721214370405
1740...

result:

ok 3000 lines

Test #5:

score: 9
Accepted
time: 0ms
memory: 11316kb

input:

2999 269276866948
538548431206 612241675263 587998860042 679065032063 968791203643 624105564957 876171768735 865424996338 768343148847 626416086908 849994644564 978324642291 909812184358 848733024999 677064065128 534919838133 771980558047 694416914392 989760295843 545517913894 935160699589 733564086...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 2998 lines

Test #6:

score: 9
Accepted
time: 0ms
memory: 11232kb

input:

1963 2
610191886592 576202220229 947693726472 699325171257 831713057807 560837173177 998927809467 888702350715 813307089865 953196185842 746662270531 887607972540 832485494055 595022138107 661488666229 864068645749 638671748996 966191644866 777734686651 841574336733 557308312743 890996541155 6850248...

output:

175912932539461
86375369695154
21996760727150
126275386984709
41322585260558
78891763179032
113878648411100
193319244194699
24802460391918
56033137953003
161677619147118
20579148338264
58108435836569
223425300243538
11636685059197
99383347148021
95720816718008
60398189173367
130008123832316
97464180...

result:

ok 2998 lines

Test #7:

score: 9
Accepted
time: 5ms
memory: 11188kb

input:

1616 167339107341
951464471961 691265189985 946974214730 918850040203 712066251897 831210958080 699433206334 907495726908 996454753697 543515234340 604971123516 914922340373 507133836106 615497917221 563424879059 915993377887 840855582528 508005407154 533513156456 773555286779 562467682854 602959393...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2999 lines

Test #8:

score: 9
Accepted
time: 0ms
memory: 11260kb

input:

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

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 3000 lines

Test #9:

score: 9
Accepted
time: 2ms
memory: 11256kb

input:

2999 177864204054
0 3 3 2 6 3 6 1 2 8 8 9 10 6 2 2 3 9 7 4 10 8 10 0 8 6 0 7 10 7 5 3 10 5 5 9 10 0 0 1 4 1 7 4 7 5 2 1 8 9 4 6 4 8 6 3 2 7 1 8 2 7 6 7 1 3 0 1 4 6 4 1 10 7 8 6 4 5 10 10 0 8 7 8 2 9 5 6 7 9 6 0 3 9 6 5 0 3 4 7 1 0 9 4 6 1 8 10 6 6 8 7 1 10 9 9 2 5 8 7 4 8 4 2 5 0 1 7 10 5 0 0 2 5 9 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 3000 lines

Test #10:

score: 9
Accepted
time: 5ms
memory: 11352kb

input:

2998 5
999999999997 999999999995 999999999997 1000000000000 999999999997 999999999995 999999999996 999999999998 999999999999 999999999991 999999999991 999999999995 1000000000000 999999999995 999999999998 1000000000000 999999999992 999999999998 999999999996 999999999992 999999999998 999999999990 9999...

output:

203485
164732
891754
323185
371406
65139
22486
88150
151449
149390
281233
23
110676
36870
855015
326332
60584
1304858
569593
147795
1142488
1192
656080
406331
167486
25206
447353
119316
255878
48231
42755
1056875
779445
32249
30508
104112
55364
431535
806852
479102
814352
114056
1156501
313326
55681...

result:

ok 3000 lines

Test #11:

score: 9
Accepted
time: 0ms
memory: 11256kb

input:

2999 443434836129
999999999990 999999999999 999999999996 999999999995 999999999993 999999999990 999999999992 999999999993 999999999995 999999999998 1000000000000 999999999995 999999999990 999999999999 1000000000000 999999999991 999999999996 999999999999 999999999994 1000000000000 999999999996 999999...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2998 lines

Test #12:

score: 9
Accepted
time: 0ms
memory: 11364kb

input:

2999 2
500251821071 500326445444 500396052368 500547306361 500804884234 501337988306 501597903900 501819350222 502048680560 502151756253 502390708880 502398823207 503106795389 503422867103 503446255976 503537529156 503538833575 503782518483 503914958697 504144503489 504152951926 504182717744 5043400...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3000 lines

Test #13:

score: 9
Accepted
time: 0ms
memory: 11356kb

input:

3000 64196398338
500130104851 500337040549 500473124001 500496698977 500613149904 500762236267 501168722598 501199095745 501296827488 501336941635 501378273227 501818053997 502027033631 502080095101 502140198224 502386562976 502514772613 502573828575 502745889724 502764952231 503424357413 5034616025...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 2998 lines

Subtask #2:

score: 7
Accepted

Test #14:

score: 7
Accepted
time: 308ms
memory: 47928kb

input:

299998 1
1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1...

output:

66819
23042
14789
76907
48256
97043
124972
51847
62064
16122
41553
77847
3537
19017
79371
9105
17876
2881
87956
92615
79378
13113
23502
9520
6701
59856
46186
102149
39956
63655
57530
19547
119
10325
81974
6779
6617
136776
45402
99308
8006
44642
3163
113827
131132
33415
73534
54964
23844
57595
1432
8...

result:

ok 299998 lines

Test #15:

score: 7
Accepted
time: 317ms
memory: 47980kb

input:

299999 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0
25491
39563
0
0
0
0
0
0
43181
0
75000
75000
75000
0
75000
75000
0
75000
75000
75000
25340
0
0
0
0
75000
0
51038
42067
0
75000
46355
51698
5258
37588
0
75000
2033
72544
0
0
22134
0
0
75000
75000
0
67458
57754
8809
0
0
75000
0
0
75000
0
259
0
0
17628
75000
12141
0
0
75000
0
75000
75000
0
75000
750...

result:

ok 299998 lines

Test #16:

score: 7
Accepted
time: 96ms
memory: 17596kb

input:

2000 5
0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300000 lines

Test #17:

score: 7
Accepted
time: 308ms
memory: 47948kb

input:

299998 4
1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299999 lines

Test #18:

score: 7
Accepted
time: 319ms
memory: 47860kb

input:

300000 618448090017
1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300000 lines

Test #19:

score: 7
Accepted
time: 325ms
memory: 47880kb

input:

300000 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
-1
0
-1
-1
0
0
-1
0
-1
-1
-1
0
-1
0
0
-1
-1
-1
0
-1
0
-1
0
0
-1
0
-1
-1
0
0
0
-1
0
-1
-1
-1
-1
-1
-1
-1
0
0
-1
0
0
0
0
-1
0
-1
-1
0
-1
0
-1
-1
0
0
0
-1
-1
0
0
-1
0
0
-1
0
0
-1
0
-1
-1
0
0
0
-1
0
0
0
-1
-1
-1
-1
-1
0
-1
-1
-1
0
0
-1
0
-1
0
-1
-1
0
-1
0
-1
0
0
-1
0
-1
0
0
0
-1
0
-1
-1
-1
0
0
-1
0
0
...

result:

ok 299998 lines

Test #20:

score: 7
Accepted
time: 336ms
memory: 47860kb

input:

299998 339200991159
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

-1
0
0
-1
0
0
-1
0
-1
0
-1
-1
-1
0
-1
-1
0
-1
0
-1
-1
0
-1
-1
0
0
0
-1
-1
0
-1
0
-1
-1
-1
0
-1
0
-1
-1
0
-1
-1
0
0
0
0
0
0
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
0
0
-1
0
-1
-1
0
-1
-1
0
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
-1
0
0
-1
-1
-1
-1
-1
-1
0
0
0
-1
0
-1
0
-1
0
-1
-1
-1
0
0
-1
-1
0
0
0
-1
-1
-1
0
0
...

result:

ok 300000 lines

Subtask #3:

score: 28
Accepted

Test #21:

score: 28
Accepted
time: 96ms
memory: 17652kb

input:

2000 1
523885289004 650963649975 802034390371 645207535758 845171097887 713822570038 781866406365 912264247128 595876738467 508631610373 800192536309 518302233821 582688881520 666473477682 687249615613 593127950101 843877684664 590035670024 537975163840 790436456421 521762621708 797598071911 5178293...

output:

19737704396718
167191285999300
20591114345259
102876427637550
83574610551242
16630259442386
33126669327008
416796877575506
108882789216692
92565605793039
186324165602066
29971146351154
287440594338879
43900719093979
45357221325660
358584719394743
24844694589177
166367685344750
33937524701446
1483440...

result:

ok 299998 lines

Test #22:

score: 28
Accepted
time: 307ms
memory: 47944kb

input:

299999 1
817594262134 825997737253 513841829002 570997299441 695807209314 515960293058 519921139794 563903438317 518785484026 941654430004 893215792369 905471781529 804313186504 777740973791 731333734263 998829820485 980462476090 903230106039 512497831452 919228725844 528778830981 605070475494 59365...

output:

13767064269823283
35675882263702847
56873935160532468
62135062625213475
15111775328427075
283158364515415
50967761315002327
32541992128734921
48500997404546492
15791444722577688
44110737807869015
2615763582993301
30789312529428121
27291890143228088
11508934326199125
15646279600269193
292417087316553...

result:

ok 299999 lines

Test #23:

score: 28
Accepted
time: 329ms
memory: 47808kb

input:

299998 1
652451320982 682076697152 684794768166 670728065392 619757059174 983201062410 729999794856 570866721653 849313757762 719748828463 630111262201 560471012727 634198555939 760000826923 999145350025 753094118019 525690614023 597177307158 803980908716 874112862980 724740124102 920137432974 61639...

output:

7653063881685443
2511649876820307
42487482837392332
10616428894611133
40907940573235634
31032274634337153
22147757519395999
39997070711490787
28523418857599096
12222501024729862
28119928545481381
7169827503626489
18031698984338883
6365961081502267
36125900759828862
39727296479852087
6129183354120002...

result:

ok 300000 lines

Test #24:

score: 28
Accepted
time: 299ms
memory: 47888kb

input:

300000 1
564003158276 578292295112 929777090927 982712293868 820506935197 726706531868 669029880075 842651190723 738550161368 632248019511 591817525918 677221134239 890950700520 641471567591 584501395405 610117006967 657533206390 508197282205 801834478664 968585450428 973974742395 717017867779 64253...

output:

18552643661405562
158833033731109
13443578940536930
23386417509227697
46599025725918596
38555799160887628
8474392100959181
53489601088991696
23281743113278979
12509937349509751
30884964959003196
31085729678347831
7729018842318950
56808026581711282
451098530937425
28947112549996054
34128875856869514
...

result:

ok 299998 lines

Test #25:

score: 28
Accepted
time: 321ms
memory: 47852kb

input:

300000 1
709040824514 885276586887 854154901084 556953504446 612515640194 708669560827 747830817451 801890645466 772431814569 583101055605 569939584176 751283782738 509684461342 649691194333 866646260449 508481238628 825362547391 628666262107 587414579199 771101583054 547322951134 528713000838 88235...

output:

36231122575460311
26735037587572826
20492619117381226
13323171369237579
28424404727009993
45109567522153993
9080762877983362
38374717730894583
33924634318899934
28027073083780086
18546707438178272
36925021870633888
41379003043974930
15888508043244819
8054656767509900
43008561120660168
55739689439525...

result:

ok 299999 lines

Test #26:

score: 28
Accepted
time: 313ms
memory: 47800kb

input:

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

output:

761330
929862
145355
500322
417393
71659
258368
172650
896432
8647
87733
289520
734042
503765
136376
410043
9629
76263
493253
393239
491595
760641
1023874
161940
205771
1003264
6676
1084296
1325725
907878
284450
407215
123829
27989
574596
1030911
594135
20048
411138
723704
455917
839695
608958
35924...

result:

ok 300000 lines

Test #27:

score: 28
Accepted
time: 316ms
memory: 47988kb

input:

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

output:

560229
439566
630935
36720
201322
1099131
101458
520368
142213
158996
835759
1333325
254013
673001
70247
340646
810031
185880
459115
199183
633889
19566
779615
803054
243405
258556
599491
168135
179049
1450891
1198309
838799
166235
472186
87630
487641
103369
272271
13415
870715
652394
606074
636517
...

result:

ok 299998 lines

Test #28:

score: 28
Accepted
time: 326ms
memory: 47844kb

input:

300000 1
999999999998 999999999992 999999999994 999999999993 999999999993 1000000000000 999999999996 999999999990 999999999991 999999999998 999999999994 999999999995 999999999999 999999999996 999999999995 999999999995 999999999998 999999999992 999999999990 999999999994 999999999997 999999999992 9999...

output:

258618
262859
960538
204497
437340
425575
78646
281622
1296507
357496
175267
159335
221679
215128
856016
484398
647959
549680
488570
1019985
722043
605112
1132903
403154
443902
16535
31031
875821
843622
609409
219764
647353
971371
318023
418669
508859
75235
1272864
666233
784195
203218
105547
271862...

result:

ok 300000 lines

Test #29:

score: 28
Accepted
time: 346ms
memory: 47856kb

input:

300000 1
999999999995 999999999998 999999999991 999999999998 999999999998 999999999998 999999999997 999999999997 999999999995 999999999998 1000000000000 999999999994 999999999996 999999999991 1000000000000 999999999994 999999999995 999999999991 999999999993 999999999997 999999999991 999999999996 999...

output:

253925
326931
594527
159785
150612
328375
462771
250055
431936
57980
412415
1084383
537416
472680
1164719
572121
486870
1152475
565246
440458
753938
486503
41717
292595
506206
965010
13077
872537
78001
973106
427876
297541
1015067
814540
914149
1467393
1329938
516133
193906
340544
1069267
680406
304...

result:

ok 299999 lines

Test #30:

score: 28
Accepted
time: 294ms
memory: 49040kb

input:

299999 1
500001440566 500001763449 500004210053 500006333597 500007677006 500011759028 500015105947 500015715269 500016369574 500017732079 500018317150 500019440615 500019474011 500022355105 500023156302 500024179394 500030314927 500030885196 500031109326 500034696483 500035256369 500036002015 50003...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 299998 lines

Test #31:

score: 28
Accepted
time: 324ms
memory: 49032kb

input:

299998 1
500000824336 500002022920 500002292809 500002296351 500003746954 500003954787 500009828394 500010411104 500011252357 500012972200 500014459862 500014670437 500014769815 500014897473 500015041690 500015628145 500015761392 500016660986 500016787421 500017520501 500017721817 500018088364 50001...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300000 lines

Test #32:

score: 28
Accepted
time: 303ms
memory: 48452kb

input:

299999 1
500002315409 500001244395 500004775887 500003371088 500002481235 500007285703 500005269888 500011312351 500007399665 500013305005 500012455313 500016699955 500013422791 500018926592 500017948586 500036538159 500031169048 500029640028 500042599826 500039332627 500047916642 500046051451 50004...

output:

37023854791
279549210982
111333789696
18252678650
54216806936
146128646970
196610361866
257833002481
84927320786
11901982359
87761651071
345548637453
6846725227
57408605081
110764239214
188171089082
145958203670
16712127257
16951606500
130814832732
33149435971
160352256297
274584428958
111783090285
...

result:

ok 299998 lines

Test #33:

score: 28
Accepted
time: 313ms
memory: 48248kb

input:

300000 1
500005945947 500003522589 500002273367 500007145628 500007031251 500009670544 500008955376 500008577570 500017266833 500010184764 500027689614 500026900452 500025714314 500028447800 500028225129 500031055464 500029160854 500028785323 500035675666 500035460266 500032927430 500038496888 50003...

output:

133548823343
90433973375
154824664386
68536199512
71194407445
93932199262
119493244104
244350307513
115383845664
61186230926
20976299166
19601435056
35420646515
251780229820
266194156204
172236269460
31041941642
181309646969
56780380034
71249870269
161721719327
9301421770
24401604173
4410365312
1440...

result:

ok 300000 lines

Subtask #4:

score: 20
Accepted

Test #34:

score: 20
Accepted
time: 289ms
memory: 35972kb

input:

248425 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

481354
31477
5040
10796
18956
0
450685
0
15010
33292
82746
78453
250500
202068
13557
925358
737113
167507
388679
195773
650521
48155
449701
0
191208
6148
3638
413084
0
210994
10494
0
161263
0
149298
457069
244725
977943
38238
92376
18824
18446
0
334470
365809
98504
41825
1010325
115953
174679
33156
...

result:

ok 299998 lines

Test #35:

score: 20
Accepted
time: 329ms
memory: 47948kb

input:

299998 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

17926
23737
50456
304968
365350
136638
1004358
0
237775
49853
86177
94871
3916
43491
63252
51122
10780
646643
342054
0
33189
79037
42611
427005
24518
24232
388373
74086
111739
22739
47066
190515
153805
0
219271
743252
151628
1149126
45023
1047144
538445
68258
19959
80670
174415
114219
49529
1112754
...

result:

ok 300000 lines

Test #36:

score: 20
Accepted
time: 188ms
memory: 24292kb

input:

65758 1
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 100000000000...

output:

12604
0
8313
42834
0
36586
29328
5485
17527
133757
0
2572
5004
214778
17855
4063
9596
106440
14335
83179
863
22887
5912
8762
4510
6879
14679
0
30053
52686
157684
5097
154609
45365
2346
34610
104715
152392
91931
49049
48561
173663
118995
65366
69079
16218
0
4558
2904
24728
0
647
10686
17967
5550
444
...

result:

ok 299998 lines

Test #37:

score: 20
Accepted
time: 344ms
memory: 47800kb

input:

299999 1
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 10000000000...

output:

71607
412465
182018
80769
517020
0
0
22175
567036
0
277882
722739
248255
0
38823
247153
33830
1488625
23633
0
210909
23347
0
164996
1057448
159231
26250
152325
78592
301552
64737
1190634
18811
226581
44611
77074
0
355437
560580
4024
9144
50574
225803
831385
120798
574504
1127045
135897
111307
12814
...

result:

ok 299998 lines

Test #38:

score: 20
Accepted
time: 348ms
memory: 46772kb

input:

263612 1
999999548276 999999343778 999999341853 999998181898 999997730933 999994177375 999993160054 999992411599 999991546081 999990551179 999986847415 999985472707 999983874570 999983771166 999978776782 999978445020 999977359253 999977003860 999976197143 999975924347 999973582632 999971201172 99997...

output:

4693875135356690
21069182470553278
438285492523087
20295513966120423
4097486382341082
3054936665351117
25602339542206441
210881617180692
3202066738332671
16047358895466979
24735574962343258
53068034739598436
5607157011017623
16988964662069767
10174532789071261
18678546433626410
7192285716810365
1390...

result:

ok 300000 lines

Test #39:

score: 20
Accepted
time: 350ms
memory: 47956kb

input:

299999 1
999992072463 999988503398 999985211789 999981035730 999979213886 999977273948 999975747977 999974503115 999974479430 999973486218 999972796256 999972677948 999972547355 999971731969 999968452503 999968207475 999967630663 999966496663 999965007185 999962913310 999960555870 999959094504 99995...

output:

3218230649563310
22035825187561806
94844110183063
6283624582868805
6834068553601637
230638895860921
1153620640751260
16125745100577410
49019885208592153
22487784528401862
13927851595676
19296042328114066
1160598018180397
1225572556793873
4686664374157694
487625928851427
26318175618705802
15748000445...

result:

ok 299999 lines

Test #40:

score: 20
Accepted
time: 290ms
memory: 35560kb

input:

236015 1
999999973485 999997478774 999993180353 999992809297 999987402948 999987024434 999982353983 999981722549 999981175459 999980669631 999980615673 999980282019 999979934787 999979353711 999977808523 999977185104 999976435958 999974768536 999973580333 999972304177 999969099427 999961969157 99995...

output:

419800846323421
23837469621774704
37240434336198206
28978455172777249
8855368797283529
7242391837904891
4185501087604488
8857993524030390
31720674680921133
3213733234349414
1344874809428043
28939062756698494
3412671617201637
10342752033628724
142769964028065
2832374986984655
33662073444979678
337192...

result:

ok 299999 lines

Test #41:

score: 20
Accepted
time: 315ms
memory: 47920kb

input:

300000 1
999999771732 999999322309 999998499084 999997256465 999993600155 999991533384 999991375069 999991186509 999988678162 999986657032 999983022607 999981236161 999980986047 999980854589 999980825390 999978446638 999977057101 999976161036 999975102182 999974421115 999974196615 999971864718 99997...

output:

20614165289560650
1957359843576830
21785897050268109
8428026789062059
56719875433975265
856439855341938
503938951842857
19369377837315387
27166965650641984
2402364825923850
13749344494868751
3879846225708457
1067524590831594
11670247613830908
771118930831199
1853633521130574
177947867812494
21361240...

result:

ok 299999 lines

Test #42:

score: 20
Accepted
time: 317ms
memory: 47924kb

input:

299999 3
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

-1
26965
12136
-1
102298
-1
9961
105841
-1
-1
-1
-1
-1
-1
-1
-1
-1
49525
-1
21294
0
0
-1
23599
0
-1
-1
2603
7609
0
-1
-1
-1
7310
-1
-1
-1
-1
-1
-1
-1
-1
80099
0
80584
-1
0
0
-1
0
-1
21435
2787
-1
84040
0
-1
-1
3435
-1
20270
-1
-1
156079
-1
615
0
-1
-1
0
13931
0
-1
-1
-1
3870
36864
-1
3990
-1
-1
7588...

result:

ok 299999 lines

Test #43:

score: 20
Accepted
time: 313ms
memory: 47988kb

input:

300000 555836250411
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

output:

-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1...

result:

ok 300000 lines

Test #44:

score: 20
Accepted
time: 334ms
memory: 47940kb

input:

299999 4
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 10000000000...

output:

121609
720530
0
44094
668121
691018
50310
598492
62007
1469457
25250
0
360608
110048
369878
12887
42727
264083
785
234756
7849
13648
100706
3624
138599
0
187738
46403
115125
265147
1452417
0
3964
0
18940
546848
714625
357964
139922
151288
173934
555598
50942
422789
60204
260360
14372
16934
525041
59...

result:

ok 299998 lines

Test #45:

score: 20
Accepted
time: 331ms
memory: 47992kb

input:

300000 333830457787
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 ...

output:

24351
-1
0
7686
63096
0
-1
0
-1
7956
-1
-1
-1
20457
10646
32010
-1
23743
-1
0
0
-1
-1
-1
-1
-1
48326
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
33213
-1
0
72093
20669
-1
-1
-1
-1
2740
-1
43147
42445
-1
57960
-1
77150
-1
-1
-1
-1
3218
-1
-1
-1
17252
78322
8626
-1
-1
-1
57738
25172
-1
19282
-1
-1
0
19064
-1
1514
-...

result:

ok 300000 lines

Test #46:

score: 20
Accepted
time: 329ms
memory: 47936kb

input:

299999 3
999999810987 999999368400 999998944650 999991821940 999991276021 999990081145 999987326960 999985093328 999983082250 999981689498 999979907324 999978776921 999978745041 999977499855 999976976255 999975560919 999975416009 999975111158 999973671169 999971173413 999969593537 999965047667 99996...

output:

1252084118887107
131761857828908
2084359481182138
12908403865260937
10525272853687554
4058886066829751
12690483162052371
1008546361514851
10683700540099329
363278647323511
3648605724223725
1306449017382089
6902827460009040
1032432551773270
573466449909199
3021116391694349
1902472523667135
6106043898...

result:

ok 299998 lines

Test #47:

score: 20
Accepted
time: 315ms
memory: 47860kb

input:

299999 705267968375
999994923452 999993722649 999992391028 999983711678 999982920863 999982525633 999982073306 999981388613 999980038497 999979642102 999979115769 999978087221 999976698924 999970150945 999969140832 999968097122 999967593025 999967322826 999966721849 999964981985 999963218253 9999624...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299998 lines

Test #48:

score: 20
Accepted
time: 312ms
memory: 47996kb

input:

299999 4
999996913538 999996802185 999994707562 999991263591 999991062989 999990543129 999985825536 999983754622 999982898195 999982550557 999981521230 999980417745 999979529661 999979203039 999977111298 999976017655 999975578988 999975426323 999973778587 999973014806 999968665319 999966193102 99996...

output:

6466876938714
7429712281719
31514022146218
5522954831730215
862451686117162
6975453826421
880925466725091
475262096456
3560501957037
67297699466749
75184213489691
101135496586984
22949900930381
16116156743836
5241124023496837
324263641565709
426591428780918
3868621232418450
28523124370379
2769404202...

result:

ok 300000 lines

Test #49:

score: 20
Accepted
time: 322ms
memory: 47980kb

input:

299998 422956900198
999999365160 999999180970 999997983002 999994589490 999991616885 999989797634 999988994341 999983651483 999980616805 999980116576 999978006028 999977340328 999976861711 999971518945 999970958414 999969577604 999968491121 999967310122 999965770601 999963922333 999962729406 9999609...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299998 lines

Subtask #5:

score: 36
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #50:

score: 36
Accepted
time: 313ms
memory: 47848kb

input:

299999 1
810159704128 901103529142 651826054526 549226999020 797685833296 561794900099 780515717698 733923036711 732225893333 860941232149 913871531174 644807459860 613090480040 890821827512 821303250427 776174249582 805738790778 876608381073 721669536343 578028929302 638609205296 909590707934 70104...

output:

3487888566115540
3109283353452930
29905982163562212
46876220982531191
3760748057577043
29353918403038086
28612758609917820
378984926011379
54857990660475568
13979222029674645
49146794505230536
3917860567509474
33264179604329651
46380372090164346
23750383818218408
16967798702221104
13224921002678427
...

result:

ok 299998 lines

Test #51:

score: 36
Accepted
time: 301ms
memory: 47808kb

input:

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

output:

121470
201323
417582
1264242
517044
601238
676633
974050
699299
335916
371038
643228
376673
742777
434148
871960
683465
552044
185161
331569
524271
147242
785296
762348
122053
173004
772195
591222
863306
1178090
436493
605287
408114
151353
925358
847009
380264
468906
147093
598562
40625
1152931
8149...

result:

ok 299999 lines

Test #52:

score: 36
Accepted
time: 291ms
memory: 47796kb

input:

300000 1
999999999997 999999999998 999999999996 999999999999 999999999994 999999999998 999999999990 999999999991 999999999999 999999999993 999999999992 999999999997 999999999996 999999999999 999999999996 999999999993 999999999992 1000000000000 999999999995 999999999996 999999999991 999999999990 9999...

output:

164162
365106
33162
260438
307055
1118813
188432
358833
193031
1046997
324510
222524
705545
193609
28303
200753
49960
14256
915165
366216
1040228
251081
585163
408128
133792
125487
588750
871175
110865
307669
1069459
1037813
183581
848593
949593
167986
1272350
847388
461683
130739
31567
319384
14355...

result:

ok 299998 lines

Test #53:

score: 36
Accepted
time: 291ms
memory: 48992kb

input:

299999 1
500003571362 500005898377 500007068761 500010730062 500012216254 500012434559 500013806021 500015297229 500019694644 500024338694 500024689888 500024733597 500027402922 500030744953 500031426068 500033092129 500042633743 500042894513 500043363392 500045046416 500049814901 500052710346 50005...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 299999 lines

Test #54:

score: 36
Accepted
time: 330ms
memory: 48328kb

input:

300000 1
500003046894 500001627557 500004629082 500003999190 500015315311 500014319512 500005059500 500018315921 500016255487 500015799064 500023726380 500021591677 500020672008 500031329672 500029283334 500024799948 500034362217 500033498283 500042672678 500036802945 500034736829 500044052502 50004...

output:

109987294350
136299941196
22064327683
297895713921
340747136810
47900333115
231753858842
81891818336
14234879077
142273310843
288995763910
272278656988
57734723180
57157528605
243132731568
179872623742
184264137198
152551235227
3636550868
229267770179
152838580854
49792734980
180504563192
1878999688...

result:

ok 299999 lines

Test #55:

score: 36
Accepted
time: 335ms
memory: 47988kb

input:

299998 3
851375391542 679274869509 625921371647 950301745739 715215109897 522753819423 501671752501 784104942207 682142180192 876232106280 536282534385 756776169500 912140311032 594919371857 809123025491 653725765110 938873418017 813770457197 710350078004 668585057042 760021160809 915002432937 96541...

output:

7442474443803763
17086312844832356
4812997228107826
6137584173919698
7130213253668594
1751450030317327
12016801787932922
5504321456888022
20508703930625498
17264450626967556
16145876301812820
10840652790516314
3049507260053766
15922323044130058
7501566305957389
10625934920641723
7474870003340561
557...

result:

ok 299998 lines

Test #56:

score: 36
Accepted
time: 333ms
memory: 47952kb

input:

299999 891926906767
859736142226 631045846643 808939158950 603332339157 525011629644 566131793296 785144398515 566605605556 653133704528 692228855018 914129970227 982620655995 732965974240 653863507490 782362309102 704026609320 889989084982 982990081354 767312814909 832891780801 651014617644 5381321...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300000 lines

Test #57:

score: 36
Accepted
time: 338ms
memory: 47948kb

input:

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

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299998 lines

Test #58:

score: 36
Accepted
time: 310ms
memory: 47920kb

input:

299998 183428173398
10 6 8 6 1 8 1 1 1 2 6 10 6 9 5 3 1 3 4 5 4 4 2 3 6 9 1 3 5 7 0 0 10 6 2 1 4 3 0 4 10 5 2 8 6 3 0 10 7 4 9 5 2 9 3 3 1 10 3 0 1 1 6 2 4 5 4 2 0 5 10 9 2 1 0 6 6 8 10 8 5 3 4 2 7 7 7 3 5 4 1 6 7 4 7 2 2 1 0 4 6 4 8 10 2 9 0 8 7 2 7 10 2 4 5 4 2 10 1 6 10 8 3 2 5 3 6 7 7 10 6 4 2 8...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299998 lines

Test #59:

score: 36
Accepted
time: 328ms
memory: 47928kb

input:

300000 3
999999999999 999999999997 999999999997 999999999998 999999999993 999999999992 999999999997 999999999999 999999999997 999999999996 999999999999 999999999998 999999999997 999999999996 999999999999 999999999998 999999999991 999999999990 999999999990 999999999992 1000000000000 999999999990 9999...

output:

2807122760
8404874655
62010988
1400236884
176532935
11491939
2284556413
1062776178
1232643613
902341133
1973980937
6979331
23625638
2186594871
132034
613868675
72042005
505621694
4921473022
2983531617
3322517103
8072157425
46484536
4957922492
18835771
173654305
1314119934
2692176
6650252
720258886
9...

result:

ok 300000 lines

Test #60:

score: 36
Accepted
time: 334ms
memory: 47884kb

input:

299998 109658123600
999999999996 999999999992 999999999991 999999999996 999999999996 999999999992 999999999993 999999999995 999999999991 999999999999 999999999999 999999999993 999999999990 999999999995 999999999996 999999999995 999999999995 999999999999 999999999990 1000000000000 999999999997 999999...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300000 lines

Test #61:

score: 36
Accepted
time: 329ms
memory: 49088kb

input:

299999 2
500000360577 500006616430 500006788263 500012056846 500012220225 500014160712 500015675476 500016270743 500019401787 500020815473 500021099115 500021833685 500024790163 500031671735 500031799591 500034105624 500035863906 500036174060 500038703576 500038924000 500039647523 500039805741 50004...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 299999 lines

Test #62:

score: 36
Accepted
time: 345ms
memory: 47988kb

input:

299998 8950474940
500002364187 500009454625 500012065549 500012477903 500013010534 500014880418 500015309004 500017087356 500017751927 500018347316 500020753584 500022294988 500025371600 500026185693 500026940167 500027565918 500027580973 500032152197 500032701168 500033272382 500033687381 500036518...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 299998 lines

Test #63:

score: 36
Accepted
time: 330ms
memory: 48400kb

input:

300000 5
500002751760 500001088193 500005018395 500004922965 500006161933 500005861405 500012081532 500011443621 500008237565 500014565174 500014308947 500015509108 500015054770 500018523076 500016482734 500016087362 500019271229 500018581484 500019666593 500019524422 500031431680 500024783253 50002...

output:

13628811189
42652675137
52642854033
75359616331
38142776890
19442543683
33114072549
8489181757
50640268561
7381200859
11592332338
9437808399
46897981180
6957754467
20710800021
8181768944
26246129673
14743609289
36070854208
27966772078
45582987632
24925010568
50606979568
52011589926
49196531481
50324...

result:

ok 299998 lines

Test #64:

score: 36
Accepted
time: 368ms
memory: 47952kb

input:

299998 281506385072
500001920467 500001624255 500005208322 500004947703 500012341810 500009093359 500008987708 500020276218 500015056924 500013762241 500022178560 500020865057 500028283208 500027949896 500022357938 500032743508 500028880685 500028498097 500033878610 500033367057 500032901811 5000450...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 299998 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 17:07:37 | OpenSource Project