QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410458#8648. TowerRafi2243 1981ms128192kbC++143.4kb2024-05-14 02:00:392024-05-14 02:00:40

Judging History

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

  • [2024-05-14 02:00:40]
  • 评测
  • 测评结果:43
  • 用时:1981ms
  • 内存:128192kb
  • [2024-05-14 02:00:39]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=200007,pot=1<<20;

ll l[N],r[N];
vector<pair<ll,int>>Q[N];
ll mn[2*N],mx[2*N];
ll X[N];
ll d;

map<ll,int>id;

ll seg[2*pot+7];
void ins(int v,ll x)
{
	v+=pot-1;
	seg[v]=x;
	while(v>1)
	{
		v/=2;
		seg[v]=min(seg[2*v],seg[2*v+1]);
	}
}
ll que(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg[v];
	if(r<a||l>b) return infl;
	return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
ll seg1[2*pot+7];
void ins1(int v,ll x)
{
	v+=pot-1;
	seg1[v]=x;
	while(v>1)
	{
		v/=2;
		seg1[v]=max(seg1[2*v],seg1[2*v+1]);
	}
}
ll que1(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg1[v];
	if(r<a||l>b) return -infl;
	return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}

set<int>xd;

void del(int l,int r)
{
	while(true)
	{
		int i=*xd.lower_bound(l);
		if(i>r) break;
		ins(i,infl); 
		ins1(i,-infl); 
		xd.erase(i);
	}
}

void upd(int l,int r,int k,ll A,ll B,int a,int b)
{
	//cout<<l<<" "<<r<<" "<<k<<" "<<A<<" "<<B<<" "<<a<<" "<<b<<endl;
	mn[k]=min(mn[k],A+que(1,l,min(r,a),1,pot));
	mn[k]=min(mn[k],A+que(1,max(l,a+1),r,1,pot)-1);
	mx[k]=max(mx[k],B+que1(1,l,min(r,b),1,pot));
	mx[k]=max(mx[k],B+que1(1,max(l,b+1),r,1,pot)-1);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    ll a,b;
    cin>>n>>q>>d>>a>>b;
    vector<pair<ll,int>>V;
    set<ll>S;
    S.insert(0);
    for(int i=1;i<=n;i++)
    {
		cin>>l[i]>>r[i];
		S.insert(l[i]%d);
		S.insert(r[i]%d);
		S.insert((r[i]+1)%d);
		if(r[i]+1>=d) V.pb({r[i]+1-d,i});
	}
    for(int i=1;i<=n+q;i++)
    {
		mn[i]=infl;
		mx[i]=-infl;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>X[i];
		S.insert(X[i]%d);
		V.pb({X[i],i+n});
	}
	int it=0;
	for(auto x:S) id[x]=++it;
	sort(all(V));
	int j=0;
	for(auto [x,i]:V)
	{
		while(j<n&&x>r[j+1]) j++;
		if(j==n||x<l[j+1]) Q[j].pb({x,i});
	}
	r[0]=-1;
	xd.insert(inf);
	for(int i=1;i<2*pot;i++)
	{
		seg[i]=infl;
		seg1[i]=-infl;
	}
	for(int i=0;i<=n;i++)
	{
		if(i>0)
		{
			if(r[i]-l[i]+1>=d) del(1,it);
			else if(id[r[i]%d]>=id[l[i]%d]) del(id[l[i]%d],id[r[i]%d]);
			else
			{
				del(1,id[r[i]%d]);
				del(id[l[i]%d],it);
			}
			mn[i]++;
			mx[i]++;
		}
		ins(id[(r[i]+1)%d],mn[i]-(r[i]+1)/d);
		ins1(id[(r[i]+1)%d],mx[i]-(r[i]+1)/d);
		//cout<<"INS "<<id[(r[i]+1)%d]<<endl;
		xd.insert(id[(r[i]+1)%d]);

		for(auto [x,k]:Q[i])
		{
			//cout<<"AAA "<<id[x%d]<<endl;
			if(x-r[i]>=d) upd(1,it,k,r[i]/d+1,x/d,id[r[i]%d],id[x%d]);
			else if(id[(r[i]+1)%d]<=id[x%d]) upd(id[(r[i]+1)%d],id[x%d],k,r[i]/d+1,x/d,id[r[i]%d],id[x%d]);
			else
			{
				upd(id[(r[i]+1)%d],it,k,r[i]/d+1,x/d,id[r[i]%d],id[x%d]);
				upd(1,id[x%d],k,r[i]/d+1,x/d,id[r[i]%d],id[x%d]);
			}
			/*if(inside(r[j]+1,x,(r[i]+1)%d))
			{
				mn[k]=min(mn[k],mn[i]+(r[j]+1-(r[i]+1)+d-1)/d);
				mx[k]=max(mx[k],mx[i]+(x-(r[i]+1))/d);
			}*/
		}	
	}
	for(int i=1;i<=q;i++)
	{
		if(mn[n+i]>=infl/2) cout<<-1<<endl;
		else
		{
			ll w1=(X[i]-mn[n+i]*d)*a+b*mn[n+i];
			ll w2=(X[i]-mx[n+i]*d)*a+b*mx[n+i];
			cout<<min(w1,w2)<<endl;
		}
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 189ms
memory: 51668kb

input:

2000 200000
500 66309 387245
91 122
793 1029
1127 1131
1304 1611
2007 2039
2601 2701
2906 3052
3253 3263
3495 3609
4157 4225
4283 4283
4757 4766
4786 4847
4885 5086
5326 5342
5607 5750
5847 5877
6093 6230
6548 6793
7206 7308
7413 7419
7752 7780
8244 8410
8501 8515
9335 9447
9512 9514
9602 9906
10076...

output:

-1
-1
1545376776
-1
1355518146
-1
-1
1538578776
1124179254
736677313
275840218
-1
314646902
120181124
592802647
1470145222
1194355416
630012616
541479470
1380556431
748297307
1579324340
83071935
-1
547672724
766967273
940718126
967114418
448357717
-1
208077708
264694996
68332763
-1
699361243
1542138...

result:

ok 200000 lines

Test #2:

score: 5
Accepted
time: 195ms
memory: 51672kb

input:

2000 200000
500 45649 229891
123 232
663 994
1023 1041
1065 1065
1523 1542
1962 1983
2044 2066
2449 2453
2589 2591
2788 2810
3207 3418
3666 3685
3944 3945
4256 4320
4699 4706
4915 4950
5196 5207
5271 5545
5705 5707
5867 6034
6273 6328
6364 6380
6764 6787
6974 7007
7363 7365
7632 7648
7754 7924
7954 ...

output:

-1
-1
1044862158
349767467
-1
-1
-1
-1
534260754
853076992
514160380
514034955
-1
-1
680989150
557376047
-1
410302211
-1
-1
14156128
-1
-1
656642980
-1
335413929
465525211
1047741337
1007928386
-1
183280077
-1
842399625
553981561
-1
-1
486838795
823208939
597570650
68518820
-1
-1
36379839
-1
4959492...

result:

ok 200000 lines

Test #3:

score: 5
Accepted
time: 197ms
memory: 51768kb

input:

2000 200000
500 11 228852
288 470
648 922
1193 1288
1509 1516
1792 1915
2023 2061
2443 2477
2512 2693
2735 2860
3176 3196
3260 3363
3622 3658
3939 3988
4177 4223
4470 4541
4640 4789
4812 4850
5167 5246
5443 5594
5692 5804
5875 5982
6265 6286
6416 6609
6816 6833
6928 7130
7298 7305
7401 7403
7778 781...

output:

61754766
1843455
193255572
95486804
80338946
188441144
126474653
-1
119132183
159054071
107422913
158596895
105813337
-1
166163718
-1
165014783
-1
2988793
146889891
-1
75748618
-1
-1
-1
109483978
-1
112469548
163413919
67263527
170983140
128997679
168000122
-1
186380233
151702042
42025050
-1
1556077...

result:

ok 200000 lines

Test #4:

score: 5
Accepted
time: 182ms
memory: 51844kb

input:

2000 200000
500 123 507044
13 349
778 805
1289 1419
2069 2074
2126 2129
2299 2392
2629 2629
3035 3054
3171 3184
3225 3381
3967 4100
4222 4225
4432 4603
4741 4745
4972 5123
5239 5245
5412 5530
5737 5757
5859 6162
6286 6289
6452 6542
6820 6825
6940 6974
7327 7328
7686 7781
8122 8169
8499 8909
8957 896...

output:

23238378
-1
320316781
492915201
-1
118374346
-1
118865646
-1
27397189
413766267
33059543
89523552
84434908
75590808
178982529
452655813
119364449
76127495
-1
-1
296028030
320308540
475355659
-1
210903877
288320772
388500820
-1
149739573
428228318
-1
-1
-1
-1
478454749
-1
-1
-1
-1
268399317
-1
310981...

result:

ok 200000 lines

Test #5:

score: 5
Accepted
time: 185ms
memory: 51716kb

input:

2000 200000
500 367 183500
395 476
616 705
1068 1085
1392 1462
1898 2004
2105 2124
2266 2553
2678 2684
2845 2855
3145 3188
3497 3630
3705 3708
3857 3995
4221 4223
4405 4642
4724 4730
4993 5199
5224 5225
5325 5637
5722 5735
6111 6152
6322 6341
6464 6694
6764 6838
7013 7174
7249 7261
7423 7713
7803 78...

output:

-1
81789987
195275562
134586974
172718274
-1
77090919
-1
169680615
26763842
81273618
74582841
-1
-1
164912918
-1
45100263
25295842
5720062
138829861
-1
23310005
142354162
158449681
-1
43546018
5823556
-1
-1
-1
-1
125462620
-1
25779548
121436630
4706408
-1
-1
-1
87290583
-1
47107386
94590213
17249256...

result:

ok 200000 lines

Test #6:

score: 5
Accepted
time: 387ms
memory: 65276kb

input:

195716 197150
20 41515 610194
34 34
36 36
38 38
40 40
42 42
44 44
46 46
83 83
85 85
87 87
89 89
91 91
93 93
95 95
97 97
99 99
104 104
106 106
108 108
110 110
112 112
114 115
118 118
120 120
132 132
134 134
136 136
138 138
140 140
142 142
144 144
146 146
148 148
150 150
175 175
177 177
179 179
181 18...

output:

27145048833
-1
20311977145
5823894704
12611222982
10375331362
-1
4666825214
8294213599
7946746140
15043381651
12084461892
2564209663
-1
2889605968
30371230407
13809822492
10059353510
20452787039
-1
186985672
-1
-1
-1
14667164575
21798169916
2551478619
-1
2357959404
24230797781
5359696913
11480637002...

result:

ok 197150 lines

Test #7:

score: 5
Accepted
time: 384ms
memory: 65056kb

input:

194401 196154
20 81884 184176
27 27
29 29
31 31
33 33
35 35
37 37
39 39
41 41
43 43
45 45
103 106
110 110
114 115
119 119
121 121
123 123
125 126
128 128
130 130
132 132
135 135
137 137
170 171
173 173
175 175
179 179
181 181
183 184
186 186
203 203
205 205
207 207
210 210
212 212
214 214
216 216
22...

output:

-1
7397081928
2079536780
1740817712
7985105512
8791917840
-1
2108310564
3818312684
3403790452
-1
-1
7282843676
8094061364
8075949632
-1
4202973208
-1
5158569260
5191129360
-1
5769244224
-1
5536679820
7825620684
4417835300
10616377912
-1
7443886064
5554791552
7631714344
4169124128
10019841164
8876887...

result:

ok 196154 lines

Test #8:

score: 5
Accepted
time: 399ms
memory: 65480kb

input:

197806 197356
20 29644 637771
3 3
5 5
7 7
9 9
11 11
13 13
15 15
17 17
19 19
21 21
71 71
73 73
75 75
77 77
79 79
81 81
83 83
85 85
87 87
89 89
94 94
96 96
98 98
100 100
102 102
104 104
106 107
122 122
124 124
126 126
128 128
131 131
133 133
135 135
156 156
158 158
160 160
163 163
165 165
216 216
218 ...

output:

-1
16958900222
16962903862
-1
-1
30908851790
986967014
7741518462
14743639172
1812847470
-1
7369833863
26993152521
2971365427
-1
-1
-1
-1
26587991346
16925804768
2134704702
17196127075
-1
26659445339
29693622258
812738814
25306954578
27428620967
29707753999
13380005667
1927010073
9821528975
-1
86888...

result:

ok 197356 lines

Test #9:

score: 5
Accepted
time: 399ms
memory: 65532kb

input:

199268 195219
20 9959 224682
19 21
23 23
26 27
29 31
33 33
35 35
37 37
57 57
59 59
61 61
63 63
65 65
67 67
69 69
71 71
73 73
127 129
131 134
136 138
153 153
155 155
157 157
159 159
161 161
163 163
166 166
196 196
198 198
200 200
202 202
204 204
206 206
208 208
210 210
212 212
214 214
224 224
226 226...

output:

1405185734
2296959792
-1
4763754065
-1
7440241155
3592032994
9232017710
-1
2996088597
7328570009
8931662575
7527861716
8627630151
4396636490
4153239129
4674940842
7142306979
5741444947
-1
-1
203363729
5005824000
-1
5999988912
-1
10315869532
2347062895
-1
499028001
-1
6310540106
6132479839
6198718827...

result:

ok 195219 lines

Test #10:

score: 5
Accepted
time: 391ms
memory: 65000kb

input:

194139 191791
20 37198 743960
1 1
3 3
5 5
7 7
9 9
11 11
13 13
15 15
17 17
19 19
28 28
30 30
32 32
34 34
36 36
39 39
41 41
43 43
45 45
79 79
81 81
83 83
85 85
87 87
89 89
91 91
97 97
103 103
105 105
107 107
109 109
111 111
113 114
116 116
118 119
121 121
124 124
126 126
128 128
130 130
132 132
134 13...

output:

5683965994
30465347990
13469395800
-1
24426289888
-1
3251625972
32267925872
-1
28405583136
32475193128
-1
10144378174
29396203074
33933652312
20332203612
-1
-1
2572204502
10948710528
24839410876
15655745448
4906750982
18881853592
11878734924
10340783614
3981301940
15892771104
36311460066
7953527568
...

result:

ok 191791 lines

Test #11:

score: 5
Accepted
time: 233ms
memory: 61508kb

input:

200000 200000
1 58118 14529
100001 100001
100006 100006
100008 100008
100010 100010
100013 100013
100019 100019
100023 100023
100026 100026
100028 100028
100032 100032
100035 100035
100042 100042
100045 100045
100048 100048
100051 100051
100053 100053
100057 100057
100064 100064
100068 100068
100071...

output:

11521497
3864714
10184829
2411814
-1
13192332
3138264
-1
-1
11913780
13846137
10097655
-1
624747
-1
10620699
-1
9066096
4663809
377754
-1
5680839
842682
-1
-1
6508992
1612719
12974397
-1
7380732
-1
-1
-1
363225
-1
7235442
813333420
-1
1670835
-1
4925331
11187330
10315590
-1
-1
1336668
-1
-1
-1
11579...

result:

ok 200000 lines

Test #12:

score: 5
Accepted
time: 282ms
memory: 64736kb

input:

200000 200000
2 301112 823921
13 13
16 16
18 18
20 20
23 23
27 27
31 31
34 34
37 37
43 43
47 47
54 54
56 56
61 61
65 65
69 69
73 73
76 76
83 83
87 87
93 93
101 101
105 105
108 108
114 114
117 117
125 125
129 129
131 131
136 136
141 141
146 146
154 154
159 159
162 162
172 172
181 181
183 183
187 187
...

output:

-1
-1
-1
-1
266027349
237726146
13850227972
159857299
-1
185465042
-1
48505478
-1
-1
105567826
284884894
-1
-1
223004754
-1
-1
254237662
-1
-1
-1
333754351
320919046
-1
-1
-1
103539457
-1
-1
111732348
-1
-1
-1
-1
125613271
-1
7624151759
-1
89420289
-1
28681730
-1
-1
23663241042
-1
-1
-1
-1
174055882...

result:

ok 200000 lines

Test #13:

score: 5
Accepted
time: 286ms
memory: 64452kb

input:

200000 200000
3 29787 89361
4 4
8 9
13 13
17 18
20 21
23 23
28 28
33 33
35 36
38 39
44 44
48 49
56 57
59 60
62 62
65 65
67 68
75 75
83 83
92 93
99 100
106 107
109 109
112 112
116 117
119 119
128 128
131 131
137 137
140 140
142 143
146 146
153 153
155 155
162 162
165 166
170 170
172 172
177 177
182 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1727646
-1
774462
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
446805
-1
-1
-1
-1
-1
-1
-1
148935
-...

result:

ok 200000 lines

Test #14:

score: 5
Accepted
time: 654ms
memory: 76916kb

input:

200000 200000
100000 1 167528
29806 29806
29808 29809
29812 29812
29814 29814
29816 29816
29822 29822
29825 29827
29829 29833
29835 29835
29847 29848
29852 29853
29856 29857
29859 29860
29864 29864
29867 29867
29870 29870
29872 29875
29879 29879
29882 29883
29885 29885
29891 29891
29893 29901
29903 ...

output:

-1
1006360
1440905
385
-1
352
509
655939
818
616
192147
14845
-1
619
-1
1293669
719
889
173180
777
949
261
209851
419
387955
1280628
417
868984
-1
809
-1
56
-1
1451072
-1
572
505
218
419794
1081185
815543
-1
663
-1
583
-1
408164
191620
393843
889671
896314
171
95
827257
1255818
779
82
-1
-1
280
7792...

result:

ok 200000 lines

Test #15:

score: 5
Accepted
time: 779ms
memory: 128192kb

input:

200000 200000
1000000 1860 149443
100003 100003
100005 100005
100007 100008
100010 100013
100018 100019
100021 100022
100024 100026
100029 100031
100033 100033
100035 100040
100045 100045
100048 100048
100050 100050
100052 100053
100055 100058
100060 100060
100064 100065
100067 100068
100070 100070
...

output:

1244340
-1
-1
-1
783060
-1
-1
1757700
-1
-1
1523340
851880
61275840
-1
390600
-1
1716780
846300
1002540
1575420
-1
72540
-1
-1
466860
-1
-1
598920
1275960
-1
1088100
137911560
123182220
1192260
-1
998820
624960
673320
-1
1752120
-1
120900
1791180
1075080
-1
1655400
130200
1091820
-1
-1
1097400
-1
-1...

result:

ok 200000 lines

Test #16:

score: 5
Accepted
time: 762ms
memory: 128152kb

input:

200000 200000
1000000000000 75183 634442
100000 100002
100004 100006
100011 100011
100013 100016
100020 100021
100023 100026
100028 100030
100034 100034
100039 100041
100044 100045
100048 100051
100056 100058
100060 100060
100063 100064
100066 100068
100071 100072
100076 100079
100081 100082
100085 ...

output:

-1
-1
-1
62777805
-1
6156510321
6691287
-1
-1
38192964
56687982
68717262
21803070
-1
-1
70145739
11803731
-1
20073861
-1
-1
5868559431
-1
27667344
-1
-1
16465077
-1
-1
-1
71499033
65709942
61800426
-1
-1
51274806
-1
-1
2510811468
-1
-1
56838348
8420496
12330012
-1
65334027
-1
-1
67138419
-1
-1
72100...

result:

ok 200000 lines

Test #17:

score: 5
Accepted
time: 150ms
memory: 52796kb

input:

1 200000
1 1 1
999999 999999
999995
334480
887900
420867
999997
878684
1000000
876358
618747
239631
999996
1000000
780417
875263
688426
700188
2
999996
494065
575102
601330
999993
209409
796732
580329
463096
862473
536243
716601
999992
307942
868274
999996
662241
390192
6
746933
999990
3
751307
8247...

output:

999995
334480
887900
420867
999997
878684
-1
876358
618747
239631
999996
-1
780417
875263
688426
700188
2
999996
494065
575102
601330
999993
209409
796732
580329
463096
862473
536243
716601
999992
307942
868274
999996
662241
390192
6
746933
999990
3
751307
824702
-1
224547
999995
416477
-1
944107
9
...

result:

ok 200000 lines

Test #18:

score: 5
Accepted
time: 156ms
memory: 52904kb

input:

1 200000
1 1000000 1
999999 999999
261223
999990
660671
999991
686540
999995
481082
6
9
210190
975680
999996
999995
999997
10
494817
999990
999998
893404
999998
289929
999991
197231
999996
22235
2
835177
999998
4
801369
520076
1000000
279802
10
287199
216013
647644
625195
999994
454938
155991
282147...

output:

261223
999990
660671
999991
686540
999995
481082
6
9
210190
975680
999996
999995
999997
10
494817
999990
999998
893404
999998
289929
999991
197231
999996
22235
2
835177
999998
4
801369
520076
-1
279802
10
287199
216013
647644
625195
999994
454938
155991
282147
152171
839255
885000
973358
940109
4748...

result:

ok 200000 lines

Test #19:

score: 5
Accepted
time: 165ms
memory: 51380kb

input:

1 200000
1 1 1000000
999999 999999
922791
999998
777168
997973
999999
999990
5
999994
549792
7
994306
999996
277953
686651
2
2
999995
6
50142
4
66529
7
463529
999990
10
528627
765208
266964
8
92765
999991
999994
103982
703958
999990
994373
999992
695826
168004
463044
999998
3
385692
486278
564796
1
...

output:

922791
999998
777168
997973
-1
999990
5
999994
549792
7
994306
999996
277953
686651
2
2
999995
6
50142
4
66529
7
463529
999990
10
528627
765208
266964
8
92765
999991
999994
103982
703958
999990
994373
999992
695826
168004
463044
999998
3
385692
486278
564796
1
2
6
209259
436231
938452
4
5
999990
7
8...

result:

ok 200000 lines

Test #20:

score: 5
Accepted
time: 164ms
memory: 52472kb

input:

1 200000
1 1000000 1000000
999999 999999
480704
4610
969413
5
999990
6
999997
120849
4
999992
526100
916996
7
42823
7
994464
899291
125047
446789
308053
545643
379966
1
7
748119
944339
8
999990
3
777027
999994
999990
999990
999996
999998
762900
452898
858332
986471
1
3
448913
999995
7
999993
992420
...

output:

480704000000
4610000000
969413000000
5000000
999990000000
6000000
999997000000
120849000000
4000000
999992000000
526100000000
916996000000
7000000
42823000000
7000000
994464000000
899291000000
125047000000
446789000000
308053000000
545643000000
379966000000
1000000
7000000
748119000000
944339000000
...

result:

ok 200000 lines

Test #21:

score: 5
Accepted
time: 242ms
memory: 61892kb

input:

1 200000
1000000 1 1
999999 999999
4
399947
736915
1
447669
1000000
259362
52351
6
813992
147272
863459
999992
7
999997
1
809636
999999
9
986388
999993
430094
2
782151
607157
45682
167704
765797
408410
999996
783731
540374
8
6
4
1000000
4
999995
8
512519
320711
999992
228605
999995
745015
8
4
521329...

output:

4
399947
736915
1
447669
1
259362
52351
6
813992
147272
863459
999992
7
999997
1
809636
-1
9
986388
999993
430094
2
782151
607157
45682
167704
765797
408410
999996
783731
540374
8
6
4
1
4
999995
8
512519
320711
999992
228605
999995
745015
8
4
521329
7
129519
964131
187402
112914
9
480716
665911
9395...

result:

ok 200000 lines

Test #22:

score: 5
Accepted
time: 240ms
memory: 61880kb

input:

1 200000
1000000 1000000 1
999999 999999
5
201390
999992
752699
10
5
1000000
455223
694001
999996
999997
999997
914856
702530
272565
4
458638
999997
799551
7
999990
7
218054
2
250231
999997
1
138997
10
693753
4
275706
623774
10
321139
8
26866
121967
5
999993
315765
228884
311503
251989
3
737033
5315...

output:

5000000
201390000000
999992000000
752699000000
10000000
5000000
1
455223000000
694001000000
999996000000
999997000000
999997000000
914856000000
702530000000
272565000000
4000000
458638000000
999997000000
799551000000
7000000
999990000000
7000000
218054000000
2000000
250231000000
999997000000
1000000...

result:

ok 200000 lines

Test #23:

score: 5
Accepted
time: 247ms
memory: 61808kb

input:

1 200000
1000000 1 1000000
999999 999999
397566
714299
999992
595860
999997
2
191908
10
5
562337
903315
6
1
10
796224
8
594507
999997
690529
856723
48324
999999
786610
2
3
999992
958713
332059
233195
999995
5
65197
6
999992
754507
663503
13009
581668
216612
653317
510740
13809
653724
999994
6
783667...

output:

397566
714299
999992
595860
999997
2
191908
10
5
562337
903315
6
1
10
796224
8
594507
999997
690529
856723
48324
-1
786610
2
3
999992
958713
332059
233195
999995
5
65197
6
999992
754507
663503
13009
581668
216612
653317
510740
13809
653724
999994
6
783667
1000000
999990
-1
733191
999995
929153
9
484...

result:

ok 200000 lines

Test #24:

score: 5
Accepted
time: 255ms
memory: 61932kb

input:

1 200000
1000000 1000000 1000000
999999 999999
858950
1
5
999993
999999
472917
999992
524703
8
62720
616928
2
453573
924939
10
164592
763671
999995
53019
124724
728051
999999
5
7
58104
6
2
886022
74483
999990
1
999996
1000000
614281
958044
570103
238595
6
551138
999991
846608
799139
922508
6
999994
...

output:

858950000000
1000000
5000000
999993000000
-1
472917000000
999992000000
524703000000
8000000
62720000000
616928000000
2000000
453573000000
924939000000
10000000
164592000000
763671000000
999995000000
53019000000
124724000000
728051000000
-1
5000000
7000000
58104000000
6000000
2000000
886022000000
744...

result:

ok 200000 lines

Test #25:

score: 5
Accepted
time: 258ms
memory: 61840kb

input:

1 200000
1000000000000 1 1
999999 999999
999990
181070
850132
6
679579
705538
7
592384
395357
865806
999995
3
999999
347161
9
6
999992
8
360528
1
2
999995
999992
40876
466962
27108
662634
10
8
999996
387926
999997
912352
437299
999994
1000000
999996
999994
999995
3
999997
955868
7
461068
2
245958
99...

output:

999990
181070
850132
6
679579
705538
7
592384
395357
865806
999995
3
-1
347161
9
6
999992
8
360528
1
2
999995
999992
40876
466962
27108
662634
10
8
999996
387926
999997
912352
437299
999994
-1
999996
999994
999995
3
999997
955868
7
461068
2
245958
999991
4
235714
7
999995
909848
7
678849
999994
5
35...

result:

ok 200000 lines

Test #26:

score: 5
Accepted
time: 250ms
memory: 61704kb

input:

1 200000
1000000000000 1000000 1
999999 999999
999999
98142
614960
1
896987
999992
5
873172
999997
686921
882660
710605
542929
2
953123
1000000
340814
722148
5
35758
8
5
307994
658223
999997
8
444255
2
5
910389
999998
576597
7
6
999996
676990
999990
692843
999998
8
2
560138
184038
78689
4849
908023
...

output:

-1
98142000000
614960000000
1000000
896987000000
999992000000
5000000
873172000000
999997000000
686921000000
882660000000
710605000000
542929000000
2000000
953123000000
-1
340814000000
722148000000
5000000
35758000000
8000000
5000000
307994000000
658223000000
999997000000
8000000
444255000000
200000...

result:

ok 200000 lines

Test #27:

score: 5
Accepted
time: 241ms
memory: 61740kb

input:

1 200000
1000000000000 1 1000000
999999 999999
212412
999996
319493
7
208889
999995
10
951178
999999
10
999994
1000000
329956
249701
770805
232184
7
7
862340
5
999998
4
999994
173822
626090
522620
315027
9
3
10
999994
721016
7
10
4
520616
999990
659325
109033
9
999997
10
987068
5
677651
984607
5
999...

output:

212412
999996
319493
7
208889
999995
10
951178
-1
10
999994
-1
329956
249701
770805
232184
7
7
862340
5
999998
4
999994
173822
626090
522620
315027
9
3
10
999994
721016
7
10
4
520616
999990
659325
109033
9
999997
10
987068
5
677651
984607
5
999990
720823
298733
999997
10
999998
481575
144004
833831
...

result:

ok 200000 lines

Test #28:

score: 5
Accepted
time: 236ms
memory: 61732kb

input:

1 200000
1000000000000 1000000 1000000
999999 999999
701915
275155
6
999997
872219
999999
977750
1000000
896614
999997
999996
999997
765121
999993
260229
999992
671681
999991
999996
999993
655970
9
252271
5
9
400099
204315
656036
999992
455708
10
252533
109626
125883
999993
627105
999992
781243
4
14...

output:

701915000000
275155000000
6000000
999997000000
872219000000
-1
977750000000
-1
896614000000
999997000000
999996000000
999997000000
765121000000
999993000000
260229000000
999992000000
671681000000
999991000000
999996000000
999993000000
655970000000
9000000
252271000000
5000000
9000000
400099000000
20...

result:

ok 200000 lines

Subtask #2:

score: 38
Accepted

Test #29:

score: 38
Accepted
time: 11ms
memory: 42064kb

input:

1938 1960
999999 47694 9291
2883622 3085639
3674880 3745876
9982198101 9982517489
19960889157 19960925795
19962228551 19962276101
19964301694 19964730442
19964826417 19965369252
19965984922 19966442459
19968019821 19968213820
19968334967 19968392242
19968426638 19968840337
19969017519 19969109591
19...

output:

2629532778036
1625568767553
-1
-1
-1
931487890158
217249154424
-1
3376854733974
453288498306
1144114552242
194772660096
116508067359
1965611506731
2806098123096
3404924462019
1737385084617
1649786307423
-1
3043407203193
2248403158668
-1
-1
538903132932
2740777563264
-1
3173320399527
-1
-1
2616652920...

result:

ok 1960 lines

Test #30:

score: 38
Accepted
time: 14ms
memory: 44056kb

input:

1837 1989
999999 41963 54422
9980315942 9981214568
9981614247 9981843710
9982430252 9982433585
9983182843 9983561789
9984404759 9984499318
9984655332 9984859904
9985420428 9985717345
9985762820 9985867258
9986396224 9986498679
9986533284 9986947589
9987502488 9988096750
9989096806 9989207060
9989676...

output:

-1
2554711024271
-1
977926019067
3238028322568
201257084557
-1
3205448836431
387280383252
-1
-1
-1
1216454626736
823964810173
117884656882
2669122054316
734561443433
1448900485845
3203724783289
796733108264
883217412007
-1
-1
147443422287
2027763666999
2378863303928
-1
-1
3091310739595
2261110540233...

result:

ok 1989 lines

Test #31:

score: 38
Accepted
time: 17ms
memory: 42592kb

input:

1985 1968
999999 1 1000000
9978505229 9979247763
9979301501 9979397117
9981449577 9981533536
9981765886 9982271507
9983158890 9983349521
9983843213 9984416208
9985032631 9985197994
9987158017 9987185683
9987259105 9988030168
9988487256 9988529335
9988581372 9988946469
9989439295 9989530721
998958116...

output:

-1
-1
700140493470
-1
489978355522
300086770672
-1
559982430287
130003223151
640114158260
450000487914
740106557204
29952519876
-1
240105075210
350026198844
170023233424
-1
700129344373
559996047761
29958778074
-1
519963146983
489976670882
610079022591
80061443986
479963278603
39959493320
1399929819...

result:

ok 1968 lines

Test #32:

score: 38
Accepted
time: 7ms
memory: 43976kb

input:

1879 1909
999999 1 1000000
460689 754731
2693364 2905962
3319681 3325104
3801465 3977535
4035457 4085070
5277090 5364349
9984311172 9984412612
9985376085 9985569458
9987260530 9987358997
19966359490 19966462743
19967267902 19967747838
19968440841 19968684937
19968871698 19969057992
19969415495 19969...

output:

479861899804
479818936396
-1
819788300403
669700939937
80006774552
-1
769777335986
869739454474
619739632941
509845128160
269956484712
919935604516
269952659247
399861650164
879829770503
40026405880
-1
-1
809756094408
130027392164
-1
449835037240
-1
190003318228
-1
30001962211
499837013487
300212407...

result:

ok 1909 lines

Test #33:

score: 38
Accepted
time: 13ms
memory: 42912kb

input:

1940 1824
999999 1 999999
9978317553 9978682456
9978688516 9978878611
9978916901 9978998453
9979512428 9980182210
9982686148 9982981767
9983520680 9984134501
9987258775 9987376861
9990965623 9991023044
9993014239 9993353245
9993498632 9993507872
9994237367 9994421501
9995634031 9996033703
9996546527...

output:

110138183242
539977719961
290029467104
200095116550
749939262424
529972467394
-1
-1
780021180799
749957388309
60012891726
-1
110139276095
860055290897
749957559179
699950438736
300066809495
-1
260070941533
230083391036
300028601356
-1
370090142336
100123227398
749913884611
100065909438
230087376207
...

result:

ok 1824 lines

Test #34:

score: 38
Accepted
time: 10ms
memory: 42200kb

input:

2000 2000
2000 72242 918440
3502 3628
3917 4295
4835 6269
8954 9053
9391 9498
9539 10488
12030 12437
12939 13001
14484 14661
21293 22714
23496 23948
24054 24123
24442 24452
25204 25888
25990 26335
27891 29357
30247 30614
32576 32787
34652 34700
34808 35396
35720 35728
35747 35836
39325 39535
40111 4...

output:

-1
-1
-1
41331109907612
-1
-1
-1
-1
-1
-1
41331302679640
-1
-1
105623453414058
-1
64292666451688
-1
146954757408300
-1
40888972
27554456283342
-1
-1
-1
41331123604136
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
41331120817986
114808753616582
-1
-1
-1
78069463962690
78069497678998
-1
-1
229...

result:

ok 2000 lines

Test #35:

score: 38
Accepted
time: 11ms
memory: 41908kb

input:

2000 2000
2000 230 625018
277 787
895 1341
2149 3435
4136 4488
4642 5289
6460 6507
6514 7706
8903 9587
15877 16228
17893 18664
19210 20608
20764 21133
21815 22730
23907 24807
24879 25004
28142 28157
28639 28653
29234 29479
31122 31898
33500 33856
19999942795 19999943136
19999943507 19999943865
19999...

output:

25299964891184
-1
-1
73599989788774
-1
-1
-1
-1
-1
20699961474702
-1
-1
-1
-1
59799962174496
55199932107284
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
59799964050362
-1
-1
-1
-1
66699981671922
-1
-1
73599990803994
-1
27599955499472
-1
-1
-1
-1
55199944607118
-1
-1
22999956186730
78199996059730
-1
-1
-1
...

result:

ok 2000 lines

Test #36:

score: 38
Accepted
time: 7ms
memory: 42672kb

input:

2000 2000
2000 295 590000
3810 4650
5193 5314
6077 6161
7589 7846
9999962966 9999963017
9999965179 9999966334
9999969386 9999970813
19999926448 19999926573
19999927152 19999927755
19999929100 19999929729
19999930809 19999931622
19999932990 19999933019
19999933778 19999933917
19999934040 19999934345
...

output:

-1
-1
-1
61950044019900
29500018664060
-1
41300037658225
85550042906275
-1
-1
-1
-1
103250043467365
-1
103250032668890
-1
23600030858180
-1
-1
23600022766920
-1
-1
-1
-1
-1
-1
-1
64900035295275
-1
-1
76700043064985
-1
-1
-1
-1
-1
-1
-1
-1
76700014152035
-1
-1
-1
-1
-1
-1
73750024285580
-1
-1
-1
-1
5...

result:

ok 2000 lines

Test #37:

score: 38
Accepted
time: 7ms
memory: 42108kb

input:

2000 2000
1000000000 84022 860353
1569988396 1685009448
1782896103 2023925423
2743748189 3201999434
3348913628 3486693274
3586050490 3600384245
3829423794 3993187865
4079023827 4145323681
4801555373 5508268361
5580494464 5597647672
5662434819 6078038246
6113079134 6228562717
6277774595 6513373409
66...

output:

1699551771303243
-1
-1
-1
1077130449787194
-1
-1
-1
4213960752006101
-1
-1
3907605594392520
3462208157256638
-1
-1
-1
436818127827278
140063800902968
733152710849402
1524830249781496
-1
140199939796929
-1
3767755882701727
-1
-1
3219254988971477
-1
-1
3791754131769005
3787309355033107
216604035661138...

result:

ok 2000 lines

Test #38:

score: 38
Accepted
time: 11ms
memory: 42436kb

input:

2000 2000
1000000000 73351 798016
5379164 85948628
152114738 186910996
216089947 296297297
320601651 498439329
749737863 883048527
1017428051 1215354384
1500998319 1851811527
2035869094 2196064026
2289057708 2373716965
2419663795 2455077575
2600831714 2796612190
3737756045 3765767374
3963896915 4138...

output:

1352392662585144
-1
-1
275619944941055
494581361210771
-1
1906283000186755
-1
-1
631672883910142
2000127534373511
1067186609237468
2744520683341053
2587495002252512
-1
1150027859519700
2191930206191286
-1
2364534538759850
-1
-1
2319174164915293
-1
3122071296236563
-1
2707809817429526
150118726886524...

result:

ok 2000 lines

Test #39:

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

input:

2000 2000
1 11621 8066
100201834835 100201834835
100258958238 100258958238
100281167128 100281167128
100429123403 100429123403
100989550866 100989550866
101166447769 101166447769
102684659624 102684659624
102808801085 102808801085
102981197474 102981197474
103001829421 103001829421
103037865521 1030...

output:

-1
482407665890812
-1
-1
723597354250222
-1
-1
-1
-1
-1
-1
-1
634158842204382
-1
767149223586088
-1
320742329546098
313907157146068
442988049072114
400535162863556
-1
578773630434064
-1
690693072960138
433934921909614
781396623802876
599823436022858
169766199217980
119517605193712
548419539744340
-1...

result:

ok 2000 lines

Test #40:

score: 38
Accepted
time: 8ms
memory: 43108kb

input:

2000 2000
2 32886 78704
204643836 204643836
1113623028 1113623028
1135646654 1135646654
1959997357 1959997357
2040819163 2040819163
2061775595 2061775595
2464113849 2464113849
3478319937 3478319937
3779559895 3779559895
3849318319 3849318319
3959865089 3959865089
5012240362 5012240362
5588017105 558...

output:

2605361503242182
2620518620132540
-1
312761570833468
896240997173292
2686095482500068
1236321842423432
363842065334418
263528977919424
2485121231037864
1249828393110782
1562748331364332
2421388383381086
-1
-1
-1
-1
-1
-1
-1
686077868878886
1746971073564236
-1
-1
-1
966005157875456
2077496417864340
1...

result:

ok 2000 lines

Test #41:

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

input:

2000 2000
3 308586 925758
229941318 229941319
810862719 810862720
1381846176 1381846177
1967227686 1967227687
2176874215 2176874216
2860203229 2860203229
3449456731 3449456732
3511222605 3511222606
3734211059 3734211060
4013508856 4013508857
4662500353 4662500354
4698830876 4698830876
5193812601 519...

output:

629433234541116
11214604732761558
-1
683088725581566
-1
23919958255515348
2601147932894166
29865833510728218
26650435163928468
-1
-1
-1
8366307952517844
-1
18808177136118366
26539226966243934
5466347690884932
11182192870993692
19699683523191750
18937036704809076
-1
-1
-1
10491593943203292
9296394537...

result:

ok 2000 lines

Test #42:

score: 38
Accepted
time: 8ms
memory: 42804kb

input:

2000 2000
1000000000000 98903 356584
100068122467 100323582946
101034122653 101037471983
101192671139 101417983373
101752751591 102138275674
102743548699 102997923214
103040734538 103215955014
103257686114 103679787488
103779917169 103810888674
104044408487 104086239085
104254838840 104683673158
104...

output:

4881267912001978
758081698558947
-1
-1
2299457562076388
-1
6225377721117954
-1
-1
9313806889712353
374853586984842
-1
-1
5514185530543543
-1
2339590367909865
-1
-1
-1
-1
3794542741845079
-1
-1
-1
-1
-1
-1
4294906976234245
-1
2980394495846950
266788141953585
370001816054486
-1
1210592068888405
987787...

result:

ok 2000 lines

Test #43:

score: 38
Accepted
time: 11ms
memory: 43036kb

input:

2000 2000
1000000000000 56232 838675
100081867458 100242549128
101925831793 101996793761
102278462889 102363135838
102609220006 102653402499
102871255176 103007518598
103011266371 103308640763
103332053476 103370250699
103408334823 103732853154
103742708168 103829810047
104116698365 104427911390
104...

output:

-1
879346853108064
-1
-1
1346153229476352
1977095062998000
-1
2522316962185416
-1
2541388335030072
3662470967464584
2881580180742648
-1
-1
-1
-1
1783397370313152
-1
89495784869040
5233202865706464
2299192313090904
-1
-1
-1
4499236901922048
1906943270738616
-1
3108715042358376
2291198847693624
-1
-1
...

result:

ok 2000 lines

Subtask #3:

score: 0
Time Limit Exceeded

Test #44:

score: 25
Accepted
time: 1903ms
memory: 125304kb

input:

198085 196577
999999 1 999999
562622 895604
1799586 1975565
2518299 2941986
4934097 5403130
5755102 5996130
6036200 6112534
6391882 6431514
6451793 6555786
6613625 6621089
7130933 7204522
7335426 7522555
7748545 7784568
8184979 8494887
9066856 9178094
9303615 9384897
9716200 9719420
11693951 1183563...

output:

27793636591
139076373265
-1
-1
164554928593
340203577240
767735640886
-1
808488370439
777661458222
428941062963
-1
756913262477
860152123456
-1
734774231229
724225013316
184932545705
418133621292
-1
890908770677
450977017227
806542610691
-1
898938307262
536837237896
805921470285
-1
588880769556
-1
4...

result:

ok 196577 lines

Test #45:

score: 25
Accepted
time: 1935ms
memory: 125256kb

input:

199371 195400
999999 1 999999
4612523 4947496
5154685 5535111
6001135 6243639
7356800 7512564
7752763 7797747
8964902 8981715
9750529 9966044
9975655 10525517
16728399 17323380
17812655 17876446
17926768 18006465
18054955 18353713
18566302 18650151
19483683 19787610
20585307 20768207
22240113 222443...

output:

-1
621180105200
-1
-1
461780052274
772236852813
710455468422
730649315181
758552247311
190536170737
472110590707
660933061395
107617202142
917915550413
-1
252526045269
-1
730423595734
-1
-1
-1
-1
-1
-1
-1
276664132078
392648881685
207163529590
748682653117
622053824210
485855702116
-1
661004479399
-...

result:

ok 195400 lines

Test #46:

score: 25
Accepted
time: 1981ms
memory: 125228kb

input:

198278 196370
999999 1 999999
161975 250088
790789 822594
1044921 1160804
1182774 1186404
1212165 1493435
1928841 1935221
2686095 2994407
3085371 3137281
4151843 4199695
4797370 4807889
7089261 7293018
7469787 8294563
8639586 9028758
9535294 9647237
10261792 10434860
14068523 14148691
14245117 14573...

output:

107006124752
127121450263
719480563528
-1
97915594959
-1
272093640421
-1
-1
779112437224
-1
278064103799
-1
-1
94629533880
-1
518947410699
295938119924
-1
286734572810
-1
462315178138
-1
656398601363
-1
515972463880
-1
-1
463731627587
29815838997
503713954019
894142823925
386885082072
675276164984
4...

result:

ok 196370 lines

Test #47:

score: 25
Accepted
time: 1950ms
memory: 123296kb

input:

190308 196088
999999 1 999999
1589316 1719530
2162548 2518931
2629052 2984381
3086913 3353461
3455225 3455282
5432539 5481306
5850838 6295339
6986760 7082054
7925601 7941270
8188318 8209952
8326216 8494288
8898926 9225853
9795199 10273087
10964225 10973927
11365962 11546260
11612346 11669740
1177897...

output:

335994513998
-1
756345517990
63844676033
816674895005
95793949773
448915126326
961367036898
926970280278
315502814398
608736217929
-1
-1
890007920329
940210562473
619071423487
926609908048
149362280657
571340649004
777210538008
256673125898
-1
349176941798
648540718499
938038904114
-1
459037706019
4...

result:

ok 196088 lines

Test #48:

score: 25
Accepted
time: 1946ms
memory: 125176kb

input:

197660 195976
999999 1 999999
13343 692586
752194 983954
2435751 2945408
5413895 5421536
5520870 5720635
6959165 7086977
8622293 8847227
9660334 9823364
9835842 10252958
10929283 11277121
13750555 13810298
16634199 16637075
16870329 16970353
17336772 17653119
17725964 17833010
17958933 18336713
1890...

output:

521609825924
-1
932434325540
43425485771
757783622284
-1
601903818129
254437477178
819025671166
-1
236626854386
-1
257471432852
235245317149
117469362126
373027753560
-1
385486221028
-1
945304016581
-1
-1
375101203285
153888061031
-1
520898561028
189327508417
-1
587569604527
108513358547
-1
11696540...

result:

ok 195976 lines

Test #49:

score: 25
Accepted
time: 649ms
memory: 65984kb

input:

200000 200000
2000 1 2000
630 1632
1876 2158
2711 3735
4234 4856
5509 5902
13850 14242
15159 15716
17404 18103
19901 20024
20304 21089
21221 21344
22180 22985
23130 23236
30082 30591
30689 31072
33612 33935
40527 42290
45383 46190
46716 46800
47173 47263
47557 48161
57768 59567
59738 59853
60060 605...

output:

79991745323
789936142800
949975423013
729941161919
-1
-1
-1
519967821113
429970845198
639947050982
909952551269
399975684295
919965655725
909951170493
-1
589951000213
269982121508
389969423060
59994813183
379961893157
659944665315
-1
249979594110
499967867639
209979928363
519968145089
199982438348
8...

result:

ok 200000 lines

Test #50:

score: 25
Accepted
time: 663ms
memory: 65732kb

input:

200000 200000
2000 1 2000
260 867
876 1570
2586 2588
2630 2673
5473 6136
6816 7919
8895 9594
10867 11177
11588 11926
11969 12540
14072 14360
17570 18053
18756 19104
20252 20268
20514 20850
20971 21741
23959 24092
24462 24567
25212 25711
28968 29583
30188 30283
30780 31258
34284 34620
35552 35705
380...

output:

-1
9997494709
239984588464
10002561642
-1
310031121401
820005048898
-1
239980275729
470006769653
740015016291
240003164340
239998669154
239988346465
29996548578
-1
-1
90006192595
239988759589
-1
90005179717
690002714628
80001200307
790011724101
240001187799
690005227176
639999528978
-1
-1
4300175646...

result:

ok 200000 lines

Test #51:

score: 25
Accepted
time: 674ms
memory: 65852kb

input:

200000 200000
2000 1 2000
4457 4812
5482 5543
6836 7518
7558 7879
16521 16744
17677 17817
17916 17952
18233 18735
22630 22876
22954 23607
31841 33245
33432 33510
34384 34614
44971 45885
51032 51076
53548 53978
53980 54480
54995 55041
56164 57051
58728 59306
60549 60759
62649 62801
63829 64019
68138 ...

output:

-1
-1
490005213735
389983980028
-1
479993577366
269964928122
30006145533
589998466131
209977981338
709974711240
589993534516
-1
909979446385
530007635029
-1
909972674899
-1
849970905468
520005647906
-1
279969864933
299980247051
-1
279977883884
-1
510008135845
89998515208
-1
-1
-1
510006963301
369988...

result:

ok 200000 lines

Test #52:

score: 0
Time Limit Exceeded

input:

200000 200000
1000000 1 1000000
1201721 1894242
3016023 3044124
3467614 3538694
3868596 3901358
5781073 5925868
6188800 6413742
6683123 6948980
9324814 9508614
9797754 9926873
11701859 11712194
12520205 12627404
12987536 13383402
14184412 14404606
15290399 15593444
16186265 16463964
17416648 1774610...

output:

154980181226
3053320078
-1
116668888082
52271638839
-1
194799064164
-1
135756169612
35949188430
-1
101574878576
177681636714
-1
23671095214
172261625503
67298510105
-1
175627528003
28969352849
196466288166
192245483818
100571063417
-1
12133638153
65877759591
-1
-1
118589141668
215552746469
-1
-1
143...

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%