QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300849#6101. Ring RoadPhantomThresholdAC ✓1450ms73936kbC++204.2kb2024-01-08 21:52:532024-01-08 21:52:54

Judging History

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

  • [2024-01-08 21:52:54]
  • 评测
  • 测评结果:AC
  • 用时:1450ms
  • 内存:73936kb
  • [2024-01-08 21:52:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<vector<int>> T(n+n+5);
	vector<vector<pair<int,ll>>> tmp(n+n+5),G(n+n+5);
	auto addedge=[&](int u,int v,ll w,int ty=1)
	{
//		cerr<<"addedge "<<u<<' '<<v<<' '<<w<<endl;
		G[u].emplace_back(v,w);
		G[v].emplace_back(u,w);
		if(ty)
		{
			T[u].push_back(v);
			T[v].push_back(u);
		}
	};
	for(int i=2;i<=n;i++)
	{
		int p;
		ll c;
		cin>>p>>c;
		tmp[p].emplace_back(i,c);
	}
	vector<int> lf;
	int ind=n;
	for(int i=1;i<=n;i++)
	{
//		cerr<<"split "<<i<<' '<<tmp[i].size()<<endl;
		if(tmp[i].empty())lf.push_back(i);
		else
		{
			int now=i;
			while(tmp[i].size()>2u)
			{
				auto [v,w]=tmp[i].back();
				tmp[i].pop_back();
				addedge(now,v,w);
				addedge(now,++ind,0);
				now=ind;
			}
			addedge(now,tmp[i][0].first,tmp[i][0].second);
			if(tmp[i].size()>1u)addedge(now,tmp[i][1].first,tmp[i][1].second);
		}
	}
	n=ind;
	int lcnt=(int)lf.size();
	for(int i=0;i<lcnt;i++)
	{
		ll c;
		cin>>c;
		addedge(lf[i],lf[(i+1)%lcnt],c,0);
	}
//	cerr<<"read graph end"<<endl;
	int q;
	cin>>q;
	vector<ll> ans(q+5,inf);
	vector<tuple<int,int,int>> qu;
	for(int i=1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		qu.emplace_back(u,v,i);
	}
	vector<ll> dis(n+5,inf);
	vector<int> good(n+5);
	auto dijk=[&](int s,int fl)
	{
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dis[s]=0;
		pq.emplace(0,s);
		while(not pq.empty())
		{
			auto [d,u]=pq.top();pq.pop();
			if(dis[u]!=d)continue;
			for(auto [v,w]:G[u])
			{
				if(good[v]==fl and dis[v]>dis[u]+w)
				{
					dis[v]=dis[u]+w;
					pq.emplace(dis[v],v);
				}
			}
		}
	};
	auto deledge=[&](int u,int v)
	{
//		cerr<<"delete edge "<<u<<' '<<v<<endl;
		for(auto it=G[u].begin();it!=G[u].end();++it)
		{
			if(it->first==v)
			{
				G[u].erase(it);
				break;
			}
		}
		for(auto it=G[v].begin();it!=G[v].end();++it)
		{
			if(it->first==u)
			{
				G[v].erase(it);
				break;
			}
		}
	};
	dijk(lf[0],0);
	for(auto [u,v,id]:qu)
	{
		ans[id]=min(ans[id],dis[u]+dis[v]);
	}
	deledge(lf[0],lf[lcnt-1]);
	
	vector<int> used(n+5),siz(n+5),mxson(n+5),vis(n+5),bel(n+5);
	vector<int> subs;
	int gcnt=0;
	function<void(int)> dfs0=[&](int u)
	{
//		cerr<<"dfs0 "<<u<<endl;
		siz[u]=1;mxson[u]=0;
		vis[u]=1;
		subs.push_back(u);
		for(auto v:T[u])
		{
			if(not used[v] and not vis[v])
			{
				dfs0(v);
				siz[u]+=siz[v];
				if(siz[v]>siz[mxson[u]])
					mxson[u]=v;
			}
		}
	};
	function<void(int,int)> dfs1=[&](int r,int u)
	{
		siz[u]=1;mxson[u]=0;
		vis[u]=0;
		for(auto v:T[u])
		{
			if(not used[v] and vis[v])
			{
				if(u==r)bel[v]=v;
				else bel[v]=bel[u];
				dfs1(r,v);
				siz[u]+=siz[v];
			}
		}
	};
	function<void(int,vector<tuple<int,int,int>>)> Divide=[&](int u,vector<tuple<int,int,int>> curq)
	{
//		cerr<<"Divide "<<u<<endl;
		subs.clear();
		dfs0(u);
		int r=u,sz=siz[u];
//		cerr<<"go "<<r<<' '<<siz[r]<<' '<<mxson[r]<<' '<<siz[mxson[r]]<<endl;
		while(mxson[r] and siz[mxson[r]]>=(sz+1)/2)
		{
			r=mxson[r];
		}
//		cerr<<"G="<<r<<endl;
		bel[r]=0;
		dfs1(r,r);
		++gcnt;
		vector<pair<int,int>> sp;
		for(auto x:subs)
		{
//			cerr<<x<<' '<<bel[x]<<endl;
			good[x]=gcnt;
			dis[x]=inf;
			if(x==r)continue;
			for(auto [y,w]:G[x])
			{
				if(x<y and bel[x]!=bel[y])
					sp.emplace_back(x,y);
			}
		}
		dijk(r,gcnt);
		for(auto [a,b,c]:curq)
		{
			ans[c]=min(ans[c],dis[a]+dis[b]);
//			cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
		}
		for(auto [x,y]:sp)
		{
			for(auto z:subs)
			{
				dis[z]=inf;
			}
			dijk(x,gcnt);
			for(auto [a,b,c]:curq)
			{
//				cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
				ans[c]=min(ans[c],dis[a]+dis[b]);
			}
			deledge(x,y);
		}
		used[r]=1;
		for(auto v:T[r])
		{
			if(not used[v])
			{
				vector<tuple<int,int,int>> tmpq;
				for(auto [a,b,c]:curq)
				{
					if(bel[a]==v and bel[b]==v)
						tmpq.emplace_back(a,b,c);
				}
				Divide(v,tmpq);
			}
		}
	};
	Divide(1,qu);
	
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

input:

4
1 9
1 8
1 0
9 9 9
6
1 2
1 3
1 4
2 3
2 4
3 4

output:

9
8
0
9
9
8

result:

ok 6 numbers

Test #2:

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

input:

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
0 0 0 0 0 0
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

output:

7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0

result:

ok 21 numbers

Test #3:

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

input:

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

output:

9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16

result:

ok 21 numbers

Test #4:

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

input:

99998
1 683940
1 335116
3 198362
4 28825
5 625394
6 314200
7 270653
8 61629
9 650997
10 693039
11 159577
12 466708
13 715788
14 262771
15 615302
16 1457
17 650381
18 542652
19 101993
20 197937
21 474452
22 859631
23 327526
24 705522
25 500710
26 595050
27 577264
28 955258
29 269967
30 4012
31 471435...

output:

683940
335116
533478
562303
1187697
1501897
1772550
1834179
2485176
3178215
3337792
3804500
4520288
4783059
5398361
5399818
6050199
6592851
6694844
6892781
7367233
8226864
8554390
9259912
9760622
10355672
10932936
11888194
12158161
12162173
12633608
13385421
13746582
14637654
14649654
15558759
15771...

result:

ok 250000 numbers

Test #5:

score: 0
Accepted
time: 332ms
memory: 46172kb

input:

99998
1 479670338308
2 121499701200
3 858712975908
4 144714509693
5 285977224040
6 864876191776
7 68574926716
8 310308615852
9 502806496434
10 361482163495
11 765497528076
12 895859015474
13 334706003457
14 379981526252
15 36757813515
16 157157422672
17 349512227463
18 338990361716
19 163391039440
2...

output:

479670338308
601170039508
1459883015416
1604597525109
1890574749149
2755450940925
2824025867641
3134334483493
3637140979927
3998623143422
4764120671498
5659979686972
5994685690429
6374667216681
6411425030196
6568582452868
6918094680331
7257085042047
7420476081487
7622906189099
8454399662437
89043817...

result:

ok 250000 numbers

Test #6:

score: 0
Accepted
time: 332ms
memory: 46184kb

input:

99998
1 178045123943
2 547685852175
3 121241296998
4 254770970696
5 492051406869
6 202334193904
7 510144241379
8 319988611700
9 116337235366
10 879642794656
11 685411730399
12 350924727333
13 594085342571
14 548936135915
15 208962464142
16 862456709774
17 288075015418
18 829298359525
19 618337059019...

output:

178045123943
725730976118
846972273116
1101743243812
1593794650681
1796128844585
2306273085964
2626261697664
2742598933030
3622241727686
4307653458085
4658578185418
5252663527989
5801599663904
6010562128046
6873018837820
7161093853238
7990392212763
8608729271782
9144448114015
9555400007353
973058283...

result:

ok 250000 numbers

Test #7:

score: 0
Accepted
time: 298ms
memory: 41960kb

input:

99998
1 505218
1 389104
3 722814
4 114842
5 630847
6 266652
7 69086
8 188782
9 302082
10 791859
11 868547
12 207649
13 144886
14 249343
15 348080
16 430422
17 677611
18 246267
19 45035
20 530145
21 674630
22 619198
23 586278
24 546781
25 135381
26 191829
27 974891
28 296123
29 309858
30 867733
31 57...

output:

49938777
183635999
291401080
222197252
152860291
146829716
117562120
288851477
115289410
138187501
289382499
200698275
193084513
80189366
308086109
123556908
220108246
57739237
205655324
153106016
175295026
56841964
226043803
301029279
147951641
127525962
157093651
291414258
313601850
102156566
2156...

result:

ok 250000 numbers

Test #8:

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

input:

99998
1 554852632074
1 877287935997
3 863063671260
4 807596967492
5 817277345167
6 963454496337
7 35181087309
8 682566158188
9 618067491408
10 163993674555
11 37973654749
12 544138262869
13 219011600890
14 444041187252
15 282634304121
16 793774000524
17 15450446700
18 355176887372
19 447528097591
20...

output:

36965622913940
32770119754145
120174886915036
175254080000187
62418986141396
175674957932261
180655959165950
102106066388664
29131554988904
34374587437849
122953102595140
55281766592353
107735923046596
88589612479211
92938994634909
172287081033431
70206151959994
112140581212107
150187289709607
12604...

result:

ok 250000 numbers

Test #9:

score: 0
Accepted
time: 339ms
memory: 42000kb

input:

99998
1 337970157731
2 733936784289
3 38690932141
4 458709248187
5 438708156192
6 955898305396
7 252188236483
8 226770136460
9 784882978281
10 581223663945
11 571145073652
12 18757792382
13 437234520805
14 605539408269
15 176108201879
16 1136649828
17 952302049470
18 739298670877
19 79494920828
20 9...

output:

159859740372295
217564176871359
137919553934290
166298320003622
46637364653325
144112640342261
211279971651073
161285633950603
190697294613587
60084753950595
97315660610726
217340534406035
24636886425737
143715928829509
131318785395185
91650500710076
139107271184521
180819789153384
158577083125405
2...

result:

ok 250000 numbers

Test #10:

score: 0
Accepted
time: 168ms
memory: 54872kb

input:

99998
1 683940
1 335116
3 198362
4 28825
5 625394
6 314200
7 270653
8 61629
9 650997
10 693039
11 159577
12 466708
13 715788
14 262771
15 615302
16 1457
17 650381
18 542652
19 101993
20 197937
21 474452
22 859631
23 327526
24 705522
25 500710
26 595050
27 577264
28 955258
29 269967
30 4012
31 471435...

output:

683940
335116
533478
562303
1187697
1501897
1772550
1834179
2485176
3178215
3337792
3804500
4520288
4783059
5398361
5399818
6050199
6592851
6694844
6892781
7367233
8226864
8554390
9259912
9760622
10355672
10932936
11888194
12158161
12162173
12633608
13385421
13746582
14637654
14649654
15558759
15771...

result:

ok 250000 numbers

Test #11:

score: 0
Accepted
time: 162ms
memory: 54848kb

input:

99998
1 479670338308
2 121499701200
3 858712975908
4 144714509693
5 285977224040
6 864876191776
7 68574926716
8 310308615852
9 502806496434
10 361482163495
11 765497528076
12 895859015474
13 334706003457
14 379981526252
15 36757813515
16 157157422672
17 349512227463
18 338990361716
19 163391039440
2...

output:

479670338308
601170039508
1459883015416
1604597525109
1890574749149
2755450940925
2824025867641
3134334483493
3637140979927
3998623143422
4764120671498
5659979686972
5994685690429
6374667216681
6411425030196
6568582452868
6918094680331
7257085042047
7420476081487
7622906189099
8454399662437
89043817...

result:

ok 250000 numbers

Test #12:

score: 0
Accepted
time: 167ms
memory: 54880kb

input:

99998
1 178045123943
2 547685852175
3 121241296998
4 254770970696
5 492051406869
6 202334193904
7 510144241379
8 319988611700
9 116337235366
10 879642794656
11 685411730399
12 350924727333
13 594085342571
14 548936135915
15 208962464142
16 862456709774
17 288075015418
18 829298359525
19 618337059019...

output:

178045123943
725730976118
846972273116
1101743243812
1593794650681
1796128844585
2306273085964
2626261697664
2742598933030
3622241727686
4307653458085
4658578185418
5252663527989
5801599663904
6010562128046
6873018837820
7161093853238
7990392212763
8608729271782
9144448114015
9555400007353
973058283...

result:

ok 250000 numbers

Test #13:

score: 0
Accepted
time: 168ms
memory: 50396kb

input:

99998
1 505218
1 389104
3 722814
4 114842
5 630847
6 266652
7 69086
8 188782
9 302082
10 791859
11 868547
12 207649
13 144886
14 249343
15 348080
16 430422
17 677611
18 246267
19 45035
20 530145
21 674630
22 619198
23 586278
24 546781
25 135381
26 191829
27 974891
28 296123
29 309858
30 867733
31 57...

output:

6475170685
18296468463
1121070836
16695742237
11066057805
42860720422
14428963674
3692054807
2227905259
1714915356
19131106974
9821315836
12524695522
3986823337
12790940916
22550803631
23610015238
3102309150
3401015881
18699384553
19905329907
865332423
6891760386
16835591504
6639521092
3148140627
17...

result:

ok 250000 numbers

Test #14:

score: 0
Accepted
time: 194ms
memory: 50412kb

input:

99998
1 554852632074
1 877287935997
3 863063671260
4 807596967492
5 817277345167
6 963454496337
7 35181087309
8 682566158188
9 618067491408
10 163993674555
11 37973654749
12 544138262869
13 219011600890
14 444041187252
15 282634304121
16 793774000524
17 15450446700
18 355176887372
19 447528097591
20...

output:

12203046887784113
10365327549230162
17079574516460217
4141534192921317
5429075254318531
3565765544700762
16952829218113345
5845875140946204
3890107933592949
984518580017239
17330516641751964
3699529649452223
11918426897241532
15952581467530069
3843116124947454
5370054179772823
16090340337819991
1375...

result:

ok 250000 numbers

Test #15:

score: 0
Accepted
time: 191ms
memory: 50088kb

input:

99998
1 337970157731
2 733936784289
3 38690932141
4 458709248187
5 438708156192
6 955898305396
7 252188236483
8 226770136460
9 784882978281
10 581223663945
11 571145073652
12 18757792382
13 437234520805
14 605539408269
15 176108201879
16 1136649828
17 952302049470
18 739298670877
19 79494920828
20 9...

output:

10339105026613567
14461690199915115
12690823238458067
7821178705209607
7076184629969823
16899171856091454
19437242126164987
11158951829491146
13679133170357567
15385713272973363
11365708278139910
1438468654825004
8861073082935820
4940900936389092
16614700449067911
13114868036582086
5311028510915450
...

result:

ok 250000 numbers

Test #16:

score: 0
Accepted
time: 956ms
memory: 59132kb

input:

99998
1 970533
1 240729
1 506011
4 913306
5 445101
5 366094
7 651162
8 863644
9 186883
10 233942
11 86762
12 214346
13 19463
14 9614
15 404874
16 919416
17 885137
17 158745
19 39820
19 881835
19 772416
22 797601
23 534988
23 74531
23 759376
26 541958
26 756133
28 265896
28 44502
30 79268
31 659653
3...

output:

970533
240729
506011
1419317
1864418
1785411
2436573
3300217
3487100
3721042
3807804
4022150
4041613
4051227
4456101
5375517
6260654
5534262
5574082
6416097
6306678
7104279
7639267
7178810
7863655
8405613
8619788
8885684
8664290
8743558
9403211
9600362
10335969
11073373
11794671
12403718
11850222
11...

result:

ok 250000 numbers

Test #17:

score: 0
Accepted
time: 1052ms
memory: 59068kb

input:

99998
1 131124635252
1 936656049863
1 138174759305
4 966891691524
5 760667907438
6 289636283597
6 10442334563
6 497444176424
9 988258248677
10 831323449001
10 166319695829
12 86883156682
12 644172526728
14 657987082235
15 240058525125
16 856801349887
16 793474065491
16 838458499696
19 414532890647
2...

output:

31696319941
31696319941
138174759305
568159280105
42138654504
31696319941
31696319941
135200711220
284899172452
31696319941
118579476623
31696319941
762752003351
281716918007
521775443132
31696319941
31696319941
98356157214
34741745948
149418638613
31696319941
126971921147
31696319941
983362194770
6...

result:

ok 250000 numbers

Test #18:

score: 0
Accepted
time: 924ms
memory: 59032kb

input:

99998
1 44770392883
1 624051118618
1 263585542367
4 524752721483
4 791993848389
6 509143587362
7 711172000354
8 379974192468
9 40447004707
10 287830133004
11 907152036932
11 687894352432
13 430153986463
14 550489549312
15 691605036651
16 608410540203
16 429284279368
18 622716535282
19 221584875717
1...

output:

44770392883
624051118618
263585542367
788338263850
1055579390756
1564722978118
2011657363250
1631683170782
1672130175489
1959960308493
1692525254061
2647854660925
3078008647388
3409629526560
2718024489909
2109613949706
2994730506609
2372013971327
2150429095610
2555606876822
2548347227261
23389617156...

result:

ok 250000 numbers

Test #19:

score: 0
Accepted
time: 974ms
memory: 55372kb

input:

99998
1 512325
2 979124
3 194805
4 394249
5 662431
6 888129
7 276170
8 626539
9 601987
10 913607
11 488518
12 779981
13 377438
14 391727
14 833801
16 18201
17 477394
18 112826
18 693157
20 206418
21 924422
22 68277
23 479134
23 557559
25 755833
25 426607
27 753161
27 885185
27 660210
30 98415
31 108...

output:

1051022
791190534
731791
11299415422
1258215
314411
3808607886
9632134254
3882738070
8127222842
9540588277
11849634419
8743859546
3518111225
8293181929
913418151
6798751977
1927395756
1770694496
8423168607
4099547593
72698993
1804688
1364475
6182029778
1343964
8307382142
6766150191
3078966937
134493...

result:

ok 250000 numbers

Test #20:

score: 0
Accepted
time: 1050ms
memory: 55352kb

input:

99998
1 829170695873
1 945697346258
3 661963543546
4 173286031372
4 188104550315
6 167395101915
6 9681517448
8 82242053182
8 638212611020
8 424769935639
11 406377539745
12 688323279541
13 567322713997
14 629057382142
15 409974832006
16 896449310256
16 953031395063
16 423517011447
16 256978319729
20 ...

output:

1197825013626
0
0
139983110438
0
0
1853346758956
858202499129
1025615376727
891813083216
0
2830359651
909708015088
423828922834
0
0
178160477776
739911029733
423345215528
0
418681604384
0
0
189294771124
0
0
207198750781
0
1039243762354
0
0
998812910071
0
0
718779760784
0
0
272112207948
379163855062
...

result:

ok 250000 numbers

Test #21:

score: 0
Accepted
time: 942ms
memory: 54844kb

input:

99998
1 179155860556
2 317805795789
3 446844205406
4 635950239649
5 307529718475
5 272034801018
7 631694733142
7 954266631254
9 128432260084
10 104243097566
11 737581337748
12 494875817975
13 746612650201
13 660887700007
15 887947559277
16 350729500538
16 363870155279
16 190186200975
16 343783778080...

output:

110569981429622
1540152716913140
1044314808492615
163484085847869
1192537505634177
2145549902102
724156949171
3170571219421206
2628050086807795
3460655128695998
2689710260404467
1180385191209
1899526016959006
1738981448989
2569135193958289
4366769598022042
1475015352121
1321901447830699
517026742371...

result:

ok 250000 numbers

Test #22:

score: 0
Accepted
time: 738ms
memory: 54124kb

input:

99997
1 934085
1 978315
3 964193
4 882774
4 697158
6 831534
6 552432
8 4238
9 73513
9 353715
11 742197
11 923639
13 917365
13 512219
15 119854
15 121847
17 989007
18 485680
19 453361
20 564637
21 830101
22 567365
23 37431
23 379090
25 719782
25 596887
27 480396
28 901706
29 141127
30 841867
31 47301...

output:

934085
978315
1942508
2825282
2639666
3471200
3192098
3196336
3269849
3550051
4292248
4473690
5391055
4985909
5105763
5107756
6096763
6582443
7035804
7600441
8430542
8997907
9035338
9376997
10096779
9973884
10454280
11355986
11497113
12338980
12811991
12797808
13177103
13347120
13737064
13705084
138...

result:

ok 250000 numbers

Test #23:

score: 0
Accepted
time: 767ms
memory: 54116kb

input:

99997
1 877587146276
1 901347281097
3 410381763257
4 189685841497
4 511676214511
6 596302137914
6 357609288990
8 820674083888
9 170552381477
9 773574394426
11 173511286596
11 151781173358
13 913953759074
13 160620156596
15 638140151972
15 421797745783
17 389663064113
18 117182048551
19 444356624453
...

output:

877587146276
901347281097
1067272987773
877587146276
1473889284190
877587146276
1425530790141
1048139527753
877587146276
1051098432872
877587146276
1202879606230
877587146276
1363499762826
877587146276
1432173683499
1042510619386
925328570835
1369685195288
1734997539118
1747509584702
1725188748906
8...

result:

ok 250000 numbers

Test #24:

score: 0
Accepted
time: 539ms
memory: 54360kb

input:

99997
1 389486711284
1 160162924039
3 459088475381
4 763676122424
4 456601532632
6 437764388417
6 437010021141
8 662763949425
9 336166033258
9 815676806103
11 626032995169
11 272311903846
13 888335162172
13 704788412045
15 79280011925
15 25532431714
17 10074241571
18 244738884815
19 942183623550
20 ...

output:

389486711284
160162924039
619251399420
683879884040
1075852932052
1439050397924
1431327980240
2094091929665
1816179002089
2842738928397
2216705933228
2985380966263
2758561245609
2280592554218
2359872566143
2255060122504
2244985880933
2489724765748
3431908389298
3751133622646
4118456427598
3140292967...

result:

ok 250000 numbers

Test #25:

score: 0
Accepted
time: 749ms
memory: 51196kb

input:

99997
1 515595
1 267321
3 412138
4 72328
4 968123
6 763250
6 452037
8 755737
9 768867
9 879251
11 217344
11 727708
13 107824
13 205822
15 613942
15 690823
17 368139
18 218638
19 203480
20 334605
21 742475
22 664216
23 426506
23 761945
25 760194
25 992076
27 921785
28 647888
29 423858
30 727829
31 36...

output:

4403245601
14446307996
15740860793
16006491438
3923714638
16708030623
8860745285
12707876489
3971229268
9692642685
7839073952
5726443397
9153584098
12330174046
9445924700
3821923953
15039472917
2348319280
12182053521
10484150192
10251166270
3936491166
5629437765
15702689893
16879120753
1451593326
10...

result:

ok 250000 numbers

Test #26:

score: 0
Accepted
time: 758ms
memory: 51204kb

input:

99997
1 976046685195
1 410296169391
3 877068451101
4 25229938184
4 59045625655
6 710381247757
6 771373785892
8 384255821053
9 820398284627
9 287743339426
11 150316641128
11 58346236492
13 697148149972
13 520620702016
15 346203543249
15 14249859139
17 30883679262
18 219864067620
19 760397722659
20 60...

output:

0
27379745108
389059677102
1307361438199
292157812733
456634458214
306006889353
472582873228
313317812522
274603691614
702827757662
0
441649399489
15456756740
638015176350
0
693794724469
86054924061
0
170529483204
0
647570609044
183021737663
253002343149
615578812222
275290488099
0
0
0
221402605398
...

result:

ok 250000 numbers

Test #27:

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

input:

99997
1 587942851829
1 175900447230
3 613526996512
4 266070894642
4 235287206822
6 28325205639
6 284814667565
8 19326879174
9 233580153845
9 891061448059
11 253736532488
11 960621871278
13 276596446793
13 961805509569
15 578991087461
15 915028180433
17 576775324358
18 578016755600
19 70273606305
20 ...

output:

5459491017848562
5612901488135033
8135853532278526
1901425857325554
1898759987754563
3546883842557165
3939049923845308
4683186540999329
3912634936214767
4312289515165676
5245071914077726
5462160187281839
1089705107986736
7447584546007727
6471183958890385
299014935041108
2828991862854248
923250394310...

result:

ok 250000 numbers

Test #28:

score: 0
Accepted
time: 1151ms
memory: 73888kb

input:

99998
1 306776
1 915969
1 770291
1 690959
1 925998
1 108588
1 241225
1 382585
1 478422
1 14595
1 614441
1 807489
1 707702
1 855344
1 715394
1 61190
1 424441
1 717514
1 157760
1 987854
1 410463
1 312678
1 784809
1 558739
1 942926
1 789224
1 416990
1 325531
1 660355
1 231841
1 894092
1 866660
1 715888...

output:

306776
915969
770291
690959
925998
108588
241225
382585
478422
14595
614441
807489
707702
855344
715394
61190
424441
717514
157760
987854
410463
312678
784809
558739
942926
789224
416990
325531
660355
231841
894092
866660
715888
677338
489180
143247
304278
346974
727888
187305
671227
117973
359949
7...

result:

ok 250000 numbers

Test #29:

score: 0
Accepted
time: 1289ms
memory: 73936kb

input:

99998
1 227659908427
1 607488418725
1 929185915564
1 545308552875
1 228860364663
1 723890724374
1 601272435897
1 321792767624
1 405309097091
1 576823599772
1 159466812240
1 707441864248
1 152257424356
1 791544438091
1 643636270038
1 559324837236
1 125808767633
1 261514050671
1 735354513360
1 8262565...

output:

3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041406
3041...

result:

ok 250000 numbers

Test #30:

score: 0
Accepted
time: 1450ms
memory: 73936kb

input:

99998
1 320027508098
1 111498125835
1 420422132927
1 302390880001
1 972063129323
1 456010398652
1 258679319113
1 178552949694
1 38186440096
1 677065878963
1 332108457517
1 382702451304
1 724061927600
1 365344808948
1 152362679891
1 381597076750
1 835478766375
1 980001864908
1 899317737851
1 74291578...

output:

320027508098
111498125835
420422132927
302390880001
526641776852
456010398652
258679319113
83873512923
38186440096
677065878963
332108457517
382702451304
464010020027
365344808948
152362679891
381597076750
835478766375
980001864908
899317737851
742915784533
675682996424
518130274562
387177463151
930...

result:

ok 250000 numbers

Test #31:

score: 0
Accepted
time: 1168ms
memory: 72068kb

input:

99998
1 523401
1 552907
1 728625
1 805234
1 684733
1 490657
1 917845
1 994241
1 611986
1 509769
1 461861
1 105713
1 563668
1 945673
1 804273
1 932758
1 474468
1 597710
1 710464
1 853272
1 326619
1 689684
1 949841
1 924436
1 316371
1 179753
1 648503
1 326912
1 926515
1 352051
1 127460
1 360583
1 2735...

output:

1302328
1470869
977226
469522
467225
391349
1089690
156580
1158753
1511977
1601967
984623
1474911
1085008
1011349
512434
1278676
1824408
1623822
1011229
874593
780820
932402
1142674
1073878
1000294
1026514
679169
821092
1577488
1246928
1374942
873141
1028793
935260
1037433
1311834
951886
1364529
179...

result:

ok 250000 numbers

Test #32:

score: 0
Accepted
time: 1323ms
memory: 72056kb

input:

99998
1 171370548250
1 827806847150
1 602783336635
1 346917172301
1 162911286528
1 464135491614
1 933161547146
1 240613233653
1 479756909817
1 99027833021
1 561992262836
1 84468298173
1 763915442397
1 479564208740
1 289136290651
1 182625627387
1 870219980956
1 435143959838
1 1726857504
1 21796923950...

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 250000 numbers

Test #33:

score: 0
Accepted
time: 1430ms
memory: 72056kb

input:

99998
1 753472953966
1 304739389117
1 870731931216
1 15517879885
1 116087334191
1 205435107812
1 478051178036
1 226117401095
1 536597553714
1 337450319196
1 676506515158
1 378917256943
1 228053561017
1 371339347664
1 597427597635
1 853191310879
1 132658390452
1 407454609023
1 129574356303
1 94614396...

output:

1013898108354
992133227437
223466077875
1075773057579
920957811473
758363837729
1246392169801
697682419806
770053015030
1765694823520
1426319734565
987960697551
1091908515411
292457711757
606028918175
1033958338739
1175337567467
428570510454
452089332786
340555233524
248297346869
777982207414
517659...

result:

ok 250000 numbers

Test #34:

score: 0
Accepted
time: 724ms
memory: 47072kb

input:

99998
1 683940
1 335116
3 198362
1 28825
5 625394
6 314200
6 270653
8 61629
9 650997
10 693039
10 159577
12 466708
13 715788
13 262771
15 615302
15 1457
17 650381
18 542652
13 101993
20 197937
21 474452
22 859631
23 327526
23 705522
25 500710
26 595050
27 577264
28 955258
29 269967
30 4012
30 471435...

output:

683940
335116
533478
28825
654219
968419
924872
986501
1637498
2330537
1797075
2263783
2979571
2526554
3141856
2528011
3178392
3721044
2365776
2563713
3038165
3897796
4225322
4603318
5104028
5699078
6276342
7231600
7501567
7505579
7973002
7028155
4964479
5855551
5867551
6776656
6988935
7383024
81922...

result:

ok 250000 numbers

Test #35:

score: 0
Accepted
time: 699ms
memory: 47072kb

input:

99998
1 479670338308
2 121499701200
1 858712975908
4 144714509693
5 285977224040
5 864876191776
7 68574926716
8 310308615852
9 502806496434
9 361482163495
11 765497528076
12 895859015474
12 334706003457
14 379981526252
14 36757813515
16 157157422672
17 349512227463
12 338990361716
19 163391039440
20...

output:

131942035763
10442334563
441134068296
296419558603
10442334563
892132373565
823557446849
513248830997
10442334563
874730994492
725129864272
10442334563
390423860815
10442334563
427181674330
359954562026
10442334563
1064120225988
1227511265428
1291917857405
460424384067
10442334563
1124711505971
1458...

result:

ok 250000 numbers

Test #36:

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

input:

99998
1 178045123943
2 547685852175
1 121241296998
4 254770970696
5 492051406869
5 202334193904
7 510144241379
8 319988611700
9 116337235366
9 879642794656
11 685411730399
12 350924727333
12 594085342571
14 548936135915
14 208962464142
16 862456709774
17 288075015418
12 829298359525
19 618337059019
...

output:

178045123943
725730976118
121241296998
376012267694
868063674563
578346461598
1088490702977
1024847914636
908510679270
1904490709292
1547265539607
1196340812274
2141350882178
2103492849206
2350313346320
3079462217056
2791387201638
2376563899132
2994900958151
3530619800384
3396724016191
3221541188101...

result:

ok 250000 numbers

Test #37:

score: 0
Accepted
time: 714ms
memory: 45748kb

input:

99998
1 505218
1 389104
3 722814
1 114842
5 630847
6 266652
6 69086
8 188782
9 302082
10 791859
10 868547
12 207649
13 144886
13 249343
15 348080
15 430422
17 677611
18 246267
13 45035
20 530145
21 674630
22 619198
23 586278
23 546781
25 135381
26 191829
27 974891
28 296123
29 309858
30 867733
30 57...

output:

61162519
116514841
25019541
49512138
67055092
107600993
31530499
80811100
23945396
40402883
115279494
70701046
59471772
32792116
136898355
139581487
137594855
34482015
52163813
70658202
140079572
21208485
42336304
106890937
48777274
26367479
137962863
78385035
128309511
58191367
40503177
34017969
15...

result:

ok 250000 numbers

Test #38:

score: 0
Accepted
time: 740ms
memory: 46560kb

input:

99998
1 554852632074
1 877287935997
3 863063671260
1 807596967492
5 817277345167
6 963454496337
6 35181087309
8 682566158188
9 618067491408
10 163993674555
10 37973654749
12 544138262869
13 219011600890
13 444041187252
15 282634304121
15 793774000524
17 15450446700
18 355176887372
13 447528097591
20...

output:

1267556540819
1663215511465
1578564116566
1607501550824
1340454638769
642398828802
1052663065648
475340131876
1505850662712
689335525949
322363815407
1409438451175
0
1148633480285
0
1045793067648
813595011039
655521609892
1134381653233
0
1088391168083
467065260035
1834094401716
1364883716576
9031806...

result:

ok 250000 numbers

Test #39:

score: 0
Accepted
time: 690ms
memory: 45740kb

input:

99998
1 337970157731
2 733936784289
1 38690932141
4 458709248187
5 438708156192
5 955898305396
7 252188236483
8 226770136460
9 784882978281
9 581223663945
11 571145073652
12 18757792382
12 437234520805
14 605539408269
14 176108201879
16 1136649828
17 952302049470
12 739298670877
19 79494920828
20 90...

output:

77414127614388
100642288120541
20087415166332
46331134007197
40849599371029
93188008174548
8715107688862
77448594701601
31794188386242
48684769538742
31633234799290
98692078232900
73064496603136
117539634922597
39575301544934
105045204609777
10670933329946
5177001431729
64496568176068
51028977465073...

result:

ok 250000 numbers

Test #40:

score: 0
Accepted
time: 861ms
memory: 49764kb

input:

99998
1 683940
1 335116
3 198362
4 28825
3 625394
6 314200
6 270653
6 61629
3 650997
10 693039
11 159577
12 466708
13 715788
12 262771
12 615302
10 1457
10 650381
18 542652
19 101993
20 197937
21 474452
22 859631
22 327526
22 705522
20 500710
26 595050
27 577264
28 955258
27 269967
30 4012
30 471435...

output:

683940
335116
533478
562303
960510
1274710
1231163
1022139
986113
1679152
1838729
2305437
3021225
2101500
2454031
987570
1636494
2179146
2281139
2479076
2953528
3813159
3281054
3659050
2781849
3376899
3954163
4909421
3646866
3650878
4118301
4870114
5231275
4537938
4549938
5459043
4762217
4944027
575...

result:

ok 250000 numbers

Test #41:

score: 0
Accepted
time: 836ms
memory: 49788kb

input:

99998
1 479670338308
2 121499701200
3 858712975908
2 144714509693
5 285977224040
5 864876191776
5 68574926716
2 310308615852
9 502806496434
10 361482163495
11 765497528076
12 895859015474
11 334706003457
11 379981526252
9 36757813515
9 157157422672
17 349512227463
18 338990361716
19 163391039440
20 ...

output:

223731770972
345231472172
10442334563
79017261279
10442334563
10442334563
10442334563
47200148078
550006644512
345148338020
906301350037
10442334563
10442334563
10442334563
10442334563
204357570750
333607048792
556626754465
662854491679
460424384067
10442334563
10442334563
10442334563
222650687100
7...

result:

ok 250000 numbers

Test #42:

score: 0
Accepted
time: 809ms
memory: 49744kb

input:

99998
1 178045123943
2 547685852175
3 121241296998
2 254770970696
5 492051406869
5 202334193904
5 510144241379
2 319988611700
9 116337235366
10 879642794656
11 685411730399
12 350924727333
11 594085342571
11 548936135915
9 208962464142
9 862456709774
17 288075015418
18 829298359525
19 618337059019
2...

output:

178045123943
725730976118
831063713500
432816094639
675597293250
635150288543
922980421547
498033735643
614370971009
1494013765665
2179425496064
1830132458479
1687639735560
1257485749097
706996199785
1360490445417
1648565460835
2477863820360
2345271972007
1809553129774
1398601236436
1984735957864
24...

result:

ok 250000 numbers

Test #43:

score: 0
Accepted
time: 839ms
memory: 48452kb

input:

99998
1 505218
1 389104
3 722814
4 114842
3 630847
6 266652
6 69086
6 188782
3 302082
10 791859
11 868547
12 207649
13 144886
12 249343
12 348080
10 430422
10 677611
18 246267
19 45035
20 530145
21 674630
22 619198
22 586278
22 546781
20 135381
26 191829
27 974891
28 296123
27 309858
30 867733
30 57...

output:

15759011
9879113
7133219
7289625
11208361
11936861
11996683
12768288
8041428
6757618
12784672
6695328
12311897
7108708
12648161
10087020
8970382
8945231
4595157
12707855
13704344
7488222
13301786
7022050
12232727
11549089
11001433
6203360
14251568
11260693
9718736
5369934
7149582
10120467
9959780
12...

result:

ok 250000 numbers

Test #44:

score: 0
Accepted
time: 852ms
memory: 48936kb

input:

99998
1 554852632074
1 877287935997
3 863063671260
4 807596967492
3 817277345167
6 963454496337
6 35181087309
6 682566158188
3 618067491408
10 163993674555
11 37973654749
12 544138262869
13 219011600890
12 444041187252
12 282634304121
10 793774000524
10 15450446700
18 355176887372
19 447528097591
20...

output:

444566623136
669017269986
407950317002
386169711824
272817019863
266254702049
1083897037633
0
1373647778314
848543462284
138035861723
562695823609
686486836521
0
408906498366
0
838560554485
0
396009838097
107932664896
0
0
307045806850
0
681494984848
400113012866
1730166122173
0
133395086793
0
452978...

result:

ok 250000 numbers

Test #45:

score: 0
Accepted
time: 846ms
memory: 48420kb

input:

99998
1 337970157731
2 733936784289
3 38690932141
2 458709248187
5 438708156192
5 955898305396
5 252188236483
2 226770136460
9 784882978281
10 581223663945
11 571145073652
12 18757792382
11 437234520805
11 605539408269
9 176108201879
9 1136649828
17 952302049470
18 739298670877
19 79494920828
20 901...

output:

12950335378127
8883757563741
6140604382198
8927517022193
9265032069756
7568034062301
6681830413442
9220402030665
9981157152820
11624699721598
11223144704050
12441400542980
12456314394460
14619976381343
6627842501990
9452320129695
6061604941696
13756268623687
9273646627027
11534953640391
719764827941...

result:

ok 250000 numbers

Test #46:

score: 0
Accepted
time: 466ms
memory: 46604kb

input:

99999
1 964193
1 882774
1 697158
4 831534
4 552432
6 4238
7 73513
7 353715
6 742197
10 923639
11 917365
12 512219
13 119854
14 121847
14 989007
13 485680
17 453361
17 564637
12 830101
20 567365
21 37431
21 379090
20 719782
24 596887
24 480396
11 901706
27 141127
28 841867
29 473011
30 458828
31 3792...

output:

964193
882774
697158
1528692
1249590
1253828
1327341
1607543
1991787
2915426
3832791
4345010
4464864
4586711
5453871
4830690
5284051
5395327
4662892
5230257
5267688
5609347
5382674
5979561
5863070
3817132
3958259
4800126
5273137
5731965
6111260
6660572
7050516
7018536
6276964
6735171
6773767
7114791...

result:

ok 250000 numbers

Test #47:

score: 0
Accepted
time: 455ms
memory: 47376kb

input:

99999
1 410381763257
1 189685841497
3 511676214511
3 596302137914
5 357609288990
6 820674083888
6 170552381477
5 773574394426
9 173511286596
10 151781173358
11 913953759074
12 160620156596
13 638140151972
13 421797745783
12 389663064113
16 117182048551
16 444356624453
11 625377723047
19 149313722222...

output:

410381763257
189685841497
410381763257
785987979411
580934144734
410381763257
410381763257
1559562373837
1733073660433
1831180634995
917226875921
832179509040
410381763257
410381763257
527563811808
410381763257
410381763257
1407297088109
1257983365887
410381763257
410381763257
672359251388
410381763...

result:

ok 250000 numbers

Test #48:

score: 0
Accepted
time: 511ms
memory: 46888kb

input:

99999
1 459088475381
1 763676122424
1 456601532632
4 437764388417
4 437010021141
6 662763949425
7 336166033258
7 815676806103
6 626032995169
10 272311903846
11 888335162172
12 704788412045
13 79280011925
14 25532431714
14 10074241571
13 244738884815
17 942183623550
17 319225233348
12 755827610127
20...

output:

459088475381
763676122424
456601532632
894365921049
893611553773
1338817412905
1002651379647
1488063301781
1519644548942
1791956452788
2364426662076
1659638250031
1580358238106
1554825806392
1590432479677
1904377134846
2129920089317
2223602368194
3120254272203
2705146228812
2245402049200
23414412687...

result:

ok 250000 numbers

Test #49:

score: 0
Accepted
time: 485ms
memory: 45064kb

input:

99999
1 412138
1 72328
1 968123
4 763250
4 452037
6 755737
7 768867
7 879251
6 217344
10 727708
11 107824
12 205822
13 613942
14 690823
14 368139
13 218638
17 203480
17 334605
12 742475
20 664216
21 426506
21 761945
20 760194
24 992076
24 921785
11 647888
27 423858
28 727829
29 367691
30 969880
31 4...

output:

9806276
8795527
17865360
9530959
14248018
17204564
15770343
16997645
12308490
14273307
11609619
10358806
12820779
14635768
9572870
10846210
17782702
14460733
13829635
15516537
15495859
13083335
15635205
17297205
10032483
14862103
14508929
14321137
16533405
14212752
14365428
17682193
17286947
1443791...

result:

ok 250000 numbers

Test #50:

score: 0
Accepted
time: 468ms
memory: 45292kb

input:

99999
1 877068451101
1 25229938184
3 59045625655
3 710381247757
5 771373785892
6 384255821053
6 820398284627
5 287743339426
9 150316641128
10 58346236492
11 697148149972
12 520620702016
13 346203543249
13 14249859139
12 30883679262
16 219864067620
16 760397722659
11 607428147389
19 82520221590
20 38...

output:

0
1113944436041
3827879229
1729601109683
370252026338
0
561451754621
1142440131313
242074237989
0
1815531195419
208441137638
136389150029
88464152485
1353512859515
872424246696
0
443412443268
0
144134427628
132980012323
581902347424
161668004920
228519268950
602777120442
670082505539
0
1878874946431...

result:

ok 250000 numbers

Test #51:

score: 0
Accepted
time: 498ms
memory: 44780kb

input:

99999
1 613526996512
1 266070894642
1 235287206822
4 28325205639
4 284814667565
6 19326879174
7 233580153845
7 891061448059
6 253736532488
10 960621871278
11 276596446793
12 961805509569
13 578991087461
14 915028180433
14 576775324358
13 578016755600
17 70273606305
18 102009147413
17 175100876679
12...

output:

13255866991015
14886434382808
13762814573638
16516021474398
13638630732628
14210909941810
12267048441979
17040698228611
2446417164241
8510997700314
15845998659498
10002739104346
12301132017031
14299158102519
11899830224110
15049949023617
12578171036137
9582517883835
13096044120546
13548973825379
123...

result:

ok 250000 numbers

Test #52:

score: 0
Accepted
time: 862ms
memory: 60836kb

input:

99999
1 964193
1 882774
1 697158
4 831534
4 552432
4 4238
7 73513
8 353715
8 742197
8 923639
8 917365
8 512219
8 119854
8 121847
8 989007
8 485680
8 453361
7 564637
19 830101
20 567365
19 37431
19 379090
19 719782
19 596887
19 480396
19 901706
19 141127
19 841867
19 473011
7 458828
31 379295
31 5493...

output:

964193
882774
697158
1528692
1249590
701396
774909
1128624
1517106
1698548
1692274
1287128
894763
896756
1763916
1260589
1228270
1266033
2096134
2663499
1303464
1645123
1985815
1862920
1746429
2167739
1407160
2107900
1739044
1160224
1539519
1709536
1550168
1518188
1325928
1618431
1657027
1501248
195...

result:

ok 250000 numbers

Test #53:

score: 0
Accepted
time: 1064ms
memory: 61796kb

input:

99999
1 410381763257
1 189685841497
3 511676214511
3 596302137914
3 357609288990
6 820674083888
7 170552381477
7 773574394426
7 173511286596
7 151781173358
7 913953759074
7 160620156596
7 638140151972
7 421797745783
7 389663064113
7 117182048551
6 444356624453
18 625377723047
18 149313722222
18 9833...

output:

290766484038
189685841497
290766484038
290766484038
460297485056
407948532589
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
440080206260
290766484038
290766484038
290766484038
290766484038
290766484038
290766484038
2...

result:

ok 250000 numbers

Test #54:

score: 0
Accepted
time: 1056ms
memory: 60860kb

input:

99999
1 459088475381
1 763676122424
1 456601532632
4 437764388417
4 437010021141
4 662763949425
7 336166033258
8 815676806103
8 626032995169
8 272311903846
8 888335162172
8 704788412045
8 79280011925
8 25532431714
8 10074241571
8 244738884815
8 942183623550
7 319225233348
19 755827610127
19 97816345...

output:

459088475381
763676122424
456601532632
894365921049
893611553773
1119365482057
1455531515315
1379023475907
1445785980518
1727843419161
2160853594282
1556611208246
1534811527240
1481063947029
1465605756886
1700270400130
2360715010088
1438590715405
2194418325532
2416754175101
2110725658566
18022956754...

result:

ok 250000 numbers

Test #55:

score: 0
Accepted
time: 881ms
memory: 58776kb

input:

99999
1 412138
1 72328
1 968123
4 763250
4 452037
4 755737
7 768867
8 879251
8 217344
8 727708
8 107824
8 205822
8 613942
8 690823
8 368139
8 218638
8 203480
7 334605
19 742475
19 664216
21 426506
19 761945
19 760194
19 992076
19 921785
19 647888
19 423858
19 727829
19 367691
7 969880
31 412416
31 1...

output:

3589159
1958668
5032403
3873725
3869561
5329976
4510458
5297015
1785284
4917404
4654430
5257226
4679757
6116290
3874579
3964132
5470892
5367378
6533541
5187839
5833650
5074189
4885898
5408252
3807110
4256659
5907672
4371914
5838639
4774278
3968489
4332438
4314292
4500621
4183284
4837283
7826884
5635...

result:

ok 250000 numbers

Test #56:

score: 0
Accepted
time: 1090ms
memory: 60768kb

input:

99999
1 877068451101
1 25229938184
3 59045625655
3 710381247757
3 771373785892
6 384255821053
7 820398284627
7 287743339426
7 150316641128
7 58346236492
7 697148149972
7 520620702016
7 346203543249
7 14249859139
7 30883679262
7 219864067620
6 760397722659
18 607428147389
18 82520221590
18 3831657713...

output:

0
0
0
0
0
0
0
0
11456029037
0
0
0
0
0
58656385346
0
0
38393163851
0
0
0
0
0
0
0
25965844484
0
0
255794865900
0
0
0
0
0
0
0
0
22901685328
0
117052555425
0
0
0
57959301640
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
61505742375
283313642
0
0
0
0
148255707188
0
22211065230
0
0
0
0
0
0
0
82468721660
0
0
0
0
4461785...

result:

ok 250000 numbers

Test #57:

score: 0
Accepted
time: 1031ms
memory: 58832kb

input:

99999
1 613526996512
1 266070894642
1 235287206822
4 28325205639
4 284814667565
4 19326879174
7 233580153845
8 891061448059
8 253736532488
8 960621871278
8 276596446793
12 961805509569
8 578991087461
8 915028180433
8 576775324358
8 578016755600
8 70273606305
8 102009147413
7 175100876679
20 74463472...

output:

5346568532373
3231053351370
4419776406723
4607204015294
3512093765678
4507978633171
3968416433996
1699168818826
3832411698030
2585188621323
4872838974111
4650834242248
3730657367271
5230025660927
4025110115776
5713171008852
4958024727143
4612480590287
5274105715418
6095010823826
2808049337751
549446...

result:

ok 250000 numbers

Test #58:

score: 0
Accepted
time: 1024ms
memory: 63532kb

input:

99999
1 964193
1 882774
1 697158
4 831534
4 552432
4 4238
4 73513
4 353715
4 742197
4 923639
4 917365
4 512219
4 119854
14 121847
15 989007
15 485680
15 453361
15 564637
15 830101
15 567365
15 37431
15 379090
15 719782
15 596887
15 480396
15 901706
15 141127
15 841867
15 473011
15 458828
15 379295
1...

output:

964193
882774
697158
1528692
1249590
701396
770671
1050873
1439355
1620797
1614523
1209377
817012
938859
1927866
1424539
1392220
1503496
1768960
1506224
976290
1317949
1658641
1535746
1419255
1840565
1079986
1780726
1411870
1397687
1318154
1488171
1328803
1296823
1104563
1397066
1435662
1279883
1731...

result:

ok 250000 numbers

Test #59:

score: 0
Accepted
time: 1171ms
memory: 64164kb

input:

99999
1 410381763257
1 189685841497
3 511676214511
3 596302137914
3 357609288990
3 820674083888
3 170552381477
3 773574394426
3 173511286596
3 151781173358
3 913953759074
3 160620156596
13 638140151972
14 421797745783
14 389663064113
14 117182048551
14 444356624453
14 625377723047
14 149313722222
14...

output:

190320958459
189685841497
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
242057553197
218481667825
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
1...

result:

ok 250000 numbers

Test #60:

score: 0
Accepted
time: 1288ms
memory: 63508kb

input:

99999
1 459088475381
1 763676122424
1 456601532632
4 437764388417
4 437010021141
4 662763949425
4 336166033258
4 815676806103
4 626032995169
4 272311903846
4 888335162172
4 704788412045
4 79280011925
14 25532431714
15 10074241571
15 244738884815
15 942183623550
15 319225233348
15 755827610127
15 978...

output:

459088475381
763676122424
456601532632
894365921049
893611553773
859530070501
792767565890
1196678297422
1082634527801
728913436478
750713117484
846752337067
535881544557
561413976271
571488217842
806152861086
1046935894175
880639209619
1226049514450
1539577435967
1233548919432
925118936300
61934748...

result:

ok 250000 numbers

Test #61:

score: 0
Accepted
time: 1048ms
memory: 61412kb

input:

99999
1 412138
1 72328
1 968123
4 763250
4 452037
4 755737
4 768867
4 879251
4 217344
4 727708
4 107824
4 205822
4 613942
14 690823
15 368139
15 218638
15 203480
15 334605
15 742475
15 664216
15 426506
15 761945
15 760194
15 992076
15 921785
15 647888
15 423858
15 727829
15 367691
15 969880
15 41241...

output:

2312963
2608184
2733054
1144168
2109504
2329018
2353721
2939405
2017480
1667502
3300926
1888464
2826622
2892658
1516084
1376315
2976611
3074110
3198653
2622690
2866283
3382904
3418313
3412575
1368543
1993779
3857985
3520837
3890243
2917488
2809857
1822004
2487937
2968826
2612362
1204346
3996997
3203...

result:

ok 250000 numbers

Test #62:

score: 0
Accepted
time: 1218ms
memory: 63104kb

input:

99999
1 877068451101
1 25229938184
3 59045625655
3 710381247757
3 771373785892
3 384255821053
3 820398284627
3 287743339426
3 150316641128
3 58346236492
3 697148149972
3 520620702016
13 346203543249
14 14249859139
14 30883679262
14 219864067620
14 760397722659
14 607428147389
14 82520221590
14 38316...

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
65980358565
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100939655762
0
0
0
0
0
0
483474623
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
707249036806
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 250000 numbers

Test #63:

score: 0
Accepted
time: 1302ms
memory: 61404kb

input:

99999
1 613526996512
1 266070894642
1 235287206822
4 28325205639
4 284814667565
4 19326879174
4 233580153845
4 891061448059
4 253736532488
4 960621871278
4 276596446793
4 961805509569
4 578991087461
14 915028180433
15 576775324358
15 578016755600
15 70273606305
15 102009147413
15 175100876679
15 744...

output:

1465967556546
3591167160327
920379371138
4025941397075
2247537090365
2420801680281
3273490471066
3041022673288
3757739469192
2655219751131
2461768077574
3055042627156
2162241065935
2599152736107
913927977640
2044848573212
2242694762572
3587210479668
3360804796249
1958304701583
1627619173863
19364721...

result:

ok 250000 numbers

Test #64:

score: 0
Accepted
time: 1093ms
memory: 63872kb

input:

99999
1 964193
1 882774
1 697158
4 831534
4 552432
4 4238
4 73513
4 353715
4 742197
4 923639
4 917365
4 512219
4 119854
4 121847
4 989007
4 485680
4 453361
4 564637
4 830101
4 567365
21 37431
4 379090
4 719782
4 596887
4 480396
4 901706
4 141127
4 841867
4 473011
4 458828
4 379295
4 549312
4 389944
...

output:

964193
882774
697158
1528692
1249590
701396
770671
1050873
1439355
1620797
1614523
1209377
817012
819005
1686165
1182838
1150519
1261795
1527259
1264523
1301954
1076248
1416940
1294045
1177554
1598864
838285
1539025
1170169
1155986
1076453
1246470
1087102
1055122
862862
1155365
1193961
1038182
14898...

result:

ok 250000 numbers

Test #65:

score: 0
Accepted
time: 1228ms
memory: 64256kb

input:

99999
1 410381763257
1 189685841497
3 511676214511
3 596302137914
3 357609288990
3 820674083888
3 170552381477
3 773574394426
3 173511286596
3 151781173358
3 913953759074
3 160620156596
3 638140151972
3 421797745783
3 389663064113
3 117182048551
3 444356624453
3 625377723047
3 149313722222
3 9833749...

output:

190320958459
189685841497
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
190320958459
1...

result:

ok 250000 numbers

Test #66:

score: 0
Accepted
time: 1351ms
memory: 63872kb

input:

99999
1 459088475381
1 763676122424
1 456601532632
4 437764388417
4 437010021141
4 662763949425
4 336166033258
4 815676806103
4 626032995169
4 272311903846
4 888335162172
4 704788412045
4 79280011925
4 25532431714
4 10074241571
4 244738884815
4 942183623550
4 319225233348
4 755827610127
4 9781634596...

output:

459088475381
763676122424
456601532632
894365921049
893611553773
859530070501
792767565890
1196678297422
1082634527801
728913436478
750713117484
846752337067
535881544557
482133964346
466675774203
632972458759
978382763590
775826765980
1212429142759
1434764992328
1128736475793
637531403047
514535044...

result:

ok 250000 numbers

Test #67:

score: 0
Accepted
time: 1103ms
memory: 61504kb

input:

99999
1 412138
1 72328
1 968123
4 763250
4 452037
4 755737
4 768867
4 879251
4 217344
4 727708
4 107824
4 205822
4 613942
4 690823
4 368139
4 218638
4 203480
4 334605
4 742475
4 664216
4 426506
4 761945
4 760194
4 992076
4 921785
4 647888
4 423858
4 727829
4 367691
4 969880
4 412416
4 110033
4 10842...

output:

2229253
1499191
1966721
873201
2033465
2665335
1648107
1248667
1494548
2102733
2577468
1230436
1719407
3370728
1484654
1056940
2005259
1994549
2522498
1339626
1519238
2095700
2104968
3474945
1409433
1407581
2286694
1973912
2290389
1983838
1434534
1532986
1681457
2639715
2443547
1633062
2331935
23485...

result:

ok 250000 numbers

Test #68:

score: 0
Accepted
time: 1251ms
memory: 63200kb

input:

99999
1 877068451101
1 25229938184
3 59045625655
3 710381247757
3 771373785892
3 384255821053
3 820398284627
3 287743339426
3 150316641128
3 58346236492
3 697148149972
3 520620702016
3 346203543249
3 14249859139
3 30883679262
3 219864067620
3 760397722659
3 607428147389
3 82520221590
3 383165771350
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
482075739421
0
0
0
0
0
0
0
0
0
210105206739
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
312947952454
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 250000 numbers

Test #69:

score: 0
Accepted
time: 1382ms
memory: 62312kb

input:

99999
1 613526996512
1 266070894642
1 235287206822
4 28325205639
4 284814667565
4 19326879174
4 233580153845
4 891061448059
4 253736532488
4 960621871278
4 276596446793
4 961805509569
4 578991087461
4 915028180433
4 576775324358
4 578016755600
4 70273606305
4 102009147413
4 175100876679
4 7446347282...

output:

2931414771848
1494615577426
1108732481115
989375397221
1217679570641
1329020694669
1357483992403
2317003581708
2287531445480
1498017498785
1714625264703
1951854381987
1861695312248
2387757083860
1988907963857
1570856540442
2277070404063
1716989348656
2604704713346
2210791776742
1826814726802
1569981...

result:

ok 250000 numbers

Test #70:

score: 0
Accepted
time: 790ms
memory: 50656kb

input:

99998
1 978315
1 964193
3 882774
4 697158
5 831534
6 552432
7 4238
8 73513
8 353715
10 742197
11 923639
12 917365
13 512219
12 119854
15 121847
15 989007
17 485680
18 453361
19 564637
17 830101
21 567365
17 37431
11 379090
11 719782
11 596887
7 480396
27 901706
28 141127
29 841867
30 473011
31 45882...

output:

978315
964193
1846967
2544125
3375659
3928091
3932329
4005842
4286044
5028241
5951880
6869245
7381464
6071734
6193581
7060741
7546421
7999782
8564419
7890842
8458207
7098172
5407331
5748023
5625128
4408487
5310193
5451320
6293187
6766198
7225026
7145493
7694805
7156142
7514106
5617024
5768400
490529...

result:

ok 250000 numbers

Test #71:

score: 0
Accepted
time: 777ms
memory: 50616kb

input:

99998
1 901347281097
2 410381763257
3 189685841497
4 511676214511
5 596302137914
6 357609288990
7 820674083888
7 170552381477
9 773574394426
10 173511286596
11 151781173358
12 913953759074
11 160620156596
14 638140151972
14 421797745783
16 389663064113
17 117182048551
18 444356624453
16 625377723047...

output:

901347281097
1311729044354
1405876127550
1917552342061
2134698766399
1777089477409
956415393521
1947641858886
1701416124473
1755175702089
1870369152595
956415393521
1594555545493
956415393521
1731106838790
1517954066525
1400772017974
956415393521
1105729115743
956415393521
956415393521
956415393521
...

result:

ok 250000 numbers

Test #72:

score: 0
Accepted
time: 779ms
memory: 50628kb

input:

99998
1 160162924039
1 459088475381
3 763676122424
4 456601532632
5 437764388417
6 437010021141
7 662763949425
8 336166033258
8 815676806103
10 626032995169
11 272311903846
12 888335162172
13 704788412045
12 79280011925
15 25532431714
15 10074241571
17 244738884815
18 942183623550
19 319225233348
17...

output:

160162924039
459088475381
1222764597805
1679366130437
1973231532028
1536221510887
873457561462
537291528204
1689134367565
1856798119209
1584486215363
1642606871388
937818459343
1505206203438
1479673771724
1515280445009
1760019329824
2401083607936
2081858374588
2271108055136
2190143833186
21874153881...

result:

ok 250000 numbers

Test #73:

score: 0
Accepted
time: 801ms
memory: 47728kb

input:

99998
1 267321
1 412138
3 72328
4 968123
5 763250
6 452037
7 755737
8 768867
8 879251
10 217344
11 727708
12 107824
13 205822
12 613942
15 690823
15 368139
17 218638
18 203480
19 334605
17 742475
21 664216
17 426506
11 761945
11 760194
11 992076
26 921785
7 647888
28 423858
29 727829
30 367691
31 96...

output:

14136737
26202182
18142644
14992077
15488213
22103001
17576269
13271680
9300121
19133536
3543542
12729256
18304021
17386572
20309985
16061399
21343927
20285440
19043516
20149393
25418500
13552641
22650065
22816832
19140846
18754479
19974001
12926483
12601016
22013761
18113815
19071919
16372515
16690...

result:

ok 250000 numbers

Test #74:

score: 0
Accepted
time: 812ms
memory: 47980kb

input:

99998
1 410296169391
1 877068451101
3 25229938184
4 59045625655
5 710381247757
6 771373785892
7 384255821053
8 820398284627
8 287743339426
10 150316641128
11 58346236492
12 697148149972
13 520620702016
12 346203543249
15 14249859139
15 30883679262
17 219864067620
18 760397722659
19 607428147389
17 8...

output:

71291754280
0
0
821275161067
596518636152
444526275382
0
1122194956148
0
590466443049
746350945345
362042451270
2225437427992
1036108900697
1537717762672
556997941466
1738836274758
517508463520
1287886872475
197586331915
1354052885299
1972552158413
920886408077
284740585723
1032928483230
17690380502...

result:

ok 250000 numbers

Test #75:

score: 0
Accepted
time: 770ms
memory: 47744kb

input:

99998
1 175900447230
1 613526996512
3 266070894642
4 235287206822
5 28325205639
6 284814667565
7 19326879174
8 233580153845
8 891061448059
10 253736532488
11 960621871278
12 276596446793
13 961805509569
12 578991087461
15 915028180433
15 576775324358
17 578016755600
18 70273606305
19 102009147413
17...

output:

15095068167057
15824281943012
21520897617274
15274440114962
21058520346313
14564793724198
18042836791078
17736233482103
12099141743686
18143278108709
22354620903778
10370262274344
24454719617757
16019365743427
14774520523500
21309068983000
23051609220361
18911783739791
12279422384918
16744567485775
...

result:

ok 250000 numbers

Test #76:

score: 0
Accepted
time: 722ms
memory: 49492kb

input:

99999
1 964193
1 882774
1 697158
4 831534
5 552432
6 4238
7 73513
8 353715
9 742197
10 923639
11 917365
12 512219
12 119854
12 121847
15 989007
15 485680
17 453361
18 564637
18 830101
20 567365
21 37431
22 379090
23 719782
24 596887
25 480396
26 901706
27 141127
28 841867
26 473011
30 458828
31 3792...

output:

964193
882774
697158
1528692
2081124
2085362
2158875
2512590
3254787
4178426
5095791
5608010
5215645
5217638
6206645
5703318
6156679
6721316
6986780
7554145
7591576
7970666
8690448
9287335
9767731
10669437
10810564
11652431
10240742
10699570
11078865
11628177
11468809
10125695
9453039
9911246
994984...

result:

ok 250000 numbers

Test #77:

score: 0
Accepted
time: 688ms
memory: 49496kb

input:

99999
1 410381763257
1 189685841497
3 511676214511
4 596302137914
5 357609288990
6 820674083888
7 170552381477
8 773574394426
9 173511286596
10 151781173358
11 913953759074
11 160620156596
11 638140151972
14 421797745783
14 389663064113
16 117182048551
17 444356624453
17 625377723047
19 149313722222...

output:

410381763257
189685841497
701362056008
1297664193922
1655273482912
919044368133
748491986656
896294379807
722783093211
571001919853
410381763257
410381763257
832179509040
410381763257
926259606515
854738387710
410381763257
1480116110757
1629429832979
988305721472
1835907324102
2154587519541
12461849...

result:

ok 250000 numbers

Test #78:

score: 0
Accepted
time: 697ms
memory: 49492kb

input:

99999
1 459088475381
1 763676122424
1 456601532632
4 437764388417
5 437010021141
6 662763949425
7 336166033258
8 815676806103
9 626032995169
10 272311903846
11 888335162172
12 704788412045
12 79280011925
12 25532431714
15 10074241571
15 244738884815
17 942183623550
18 319225233348
18 755827610127
20...

output:

459088475381
763676122424
456601532632
894365921049
1331375942190
1994139891615
2330305924873
3145982730976
2714073261829
2441761357983
1553426195811
1365860725288
1474146183886
1578958627525
1589032869096
1823697512340
1975020607055
1655795373707
2730848217182
3709011676878
4381146620039
4461528307...

result:

ok 250000 numbers

Test #79:

score: 0
Accepted
time: 735ms
memory: 46864kb

input:

99999
1 412138
1 72328
1 968123
4 763250
5 452037
6 755737
7 768867
8 879251
9 217344
10 727708
11 107824
12 205822
12 613942
12 690823
15 368139
15 218638
17 203480
18 334605
18 742475
20 664216
21 426506
22 761945
23 760194
24 992076
25 921785
26 647888
27 423858
28 727829
26 367691
30 969880
31 4...

output:

11351411
12988888
27561052
24747680
21713309
20790461
31408207
17047952
27613629
28875819
26736699
25733932
29366706
24466985
26190153
32108007
23948795
13637917
20929465
25454629
16856896
26634162
24897723
27691323
15300944
29452287
22222103
22518284
27391620
18182358
17113046
24547274
27142929
291...

result:

ok 250000 numbers

Test #80:

score: 0
Accepted
time: 723ms
memory: 47120kb

input:

99999
1 877068451101
1 25229938184
3 59045625655
4 710381247757
5 771373785892
6 384255821053
7 820398284627
8 287743339426
9 150316641128
10 58346236492
11 697148149972
11 520620702016
11 346203543249
14 14249859139
14 30883679262
16 219864067620
17 760397722659
17 607428147389
19 82520221590
20 38...

output:

559123494289
263815676785
198328679295
889480871181
550409256919
394531605811
659378168522
0
0
778250921479
604989047114
764700803724
733698082444
570539891906
736488188223
870789663899
0
0
780053095793
727606508027
0
0
587819680286
874726415293
0
156571284263
788522973040
398052850033
402136340814
...

result:

ok 250000 numbers

Test #81:

score: 0
Accepted
time: 729ms
memory: 46856kb

input:

99999
1 613526996512
1 266070894642
1 235287206822
4 28325205639
5 284814667565
6 19326879174
7 233580153845
8 891061448059
9 253736532488
10 960621871278
11 276596446793
12 961805509569
12 578991087461
12 915028180433
15 576775324358
15 578016755600
17 70273606305
18 102009147413
18 175100876679
20...

output:

26276931817824
20564911756277
12462373440569
20993740071301
15775547188013
22764576748293
14075607523892
23156601395499
19093232848481
18800062335122
21679243834294
15901120004659
22306410940658
22625690131174
19190952166224
26025893751603
16420850947784
20540978877772
21657522644541
17810944516494
...

result:

ok 250000 numbers

Test #82:

score: 0
Accepted
time: 659ms
memory: 48760kb

input:

100000
1 803728
1 100496
3 744948
4 683940
5 335116
6 198362
7 28825
8 625394
9 314200
10 270653
11 61629
12 650997
13 693039
14 159577
15 466708
16 715788
17 262771
18 615302
19 1457
20 650381
21 542652
22 101993
23 197937
24 474452
25 859631
26 327526
27 705522
28 500710
29 595050
30 577264
31 955...

output:

803728
100496
845444
1529384
1864500
2062862
2091687
2717081
3031281
3301934
3363563
4014560
4707599
4867176
5333884
6049672
6312443
6927745
6929202
7579583
8122235
8224228
8422165
8896617
9756248
10083774
10789296
11290006
11885056
12462320
13417578
13687545
13691557
14162992
14914805
15275966
1616...

result:

ok 250000 numbers

Test #83:

score: 0
Accepted
time: 694ms
memory: 48756kb

input:

100000
1 938486335915
1 582363851503
3 825265416450
4 479670338308
5 121499701200
6 858712975908
7 144714509693
8 285977224040
9 864876191776
10 68574926716
11 310308615852
12 502806496434
13 361482163495
14 765497528076
15 895859015474
16 334706003457
17 379981526252
18 36757813515
19 157157422672
...

output:

289636283597
582363851503
1407629267953
1887299606261
2008799307461
2867512283369
3012226793062
3298204017102
4163080208878
4231655135594
4541963751446
5044770247880
5406252411375
6171749939451
7067608954925
7402314958382
7782296484634
7819054298149
7976211720821
8325723948284
8301555460844
81381644...

result:

ok 250000 numbers

Test #84:

score: 0
Accepted
time: 621ms
memory: 48764kb

input:

100000
1 34093503696
1 748919240150
3 157167744630
4 178045123943
5 547685852175
6 121241296998
7 254770970696
8 492051406869
9 202334193904
10 510144241379
11 319988611700
12 116337235366
13 879642794656
14 685411730399
15 350924727333
16 594085342571
17 548936135915
18 208962464142
19 862456709774...

output:

34093503696
748919240150
906086984780
1084132108723
1631817960898
1753059257896
2007830228592
2499881635461
2702215829365
3212360070744
3532348682444
3648685917810
4528328712466
5213740442865
5564665170198
6158750512769
6707686648684
6916649112826
7779105822600
8067180838018
8896479197543
9514816256...

result:

ok 250000 numbers

Test #85:

score: 0
Accepted
time: 677ms
memory: 46116kb

input:

100000
1 287637
1 552752
3 649886
4 505218
5 389104
6 722814
7 114842
8 630847
9 266652
10 69086
11 188782
12 302082
13 791859
14 868547
15 207649
16 144886
17 249343
18 348080
19 430422
20 677611
21 246267
22 45035
23 530145
24 674630
25 619198
26 586278
27 546781
28 135381
29 191829
30 974891
31 2...

output:

124275787
226894256
148544522
270426363
185196653
71214352
144523199
169440038
207033814
286418588
19760246
261802470
320970965
225733683
212660730
302845280
270760175
140702990
305429606
98640012
218025544
99939012
108635489
59924473
84871417
298662790
130170752
221492485
253062765
99546231
3020383...

result:

ok 250000 numbers

Test #86:

score: 0
Accepted
time: 708ms
memory: 46424kb

input:

100000
1 353067977680
2 282719177005
3 4779008523
4 554852632074
5 877287935997
6 863063671260
7 807596967492
8 817277345167
9 963454496337
10 35181087309
11 682566158188
12 618067491408
13 163993674555
14 37973654749
15 544138262869
16 219011600890
17 444041187252
18 282634304121
19 793774000524
20...

output:

372985061179
235312932475
1450197521985
538857201345
1261804810507
2163997236832
2013671265828
1702311423322
289139933047
1829611652689
297400351354
0
196150306810
132933220160
2131680497316
472376340079
0
372314673017
1004002940347
2332294113471
664142882713
922170916783
613931227271
1076053063753
...

result:

ok 250000 numbers

Test #87:

score: 0
Accepted
time: 653ms
memory: 46160kb

input:

100000
1 645693229291
2 922006456793
3 583199545750
4 337970157731
5 733936784289
6 38690932141
7 458709248187
8 438708156192
9 955898305396
10 252188236483
11 226770136460
12 784882978281
13 581223663945
14 571145073652
15 18757792382
16 437234520805
17 605539408269
18 176108201879
19 1136649828
20...

output:

139816794854778
105161881588828
103490046023840
145165581723064
77164324644210
64028607604110
132672088660049
104878249622795
128006422011904
133014022317295
121227764780045
103099730578495
22142849539736
62201886233206
64585349148379
129103532264096
77801601687545
79554692721155
55677218973817
4620...

result:

ok 250000 numbers

Test #88:

score: 0
Accepted
time: 812ms
memory: 58176kb

input:

99998
1 970533
1 240729
1 506011
4 913306
5 445101
6 366094
7 651162
8 863644
8 186883
10 233942
11 86762
12 214346
13 19463
13 9614
15 404874
15 919416
17 885137
18 158745
18 39820
20 881835
20 772416
22 797601
22 534988
24 74531
24 759376
26 541958
27 756133
28 265896
28 44502
30 79268
31 659653
3...

output:

970533
240729
506011
1419317
1864418
2230512
2881674
3745318
3068557
3302499
3389261
3603607
3623070
3613221
4018095
4532637
5417774
5576519
5457594
6339429
6230010
7027611
6764998
6839529
7524374
8066332
8822465
9088361
8866967
8946235
9605888
9143386
9681842
9683639
10404937
11013984
11069535
1126...

result:

ok 250000 numbers

Test #89:

score: 0
Accepted
time: 1037ms
memory: 58164kb

input:

99998
1 131124635252
1 936656049863
1 138174759305
4 966891691524
5 760667907438
6 289636283597
7 10442334563
7 497444176424
9 988258248677
9 831323449001
11 166319695829
11 86883156682
13 644172526728
14 657987082235
14 240058525125
16 856801349887
17 793474065491
17 838458499696
19 414532890647
19...

output:

31696319941
31696319941
138174759305
70239932741
331774938101
42138654504
31696319941
539582830928
31696319941
198016015770
31696319941
284899172452
248392516792
31696319941
488451041917
825170385432
31696319941
298167898786
31696319941
285061015529
54143037407
31696319941
31696319941
639734693787
3...

result:

ok 250000 numbers

Test #90:

score: 0
Accepted
time: 677ms
memory: 58324kb

input:

99998
1 44770392883
1 624051118618
1 263585542367
4 524752721483
5 791993848389
5 509143587362
7 711172000354
8 379974192468
9 40447004707
9 287830133004
11 907152036932
12 687894352432
13 430153986463
13 550489549312
15 691605036651
15 608410540203
15 429284279368
18 622716535282
19 221584875717
19...

output:

44770392883
624051118618
263585542367
788338263850
1155647166132
1297481851212
2008653851566
2100281161050
2059834156343
2388111294054
3295263330986
2907076838451
2476922851988
3209343034543
2517737997892
2706270617961
3638627313911
3208119463024
2986534587307
4063368436492
4056108786931
39682924297...

result:

ok 250000 numbers

Test #91:

score: 0
Accepted
time: 860ms
memory: 54408kb

input:

99998
1 512325
2 979124
3 194805
4 394249
5 662431
6 888129
6 276170
8 626539
9 601987
9 913607
11 488518
11 779981
13 377438
14 391727
15 833801
15 18201
15 477394
15 112826
19 693157
19 206418
21 924422
22 68277
22 479134
24 557559
24 755833
26 426607
26 753161
28 885185
29 660210
29 98415
31 1085...

output:

849771187
789285910
12400776689
11776289831
4459750651
3685385038
21058651864
7618022362
5187487047
9249324998
7992901212
6196589627
15955713210
5609628872
10245121758
8189920339
4706143694
1933141290
10908301076
10291449196
19508355591
7385805476
775856848
3897825950
11005672410
2208922865
13170895...

result:

ok 250000 numbers

Test #92:

score: 0
Accepted
time: 1052ms
memory: 54624kb

input:

99998
1 829170695873
1 945697346258
3 661963543546
4 173286031372
4 188104550315
6 167395101915
7 9681517448
7 82242053182
9 638212611020
10 424769935639
11 406377539745
11 688323279541
13 567322713997
13 629057382142
15 409974832006
16 896449310256
17 953031395063
18 423517011447
19 256978319729
20...

output:

639927226258
660640622461
0
349716854347
677105680608
0
855365499813
959149201864
0
1378961762130
881015376478
1036326032609
477400727322
688473442538
561596845495
0
0
0
1067279170813
1686938708366
898224027331
766618585851
0
868335989502
1441928555979
2311083625362
207198750781
593619357829
0
85028...

result:

ok 250000 numbers

Test #93:

score: 0
Accepted
time: 708ms
memory: 53928kb

input:

99998
1 179155860556
2 317805795789
3 446844205406
3 635950239649
5 307529718475
5 272034801018
7 631694733142
8 954266631254
9 128432260084
9 104243097566
11 737581337748
12 494875817975
13 746612650201
13 660887700007
15 887947559277
16 350729500538
16 363870155279
16 190186200975
19 343783778080
...

output:

5187470033208326
6612899632572972
65872559808289
2440250487519078
903577028722977
1926030948696288
5863446884675785
7054962461502897
6241524794733102
1813922900604828
2038750701853048
1719623576162704
1785204445765038
5232973900944330
2202160032641394
653078736121611
4096856459746900
650340673075003...

result:

ok 250000 numbers

Test #94:

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

input:

50313
1 1153
2 83462
3 497073
4 929701
5 401627
6 591319
7 193794
8 582605
9 547542
10 789400
11 869694
12 988723
13 925440
14 567139
15 66290
16 225405
17 580326
18 111304
19 995281
20 249727
21 881092
22 585125
23 569821
24 423583
25 844321
26 5602
27 66295
28 738644
29 282723
30 308715
31 988384
...

output:

1153
84615
581688
1511389
1913016
2504335
2698129
3280734
3828276
4617676
5487370
6476093
7401533
7968672
8034962
8260367
8840693
8951997
9947278
10197005
11078097
11663222
12233043
12656626
13500947
13506549
13572844
14311488
14594211
14902926
15891310
16536743
16803632
16897899
17837030
18507388
1...

result:

ok 250000 numbers

Test #95:

score: 0
Accepted
time: 177ms
memory: 31140kb

input:

50313
1 946748733890
2 741514091094
3 250813685504
4 773428901734
5 205041648548
6 976548472177
7 63080171135
8 31119100294
9 891203170764
10 284139467750
11 863829891505
12 387756675839
13 481809961987
14 958574610856
15 383651704810
16 417008418264
17 359023619819
18 636501097998
19 441322530204
2...

output:

946748733890
1688262824984
1939076510488
2712505412222
2917547060770
3894095532947
3957175704082
3988294804376
4879497975140
5163637442890
6027467334395
6415224010234
6897033972221
7855608583077
8239260287887
8656268706151
9015292325970
9651793423968
10093115954172
11010106685543
11632089532240
1258...

result:

ok 250000 numbers

Test #96:

score: 0
Accepted
time: 161ms
memory: 31112kb

input:

50313
1 661562269328
2 108612246220
3 231444754022
4 794534954598
5 865304932891
6 97870025216
7 482326949354
8 65536895699
9 784416756637
10 24385149795
11 239770685882
12 482051274773
13 478518417353
14 655958968965
15 609351167573
16 781509594965
17 239914863790
18 517645527419
19 368015504368
20...

output:

661562269328
770174515548
1001619269570
1796154224168
2661459157059
2759329182275
3241656131629
3307193027328
4091609783965
4115994933760
4355765619642
4837816894415
5316335311768
5972294280733
6581645448306
7363155043271
7603069907061
8120715434480
8488730938848
8533814766311
8799236081966
92417667...

result:

ok 250000 numbers

Test #97:

score: 0
Accepted
time: 167ms
memory: 27716kb

input:

50313
1 254777
2 720401
3 492406
4 43975
5 235045
6 973389
7 907412
8 194260
9 644107
10 322257
11 754799
12 287632
13 781407
14 695152
15 155169
16 59972
17 667352
18 991501
19 547983
20 77462
21 797249
22 999130
23 734853
24 789280
25 217766
26 433817
27 260124
28 702341
29 474885
30 466609
31 184...

output:

236023691
202025268
254355304
159415667
60904371
84943038
135201781
68520728
267977935
54085696
269729248
237824870
131142461
69991973
135500696
99320773
182255013
161654075
163239794
150005564
198458442
179353551
255038593
189552667
148056531
244045836
99570961
70669998
156676215
190543219
20640874...

result:

ok 250000 numbers

Test #98:

score: 0
Accepted
time: 171ms
memory: 27712kb

input:

50313
1 849318853981
2 961832519520
3 924411106576
4 603293139003
5 171643155554
6 716793239418
7 431814834820
8 954234533620
9 998201568629
10 765203181267
11 270650309396
12 764783109765
13 130313532463
14 646594381504
15 24856758126
16 40309208415
17 103434833141
18 801541072573
19 707694874349
2...

output:

86256691637876
28057245012296
127460273620008
47904886619059
42760135352885
100467673651456
22550697469028
86178443693492
46447596707595
99976779515176
16666077554563
130032913781611
70249350309978
87419186556158
89259422522570
113060031329098
97750661685885
111812330930356
114679422717622
743632332...

result:

ok 250000 numbers

Test #99:

score: 0
Accepted
time: 184ms
memory: 27704kb

input:

50313
1 90712747898
2 297558542206
3 681754552310
4 466521434749
5 9329137760
6 851589701673
7 664853255841
8 71960827368
9 282827870254
10 684769590029
11 579873776227
12 515111632848
13 978215083475
14 661953507681
15 50121118020
16 253103829093
17 573940040304
18 945098271535
19 602567090117
20 2...

output:

163507240139411
161829507031395
101632308665060
128352668593118
108763936244027
112687038530027
69847990312071
148315798958264
114278588901449
38426545270868
89330463295431
142117497514825
39054743393523
126155291902777
67974774819673
152683134449800
97281473297615
110359373500818
120894951208068
13...

result:

ok 250000 numbers

Test #100:

score: 0
Accepted
time: 489ms
memory: 55632kb

input:

99990
1 1153
1 83462
3 497073
3 929701
5 401627
5 591319
7 193794
7 582605
9 547542
9 789400
11 869694
11 988723
13 925440
13 567139
15 66290
15 225405
17 580326
17 111304
19 995281
19 249727
21 881092
21 585125
23 569821
23 423583
25 844321
25 5602
27 66295
27 738644
29 282723
29 308715
31 988384
3...

output:

1153
83462
580535
1013163
1414790
1604482
1798276
2187087
2734629
2976487
3846181
3965210
4890650
4532349
4598639
4757754
5338080
4869058
5864339
5118785
5999877
5703910
6273731
6127493
6971814
6133095
6199390
6871739
7154462
7180454
8168838
7825887
8092776
7920154
8859285
8590512
9515218
9493290
10...

result:

ok 250000 numbers

Test #101:

score: 0
Accepted
time: 559ms
memory: 55548kb

input:

99990
1 946748733890
1 741514091094
3 250813685504
3 773428901734
5 205041648548
5 976548472177
7 63080171135
7 31119100294
9 891203170764
9 284139467750
11 863829891505
11 387756675839
13 481809961987
13 958574610856
15 383651704810
15 417008418264
17 359023619819
17 636501097998
19 441322530204
19...

output:

946748733890
741514091094
946748733890
1151790382438
946748733890
1009828905025
946748733890
1040948005319
946748733890
1325087473069
946748733890
1428558695877
946748733890
1330400438700
946748733890
1305772353709
946748733890
1388071264094
946748733890
1568731580587
946748733890
1564394672038
9467...

result:

ok 250000 numbers

Test #102:

score: 0
Accepted
time: 317ms
memory: 55632kb

input:

99990
1 661562269328
1 108612246220
3 231444754022
3 794534954598
5 865304932891
5 97870025216
7 482326949354
7 65536895699
9 784416756637
9 24385149795
11 239770685882
11 482051274773
13 478518417353
13 655958968965
15 609351167573
15 781509594965
17 239914863790
17 517645527419
19 368015504368
19 ...

output:

526701171460
108612246220
340057000242
903147200818
541353868518
1001017226034
623776825668
1066554121733
1241100246159
1090939271528
1330709957410
1572990546301
2051508963654
2228949515266
2340237022271
3010459110231
3098584276722
3528104637650
3297016294468
3573188465113
3838609780768
401571916378...

result:

ok 250000 numbers

Test #103:

score: 0
Accepted
time: 515ms
memory: 51112kb

input:

99990
1 254777
1 720401
3 492406
3 43975
5 235045
5 973389
7 907412
7 194260
9 644107
9 322257
11 754799
11 287632
13 781407
13 695152
15 155169
15 59972
17 667352
17 991501
19 547983
19 77462
21 797249
21 999130
23 734853
23 789280
25 217766
25 433817
27 260124
27 702341
29 474885
29 466609
31 1847...

output:

17047944816
8124238152
663761199
189055308
2172711563
19504647073
13910588448
590591391
8984318927
2741885644
1419338816
5047305258
10580601911
2368031005
14268181303
782731057
4495106196
2582030811
6063466366
3372967434
13064999883
14254664377
5001541004
16279890080
6249779686
13328879234
425268067...

result:

ok 250000 numbers

Test #104:

score: 0
Accepted
time: 554ms
memory: 51452kb

input:

99990
1 849318853981
1 961832519520
3 924411106576
3 603293139003
5 171643155554
5 716793239418
7 431814834820
7 954234533620
9 998201568629
9 765203181267
11 270650309396
11 764783109765
13 130313532463
13 646594381504
15 24856758126
15 40309208415
17 103434833141
17 801541072573
19 707694874349
19...

output:

234473027884
233734430750
1241864675772
873535847511
0
0
0
383796901638
485009505783
824500214628
545555757266
210773075772
802636225941
241779611005
1352966838728
0
423114755701
283721777949
206842864152
390473538989
717039917232
326241566675
595406316749
295977898591
509408979337
180238815560
5404...

result:

ok 250000 numbers

Test #105:

score: 0
Accepted
time: 334ms
memory: 51096kb

input:

99990
1 90712747898
1 297558542206
3 681754552310
3 466521434749
5 9329137760
5 851589701673
7 664853255841
7 71960827368
9 282827870254
9 684769590029
11 579873776227
11 515111632848
13 978215083475
13 661953507681
15 50121118020
15 253103829093
17 573940040304
17 945098271535
19 602567090117
19 20...

output:

499380418708680
7129794661188984
7699913227876094
1294473585075455
10186285758528486
10445586771445110
4689928284596667
7405504631245281
7183828210983408
7508615617810095
1953826713791656
2598379449429724
3122753716721621
9514616851977234
5846642834185000
8902813797708271
8176033797781414
2656951155...

result:

ok 250000 numbers

Test #106:

score: 0
Accepted
time: 381ms
memory: 34896kb

input:

70338
1 1153
1 83462
3 497073
4 929701
5 401627
6 591319
6 193794
8 582605
9 547542
9 789400
11 869694
8 988723
13 925440
14 567139
15 66290
16 225405
17 580326
16 111304
19 995281
15 249727
21 881092
22 585125
23 569821
24 423583
22 844321
26 5602
27 66295
28 738644
28 282723
30 308715
31 988384
27...

output:

1153
83462
580535
1510236
1911863
2503182
2105657
2688262
3235804
3477662
4347356
3094380
4019820
4586959
4653249
4878654
5458980
4764553
5759834
4836686
5717778
6302903
6872724
7296307
6562099
6567701
6633996
7372640
6916719
7225434
8213818
7213134
7480023
7574290
8513421
9183779
10108485
10086557
...

result:

ok 250000 numbers

Test #107:

score: 0
Accepted
time: 377ms
memory: 34900kb

input:

70338
1 946748733890
1 741514091094
3 250813685504
4 773428901734
5 205041648548
6 976548472177
6 63080171135
8 31119100294
9 891203170764
9 284139467750
11 863829891505
8 387756675839
13 481809961987
14 958574610856
15 383651704810
16 417008418264
17 359023619819
16 636501097998
19 441322530204
15 ...

output:

946748733890
741514091094
992327776598
1765756678332
1923297206067
946748733890
1869071004948
1837951904654
946748733890
1810578625395
946748733890
2256827680787
2738637642774
2106432476783
1722780771973
1305772353709
946748733890
1388071264094
946748733890
3023423208154
2474138762625
2216724458809
...

result:

ok 250000 numbers

Test #108:

score: 0
Accepted
time: 356ms
memory: 34888kb

input:

70338
1 661562269328
1 108612246220
3 231444754022
4 794534954598
5 865304932891
6 97870025216
6 482326949354
8 65536895699
9 784416756637
9 24385149795
11 239770685882
8 482051274773
13 478518417353
14 655958968965
15 609351167573
16 781509594965
17 239914863790
16 517645527419
19 368015504368
15 4...

output:

467454889158
108612246220
340057000242
1134591954840
943403769597
845533744381
1425730718951
1491267614650
1440822452602
1515652764445
1471441061155
1907781993724
2386300411077
3042259380042
2747514763119
1966005168154
1726090304364
2449443545714
2081428041346
3087343207505
3352764523160
37952952218...

result:

ok 250000 numbers

Test #109:

score: 0
Accepted
time: 397ms
memory: 34964kb

input:

70338
1 254777
1 720401
3 492406
4 43975
5 235045
6 973389
6 907412
8 194260
9 644107
9 322257
11 754799
8 287632
13 781407
14 695152
15 155169
16 59972
17 667352
16 991501
19 547983
15 77462
21 797249
22 999130
23 734853
24 789280
22 217766
26 433817
27 260124
28 702341
28 474885
30 466609
31 18475...

output:

84797007
108949614
65786873
107233045
71888415
72765194
79357801
28512742
116088484
62613918
73825020
56432188
114962981
86850757
77215019
88049091
91937878
55761154
81860759
102726435
107613766
66326605
96687767
169857414
72602506
75827258
95955594
97425592
100474530
103774346
45169275
110231240
64...

result:

ok 250000 numbers

Test #110:

score: 0
Accepted
time: 381ms
memory: 34908kb

input:

70338
1 849318853981
1 961832519520
3 924411106576
4 603293139003
5 171643155554
6 716793239418
6 431814834820
8 954234533620
9 998201568629
9 765203181267
11 270650309396
8 764783109765
13 130313532463
14 646594381504
15 24856758126
16 40309208415
17 103434833141
16 801541072573
19 707694874349
15 ...

output:

2321171404552
1253851486024
1347159911600
112501111719
604641462166
2023569014306
831574600380
1022842510666
0
640670088608
1296062733439
693785064911
999894483770
1432480915549
2431019620067
1434124711370
1156037507416
3194397107969
265135356996
366546201607
1151624524654
1477131257042
829073753031...

result:

ok 250000 numbers

Test #111:

score: 0
Accepted
time: 386ms
memory: 34964kb

input:

70338
1 90712747898
1 297558542206
3 681754552310
4 466521434749
5 9329137760
6 851589701673
6 664853255841
8 71960827368
9 282827870254
9 684769590029
11 579873776227
8 515111632848
13 978215083475
14 661953507681
15 50121118020
16 253103829093
17 573940040304
16 945098271535
19 602567090117
15 207...

output:

75604577775237
86856333958670
78337784104719
56408972020904
110032927799599
39772525215188
95538144607566
30413248706813
30681191037547
84347870062186
56937530331092
78601226819927
61485725274477
91942859502029
10324066316703
109749708503979
34938688606626
74009712310746
47581180102748
6820483507385...

result:

ok 250000 numbers

Test #112:

score: 0
Accepted
time: 413ms
memory: 36652kb

input:

75063
1 1153
2 83462
3 497073
4 929701
5 401627
6 591319
7 193794
8 582605
8 547542
10 789400
6 869694
12 988723
5 925440
14 567139
14 66290
16 225405
17 580326
18 111304
18 995281
20 249727
21 881092
22 585125
21 569821
24 423583
24 844321
26 5602
20 66295
28 738644
29 282723
29 308715
31 988384
32...

output:

1153
84615
581688
1511389
1913016
2504335
2698129
3280734
3245671
4035071
2782710
3771433
2436829
3003968
2503119
2728524
3308850
3420154
4304131
4553858
5434950
6020075
5123679
5547262
5968000
5973602
4370426
5109070
5391793
5417785
6406169
7051602
7318491
5512052
6451183
5040784
5965490
3631302
44...

result:

ok 250000 numbers

Test #113:

score: 0
Accepted
time: 414ms
memory: 36788kb

input:

75063
1 946748733890
2 741514091094
3 250813685504
4 773428901734
5 205041648548
6 976548472177
7 63080171135
8 31119100294
8 891203170764
10 284139467750
6 863829891505
12 387756675839
5 481809961987
14 958574610856
14 383651704810
16 417008418264
17 359023619819
18 636501097998
18 441322530204
20 ...

output:

946748733890
1688262824984
1939076510488
2191252415115
1986210766567
1009662294390
946582123255
915463022961
1199602490711
915463022961
1303219698800
915463022961
1874037633817
915463022961
2257689338627
1910987740778
1551964120959
915463022961
1993286651163
2185438747880
1870778113240
915463022961
...

result:

ok 250000 numbers

Test #114:

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

input:

75063
1 661562269328
2 108612246220
3 231444754022
4 794534954598
5 865304932891
6 97870025216
7 482326949354
8 65536895699
8 784416756637
10 24385149795
6 239770685882
12 482051274773
5 478518417353
14 655958968965
14 609351167573
16 781509594965
17 239914863790
18 517645527419
18 368015504368
20 4...

output:

661562269328
770174515548
1001619269570
1796154224168
2591967945509
2494097920293
2011770970939
1946234075240
2486733947112
2462348797317
2831738631391
3022377355321
2274672641521
2930631610486
2884023809094
3665533404059
3905448267849
3397582499636
4273463772217
4318547599680
4195230982634
37527002...

result:

ok 250000 numbers

Test #115:

score: 0
Accepted
time: 434ms
memory: 36472kb

input:

75063
1 254777
2 720401
3 492406
4 43975
5 235045
6 973389
7 907412
8 194260
8 644107
10 322257
6 754799
12 287632
5 781407
14 695152
14 155169
16 59972
17 667352
18 991501
18 547983
20 77462
21 797249
22 999130
21 734853
24 789280
24 217766
26 433817
20 260124
28 702341
29 474885
29 466609
31 18475...

output:

29494936
41344890
13692974
18167631
48283160
9922040
45183384
28935546
26149714
22435133
17734365
27313113
32238050
51491555
25134293
48766483
38716424
35197115
32569741
35510970
25920580
20261635
29553161
30279049
33632610
38320342
25093505
46079065
24756758
48123972
40029023
43730175
38636992
2291...

result:

ok 250000 numbers

Test #116:

score: 0
Accepted
time: 408ms
memory: 36428kb

input:

75063
1 849318853981
2 961832519520
3 924411106576
4 603293139003
5 171643155554
6 716793239418
7 431814834820
8 954234533620
8 998201568629
10 765203181267
6 270650309396
12 764783109765
5 130313532463
14 646594381504
14 24856758126
16 40309208415
17 103434833141
18 801541072573
18 707694874349
20 ...

output:

604023326874
637676044014
1315955895107
1392395983167
89684281879
1183873134532
631897564344
0
1815619444648
412632442340
1645210217671
2386278014432
1273717509114
115744203618
895089634628
232589652872
1397266011047
1178469123648
1086238956592
1181398028149
1548562101332
1341675349485
940558523826
...

result:

ok 250000 numbers

Test #117:

score: 0
Accepted
time: 413ms
memory: 36460kb

input:

75063
1 90712747898
2 297558542206
3 681754552310
4 466521434749
5 9329137760
6 851589701673
7 664853255841
8 71960827368
8 282827870254
10 684769590029
6 579873776227
12 515111632848
5 978215083475
14 661953507681
14 50121118020
16 253103829093
17 573940040304
18 945098271535
18 602567090117
20 207...

output:

45781933941012
23712714517078
14915350206653
29487557450761
18056655816723
22997439197721
24716281978681
40855534274338
23945119324412
20190997603401
24361966990059
26563825294866
18937102224531
18307624230385
34591357172928
25182530599871
13769926441229
16973240387986
44479547243983
36878193078931
...

result:

ok 250000 numbers

Test #118:

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

input:

71756
1 1153
2 83462
1 497073
4 929701
5 401627
5 591319
7 193794
8 582605
9 547542
10 789400
11 869694
12 988723
13 925440
14 567139
15 66290
16 225405
17 580326
18 111304
19 995281
17 249727
21 881092
13 585125
23 569821
24 423583
25 844321
26 5602
27 66295
27 738644
29 282723
24 308715
31 988384
...

output:

1153
84615
497073
1426774
1828401
2018093
2211887
2794492
3342034
4131434
5001128
5989851
6915291
7482430
7548720
7774125
8354451
8465755
9461036
8023852
8904944
6574976
7144797
7568380
8412701
8418303
8484598
9156947
9439670
7453512
8441896
9087329
8708785
8803052
5940259
6610617
5056140
5958918
67...

result:

ok 250000 numbers

Test #119:

score: 0
Accepted
time: 375ms
memory: 39048kb

input:

71756
1 946748733890
2 741514091094
1 250813685504
4 773428901734
5 205041648548
5 976548472177
7 63080171135
8 31119100294
9 891203170764
10 284139467750
11 863829891505
12 387756675839
13 481809961987
14 958574610856
15 383651704810
16 417008418264
17 359023619819
18 636501097998
19 441322530204
1...

output:

946748733890
1229284235786
250813685504
1024242587238
1229284235786
2000791059415
2063871230550
2094990330844
2986193501608
2836939767867
2254851648826
2642608324665
3124418286652
3466791606881
3083139902071
2666131483807
2307107863988
1670606765990
1229284235786
1851267082483
1229284235786
23799694...

result:

ok 250000 numbers

Test #120:

score: 0
Accepted
time: 375ms
memory: 39060kb

input:

71756
1 120796576046
2 869030462078
1 672345770497
4 157145624098
5 340608464395
5 645727526997
7 760534286518
8 398698676470
9 313261898455
10 632319941563
11 399999260451
12 356359159992
13 27955338053
14 228570943252
15 704929406376
16 735838118043
17 13198426472
18 12279964109
19 688558573046
17...

output:

120796576046
989827038124
672345770497
829491394595
1170099858990
1475218921592
2235753208110
2634451884580
2947713783035
3580033724598
3980032985049
4336392145041
4364347483094
4323420712865
3618491306489
2882653188446
2869454761974
2857174797865
2168616224819
3863811495142
2942893175539
5069165289...

result:

ok 250000 numbers

Test #121:

score: 0
Accepted
time: 399ms
memory: 35860kb

input:

71756
1 254777
2 720401
1 492406
4 43975
5 235045
5 973389
7 907412
8 194260
9 644107
10 322257
11 754799
12 287632
13 781407
14 695152
15 155169
16 59972
17 667352
18 991501
19 547983
17 77462
21 797249
13 999130
23 734853
24 789280
25 217766
26 433817
27 260124
27 702341
29 474885
24 466609
31 184...

output:

34756125
24898482
20262482
20188105
29905175
23587135
30667735
24141641
28363206
36957707
46729932
32754868
23437333
27783264
12284179
24893465
36584972
41985991
25920104
38893828
36954346
26685662
24723825
14644258
19896753
21749167
36838140
20868872
27422177
23838821
27593347
29239290
24824677
202...

result:

ok 250000 numbers

Test #122:

score: 0
Accepted
time: 373ms
memory: 35616kb

input:

71756
1 849318853981
2 961832519520
1 924411106576
4 603293139003
5 171643155554
5 716793239418
7 431814834820
8 954234533620
9 998201568629
10 765203181267
11 270650309396
12 764783109765
13 130313532463
14 646594381504
15 24856758126
16 40309208415
17 103434833141
18 801541072573
19 707694874349
1...

output:

0
1167761999060
2429120082930
1560129924294
2209787374914
954606656772
1535173644446
758864698245
0
651007650690
1801845059830
0
2312239862464
1037022073069
0
2085057720226
26181316741
1667395085042
1133973917841
0
622730258982
1764306157194
1468254569747
1295328805424
113539326921
812803758061
3568...

result:

ok 250000 numbers

Test #123:

score: 0
Accepted
time: 383ms
memory: 35408kb

input:

71756
1 89596358871
2 797933368658
1 409622183028
4 903127483929
5 367644839965
5 322598265881
7 212710757621
8 350168164531
9 615989651025
10 209319764551
11 192103535290
12 634199687686
13 861112903286
14 207095461085
15 622733092309
16 348682067897
17 523973596087
18 718381834217
19 97201526808
1...

output:

18793500485089
26815963737239
23545935243784
32324844722233
26427164684779
14819842470243
31955332164146
26644633280937
19626317360153
27110294423867
22529123230518
35229089500871
32980572460090
27417532474564
19839947562778
26652232970771
13936376821188
25277037262394
15324741266810
24932747078230
...

result:

ok 250000 numbers

Test #124:

score: 0
Accepted
time: 377ms
memory: 37804kb

input:

70450
1 1153
2 83462
3 497073
4 929701
5 401627
6 591319
7 193794
8 582605
8 547542
10 789400
11 869694
12 988723
13 925440
14 567139
13 66290
16 225405
17 580326
18 111304
18 995281
20 249727
20 881092
22 585125
23 569821
24 423583
25 844321
17 5602
27 66295
28 738644
28 282723
30 308715
31 988384
...

output:

1153
84615
581688
1511389
1913016
2504335
2698129
3280734
3245671
4035071
4904765
5893488
6818928
7386067
5959778
6185183
6765509
6876813
7760790
8010517
8641882
9227007
9796828
10220411
11064732
6190785
6257080
6995724
6539803
6848518
7836902
8482335
8749224
7931169
8870300
9540658
10465364
1136814...

result:

ok 250000 numbers

Test #125:

score: 0
Accepted
time: 360ms
memory: 37836kb

input:

70450
1 946748733890
2 741514091094
3 250813685504
4 773428901734
5 205041648548
6 976548472177
7 63080171135
8 31119100294
8 891203170764
10 284139467750
11 863829891505
12 387756675839
13 481809961987
14 958574610856
13 383651704810
16 417008418264
17 359023619819
18 636501097998
18 441322530204
2...

output:

946748733890
1688262824984
1939076510488
1924921769488
1719880120940
743331648763
680251477628
649132377334
1571454648392
1855594116142
2477273626016
2089516950177
1607706988190
649132377334
2061665513415
1644657095151
1285633475332
649132377334
1566123108705
649132377334
2188105955402
2070731275717...

result:

ok 250000 numbers

Test #126:

score: 0
Accepted
time: 374ms
memory: 37896kb

input:

70450
1 120796576046
2 869030462078
3 672345770497
4 157145624098
5 340608464395
6 645727526997
7 760534286518
8 398698676470
8 313261898455
10 632319941563
11 399999260451
12 356359159992
13 27955338053
14 228570943252
13 704929406376
16 735838118043
17 13198426472
18 12279964109
18 688558573046
20...

output:

120796576046
989827038124
1662172808621
1819318432719
2159926897114
2805654424111
2338000708723
1939302032253
2651262607178
3283582548741
3169668033665
2813308873673
2785353535620
2556782592368
3518238280049
3430721812901
3417523386429
3405243422320
4106081959475
3471283027434
5064692499254
57974656...

result:

ok 250000 numbers

Test #127:

score: 0
Accepted
time: 401ms
memory: 34940kb

input:

70450
1 254777
2 720401
3 492406
4 43975
5 235045
6 973389
7 907412
8 194260
8 644107
10 322257
11 754799
12 287632
13 781407
14 695152
13 155169
16 59972
17 667352
18 991501
18 547983
20 77462
20 797249
22 999130
23 734853
24 789280
25 217766
17 433817
27 260124
28 702341
28 474885
30 466609
31 184...

output:

32402800
36013687
42159649
8703498
42328936
41403622
23973349
24629475
23323231
30176872
32234852
44140997
24907436
25598190
31899843
21001829
37433976
32707657
46187415
33547311
26102182
33096318
29485883
35487900
29570838
29691301
24721136
26784383
57208215
28374354
32115176
27160633
22782923
2497...

result:

ok 250000 numbers

Test #128:

score: 0
Accepted
time: 384ms
memory: 34912kb

input:

70450
1 849318853981
2 961832519520
3 924411106576
4 603293139003
5 171643155554
6 716793239418
7 431814834820
8 954234533620
8 998201568629
10 765203181267
11 270650309396
12 764783109765
13 130313532463
14 646594381504
13 24856758126
16 40309208415
17 103434833141
18 801541072573
18 707694874349
2...

output:

1575546848798
0
1117462389718
0
1041012776334
1133905169786
723822800719
143002444077
820102677108
456464263356
2453954158680
2096265071297
609466771326
1962656579227
1046946257489
611479179804
1537247835344
479570765631
2038408921134
1277398581909
1197575310193
1361162405244
795922273753
6379497305...

result:

ok 250000 numbers

Test #129:

score: 0
Accepted
time: 385ms
memory: 34932kb

input:

70450
1 89596358871
2 797933368658
3 409622183028
4 903127483929
5 367644839965
6 322598265881
7 212710757621
8 350168164531
8 615989651025
10 209319764551
11 192103535290
12 634199687686
13 861112903286
14 207095461085
13 622733092309
16 348682067897
17 523973596087
18 718381834217
18 97201526808
2...

output:

30273475396976
23470093987509
19989390339075
23361186348557
14635203582145
18221697046398
36736705667216
19587834120391
27546141921197
29242833246756
32364342512941
34465173519736
30965761572075
22961151204679
16130363025643
12386669176858
34943329710567
40215140246324
16339160815516
16160077256853
...

result:

ok 250000 numbers

Test #130:

score: 0
Accepted
time: 384ms
memory: 32900kb

input:

68358
1 1153
2 83462
3 497073
4 929701
5 401627
6 591319
7 193794
8 582605
9 547542
10 789400
11 869694
12 988723
13 925440
14 567139
15 66290
16 225405
17 580326
18 111304
19 995281
20 249727
21 881092
22 585125
23 569821
24 423583
25 844321
26 5602
27 66295
28 738644
29 282723
30 308715
31 988384
...

output:

1153
84615
581688
1511389
1913016
2504335
2698129
3280734
3828276
4617676
5487370
6476093
7401533
7968672
8034962
8260367
8840693
8951997
9947278
10197005
11078097
11663222
12233043
12656626
13500947
13506549
13572844
14311488
14594211
14902926
15891310
16536743
16803632
16897899
17837030
18507388
1...

result:

ok 250000 numbers

Test #131:

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

input:

68358
1 946748733890
2 741514091094
3 250813685504
4 773428901734
5 205041648548
6 976548472177
7 63080171135
8 31119100294
9 891203170764
10 284139467750
11 863829891505
12 387756675839
13 481809961987
14 958574610856
15 383651704810
16 417008418264
17 359023619819
18 636501097998
19 441322530204
2...

output:

946748733890
1688262824984
1939076510488
2712505412222
2917547060770
3894095532947
3957175704082
3988294804376
4879497975140
5163637442890
6027467334395
6415224010234
6897033972221
7855608583077
8239260287887
8656268706151
9015292325970
9651793423968
9788872800441
8871882069070
8249899222373
7294584...

result:

ok 250000 numbers

Test #132:

score: 0
Accepted
time: 349ms
memory: 32920kb

input:

68358
1 120796576046
2 869030462078
3 672345770497
4 157145624098
5 340608464395
6 645727526997
7 760534286518
8 398698676470
9 313261898455
10 632319941563
11 399999260451
12 356359159992
13 27955338053
14 228570943252
15 704929406376
16 735838118043
17 13198426472
18 12279964109
19 688558573046
20...

output:

120796576046
989827038124
1662172808621
1819318432719
2159926897114
2805654424111
3566188710629
3964887387099
4278149285554
4910469227117
5310468487568
5666827647560
5694782985613
5923353928865
6628283335241
7364121453284
7377319879756
7389599843865
8078158416911
9059316723607
10017927263386
1052066...

result:

ok 250000 numbers

Test #133:

score: 0
Accepted
time: 390ms
memory: 34728kb

input:

68358
1 254777
2 720401
3 492406
4 43975
5 235045
6 973389
7 907412
8 194260
9 644107
10 322257
11 754799
12 287632
13 781407
14 695152
15 155169
16 59972
17 667352
18 991501
19 547983
20 77462
21 797249
22 999130
23 734853
24 789280
25 217766
26 433817
27 260124
28 702341
29 474885
30 466609
31 184...

output:

158396186
112069437
267853016
254532092
99679886
27386431
340228362
268748989
420125765
360710920
116639594
91891762
33944777
136004086
297965259
250260019
109132633
388862894
50009886
394366426
117858471
283247984
299968864
315957682
189640203
349290146
100117205
319009655
98203356
214373743
361367...

result:

ok 250000 numbers

Test #134:

score: 0
Accepted
time: 408ms
memory: 34760kb

input:

68358
1 849318853981
2 961832519520
3 924411106576
4 603293139003
5 171643155554
6 716793239418
7 431814834820
8 954234533620
9 998201568629
10 765203181267
11 270650309396
12 764783109765
13 130313532463
14 646594381504
15 24856758126
16 40309208415
17 103434833141
18 801541072573
19 707694874349
2...

output:

398291278512
1651666387964
65508731385
2457143559127
927554577133
2240055793629
330337392946
780399496958
4052878223657
2754545162184
1178986555916
1411618899767
1385597611908
2832183783967
972184878015
2015845614975
2242321490230
992989209796
0
593916445769
400377030698
848488865996
941474777042
93...

result:

ok 250000 numbers

Test #135:

score: 0
Accepted
time: 361ms
memory: 34464kb

input:

68358
1 89596358871
2 797933368658
3 409622183028
4 903127483929
5 367644839965
6 322598265881
7 212710757621
8 350168164531
9 615989651025
10 209319764551
11 192103535290
12 634199687686
13 861112903286
14 207095461085
15 622733092309
16 348682067897
17 523973596087
18 718381834217
19 97201526808
2...

output:

70679376089882
63330895456551
64702037617627
220559210364988
196748515365955
152245333093861
157488418595819
144875424038600
17282609348554
50587363419888
79524338278687
149320818248184
115043833294541
50685699153869
192911413884720
37698496611314
80507594459417
31230959052759
68989135302390
6535240...

result:

ok 250000 numbers

Test #136:

score: 0
Accepted
time: 340ms
memory: 44996kb

input:

98004
1 135608
2 204549
2 433456
4 589244
4 37332
6 228497
6 371905
8 784057
8 981275
10 298098
10 310635
12 486661
12 939705
14 578235
14 664889
16 112606
16 264246
18 87417
18 773964
20 450477
20 867750
22 815966
22 386363
24 945230
24 759513
26 144351
26 261648
28 109273
28 25041
30 995958
30 511...

output:

28540174805
28539384446
28539072608
28538227769
28537301110
28536485909
28536060105
28535845660
28535777870
28535683134
28535163835
28534625012
28534414029
28533628097
28533224054
28532436959
28532249736
28532186791
28531511504
28531145579
28531047766
28530699489
28530282250
28529370215
28529086337
...

result:

ok 250000 numbers

Test #137:

score: 0
Accepted
time: 351ms
memory: 45224kb

input:

98004
1 827910121746
2 908903346014
2 156109185278
4 114896761987
4 903457580241
6 382873444401
6 261048420970
8 173394967662
8 120896027988
10 570990024505
10 78144886850
12 516516809815
12 736091141914
14 351815170863
14 281242541462
16 132581871806
16 512114904912
18 390670658631
18 251520039127
...

output:

0
347286969352
451643931018
1411841348147
1644685300598
2017754406667
2737827755184
3579251116948
4022986916442
4634281881767
4677433198568
5442274665081
5797363247164
6533182850979
7459628052075
8261131453501
8935096788665
8979485910251
9060934946595
10050765650316
10452320317449
10885559440954
117...

result:

ok 250000 numbers

Test #138:

score: 0
Accepted
time: 254ms
memory: 45084kb

input:

98004
1 415849524223
2 380537001512
2 657542022619
4 152814003904
4 550713715057
6 625731304879
6 171343452828
8 289228455973
8 832720936455
10 852656476465
10 48576462730
12 552682042927
12 238683384306
14 221497320430
14 413971095451
16 792392602575
16 38665733288
18 311741432140
18 21125802008
20...

output:

3122147330245512
3122339638923738
3123225982735542
3123314886343934
3124235042993715
3124780382848461
3125175055894000
3125246073071272
3125525947006157
3125807829838412
3126125060906784
3127112996950376
3127403655905550
3127495898659461
3127507963488293
3128215373094233
3128566431897488
31288575925...

result:

ok 250000 numbers

Test #139:

score: 0
Accepted
time: 340ms
memory: 46856kb

input:

98003
1 135608
2 204549
3 433456
4 589244
5 37332
6 228497
7 371905
8 784057
9 981275
10 298098
11 310635
12 486661
13 939705
14 578235
15 664889
16 112606
17 264246
18 87417
19 773964
20 450477
21 867750
22 815966
23 386363
24 945230
25 759513
26 144351
27 261648
28 109273
29 25041
30 995958
31 511...

output:

33796684630
33795908599
33795204796
33794468483
33794122290
33793859677
33793266682
33792367074
33792206910
33792200819
33791302547
33790411222
33789999654
33789903166
33789625528
33788985932
33788856655
33788311984
33787430180
33786790435
33785870519
33785633657
33784664964
33784200645
33783583182
...

result:

ok 250000 numbers

Test #140:

score: 0
Accepted
time: 344ms
memory: 47348kb

input:

98003
1 827910121746
2 908903346014
3 156109185278
4 114896761987
5 903457580241
6 382873444401
7 261048420970
8 173394967662
9 120896027988
10 570990024505
11 78144886850
12 516516809815
13 736091141914
14 351815170863
15 281242541462
16 132581871806
17 512114904912
18 390670658631
19 251520039127
...

output:

0
745624624766
1291922464084
1522322843082
1821440194509
2467767850035
2867448499447
3411354674853
3491486272562
4396044061522
5024821746802
5606949308536
5797513703814
6264939758411
6749620108457
6847978483087
7511105104466
8041573858756
8747038941851
9720749878538
9967833766912
10451823313299
1050...

result:

ok 250000 numbers

Test #141:

score: 0
Accepted
time: 243ms
memory: 46836kb

input:

98003
1 415849524223
2 380537001512
3 657542022619
4 152814003904
5 550713715057
6 625731304879
7 171343452828
8 289228455973
9 832720936455
10 852656476465
11 48576462730
12 552682042927
13 238683384306
14 221497320430
15 413971095451
16 792392602575
17 38665733288
18 311741432140
19 21125802008
20...

output:

2609815276403426
2609867209240849
2609897921181020
2610732843649306
2611596008377563
2612275874116813
2612885853834314
2612947043497925
2613277463647536
2613462161261675
2613464414670445
2613770842388565
2614001608768771
2614763269575624
2615005153490218
2615865430700173
2616255860670585
26164609272...

result:

ok 250000 numbers

Test #142:

score: 0
Accepted
time: 339ms
memory: 46556kb

input:

98003
1 135608
2 204549
3 433456
4 589244
5 37332
6 228497
7 371905
8 784057
9 981275
10 298098
11 310635
12 486661
13 939705
14 578235
15 664889
16 112606
17 264246
18 87417
19 773964
20 450477
21 867750
22 815966
23 386363
24 945230
25 759513
26 144351
27 261648
28 109273
29 25041
30 995958
31 511...

output:

35173886875
35173110844
35172407041
35171670728
35171324535
35171061922
35170468927
35169569319
35169409155
35169403064
35168504792
35167613467
35167201899
35167105411
35166827773
35166188177
35166058900
35165514229
35164632425
35163992680
35163072764
35162835902
35161867209
35161402890
35160785427
...

result:

ok 250000 numbers

Test #143:

score: 0
Accepted
time: 342ms
memory: 47096kb

input:

98003
1 827910121746
2 908903346014
3 156109185278
4 114896761987
5 903457580241
6 382873444401
7 261048420970
8 173394967662
9 120896027988
10 570990024505
11 78144886850
12 516516809815
13 736091141914
14 351815170863
15 281242541462
16 132581871806
17 512114904912
18 390670658631
19 251520039127
...

output:

0
745624624766
1291922464084
1522322843082
1821440194509
2467767850035
2867448499447
3411354674853
3491486272562
4396044061522
5024821746802
5606949308536
5797513703814
6264939758411
6749620108457
6847978483087
7511105104466
8041573858756
8747038941851
9720749878538
9967833766912
10451823313299
1050...

result:

ok 250000 numbers

Test #144:

score: 0
Accepted
time: 249ms
memory: 46604kb

input:

98003
1 415849524223
2 380537001512
3 657542022619
4 152814003904
5 550713715057
6 625731304879
7 171343452828
8 289228455973
9 832720936455
10 852656476465
11 48576462730
12 552682042927
13 238683384306
14 221497320430
15 413971095451
16 792392602575
17 38665733288
18 311741432140
19 21125802008
20...

output:

1473718875365646
1473770808203069
1473801520143240
1474636442611526
1475499607339783
1476179473079033
1476789452796534
1476850642460145
1477181062609756
1477365760223895
1477368013632665
1477674441350785
1477905207730991
1478666868537844
1478908752452438
1479769029662393
1480159459632805
14803645262...

result:

ok 250000 numbers