QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326157#8232. Yet Another Shortest Path QueryLynkcatAC ✓3247ms634204kbC++233.0kb2024-02-12 13:52:342024-02-12 13:52:34

Judging History

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

  • [2024-02-12 13:52:34]
  • 评测
  • 测评结果:AC
  • 用时:3247ms
  • 内存:634204kb
  • [2024-02-12 13:52:34]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e9
#define mod 998244353
#define sz(x) (int)((x).size())
// #define int ll
//#define N
using namespace std;
const int N=1000005;
int n,m,q,vis[N];
vector<pa>G[N],E[N];
int du[N],ans[N];
vector<pair<int,pa>>qr[N],cao[N];
int dfn[N],DFN,dis[N];
vector<pa>Qr[N];
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		G[x].push_back(mp(y,w));
		G[y].push_back(mp(x,w));
		du[x]++;
		du[y]++;
	}
	queue<int>qq;
	for (int i=1;i<=n;i++)
		if (du[i]<=5) qq.push(i);
	while (!qq.empty())
	{
		int u=qq.front();
		qq.pop();
		if (vis[u]) continue;
		// cout<<"vs "<<u<<endl;
		vis[u]=1;
		for (auto [y,w]:G[u])
			if (!vis[y])
			{
				E[u].push_back(mp(y,w));
				du[y]--;
				if (du[y]<=5) qq.push(y);
			}
	}
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		ans[i]=inf;
		for (auto [u,w]:E[x])
			if (u==y) ans[i]=min(ans[i],w);
		for (auto [u,w]:E[y])
			if (u==x) ans[i]=min(ans[i],w);
		//)xx
		for (auto [u,w]:E[x])
		{
			qr[u].push_back(mp(w,mp(i,y)));
			qr[y].push_back(mp(w,mp(i,u)));
			
			cao[u].push_back(mp(w,mp(i,y)));
			cao[y].push_back(mp(w,mp(i,u)));
		}
		//xx(
		for (auto [u,w]:E[y])
		{
			qr[u].push_back(mp(w,mp(i,x)));
			qr[x].push_back(mp(w,mp(i,u)));
			
			cao[u].push_back(mp(w,mp(i,x)));
			cao[x].push_back(mp(w,mp(i,u)));
		}
		//<x>
		Qr[x].push_back(mp(i,y));
		Qr[y].push_back(mp(i,x));	
		
		qr[y].push_back(mp(0,mp(i,x)));
		qr[x].push_back(mp(0,mp(i,y)));
	}
	
	for (int i=1;i<=n;i++)
	{
		++DFN;
		for (auto [u,w]:G[i])
		{
			for (auto [md,ww]:E[u])
				for (auto [v,www]:E[md])
				{
					if (dfn[v]!=DFN)
						dis[v]=w+ww+www,dfn[v]=DFN;
					else dis[v]=min(dis[v],w+ww+www);
				}
		}
		for (auto [id,x]:Qr[i])
			if (dfn[x]==DFN)
			{
				ans[id]=min(ans[id],dis[x]);
			}
	}
	for (int i=1;i<=n;i++)
	{
		++DFN;
		for (auto [u,w]:G[i])
		{
				for (auto [v,ww]:E[u])
				{
					if (dfn[v]!=DFN)
						dis[v]=w+ww,dfn[v]=DFN;
					else dis[v]=min(dis[v],w+ww);
				}
		}
		for (auto [w,u]:qr[i])
		{
			auto [id,x]=u;
			// cout<<i<<","<<x<<" "<<dis[x]<<"."<<dfn[x]<<"."<<DFN<<endl;
			if (dfn[x]==DFN)
			{
				ans[id]=min(ans[id],dis[x]+w);
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		++DFN;
		for (auto [v,w]:G[i])
		{
			if (dfn[v]!=DFN)
				dis[v]=w,dfn[v]=DFN;
			else dis[v]=min(dis[v],w);
		}
		for (auto [w,u]:cao[i])
		{
			auto [id,x]=u;
			// cout<<i<<","<<x<<" "<<dis[x]<<"."<<dfn[x]<<"."<<DFN<<endl;
			if (dfn[x]==DFN)
			{
				ans[id]=min(ans[id],dis[x]+w);
			}
		}
	}
	for (int i=1;i<=q;i++)
		if (ans[i]==inf) cout<<"-1\n";
		else cout<<ans[i]<<'\n';
				
	
}
/*
<*>
*/
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 9756kb

input:

6 9
1 2 4
2 3 6
3 6 5
6 5 3
5 4 2
4 1 3
3 4 9
1 3 100
5 3 1
5
1 3
1 6
3 4
3 5
2 5

output:

6
8
3
1
7

result:

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

Test #2:

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

input:

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

output:

3
-1
-1

result:

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

Test #3:

score: 0
Accepted
time: 889ms
memory: 393036kb

input:

40005 79608
1 2 70031203
1 3 99924845
1 4 61645659
1 5 9324967
2 3 15761918
3 4 62534796
4 5 35260314
5 2 35948540
6 2 23727405
6 7 83302920
7 3 31010426
7 8 75060393
8 4 94275932
8 9 99663793
9 5 81701979
9 6 439297
10 6 46955645
10 11 89514237
11 7 21257310
11 12 53896253
12 8 67933315
12 13 26161...

output:

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

result:

ok 1000000 numbers

Test #4:

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

input:

35479 70156
1 2 53094201
1 3 95796673
1 4 35585979
1 5 55612594
2 3 60766083
3 4 64392832
4 5 32896460
5 2 91649893
6 2 6196154
6 7 4986564
7 3 91799790
7 8 10909791
8 4 30034265
8 9 95672010
9 4 67004237
9 10 77872672
10 5 68900058
10 6 42927604
11 6 71288663
11 12 51597962
12 7 79690815
12 13 9742...

output:

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

result:

ok 1000000 numbers

Test #5:

score: 0
Accepted
time: 991ms
memory: 397920kb

input:

35811 70820
1 2 40434193
1 3 13483892
1 4 32864259
1 5 47591755
1 6 65123023
1 7 81695948
1 8 1102880
1 9 47223939
1 10 52947058
1 11 31439481
2 3 94162364
3 4 20590842
4 5 24137043
5 6 74926235
6 7 9376267
7 8 97130364
8 9 75568799
9 10 5022411
10 11 59066963
11 2 96177033
12 2 17823959
12 13 83906...

output:

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

result:

ok 1000000 numbers

Test #6:

score: 0
Accepted
time: 1058ms
memory: 248300kb

input:

200000 599952
127401 69434 88680591
127401 39916 10673559
127401 52475 59546013
127401 77787 74018113
127401 11462 7023970
60723 37187 65141305
60723 115008 72307785
60723 71812 47362248
60723 143858 20042617
60723 153890 48502784
60723 172009 21754689
60723 23327 97998405
63817 58332 30056889
63817...

output:

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

result:

ok 1000000 numbers

Test #7:

score: 0
Accepted
time: 1069ms
memory: 249832kb

input:

200000 599962
127401 36130 68347938
127401 56107 50001021
127401 35011 47850437
127401 166086 58628679
127401 167575 97121890
127401 150008 97636763
127401 148173 79875436
60723 38275 3780759
60723 75775 69051390
60723 93280 43415633
60723 108525 89666833
60723 119851 80916915
60723 134418 23881201
...

output:

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

result:

ok 1000000 numbers

Test #8:

score: 0
Accepted
time: 1032ms
memory: 248016kb

input:

200000 599957
127401 62215 44179748
127401 96198 78839479
127401 81659 96992357
127401 105920 13674618
127401 192829 54389653
60723 66329 69331527
60723 139474 14904280
60723 186870 86233097
60723 134036 31587848
60723 161658 81495543
60723 156381 83635122
60723 187612 77920441
60723 189714 55041890...

output:

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

result:

ok 1000000 numbers

Test #9:

score: 0
Accepted
time: 706ms
memory: 307976kb

input:

35011 70019
1 2 65752645
2 3 52997572
3 4 14100539
4 5 78562579
5 6 99655664
6 7 26904774
7 8 88411503
8 9 89420520
9 10 88149169
10 11 53207001
11 12 16506048
12 13 37143703
13 14 1295901
14 15 61139259
15 16 79880287
16 17 4390087
17 18 2733598
18 19 48969502
19 20 77562639
20 21 53171540
21 22 36...

output:

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

result:

ok 1000000 numbers

Test #10:

score: 0
Accepted
time: 654ms
memory: 274388kb

input:

50000 99997
1 2 5460409
2 3 95815999
3 4 17091945
4 5 91580749
5 6 91717493
6 7 55420828
7 8 10603109
8 9 62048169
9 10 28446542
10 11 38346952
11 12 66167473
12 13 80749600
13 14 20348320
14 15 5868535
15 16 45627426
16 17 2445360
17 18 21766361
18 19 20516369
19 20 8226530
20 21 86609482
21 22 134...

output:

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

result:

ok 1000000 numbers

Test #11:

score: 0
Accepted
time: 566ms
memory: 331648kb

input:

50000 99997
1 2 92917899
2 3 90125226
3 4 10806409
4 5 56452040
5 6 34960749
6 7 14085023
7 8 96350028
8 9 49181182
9 10 70920046
10 11 3727766
11 12 42039112
12 13 63921049
13 14 7634090
14 15 24597384
15 16 13087802
16 17 63136838
17 18 58806049
18 19 98769520
19 20 943620
20 21 70246129
21 22 145...

output:

53806372
101314854
124850165
38514625
96220435
122794730
84721400
112668433
107849606
160932332
116266392
101162529
140732651
93988737
87814230
71121316
72361729
54614389
95539309
119384111
95776872
109513557
60646451
142757728
61377855
40164780
49674827
71836734
15251469
135919057
66944724
83240312...

result:

ok 1000000 numbers

Test #12:

score: 0
Accepted
time: 627ms
memory: 271120kb

input:

47254 94505
1 2 66784117
2 3 20692517
3 4 98907287
4 5 41209476
5 6 7315104
6 7 98282771
7 8 64009902
8 9 85598965
9 10 9106474
10 11 43526655
11 12 86178462
12 13 61614372
13 14 27069126
14 15 79504944
15 16 86618089
16 17 67501242
17 18 46707561
18 19 78208083
19 20 17517466
20 21 71088132
21 22 4...

output:

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

result:

ok 1000000 numbers

Test #13:

score: 0
Accepted
time: 597ms
memory: 319880kb

input:

50000 99997
1 2 98934090
2 3 49958895
3 4 58253925
4 5 86958288
5 6 70023844
6 7 4574778
7 8 49968914
8 9 40118056
9 10 93722127
10 11 77674148
11 12 44589976
12 13 74650925
13 14 83434953
14 15 34825819
15 16 35073184
16 17 59460038
17 18 16371972
18 19 27840035
19 20 9921286
20 21 96569520
21 22 4...

output:

-1
-1
134038278
-1
83855508
-1
94630818
86426735
117282785
-1
-1
-1
109399438
-1
69917163
117201505
-1
213614655
73984801
66457361
130458925
-1
146183017
-1
-1
103976773
-1
140048318
-1
62379190
110100909
-1
-1
251950582
130937281
269193796
195833904
65545467
41245573
174339106
35843841
-1
225365426...

result:

ok 1000000 numbers

Test #14:

score: 0
Accepted
time: 639ms
memory: 269664kb

input:

50000 99997
1 2 17375119
2 3 31851662
3 4 8170046
4 5 23402169
5 6 16593634
6 7 67608438
7 8 2152560
8 9 39976586
9 10 69360624
10 11 65763420
11 12 79851569
12 13 83366479
13 14 73247163
14 15 79617102
15 16 51422981
16 17 8247209
17 18 53533672
18 19 5835039
19 20 9087828
20 21 78361404
21 22 1259...

output:

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

result:

ok 1000000 numbers

Test #15:

score: 0
Accepted
time: 622ms
memory: 322976kb

input:

50000 99997
1 2 5365249
2 3 3680840
3 4 78159884
4 5 47955436
5 6 79818314
6 7 28290681
7 8 40921438
8 9 24688692
9 10 51624528
10 11 91390229
11 12 85086584
12 13 54065610
13 14 63418526
14 15 68141823
15 16 34254175
16 17 40363485
17 18 25950162
18 19 72245968
19 20 33162092
20 21 66673294
21 22 9...

output:

-1
-1
-1
134550531
-1
-1
-1
-1
-1
120627184
-1
-1
61901139
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
124447122
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
166056372
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
211256959
-1
-1
-1
-1
-...

result:

ok 1000000 numbers

Test #16:

score: 0
Accepted
time: 625ms
memory: 330308kb

input:

50000 99997
1 2 35057961
2 3 18981482
3 4 95632037
4 5 86885314
5 6 25182878
6 7 72699727
7 8 20208774
8 9 59268387
9 10 95119664
10 11 62893530
11 12 48832042
12 13 68165768
13 14 40252493
14 15 62587376
15 16 36404114
16 17 93940727
17 18 73595432
18 19 16433752
19 20 63341507
20 21 10402200
21 22...

output:

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

result:

ok 1000000 numbers

Test #17:

score: 0
Accepted
time: 529ms
memory: 255960kb

input:

50000 99997
1 2 46544767
2 3 8243609
3 4 5601548
4 5 60479579
5 6 14824151
6 7 28422743
7 8 88933456
8 9 60953889
9 10 20751441
10 11 39806723
11 12 38344448
12 13 53972218
13 14 89573878
14 15 28259842
15 16 37315745
16 17 16482195
17 18 64455654
18 19 15699308
19 20 9371659
20 21 1596047
21 22 313...

output:

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

result:

ok 1000000 numbers

Test #18:

score: 0
Accepted
time: 1352ms
memory: 310784kb

input:

300000 524957
271965 75040 3707206
274807 129357 30958435
117116 83872 16523219
226906 176337 54622289
292180 129339 99517106
108353 68942 43859480
54225 298731 62385795
150951 54672 53188105
261944 206344 44581560
178510 222455 29849439
283315 31967 86418219
81867 95292 78675143
286216 196835 73299...

output:

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

result:

ok 1000000 numbers

Test #19:

score: 0
Accepted
time: 1788ms
memory: 353652kb

input:

300000 657723
161802 55990 96498214
248178 5906 52198569
139131 242589 66337226
65957 96980 34478261
31925 39409 37403752
235637 201318 97690264
158188 56254 33799900
155108 271456 76855577
102838 168675 95897185
274694 291785 8110654
75921 138401 57787947
60050 46287 4138252
265123 65590 4089049
15...

output:

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

result:

ok 1000000 numbers

Test #20:

score: 0
Accepted
time: 2110ms
memory: 429244kb

input:

300000 801130
214464 159995 67934277
182521 173435 11678060
160531 30598 61361564
196665 45590 26743754
68506 169799 12121538
286270 127382 14197098
80500 152479 65099496
135149 91239 63849742
172936 94297 4157559
14122 214829 20207488
226265 171183 81013564
247672 163157 15761538
236317 120486 9434...

output:

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

result:

ok 1000000 numbers

Test #21:

score: 0
Accepted
time: 2351ms
memory: 421992kb

input:

500000 1000000
322308 151883 41981834
371877 7480 32717482
270472 377550 56357209
416535 153234 19747242
23689 379024 7784618
495383 44618 98009139
17394 159574 28343603
463029 59196 18163336
320455 290842 55655680
342588 272632 6267757
339225 252031 51576918
189741 7120 61729667
65181 345004 572543...

output:

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

result:

ok 1000000 numbers

Test #22:

score: 0
Accepted
time: 2231ms
memory: 405764kb

input:

700000 1000000
248742 137886 89549312
207920 429979 53131919
696826 79879 17888996
384989 366416 65436832
602499 29942 48394982
293930 672547 27513017
304140 28727 64018302
14448 394511 24471898
697647 399928 83196041
544606 251065 20907345
690191 283041 27965421
177856 536041 48795144
108791 226512...

output:

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

result:

ok 1000000 numbers

Test #23:

score: 0
Accepted
time: 1965ms
memory: 344672kb

input:

1000000 1000000
578663 124353 7995133
132721 400591 20059202
220462 70088 48506217
789368 286805 88475136
288204 403116 74261982
490130 887941 31971506
946993 188504 83041769
57590 782693 46157861
432990 322877 72070959
701052 343251 50243750
711719 880366 69200369
700987 530907 14734093
248148 5986...

output:

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

result:

ok 1000000 numbers

Test #24:

score: 0
Accepted
time: 1685ms
memory: 490120kb

input:

500000 815736
350550 193402 47089706
274243 266891 2117695
319926 413649 58445547
113629 447095 2463200
209743 178418 67671305
5308 188781 24182018
345488 193389 56109858
69511 48860 50797455
416106 421661 10868315
247321 262272 39646360
491742 22470 99163427
82712 195423 70594072
304590 395296 4163...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
104097905
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
65103896
-1
-1
-1
-1
-1
-1
-1
-1
69288123
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000000 numbers

Test #25:

score: 0
Accepted
time: 1570ms
memory: 416420kb

input:

500000 805867
3742 226457 19851757
262760 411209 88710569
165612 6351 23613247
234564 302955 63950854
348965 411593 70515799
132321 233996 54275781
269514 342251 62064728
443887 130598 78416637
454282 140510 61518164
30309 468431 38148480
422932 459047 33460815
161220 55203 37962326
226455 284726 69...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
126305483
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000000 numbers

Test #26:

score: 0
Accepted
time: 1540ms
memory: 383272kb

input:

500000 802717
223326 79732 16507671
452135 265201 42612447
224825 407554 25278574
5607 407325 33180581
136519 368621 1958763
331509 220773 58941334
498528 482763 43504421
263084 178939 71500310
25399 233323 27156494
355707 19267 91304718
461846 250686 61990053
137377 234997 56476766
264243 128103 40...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
189253126
-1
-1
-1
-1
-1
-1
96508290
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
174199847
-1
-1
-1
43809030
-1
-1
107108446
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
74841683
165389830
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
59493247
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
90446058
-1...

result:

ok 1000000 numbers

Test #27:

score: 0
Accepted
time: 1357ms
memory: 371680kb

input:

500000 801337
305506 2398 52928883
117464 117635 76960148
121282 267421 66773902
376966 374202 69607752
345870 371883 53009862
375136 306364 79037634
446949 363954 29264507
369425 72233 64342517
334398 436962 27095774
493081 2398 78508275
164282 139452 96326681
455544 367913 20095817
27223 282416 57...

output:

-1
-1
-1
-1
-1
85148356
-1
-1
73848395
-1
-1
139940909
117539438
126029785
-1
-1
-1
-1
-1
-1
80772941
-1
178291282
-1
-1
136005979
154977897
-1
207652228
-1
-1
-1
-1
206959717
-1
201082182
-1
-1
115944891
180681055
-1
-1
-1
-1
-1
100177591
-1
-1
19932663
-1
99689799
-1
-1
-1
-1
-1
126210718
-1
-1
-1...

result:

ok 1000000 numbers

Test #28:

score: 0
Accepted
time: 2140ms
memory: 393896kb

input:

500000 809172
4396 427668 47269775
302084 273684 29437269
255380 167109 5365730
273684 405189 84252609
437707 413571 44375835
195183 418494 35495205
165100 221719 76976299
484384 487143 97837667
382365 24678 47896835
280441 273684 37504587
332483 351024 11660121
273917 244749 36146151
384770 416047 ...

output:

-1
-1
117379351
223548577
-1
-1
-1
-1
56704448
-1
149532285
-1
206010423
-1
-1
-1
-1
-1
-1
-1
-1
161523094
104721651
-1
-1
82326907
-1
180887541
-1
114595934
-1
-1
113025877
108900308
103797263
-1
164371433
-1
224395967
99997301
124572607
-1
-1
126101052
-1
-1
150566636
166958782
-1
-1
-1
-1
-1
1577...

result:

ok 1000000 numbers

Test #29:

score: 0
Accepted
time: 2056ms
memory: 389480kb

input:

500000 808857
91518 177989 97810071
324867 360905 22853894
47057 201786 95209433
9716 102481 97189086
104217 255926 96531273
570 330531 97934593
123308 166484 16947075
121419 392210 25784403
276228 438201 11531396
309126 123308 2329325
309314 123308 6051203
180189 87565 93993404
180899 180989 129061...

output:

-1
27776500
-1
34781555
-1
-1
41401692
36846565
29394166
-1
-1
-1
-1
54990138
55672215
-1
-1
33059398
73332846
47724403
-1
43897149
40257634
44663001
73414820
12311801
62368633
-1
-1
-1
-1
-1
41941276
-1
-1
-1
15972488
32187447
31562483
-1
45731955
33324483
-1
34844067
-1
45545942
-1
43067289
198625...

result:

ok 1000000 numbers

Test #30:

score: 0
Accepted
time: 1503ms
memory: 411616kb

input:

666666 1000000
102223 546500 15229387
361863 465483 17686384
490450 251077 29479777
456521 325924 538101
522212 251613 95356714
348942 95120 3859288
102223 61190 93363278
407267 319678 96027438
37263 448396 25995711
102223 561582 15489321
339093 528788 7622129
102223 655310 12140762
371554 455348 33...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
62627845
-1
-1
-1
-1
-1
71529176
-1
63614619
-1
-1
-1
-1
-1
-1
-1
37666709
-1
-1
53833820
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
62895924
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
47467243
-1
53420303
-1
-1
23957759
-1
-1
-1
-1
-1
-1
30745326
-1
-1
-1
73212232
-1
-1
-1
-1
-1
-1
...

result:

ok 1000000 numbers

Test #31:

score: 0
Accepted
time: 1496ms
memory: 410484kb

input:

666666 1000000
662548 559562 63714269
94 344814 74194798
77199 258954 69923936
458256 237574 18511098
220264 68 39124008
421322 91170 80072916
64663 510794 47014538
212452 658954 35260296
493760 565739 67557832
418557 603770 12189729
223243 503837 65776420
653138 83409 51608663
494999 393620 6307608...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
243389624
-1
203816706
-1
-1
-1
-1
153949507
21120640
214073271
-1
-1
-1
116346627
-1
-1
132720338
-1
-1
-1
-1
223722477
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
157176410
-1
149893849
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
134203297
-1
-1
-1
78717775
-1
-1
-1
-1
-1...

result:

ok 1000000 numbers

Test #32:

score: 0
Accepted
time: 1751ms
memory: 393628kb

input:

912345 1000000
559627 228187 78721861
68245 200332 69410410
329133 19660 25993615
242103 773215 16927161
30191 28043 43928851
603573 444179 98958352
773215 797469 83552202
403239 303014 9474098
114107 192405 21506963
840624 682149 57282628
393688 55896 18232778
817847 128772 26991686
38512 826367 87...

output:

189819324
-1
-1
-1
-1
-1
-1
-1
171301712
-1
-1
-1
-1
-1
89088956
-1
-1
76566947
-1
-1
-1
-1
-1
-1
-1
170591254
-1
-1
-1
-1
-1
-1
-1
-1
175960797
-1
-1
-1
-1
-1
-1
-1
-1
-1
120850012
-1
-1
-1
-1
-1
-1
181421284
-1
-1
-1
-1
-1
-1
-1
-1
-1
200319467
-1
-1
162385667
-1
-1
-1
-1
-1
-1
-1
-1
155194958
-1
...

result:

ok 1000000 numbers

Test #33:

score: 0
Accepted
time: 1784ms
memory: 393048kb

input:

912345 1000000
145350 495183 2829259
437503 532648 29303533
393216 372374 1281375
645953 187695 3870647
146316 259650 1309246
374193 145733 26191699
19553 18582 17913562
681213 328782 93303267
440729 306362 24535049
251382 185307 3419131
67381 140079 19644359
487668 19262 5839440
47697 351818 103182...

output:

-1
-1
49640252
-1
-1
-1
-1
-1
-1
72560261
-1
-1
-1
-1
-1
-1
-1
-1
-1
60458862
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
38783684
49956243
-1
64088983
-1
-1
32428959
-1
-1
-1
46738966
-1
-1
15302810
53350544
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
43714948
-1
-1
45088545
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000000 numbers

Test #34:

score: 0
Accepted
time: 1869ms
memory: 405644kb

input:

800000 1000000
616853 226681 92215826
750167 490096 7128077
645616 407550 28070634
517575 69415 15596538
154962 53230 11080996
401816 487707 29627334
314147 139414 24362315
195778 695425 96533764
470954 139882 28293033
114669 174160 26312544
12980 791345 25851503
464624 17338 90598222
235535 457059 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
58096313
-1
-1
-1
50100611
28126895
-1
-1
-1
-1
-1
-1
11938178
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
61832061
-1
-1
-1
29027441
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
18213553
-1
-1
-1
-1
-1
-1
-1
29810062
-1
59237919
-1
44960833
29494170
-1
27206363
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000000 numbers

Test #35:

score: 0
Accepted
time: 1443ms
memory: 393004kb

input:

1000000 1000000
89671 780863 5191336
122284 145764 701571
365232 387393 5639788
317333 439196 8575745
346455 792627 14404611
948933 199779 26604575
302340 413091 3871461
158642 37660 26280726
982636 130449 8746090
839219 531234 25874985
871570 492269 2295650
806549 498323 12275955
768618 248084 2344...

output:

-1
39257153
-1
-1
-1
-1
58748405
-1
-1
-1
-1
-1
47345429
44221916
42248585
-1
-1
-1
-1
-1
-1
-1
-1
34939578
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
27855015
-1
-1
-1
-1
-1
-1
50471194
-1
-1
-1
-1
64660230
-1
40395065
41563973
-1
-1
-1
61630034
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
285711...

result:

ok 1000000 numbers

Test #36:

score: 0
Accepted
time: 1004ms
memory: 356032kb

input:

1000000 1000000
747651 207443 7143696
184088 497671 25887361
899976 96144 21166915
462719 783653 4203782
779567 5310 12638528
93047 831376 28345802
33265 950936 27463940
847731 478264 1997983
259801 866711 14253662
808329 473314 16056423
571909 494301 17935521
142175 309255 5817228
572523 3558 72705...

output:

-1
-1
-1
-1
-1
-1
-1
-1
37190927
-1
68094325
-1
-1
-1
-1
-1
-1
-1
58965831
-1
-1
-1
-1
-1
-1
-1
-1
-1
42696595
-1
-1
-1
-1
-1
-1
-1
-1
-1
52049664
-1
-1
51575216
9411105
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
46338576
-1
-1
-1
-1
-1
-1
-1
-1
39548410
-1
-1
-1
-1
-1
-1
-1
44259218
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 1000000 numbers

Test #37:

score: 0
Accepted
time: 1886ms
memory: 350856kb

input:

500000 808701
395130 229657 90682667
325677 39134 16958153
39134 129402 3633693
107087 5826 99570790
60087 155360 94897854
412982 477761 91109239
5790 211508 14676692
162791 13470 90802624
297189 150750 97013318
275405 4058 96582456
335629 274907 24356315
104293 422336 5790759
367309 28293 6059442
4...

output:

-1
-1
-1
-1
38350627
22388077
36771827
-1
-1
-1
72262972
-1
-1
-1
-1
-1
-1
64937166
-1
-1
34368650
-1
41500337
-1
20581584
-1
-1
-1
-1
26222169
18952316
-1
-1
38100378
-1
56050653
-1
37733898
38462788
53135914
-1
-1
8769579
52054095
-1
44844264
-1
-1
-1
-1
-1
-1
33058764
-1
-1
-1
-1
101154810
-1
-1
...

result:

ok 1000000 numbers

Test #38:

score: 0
Accepted
time: 1439ms
memory: 395420kb

input:

666666 1000000
91342 506736 12679304
588643 533040 27548881
81433 453674 92232790
151297 424699 96095227
561790 91342 7437858
374495 442960 19549655
60044 336438 10437703
651731 470854 90768907
328966 351048 1480769
344646 179846 97959745
91342 406605 5796183
58574 510840 28377956
94704 656500 27859...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
56415603
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
57181736
-1
-1
33257552
-1
51773278
-1
-1
-1
32276711
28265494
-1
-1
-1
-1
-1
-1
-1
-1
33709431
-1
44321654
-1
-1
-1
-1
85478860
-1
-1
48203778
-1
46837327
-1
-1
55925728
-1
38183087
-1
-1
-1
-1
37382519
-1
49305044
-1
-1
-1
...

result:

ok 1000000 numbers

Test #39:

score: 0
Accepted
time: 1567ms
memory: 367728kb

input:

912345 1000000
529565 283838 17723323
15805 520317 24705466
205436 78548 6754490
544498 626311 4430637
655316 396138 17448241
235727 195100 16759630
802804 899439 27940238
138140 65774 15146741
462939 816492 99128852
153555 650674 706904
52474 76214 19296601
722532 573571 5978265
553555 195367 96374...

output:

-1
-1
57365705
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
49424556
-1
-1
-1
-1
-1
-1
-1
48375729
-1
-1
-1
-1
-1
-1
-1
-1
66279761
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
54730691
47758750
-1
-1
-1
-1
-1
-1
-1
-1
-1
37976035
-1
64814179
-1
22682165
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000000 numbers

Test #40:

score: 0
Accepted
time: 1571ms
memory: 377432kb

input:

800000 1000000
37101 107452 97642097
651155 437165 12547086
241683 754099 12337896
671975 595936 96948130
196319 459912 21387283
461158 788663 18046619
667334 543600 23309478
375645 183740 2864921
550837 283593 6655589
226300 616439 5050938
423372 89361 92214327
581345 5824 15120348
3899 9507 753030...

output:

-1
-1
38604190
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
47585395
-1
-1
-1
-1
-1
-1
-1
26514386
-1
-1
54076304
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
58776018
-1
50416863
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
64424670
-1
-1
-1
-1
-1
62605157
-1
48745019
-1
-1
...

result:

ok 1000000 numbers

Test #41:

score: 0
Accepted
time: 3247ms
memory: 634204kb

input:

326840 980514
91571 183644 94559522
130619 247880 97860634
83071 60114 92540306
317115 13100 91754440
79986 7632 95579623
171514 17161 90011882
34581 10591 90677204
137990 281041 93655441
185194 279893 95405801
286007 8545 91911925
23782 23666 93761819
91206 81825 90758869
179375 144184 93488757
141...

output:

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

result:

ok 1000000 numbers

Test #42:

score: 0
Accepted
time: 3230ms
memory: 632272kb

input:

327649 982941
291722 14095 95075847
39192 281311 99112192
188481 31321 93205327
101636 163724 92309406
242023 293769 99874897
264688 7259 99892967
192431 267557 92834640
79106 91207 97112632
18479 272736 92287648
44338 137180 91996183
279703 127542 97027305
211601 223675 98837468
32355 123680 942377...

output:

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

result:

ok 1000000 numbers

Test #43:

score: 0
Accepted
time: 3156ms
memory: 631152kb

input:

328459 985371
318077 169813 9670294
184716 221245 56731849
281729 114322 64023155
9562 181639 77764486
87185 294710 56243226
50806 256554 15288577
325005 320734 3573158
23749 88289 6983049
215129 126368 32348458
176135 150469 40929680
122752 97002 32136682
26507 205518 23701963
226632 255241 6221053...

output:

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

result:

ok 1000000 numbers

Test #44:

score: 0
Accepted
time: 3121ms
memory: 633612kb

input:

329270 987804
92819 80879 52644711
65780 23473 22441194
299008 54356 26143487
44292 177426 43411835
214145 72169 14195647
318375 176125 50215577
208080 139756 81187374
274596 74660 67060455
48294 321640 62256077
82645 32371 76345697
234889 255785 70661498
46886 224866 22943323
81712 171109 45143948
...

output:

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

result:

ok 1000000 numbers

Extra Test:

score: 0
Extra Test Passed