QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376058#4895. Lovely Dogsmarher40 804ms137884kbC++142.3kb2024-04-03 20:09:372024-04-03 20:09:37

Judging History

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

  • [2024-04-03 20:09:37]
  • 评测
  • 测评结果:40
  • 用时:804ms
  • 内存:137884kb
  • [2024-04-03 20:09:37]
  • 提交

answer

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+500,M=2e7+19260+817;

struct node
{
	int u,v,nxt;
}e[N];

int n,d,head[N],cnt,pri[N],cc,a[N],fir[N],f[N],mx[N],tot,tl[M],tr[M],sa[M],sb[M],ro[N],ans[N],sz[N];ll sum[M];
vector<pair<ll,ll>>p[N];vector<int>in[N];int st[N],top;

void init()
{
	for(int i=2;i<=n;i++)
	{
		if(!a[i])pri[++cc]=fir[i]=i;
		for(int j=1;j<=cc&&i*pri[j]<=n;j++)
		{
			a[i*pri[j]]=1;fir[i*pri[j]]=pri[j];
			if(i%pri[j]==0)break;
		}
	}
	p[1].push_back(make_pair(1,1));f[1]=1;
	for(int i=2;i<=n;i++)
	{
		int num=0,x=i,k=1;
		while(x%fir[i]==0)++num,x/=fir[i];
		mx[i]=max(mx[x],num);
		if(mx[i]<=d)f[i]=-f[i/fir[i]];
		else continue;
		for(int j=1;j<=d-num+1&&k<=n;j++)k*=fir[i];
		for(auto t:p[x])
		{
			p[i].push_back(t);
			t.first*=k;t.second*=-1;
			if(t.first<=n)p[i].push_back(t);
		}
	}
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)in[j].push_back(i);
}

#define mid ((l+r)>>1)

void add(int&x)
{
	if(top)x=st[top--];
	else x=++tot;
}

void insert(int&x,int l,int r,int d,int da,int db)
{
	if(!x)add(x);
	if(l==r)
	{
		sa[x]+=da;sb[x]+=db;sum[x]=1ll*sa[x]*sb[x];
		return;
	}
	if(d<=mid)insert(tl[x],l,mid,d,da,db);
	else insert(tr[x],mid+1,r,d,da,db);
	sum[x]=sum[tl[x]]+sum[tr[x]];
}

void erase(int x)
{
	st[++top]=x;tl[x]=tr[x]=sum[x]=sa[x]=sb[x]=0;
}

void merge(int&a,int b,int l,int r)
{
	if(!a||!b)return void(a=a+b);
	if(l==r)
	{
		sa[a]+=sa[b];sb[a]+=sb[b];sum[a]=1ll*sa[a]*sb[a];
		return;
	}
	merge(tl[a],tl[b],l,mid);merge(tr[a],tr[b],mid+1,r);
	sum[a]=sum[tl[a]]+sum[tr[a]];erase(b);
}

void dfs(int x,int fa)
{
	add(ro[x]);sz[x]=(mx[a[x]]*2<=d?1:0);
	if(f[a[x]])for(auto t:p[a[x]])insert(ro[x],1,n,t.first,f[a[x]]*t.second,0);
	if(f[a[x]])for(auto t:in[a[x]])insert(ro[x],1,n,t,0,f[a[x]]);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,x);sz[x]+=sz[v];
		merge(ro[x],ro[v],1,n);
	}
	ans[x]=sum[ro[x]]+sz[x];
}

int main()
{
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);
	cin>>n>>d;
	init();
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		e[++cnt]=(node){u,v,head[u]};head[u]=cnt;
		e[++cnt]=(node){v,u,head[v]};head[v]=cnt;
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs(1,0);
	for(int i=1;i<=n;i++)cout<<ans[i]/2<<'\n';
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 42544kb

input:

20 2
18 8
18 11
13 19
10 8
9 11
4 8
9 15
9 17
2 1
13 18
20 18
1 8
12 17
7 16
5 11
16 15
6 19
14 16
1 3
2 15 5 13 20 6 16 18 9 19 17 7 14 10 11 3 1 12 4 8

output:

16
1
1
1
0
1
0
12
3
1
6
1
3
1
2
1
1
7
1
0

result:

ok 20 tokens

Test #2:

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

input:

500 1
287 459
335 297
303 82
427 202
500 158
257 45
410 274
208 19
172 113
274 379
380 65
234 46
161 441
73 488
473 327
474 481
152 67
78 414
260 20
142 385
494 343
446 72
498 296
111 9
349 372
448 217
282 442
412 144
342 44
282 92
337 128
426 201
104 493
278 298
278 145
363 121
92 305
278 379
166 1...

output:

158
-3
0
0
-1
0
0
0
-1
-1
-2
0
0
1
0
0
0
0
-1
-3
0
0
1
0
1
0
0
0
0
0
1
6
5
0
0
0
0
0
1
0
0
0
-1
2
0
0
0
98
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
-11
0
0
1
0
0
0
-5
0
0
11
0
0
0
0
-1
0
0
1
0
7
-2
0
31
0
2
14
-3
0
1
0
0
0
0
1
0
0
-2
-3
0
0
-3
0
0
0
0
0
0
0
0
0
-1
0
0
-1
0
1
0
0
0
2
1
0
-3
0
0
0
-1
0
0
0
-...

result:

ok 500 tokens

Test #3:

score: 0
Accepted
time: 7ms
memory: 44700kb

input:

500 1
420 282
9 357
176 82
390 58
280 145
303 106
342 485
300 241
149 18
233 286
499 473
288 22
472 103
271 244
490 273
419 93
26 5
408 243
132 423
75 53
112 390
26 227
413 312
401 320
96 71
479 129
459 373
322 425
465 85
244 117
155 7
44 407
225 351
67 480
370 24
408 60
463 245
270 264
271 82
109 3...

output:

158
0
-1
0
6
0
0
0
0
1
0
0
-1
18
0
0
0
0
0
0
0
1
0
0
0
4
0
0
0
1
1
2
0
0
0
0
0
-3
0
0
0
0
0
0
-1
0
3
-1
0
-3
0
0
0
0
0
-1
-1
0
1
0
0
0
1
0
0
0
0
1
0
0
-1
0
7
0
1
230
2
0
0
-6
0
6
0
-2
-2
0
0
-8
0
0
-1
3
1
0
1
0
0
1
0
-3
1
0
0
0
0
-1
0
0
0
0
0
-2
0
-1
0
1
0
7
0
0
-1
0
0
0
0
0
1
0
0
-3
0
-1
0
0
0
0
0
...

result:

ok 500 tokens

Test #4:

score: 0
Accepted
time: 7ms
memory: 44660kb

input:

500 1
407 7
167 9
444 291
345 93
446 169
305 310
231 378
93 158
93 128
233 75
499 106
93 430
403 132
26 186
305 452
15 238
82 93
146 93
272 11
62 319
301 91
136 28
93 60
478 324
101 248
180 445
253 155
61 456
348 130
137 308
93 63
376 93
202 446
93 401
458 9
226 93
164 93
432 484
265 93
396 218
473 ...

output:

158
-207
0
-12
20
0
0
0
49
0
-34
0
56
-59
-38
-119
0
0
0
103
-48
-46
-64
-11
0
-54
0
65
0
0
0
0
0
0
-41
-7
0
0
0
-54
0
39
0
-155
0
0
-49
0
0
-67
0
0
0
-54
-120
0
0
-55
0
0
-21
115
0
0
0
-206
0
0
-21
0
-48
-27
0
0
-71
0
151
0
2
-41
-58
0
0
0
0
0
-11
0
0
-49
-54
-38
49
-32
0
37
0
0
0
0
-42
0
0
-56
54
...

result:

ok 500 tokens

Test #5:

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

input:

500 1
27 412
370 80
199 200
189 311
29 174
242 428
302 491
64 278
390 342
334 86
145 468
329 308
466 462
85 371
198 182
18 435
338 85
473 105
50 131
312 62
58 417
233 53
38 278
377 365
162 397
293 228
12 211
432 499
218 134
390 130
272 381
336 133
137 356
95 449
290 327
151 232
179 272
201 269
304 3...

output:

158
1
2
0
0
0
0
0
1
0
0
0
0
1
1
0
0
3
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
2
0
-8
0
0
0
0
0
0
0
-1
0
0
0
0
0
1
0
0
0
-1
0
0
0
0
-2
0
-2
-1
-3
0
0
0
2
0
-1
0
0
1
1
0
-1
-4
0
1
0
0
0
0
0
1
0
-3
0
0
0
0
0
0
-2
0
0
0
0
0
0
1
1
1
-1
0
0
0
0
0
-1
0
9
0
-67
0
0
0
0
0
0
-4
-2
0
0
0
0
-2
-1
-1
0
-2
0
0
-...

result:

ok 500 tokens

Test #6:

score: 0
Accepted
time: 7ms
memory: 46776kb

input:

500 2
428 7
101 379
176 90
188 28
455 459
196 332
481 438
294 234
222 285
2 448
58 491
132 449
111 413
254 163
9 201
269 393
79 11
182 331
277 265
88 370
233 188
329 294
446 445
136 131
317 453
311 219
437 486
496 310
85 349
421 326
316 490
499 367
404 361
446 411
249 494
462 58
433 60
57 278
45 456...

output:

629
8
20
1
0
1
1
1
2
0
2
0
1
0
3
0
4
0
0
0
1
0
0
1
0
1
1
169
1
0
2
1
1
0
2
1
1
1
1
568
2
2
0
0
0
1
1
0
0
48
1
0
1
1
0
2
0
8
0
0
1
0
0
2
2
2
2
1
1
0
1
0
1
1
0
7
0
0
1
1
1
0
0
2
7
0
0
0
0
1
13
1
0
6
-1
1
0
1
2
0
4
1
1
4
1
1
1
1
0
0
1
-1
3
2
1
1
0
0
0
1
1
2
3
1
9
1
1
1
3
0
5
8
-1
1
2
0
5
1
1
0
0
2
0
1
...

result:

ok 500 tokens

Test #7:

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

input:

500 3
102 64
271 215
377 453
237 410
39 280
210 109
7 139
446 304
9 484
189 335
60 398
269 65
429 487
186 279
451 44
245 144
288 396
498 433
225 335
254 482
392 335
477 139
275 193
58 274
312 334
427 201
141 4
389 330
184 133
436 18
239 302
188 38
45 348
173 433
285 54
33 296
150 189
320 278
182 316...

output:

104
0
4
75
1
21
1
1
7
0
2
2
4
4
4
-3
0
1
0
1
2
1
0
2
1
2
0
6
0
1
0
8
3
5
2
1
1
1
2
2
6
1
0
0
0
3
-2
1
3
1
0
5
0
0
0
1
1
1
1
33
1
1
0
1
6
1
2
3
0
-1
1
1
1
1
1
1
7
1
1
0
1
0
1
1
120
3
1
2
10
0
3
0
0
1
3
1
3
1
0
0
1
0
2
1
0
1
0
26
2
6
1
0
0
1
4
1
0
0
1
1
2
1
0
3
1
1
0
0
1
0
14
1
0
3
0
1
1
0
11
0
8
0
1
...

result:

ok 500 tokens

Test #8:

score: 0
Accepted
time: 3ms
memory: 44704kb

input:

500 4
89 102
92 484
360 314
414 280
439 165
331 311
349 110
484 252
422 473
401 137
183 34
175 91
306 42
285 186
296 22
62 441
389 238
240 268
165 44
117 34
110 255
465 58
53 82
478 350
195 306
362 422
239 35
36 33
484 284
153 181
285 478
201 148
5 196
331 350
235 291
497 270
140 292
317 439
222 252...

output:

525
6
6
1
4
0
1
1
1
1
3
1
1
1
1
3
1
1
1
3
12
3
1
5
1
1
2
3
1
11
1
3
6
1
2
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
2
0
1
3
1
4
0
1
1
1
1
1
2
1
1
0
547
1
6
5
62
0
1
1
6
0
1
0
4
6
1
0
1
3
3
1
3
0
4
6
3
7
0
2
1
1
1
0
1
1
1
6
1
1
1
1
1
0
307
5
2
1
1
0
0
1
5
1
1
1
5
1
2
1
1
1
1
0
2
0
1
1
3
2
7
2
405
1
1
3
1
1
0
4
2...

result:

ok 500 tokens

Test #9:

score: 0
Accepted
time: 3ms
memory: 44664kb

input:

500 5
487 484
346 261
290 56
40 334
16 3
171 224
311 151
425 371
460 469
248 256
117 217
309 79
165 482
259 374
131 408
117 24
18 234
448 197
253 205
421 211
437 408
218 298
159 35
463 169
247 310
289 365
389 275
64 411
117 431
472 279
259 236
351 106
447 39
75 54
18 336
82 89
259 41
331 356
385 77
...

output:

308
1
24
1
0
0
1
1
0
1
1
6
12
1
3
2
1
11
1
1
0
1
6
4
1
1
1
1
1
1
1
1
1
1
10
1
6
2
38
1
3
5
0
1
1
0
0
1
5
0
61
3
1
2
5
1
5
32
4
8
1
0
0
4
1
1
1
9
1
2
4
1
4
1
1
1
8
0
1
0
4
1
0
1
4
1
38
2
2
1
1
1
3
6
0
119
10
1
1
13
1
3
1
1
1
7
1
3
1
1
1
1
1
1
3
1
6
3
1
1
3
1
5
1
3
1
1
1
3
0
10
3
8
2
1
2
4
2
1
1
0
1
0...

result:

ok 500 tokens

Test #10:

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

input:

500 6
387 133
199 269
328 469
142 241
334 323
266 453
479 411
141 56
287 158
493 267
306 387
257 483
310 381
398 14
110 457
462 170
11 262
321 316
413 299
364 488
132 166
304 131
208 245
423 21
360 427
369 188
72 10
219 93
181 279
118 129
20 499
462 122
261 254
180 495
199 300
241 90
491 274
382 127...

output:

506
1
4
1
1
1
1
1
1
1
15
1
2
1
0
1
1
5
1
2
2
3
1
12
1
6
7
1
3
5
1
1
4
1
2
1
70
1
1
12
32
4
3
1
1
3
11
1
3
3
1
9
4
10
1
0
4
1
63
1
1
1
26
4
1
1
3
1
3
3
1
1
1
1
1
1
7
1
1
2
1
1
8
1
1
1
5
7
5
3
2
1
4
3
1
1
6
1
1
2
0
2
1
3
1
1
6
1
4
1
3
3
1
1
2
1
2
0
5
3
1
1
2
3
1
7
1
1
343
1
1
2
4
2
1
1
2
1
1
1
12
1
1
...

result:

ok 500 tokens

Test #11:

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

input:

500 7
366 320
150 327
384 317
144 293
399 290
438 76
27 305
210 43
472 144
310 490
347 234
457 268
319 142
268 407
295 371
82 111
282 244
324 203
438 60
493 170
162 157
96 104
489 323
274 236
170 307
252 84
144 404
483 264
370 272
124 282
353 250
499 406
492 306
361 54
233 361
366 155
72 17
114 103
...

output:

412
1
1
1
2
1
1
0
1
3
4
1
3
6
1
1
343
6
3
1
11
1
1
3
1
1
6
9
9
5
2
1
3
1
1
1
6
1
1
1
1
2
1
8
1
1
11
4
0
8
1
1
19
1
5
6
1
2
11
1
6
1
0
34
8
1
1
1
1
2
1
203
2
2
4
12
1
1
1
1
1
9
1
2
1
1
1
1
1
2
1
3
1
0
1
37
1
1
3
1
3
1
7
11
0
1
1
2
1
2
6
1
1
1
1
1
1
2
3
1
1
1
0
2
10
3
1
75
0
1
1
1
0
1
2
1
1
1
3
19
2
1...

result:

ok 500 tokens

Test #12:

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

input:

500 8
14 22
499 298
38 476
195 58
38 306
98 258
313 252
220 303
68 28
87 303
27 172
322 264
430 419
354 351
29 324
160 207
475 237
492 303
335 243
61 386
444 491
263 382
264 133
382 85
259 128
416 48
308 115
83 392
426 321
354 28
325 466
152 433
363 349
325 353
423 142
443 362
190 166
462 362
183 24...

output:

450
3
2
1
1
1
3
9
1
3
1
79
1
3
4
1
1
14
1
7
1
2
3
3
7
3
1
162
1
1
1
1
10
1
1
1
1
9
2
1
1
7
1
0
1
1
2
3
1
1
4
1
2
22
1
1
1
2
1
1
1
11
1
1
1
2
5
119
1
1
5
3
7
12
1
1
3
1
1
4
1
1
37
3
54
5
2
1
2
1
2
1
1
1
1
17
1
1
1
1
1
3
1
1
1
1
0
1
3
1
1
1
3
1
448
3
1
3
4
1
2
1
1
1
1
6
3
10
1
1
2
1
2
1
1
1
1
1
2
3
1
...

result:

ok 500 tokens

Test #13:

score: 0
Accepted
time: 4ms
memory: 44708kb

input:

500 8
440 350
94 352
197 47
495 208
490 353
489 432
266 407
176 397
201 352
331 428
450 444
168 23
464 398
428 229
123 481
218 122
193 117
39 255
190 84
483 140
345 111
334 358
200 30
5 59
466 331
128 125
217 285
370 17
90 20
43 429
368 294
380 278
40 486
176 13
471 468
53 69
2 163
58 153
355 374
38...

output:

450
4
1
5
2
4
1
1
1
6
1
3
469
14
19
1
1
3
1
18
10
28
3
1
1
0
1
1
3
3
5
1
3
4
3
8
3
1
1
15
3
1
1
3
10
1
6
1
1
1
1
1
2
1
1
1
1
21
1
3
1
10
1
2
1
1
1
4
1
1
4
1
1
0
3
1
1
1
1
5
2
7
4
14
2
1
1
1
1
7
2
1
4
1
4
1
433
10
2
13
1
1
1
1
5
1
4
6
1
1
3
1
1
1
1
1
1
1
1
2
3
1
1
7
1
1
5
9
1
1
3
4
1
2
3
1
19
1
11
1
...

result:

ok 500 tokens

Test #14:

score: 0
Accepted
time: 3ms
memory: 44792kb

input:

500 8
88 395
88 162
192 401
232 209
136 168
308 94
198 88
298 285
17 43
227 112
361 33
181 31
88 200
88 372
128 493
415 347
256 203
88 447
88 436
315 222
88 294
366 483
280 486
215 163
133 343
226 283
183 88
272 23
88 379
88 45
49 341
344 426
237 64
278 197
271 217
178 405
88 111
88 74
165 50
131 49...

output:

450
1
1
1
1
1
1
161
1
1
0
175
241
1
1
219
132
199
1
1
1
1
134
1
1
1
1
176
135
1
193
125
145
1
1
1
1
1
400
1
0
1
134
1
1
1
238
1
178
227
208
231
1
0
1
1
186
1
1
219
1
1
138
144
209
1
183
183
1
213
1
182
218
1
1
190
1
1
1
131
161
149
198
1
1
209
1
118
1
193
1
137
1
138
1
1
178
1
227
139
422
1
130
382
...

result:

ok 500 tokens

Test #15:

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

input:

500 8
396 247
170 343
238 295
438 423
408 442
98 180
207 350
72 425
437 147
82 85
5 178
168 141
87 372
250 218
396 130
303 328
470 237
127 297
178 327
90 130
97 50
326 299
293 280
413 401
286 32
478 353
282 38
159 84
383 158
14 276
469 261
394 179
367 388
484 497
494 232
162 314
292 344
26 483
211 3...

output:

450
1
2
1
1
1
1
1
1
1
1
1
1
1
2
16
1
1
4
1
1
7
1
8
2
15
1
2
1
6
1
16
1
8
1
2
4
1
1
1
1
4
1
2
8
1
2
1
1
1
1
1
16
2
1
1
6
2
1
40
1
16
0
1
33
1
124
1
32
7
8
1
153
1
1
1
1
1
2
1
2
2
2
19
4
1
20
8
1
8
4
1
0
1
1
3
2
1
1
1
8
2
6
1
6
6
1
2
38
6
1
1
1
2
1
1
56
1
2
2
2
6
11
1
2
1
4
6
12
16
1
6
1
1
4
1
2
1
1
1...

result:

ok 500 tokens

Test #16:

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

input:

500 9
500 139
126 130
264 199
277 262
21 410
108 314
347 142
497 397
416 417
438 321
101 438
292 345
277 299
22 146
127 21
119 316
339 198
236 380
485 347
31 156
276 156
270 493
362 39
210 13
499 477
497 391
173 45
423 451
239 311
219 390
282 303
4 475
88 234
34 472
271 470
66 143
391 223
54 386
404...

output:

439
1
1
3
1
6
164
2
1
1
1
1
132
2
3
1
1
1
1
4
4
1
4
1
55
202
3
8
1
0
4
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
3
1
1
1
0
3
1
7
1
1
7
1
17
1
1
1
3
2
3
2
2
1
1
11
7
2
1
18
1
1
1
1
1
0
6
3
3
1
1
5
1
3
1
1
26
1
8
1
1
1
4
3
1
1
1
2
3
1
1
1
1
3
6
1
1
1
3
1
1
1
34
1
26
1
1
1
1
1
1
1
2
1
1
3
1
4
4
1
1
2
10
1
3
1
6
1
...

result:

ok 500 tokens

Test #17:

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

input:

500 9
281 499
420 114
385 279
336 190
296 247
274 483
148 269
132 25
319 66
482 444
445 81
7 136
272 330
108 417
204 92
48 25
414 175
277 155
295 213
140 183
16 420
348 28
179 415
157 357
359 299
469 335
439 17
173 67
330 221
297 132
257 333
205 232
147 333
111 273
270 340
19 329
205 118
387 218
20 ...

output:

439
1
3
1
3
4
1
3
2
53
1
1
0
2
1
8
1
3
249
1
1
1
1
6
282
10
1
2
5
1
1
14
1
1
2
6
6
20
1
1
1
1
1
1
1
2
1
399
12
1
9
1
2
5
1
1
2
1
1
1
1
1
1
3
1
6
1
3
1
1
1
1
1
3
1
1
8
1
2
1
2
1
11
3
3
4
1
1
3
1
3
2
7
1
1
1
243
1
27
7
6
3
1
1
1
1
1
8
6
28
6
1
1
1
3
3
2
15
10
6
1
0
1
6
1
3
2
1
1
1
1
1
3
1
1
3
1
3
3
11...

result:

ok 500 tokens

Test #18:

score: 0
Accepted
time: 4ms
memory: 44720kb

input:

500 9
26 71
446 145
445 145
485 149
373 485
145 110
145 142
145 123
249 145
418 21
308 392
334 145
145 46
145 429
417 246
425 218
488 145
166 236
460 47
354 145
141 477
277 32
447 69
278 145
53 204
93 106
145 221
145 424
305 371
145 213
145 292
144 349
476 374
358 277
169 145
189 422
76 247
472 42
1...

output:

439
219
364
459
1
1
1
1
1
1
1
0
526
1
1
1
1
516
1
1
409
1
248
1
1
515
1
514
1
198
1
613
1
1
310
1
438
435
171
585
465
1
1
1
1
1
488
1
1
1
1
1
182
1
466
1
1
1
1
1
1
519
1
347
514
313
1
130
510
1
515
1
1
493
1
474
1
1
1
1
686
217
517
1
1
176
343
1
185
476
545
282
480
1
242
1
487
1
1
1
154
1
1
502
1
45...

result:

ok 500 tokens

Test #19:

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

input:

500 9
333 445
388 344
148 429
115 197
396 495
448 500
296 398
309 138
41 5
317 267
400 180
210 99
16 439
156 346
64 133
253 371
200 251
428 211
308 408
242 16
82 104
479 483
405 142
402 141
106 224
408 158
69 477
382 357
269 83
373 139
339 244
346 99
449 255
484 368
362 167
98 186
83 341
92 399
407 ...

output:

439
1
1
1
6
1
2
1
1
1
1
2
2
1
6
4
12
1
1
2
1
4
2
2
1
1
1
60
2
2
4
1
4
1
1
1
2
6
1
1
16
29
2
1
1
1
1
2
1
1
1
2
1
1
0
5
1
1
2
3
4
1
1
12
2
1
2
1
1
4
48
4
8
1
12
2
64
5
1
6
21
1
2
2
1
1
1
1
3
1
6
1
34
1
1
35
1
6
8
1
1
28
1
1
6
6
1
2
2
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
8
4
1
2
1
16
1
1
1
2
2
2
6
1
1
3...

result:

ok 500 tokens

Test #20:

score: 0
Accepted
time: 4ms
memory: 44716kb

input:

500 10
236 243
150 347
16 309
12 83
83 205
358 158
332 130
366 218
195 376
345 298
80 397
307 192
354 321
142 382
151 361
361 459
368 354
241 159
170 51
304 500
294 245
469 358
132 327
346 192
279 426
287 306
268 151
321 209
240 340
386 482
420 375
338 158
261 125
143 11
194 167
23 51
165 145
157 28...

output:

447
4
1
2
1
4
1
8
22
1
7
3
4
3
1
7
2
2
1
1
2
1
1
7
1
28
1
1
1
1
1
1
1
1
84
1
2
1
1
8
4
1
1
2
1
6
2
43
1
1
9
1
0
9
11
1
1
1
1
1
3
12
2
1
1
6
1
1
1
1
3
3
1
16
7
1
3
3
1
3
2
18
6
1
4
1
1
2
1
1
1
1
13
1
1
1
33
1
1
1
1
3
1
1
1
8
2
1
1
1
1
1
2
1
1
1
42
23
1
1
2
1
1
1
13
21
1
18
2
20
3
1
10
32
1
1
1
1
1
1
...

result:

ok 500 tokens

Test #21:

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

input:

500 10
434 176
89 379
84 202
336 499
149 486
242 33
483 182
6 329
461 377
322 299
63 131
324 141
454 255
312 467
448 349
447 266
181 283
316 150
81 431
351 97
492 459
185 453
317 145
471 374
473 292
383 179
225 88
349 121
193 42
424 134
188 107
279 336
30 124
416 116
247 189
354 367
331 266
46 128
4...

output:

447
1
1
3
1
1
3
1
1
18
1
1
2
1
2
26
1
1
1
1
11
1
2
2
1
1
1
8
1
3
1
4
8
0
23
1
1
1
1
20
1
3
4
132
37
2
4
1
3
1
31
1
2
1
1
3
3
1
1
1
1
1
1
1
1
2
1
1
3
6
1
5
3
1
1
3
1
1
1
4
21
1
1
1
10
1
8
1
84
1
1
3
1
1
1
1
2
3
1
1
4
1
3
1
1
1
1
1
2
1
10
1
1
11
3
142
24
9
1
1
19
1
6
1
2
1
1
12
1
427
1
5
1
3
1
3
36
1
...

result:

ok 500 tokens

Test #22:

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

input:

500 10
390 79
132 84
267 132
94 132
132 179
435 302
368 27
437 424
251 32
132 90
447 132
64 361
207 132
210 448
328 388
417 229
199 442
265 432
387 492
373 120
132 355
161 140
136 132
242 239
112 184
49 132
132 150
139 81
44 496
293 483
132 122
295 132
132 482
132 39
3 350
146 66
132 30
251 155
214 ...

output:

447
1
291
1
230
184
506
1
1
1
1
1
360
1
1
240
1
167
191
218
1
1
207
1
1
1
1
1
425
1
1
204
215
1
195
1
201
1
1
1
1
1
1
1
1
1
1
1
1
227
183
1
1
1
1
1
439
217
163
1
1
1
1
189
195
211
183
194
1
162
1
163
1
0
164
1
1
1
293
1
1
1
1
1
191
1
170
218
1
1
219
1
1
1
232
215
173
1
217
204
1
177
1
266
197
1
1
1
...

result:

ok 500 tokens

Test #23:

score: 0
Accepted
time: 4ms
memory: 44640kb

input:

500 10
149 278
398 52
189 310
323 190
423 312
32 147
350 458
44 327
340 371
61 430
20 175
60 101
4 353
293 279
303 187
302 370
379 129
96 274
491 458
218 477
318 60
95 126
336 110
433 171
134 392
377 35
413 44
423 474
484 476
304 51
458 112
406 93
264 256
16 186
213 310
108 38
485 110
354 53
420 450...

output:

447
4
8
1
2
1
1
1
2
3
150
1
3
1
2
545
2
1
1
2
12
4
2
4
1
1
6
2
5
2
1
2
0
1
2
1
8
4
4
1
1
2
1
76
0
6
2
12
1
1
4
20
1
8
1
56
1
1
2
2
1
1
1
6
12
1
20
1
6
1
1
1
1
1
1
4
1
1
1
2
2
1
1
0
1
1
1
6
1
1
1
1
1
1
2
2
2
1
1
1
1
1
5
40
1
19
1
2
1
4
8
1
1
2
12
6
7
1
1
6
1
2
1
2
34
1
1
2
2
1
1
1
2
8
1
1
8
1
4
14
1
...

result:

ok 500 tokens

Subtask #2:

score: 10
Accepted

Test #24:

score: 10
Accepted
time: 10ms
memory: 46936kb

input:

2000 1
134 1468
867 1750
351 1220
1690 1888
1685 134
585 282
1142 643
206 271
260 1833
1987 770
1029 1667
322 1371
341 518
601 915
119 893
1933 1502
951 1785
1056 1630
1957 1208
96 55
1508 1212
331 427
505 151
1378 1486
1545 697
1459 629
202 997
180 1917
1638 1177
1244 1896
302 658
1433 1605
1318 19...

output:

581
-3
0
0
0
0
0
0
0
-2
0
0
0
0
0
-1
0
0
0
1
0
-1
0
0
-1
0
0
0
17
-2
0
-1
-2
0
0
0
0
0
0
0
-5
0
0
0
0
-14
0
-1
0
-1
0
0
1
1
-1
-4
0
0
1
0
0
0
3
0
0
0
-1
-2
0
0
4
0
0
0
0
-1
0
1
0
0
0
-5
0
0
0
0
-1
0
0
0
0
0
0
0
1
-1
0
18
0
0
13
-2
0
-2
0
0
0
0
2
-2
2
0
0
3
0
-1
0
0
0
0
-3
0
0
0
0
0
0
1
-1
0
0
0
0
0
...

result:

ok 2000 tokens

Test #25:

score: 0
Accepted
time: 4ms
memory: 42936kb

input:

2000 1
1754 1650
906 642
596 1542
1656 1549
716 1578
1799 1182
53 244
1032 41
1290 1758
485 1496
1438 948
1683 684
400 653
1756 1459
1965 1322
1540 1263
1365 1564
108 1801
741 717
1113 13
1787 1124
411 732
64 1817
907 259
1308 29
1518 752
375 422
663 1631
528 799
863 310
790 793
587 579
1828 874
502...

output:

581
0
-1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
-12
0
0
0
0
0
0
2
-1
0
0
0
0
0
0
0
0
0
-1
-1
1
0
0
-2
0
20
-1
0
-3
1
0
5
-1
0
0
1
1
0
0
0
0
-1
0
-2
0
0
0
-15
1
1
0
0
0
0
0
1
0
30
0
1
0
0
1
-1
0
0
0
0
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
-1
0
1
0
1
-1
0
-1
0
0
0
0
-3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
1
0
0
0...

result:

ok 2000 tokens

Test #26:

score: 0
Accepted
time: 7ms
memory: 47252kb

input:

2000 1
146 1160
146 388
146 1033
382 1917
162 1342
1 1425
1841 764
1674 780
1109 1649
1282 1786
488 1386
1753 1698
17 192
1692 944
693 146
1933 146
976 463
1603 392
1709 248
18 678
146 1157
1517 1416
31 1153
973 39
1359 1046
625 1840
745 146
1316 146
124 146
627 1410
146 540
772 1461
1041 1537
1374 ...

output:

581
0
-36
-192
435
473
506
0
0
358
0
0
0
0
0
0
-180
35
438
0
0
0
607
0
0
0
-17
0
0
26
2
499
0
-180
-85
0
-104
-120
-63
-60
0
0
0
0
598
0
0
0
0
356
592
0
0
0
45
-73
-116
343
0
0
0
0
0
0
31
-108
-5
0
0
0
637
270
494
0
0
487
0
-197
0
401
520
0
0
52
0
128
0
0
82
0
0
0
-22
0
0
0
0
0
0
30
0
0
0
0
0
0
0
0
...

result:

ok 2000 tokens

Test #27:

score: 0
Accepted
time: 7ms
memory: 47112kb

input:

2000 1
681 278
1551 1142
424 928
738 174
1393 1727
456 944
1713 468
359 1597
1265 1737
246 500
1095 695
654 904
1465 27
1172 1385
1455 40
1391 1384
1979 970
1123 800
1618 1892
1444 1506
79 806
313 1350
1872 85
1467 1031
741 1139
739 1681
263 1454
169 885
1222 153
864 799
192 1339
935 1843
1633 1358
...

output:

581
0
-1
0
0
0
1
25
0
0
0
0
1
0
-8
0
0
-3
0
0
0
-2
0
0
-3
0
0
0
0
0
0
0
-3
-1
-1
0
0
-1
1
-2
3
0
0
0
0
0
2
3
0
0
-1
-7
0
0
0
0
0
-7
0
0
-1
1
9
0
0
-1
0
0
0
0
0
-1
-3
-1
1
-3
0
-1
-1
0
-1
-1
-1
-1
0
0
-2
-1
12
-7
-10
0
0
0
-6
0
0
0
0
41
0
0
-15
0
0
0
0
0
1
1
0
0
0
0
0
-7
0
-3
-26
0
0
0
0
0
0
0
0
0
2
...

result:

ok 2000 tokens

Test #28:

score: 0
Accepted
time: 3ms
memory: 45104kb

input:

2000 2
1608 842
1808 1921
1404 549
594 1521
1755 855
1047 1256
340 1877
407 670
1100 1239
1511 1142
790 1103
1212 944
515 167
180 415
399 1563
1458 136
728 1480
1074 819
555 1594
1693 1301
1802 1879
1936 501
306 87
1125 796
720 1298
1999 1529
767 1396
1258 1940
1651 1564
1059 281
704 848
1861 473
13...

output:

2854
3
3
12
1
1
1
1
55
1
1
1
2
0
4
3
7
1
0
1
0
1
1
1
1
0
3
5
0
0
1
126
0
2
15
45
0
0
0
0
1
1
1
1
1
1
1
7
2
0
-2
1
1
3
0
0
0
0
2
0
1
0
3
1
1
5
1
-2
1
1
2
1
1
0
0
6
0
1
1
1
6
1
1
1
0
0
3
1
0
1
1
1
4
1
1
0
1
4
0
-1
1
1
0
1
1
1
3
0
0
0
2
1
0
1
1
1
0
0
1
1
23
1
0
1
1
0
1
1
2
0
1
4
1
3
0
2
1
1
0
3
3
2
1
0...

result:

ok 2000 tokens

Test #29:

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

input:

2000 3
1424 1720
1698 425
1429 965
955 45
629 466
537 1175
656 1047
1333 1754
1060 818
688 1990
1859 292
1588 1664
1134 1683
1378 1828
1353 1173
1906 1710
106 1208
1938 746
368 1557
1899 1866
433 1933
614 1604
999 278
418 1609
458 1347
1688 1325
1089 434
208 1987
519 1275
1227 870
305 1164
425 1930
...

output:

-26
3
0
1
10
1
1
0
4
6
1
2
0
50
15
1
0
1
1
0
0
0
1
1
1
4
4
3
1
0
1
1
3
0
1
5
1
1
3
3
1
11
0
1
0
1
2
1
157
0
1
3
0
1
1
2
1
3
1
0
3
4
1
0
0
0
1
0
7
1
0
0
1
1
1
0
0
1
1
1
2
1
0
1
0
1
1
1
1
0
0
0
1
4
1
1
0
12
0
1
17
2
1
1
1
6
0
3
0
2
2
5
0
0
0
1
1
1
2
1
0
0
1
0
0
0
2
1
1
1
3
-1
0
0
3
1
1
1
5
0
0
2
1
1
1...

result:

ok 2000 tokens

Test #30:

score: 0
Accepted
time: 7ms
memory: 47064kb

input:

2000 4
836 736
1179 1789
800 1646
768 914
1814 370
3 1531
1357 1646
1092 1016
1361 1295
1087 1220
210 574
885 1057
21 649
567 1568
1205 1889
869 1810
618 1075
1566 1575
1704 1349
1275 1029
190 1862
1661 1962
140 85
1764 19
226 1945
600 1727
849 724
383 1311
891 1457
183 643
1510 959
1701 346
1151 11...

output:

1802
1
1
6
1
0
1
3
2
25
3
4
1
0
1
5
6
1
1
3
11
1
5
1
0
2
1
1
1
31
3
1
23
1
1
25
1
0
1
1
54
9
3
5
3
1
1
1
0
1
0
0
21
1
3
1
1
2
34
1
5
4
3
0
4
0
1
2
1
41
1
1
1
1
1
1
3
6
0
1
22
11
2
0
3
2
4
15
0
1
1
74
2
1
11
0
1
1
3
1
1
3
1
25
3
0
1
1
1
1
1
1
0
1
1
1
1
5
15
1
80
1
3
3
2
5
1
10
3
3
1817
16
1
0
3
2
4
1...

result:

ok 2000 tokens

Test #31:

score: 0
Accepted
time: 3ms
memory: 45032kb

input:

2000 5
1800 301
502 481
173 833
98 1487
1118 1092
1418 1661
47 1275
1575 688
814 79
1428 1543
537 1252
1550 1326
1614 1397
551 1299
1918 1840
1682 1751
997 1168
240 1433
651 758
1881 1142
1845 1627
406 1097
1828 964
1387 1266
1764 1063
1852 1402
1021 1050
723 465
956 1865
1192 1255
387 1917
948 1695...

output:

434
0
390
1
3
2
1
0
1
45
5
2
1
1
2
12
6
4
1
1
1
0
0
24
1
1
1
1
1
0
0
2
1
1
17
1
0
2
0
0
1
3
1
0
1
0
4
1
1
0
0
1
1
1
2
2
0
1
14
2
3
1
3
1
5
2
0
10
1
1
0
10
1
1
1
12
3
0
1
1
1
1
1
6
1
0
3
6
1
6
1
6
1
1
3
0
5
1
2
1
3
1
47
1
9
17
0
3
3
1
1
3
2
0
3
19
1
1
1
1
3
1
6
1
1
1
7
1
3
1
1
2
0
2
0
1
3
1
1
0
1
13
...

result:

ok 2000 tokens

Test #32:

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

input:

2000 5
1046 1301
658 546
1365 1072
1242 1786
1598 1783
1794 229
430 1984
373 1473
352 1136
1203 348
1078 602
428 1355
1356 144
33 546
1149 1190
1706 1224
741 1461
293 393
1659 1208
1456 970
803 1588
1068 1922
1700 1067
1938 842
900 1799
192 948
1480 1339
1556 335
1943 1382
1197 1060
1085 1102
215 95...

output:

434
178
5
1
1
1
2
1
1
1
3
1
1
1
1
35
3
1
1
6
7
1
1
1
1
1
1
1
1
2
1
0
1
0
1
2
1
1
1
1
3
1
1
1
2
0
1
1
1
5
2
1
1
1
1
1
1
2
1
3
6
0
1
1
1
1
1
1
2
2
1
2
2
2
34
1
0
1
1
1
3
3
1
2
1
1
1
1
1
1
2
3
0
0
3
6
0
1
1
2
1
1
1
5
63
1
2
1
1
1
0
9
0
4
2
2
0
34
1
2
0
1
1
1
1
1
7
1
1
4
1
0
1
1
2
1
1
5
1
16
11
71
2
5
1...

result:

ok 2000 tokens

Test #33:

score: 0
Accepted
time: 3ms
memory: 45584kb

input:

2000 5
1052 767
1728 1664
1664 582
1664 1487
1664 704
331 1664
426 781
314 509
1978 1600
1007 1619
1112 1379
272 737
178 1500
1664 143
1664 797
1910 1664
1128 1664
922 1605
56 1802
880 1450
1254 111
1664 967
908 522
1664 993
97 1664
1664 1074
151 251
614 1664
859 886
750 1664
1664 1897
978 569
518 6...

output:

434
233
322
389
1
1
1
1
1
232
253
273
1
1
187
514
252
274
240
1
1
288
1
539
1
459
1
1
237
1
1
1
444
1
0
306
295
1
347
1
1
1
1
1
353
433
1
1
1
1
0
0
316
1
1
247
1
1
1
243
1
1
250
1
1
1
590
218
220
0
348
1
279
1
473
281
296
228
1
213
562
1
0
1
1
1
1
316
331
1
359
1
1
1
180
1
1
331
1
347
304
219
314
1
...

result:

ok 2000 tokens

Test #34:

score: 0
Accepted
time: 15ms
memory: 45144kb

input:

2000 5
1055 470
1642 1358
920 379
1771 1668
1475 1643
1845 1656
1542 1078
163 1717
1954 630
1350 1939
675 449
11 1447
304 186
1681 1077
1168 1348
1165 1621
1119 11
265 796
1897 559
844 1510
1269 185
1027 413
1198 43
1006 50
1053 900
769 179
1403 1255
1265 1170
606 211
760 7
1726 681
32 671
1109 1597...

output:

434
0
1
0
7
0
3
2
142
0
6
36
9
4
1
6
1
0
1
1
9
4
1
7
76
23
1
2
3
13
1
1
1
4
13
24
0
1
1
1
2
0
1
1
1
0
0
2
6
2
0
1
1
114
1
1
2
1
6
1
6
7
1
2
2
1
1
1
1
1
30
2
18
1
0
2
0
1
0
1
37
2
1
2
1
1
1
1
6
21
1
20
2
1
1
4
2
5
22
1
64
20
1
5
1
7
11
0
3
91
1
8
1
11
25
1
1
8
1
1
1
1
4
2
3
1
1
1
74
1
9
3
1
0
1
4
6
1...

result:

ok 2000 tokens

Test #35:

score: 0
Accepted
time: 15ms
memory: 47000kb

input:

2000 6
70 597
61 14
1492 388
1497 1872
1657 1701
216 1675
1993 1516
982 1112
669 315
1785 975
20 456
1344 471
375 1509
915 1114
877 369
1822 808
119 1128
1775 1218
1658 1024
1343 1377
716 1195
690 1251
518 1746
1282 728
735 1032
1023 1860
125 1014
1131 119
1856 1212
773 1621
88 160
649 1045
927 1357...

output:

1544
1
1
1
148
1
10
1
1
1
1
3
45
6
1
3
0
3
7
26
1
5
1
2
18
2
3
1
1
71
2
6
5
1
2
3
8
1
1
3
1
1
1
1
3
1
1
3
3
6
1
3
1
1
1
7
1
1
1
1
1
36
143
1
5
3
0
6
3
4
1
2
3
1
6
1
5
2
2
8
1
2
1
1
8
3
1
31
1
2
1
1
9
1
93
7
6
10
1
8
1
1
1
11
0
1
0
0
6
1
1
3
1
1
1
1
1
1
4
4
1
1
1
3
31
1
1
4
1
1
1
1
1547
2
1
0
1
6
5
1...

result:

ok 2000 tokens

Test #36:

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

input:

2000 6
1401 491
221 95
766 1497
1929 631
310 1758
1721 1913
6 53
1501 1704
979 1318
1678 332
1276 1081
934 755
895 1090
1421 1020
29 1993
1896 1062
1654 1452
1439 106
1341 1702
1703 1008
610 804
1796 403
72 156
1254 1998
1780 1389
746 72
1439 1173
1650 519
833 1655
1354 535
1789 1956
1879 263
1854 1...

output:

1544
3
11
1
1
66
13
2
3
1
1
1
1
5
9
1
1
1
2
1
1
1
1
1
6
18
1
5
4
1
4
2
1
1
1
1
2
1
193
1
4
40
1
0
1
1
9
1
1
4
1
1
118
3
1413
1
2
1
25
1
7
1
4
0
0
8
1
1
6
3
1
189
42
4
1
1
1
1
6
3
1
1
3
1
2
6
1
1
7
1
1
1
1
2
7
4
81
12
20
3
4
1
36
1
1
3
1
13
3
2
2
1
1
1
0
1
0
3
1
1
3
9
1
2
1
1
1
1
1
1
3
28
0
1
1
3
1
0...

result:

ok 2000 tokens

Test #37:

score: 0
Accepted
time: 3ms
memory: 45576kb

input:

2000 6
1409 372
1082 192
290 192
665 1493
192 897
1237 1815
192 806
1738 192
1016 295
1190 432
1000 539
192 1046
192 446
755 1558
519 427
192 149
557 1336
1391 45
1254 1058
1138 811
192 523
192 375
192 1553
830 547
209 164
330 400
760 860
192 1062
316 1930
1477 1909
1088 192
309 585
1263 1992
192 13...

output:

1544
1
1
1
857
0
1
1051
0
905
1
1376
1
1066
1
1
1
1
1
902
870
1
1
1183
1
1
975
1
1
1
1064
1119
1
748
1074
1086
1
899
1
1107
1466
1
0
1098
1136
1
1
1
1
1263
1
1259
1
1185
1381
1
1178
1068
1
1
1161
1258
1
1
1
1
1
1
1
1
1180
1
928
1
1
1229
1
906
1222
1245
1159
1461
1
1
809
1165
1
1064
1078
1109
1
1038
...

result:

ok 2000 tokens

Test #38:

score: 0
Accepted
time: 7ms
memory: 47068kb

input:

2000 6
221 1483
912 520
1926 976
1236 1865
215 1363
1616 1893
1577 1435
498 652
17 1881
1750 102
1687 1230
1562 58
1256 767
596 1924
276 1997
285 885
1926 1775
1 981
1723 1764
1548 1929
329 903
861 1600
230 1379
1539 669
1900 1904
1767 1205
1360 1532
1867 1377
1294 973
137 1890
772 336
1504 9
533 98...

output:

1544
4
20
1
2
1
5
2
34
6
2
7
11
6
6
122
101
1
1
1
325
1
4
1
37
1
1
59
6
1
1
6
1
6
1
12
2
1
8
1
2
44
1
1
1
2
2
8
4
1
1
4
1
2
2
1
5
1
2
19
1
6
1
2
1
2
37
2
1
43
4
1
1
1
1
6
6
2
12
2
1
1
1
6
1
1
4
17
7
4
1
2
2
1
2
1
1
1
7
86
2
2
1
0
4
2
1
6
62
1
0
1
8
1
0
1
1
1
27
1
4
2
2
1
2
6
1
1
2
6
1
1
19
3
2
1
1
0...

result:

ok 2000 tokens

Test #39:

score: 0
Accepted
time: 10ms
memory: 47132kb

input:

2000 7
123 1984
239 1693
32 702
1732 1411
1756 849
1938 732
532 1131
1819 172
1447 1824
1999 1486
701 91
1498 197
1854 1439
413 1977
58 1452
835 608
824 551
953 1631
254 408
1833 1084
1775 1963
1614 549
503 1413
586 306
938 1576
938 174
525 378
124 1799
306 1979
1837 30
645 1123
1672 1603
121 837
10...

output:

880
11
71
1
1
3
2
1
1
2
4
1
1
1
3
1
1
1
0
1
4
3
79
1
1
1
0
1
1
1
1
3
8
1
2
4
1
1
0
1
1
0
2
1
16
3
75
1
0
21
1
3
1
1
7
1
46
1
6
1
1
1
1
1
1
1
1
3
10
1
0
37
1
28
1
1
9
1075
1
1
1
1
1
10
2
1
1
1
2
9
9
0
1
5
1
1
1
1
6
1
3
9
1
13
1
1
2
4
0
0
3
1
2
9
1
1
2
1
5
2
1
3
31
2
1
1
2
86
5
0
1
1
1
1
1
6
1
1
1
1
1...

result:

ok 2000 tokens

Test #40:

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

input:

2000 8
1646 1528
1742 1700
61 1068
883 713
637 316
198 1289
1161 1587
1654 456
311 891
546 1536
884 1484
1006 1104
754 905
1270 928
1555 1543
323 808
536 1976
278 1905
1735 828
672 1650
1679 865
14 369
776 976
786 36
556 763
670 280
916 1608
1889 886
6 1618
1648 123
1740 943
1169 1110
145 1295
1627 ...

output:

1404
7
1
1
1
1
1
1
1
1
5
11
3
3
1
1
1
1
3
3
4
4
3
3
414
14
3
7
1382
1
13
1
1
1
1
5
1
1
1
1
1
1
0
1
1
1
30
1
1
1
3
1
1
1
1
1
1
5
6
1
9
1
1
1
18
1
1
4
1
4
9
12
2
19
1
1
1
1
1
1
1
1
6
24
1
2
1
1
1
22
3
1
1
3
36
2
2
4
1
4
3
2
1
1
7
3
6
2
6
1
3
0
1
1
2
2
0
0
21
8
2
1
0
6
1
1
0
1
2
1
5
1
3
2
1
5
1
1
2
1
1...

result:

ok 2000 tokens

Test #41:

score: 0
Accepted
time: 11ms
memory: 45036kb

input:

2000 9
1049 342
121 1775
1116 1794
1818 1041
1566 441
61 423
724 364
601 1551
329 1304
765 96
1095 742
679 1760
103 1267
925 1486
1355 1737
1921 1369
1163 916
1938 1169
1139 1037
836 56
1767 816
196 1663
1858 970
1077 751
447 229
1699 388
1808 1193
864 255
1651 1760
1353 1021
835 1950
1360 1515
1749...

output:

1109
3
1
4
1
2
1
3
3
13
3
1
3
1
1
6
1
1
1
3
7
1
1
1
10
1
1
1
1
1
9
1
2
1
1
1
1
1
1
5
3
50
1
10
1
3
6
1
1
3
61
1
42
1
5
1
1
1
1
1
321
15
1
1
1
1
1
1
1
11
1
1
27
1
1
1
2
1
1
1
1
2
3
1
1
1
3
1
1
0
2
1
1
1
1
32
3
3
1
3
2
1
2
1
2
1
1
1
1
1
1
1
1
1
3
3
1
1
4
1
10
77
25
1
3
1
6
9
3
1
1
1
1
1
5
1
1
1
1
1
16...

result:

ok 2000 tokens

Test #42:

score: 0
Accepted
time: 11ms
memory: 42928kb

input:

2000 10
318 1846
1862 1104
1226 1300
1101 756
826 1313
752 648
1897 744
302 58
1832 611
65 520
443 1433
1277 182
691 313
1792 521
1058 1160
919 887
1392 156
1198 896
1362 1252
626 1437
829 255
524 1760
1201 1656
914 307
139 307
1432 961
443 279
996 1597
1336 1405
1647 102
53 658
1025 812
1362 1909
1...

output:

1266
3
1
1
1
4
4
1
3
3
1
2
1
1
2
1
1
1
1
15
1
1
1
1
4
4
7
3
6
1
68
1
1
1
10
2
1
1
6
1
1
1
1
5
1
1
1
3
18
4
5
1
3
1
1
11
1
1
4
1
1
3
1
3
11
1
1
372
0
1
42
1
1
3
1
1
1
2
1
1
1
2
1
1
1
8
3
1
1
1
1
1
3
1
1
2
1
1
1
5
1
1
1
2
3
3
1
1
1
1
53
1
1
3
1
1
1
12
3
1
2
7
3
1
3
21
1
1
1
1
1
1
1
1
5
1
1
2
3
14
1
1
...

result:

ok 2000 tokens

Test #43:

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

input:

2000 11
1906 39
837 1799
1266 565
1488 321
1383 348
147 1317
362 154
488 216
1283 1597
1452 39
1120 156
255 1304
388 781
86 246
732 1457
1737 1895
28 1884
840 1787
304 263
1650 363
63 1397
355 423
1076 512
773 295
250 1719
535 1408
1254 396
502 1284
1866 1908
1816 1860
1076 1951
1793 1346
1867 1871
...

output:

1206
1
40
1
3
1
33
2
11
1
1
1
3
3
5
1
1
1
1
1
1
1
1
0
1
1
1
3
0
6
1
3
1226
1
1
2
12
9
10
3
1
3
3
1
1
3
3
3
1
3
1
10
4
1
1
2
1
1
1
1
8
17
4
3
2
1
1
1
1
3
1
11
1
1
1
3
1
1
1
1
1
3
1
1
1
1
1
1
1
2
1
1
1
1
1
3
1
1
6
1
1
1
2
0
1
4
1
22
1
3
1
1
3
1
2
2
3
10
1
1
1
1
6
1
3
2
1
1
2
1
3
3
14
0
11
1
7
1
1
1
2
...

result:

ok 2000 tokens

Test #44:

score: 0
Accepted
time: 5ms
memory: 45016kb

input:

2000 12
1634 1603
1000 588
1508 224
649 324
491 1780
124 24
334 1226
1151 1623
127 855
1690 1613
951 1586
533 653
1219 1025
1123 1546
1815 1045
1806 1240
1096 1471
1605 1509
72 1543
584 1233
1723 989
1720 1752
1302 1438
1133 394
1630 1815
307 672
798 1751
57 1500
1111 1160
1944 611
1356 350
1905 932...

output:

1243
2
1
1
1
1
4
1
2
1
1
1
15
1
38
1
2
13
1
1
1
2
1
36
1
1
12
1
3
1
3
6
1
3
1
1
1
4
1
4
3
1
3
1
1
1
1
2
1
4
1
5
2
1
1
4
2
14
3
1
1
3
1
1
1
53
1
1
1
1
1
1
4
4
32
140
2
4
1
1
1
1
15
1
5
3
2
1
1
1
4
2
3
12
2
1
51
5
1
1
1
3
1
1
1
1
1
5
1
1
2
1
6
1
1
1
3
1
3
1
1
3
1
69
2
1
3
2
7
1
13
1
1
9
1
1
9
1
1
4
1
...

result:

ok 2000 tokens

Subtask #3:

score: 0
Time Limit Exceeded

Test #45:

score: 0
Time Limit Exceeded

input:

200000 20
117994 12616
53490 106425
103660 50033
132640 78252
58384 19939
69183 10015
39098 165030
179856 130356
65245 57831
18234 83378
4240 154896
177149 102260
4634 180087
132390 19627
98506 60775
1890 120740
87908 21917
41323 192721
181885 96684
69412 139951
9800 38301
59025 29879
186185 81402
1...

output:


result:


Subtask #4:

score: 20
Accepted

Test #50:

score: 20
Accepted
time: 538ms
memory: 108776kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #51:

score: 0
Accepted
time: 542ms
memory: 107744kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #52:

score: 0
Accepted
time: 536ms
memory: 109700kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #53:

score: 0
Accepted
time: 553ms
memory: 108368kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #54:

score: 0
Accepted
time: 523ms
memory: 108392kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Subtask #5:

score: 0
Wrong Answer

Test #55:

score: 15
Accepted
time: 533ms
memory: 107964kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #56:

score: 0
Accepted
time: 540ms
memory: 107688kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #57:

score: 0
Accepted
time: 544ms
memory: 108440kb

input:

200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

-44916
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 200000 tokens

Test #58:

score: -15
Wrong Answer
time: 804ms
memory: 137884kb

input:

200000 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

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

result:

wrong answer 1st words differ - expected: '685522', found: '-795373'

Subtask #6:

score: 0
Runtime Error

Test #78:

score: 10
Accepted
time: 120ms
memory: 61256kb

input:

50000 1
8097 41839
17674 41774
40520 8024
5786 38261
20664 43471
1217 49276
11185 40807
14186 25584
31704 14814
42333 41475
13053 39565
45938 30104
5826 39463
5031 10814
43784 6042
58 33849
42978 18978
36307 33276
34769 4351
27884 37532
27528 29431
29451 39345
10946 9667
19016 47269
7911 30103
10308...

output:

-9152
0
0
0
0
0
0
-1
0
-1
0
0
1
0
0
0
0
0
0
0
0
-2
-1
-2
0
-2
0
2
-3
3
0
0
-1
0
0
0
0
0
0
0
0
-2
-1
0
-1
0
2
0
1
0
0
0
0
1
0
0
31
0
0
0
0
0
0
-3
0
-1
26
-2
9
-1
-1
5
0
0
2
0
-1
0
0
0
4
-1
-1
0
-1
0
0
0
0
0
-1
0
0
-2
-1
-1
0
0
4
0
0
0
0
0
0
8
-12
0
0
0
0
0
0
0
9
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
-...

result:

ok 50000 tokens

Test #79:

score: 0
Accepted
time: 117ms
memory: 63128kb

input:

50000 1
32034 47865
25944 188
8598 48750
2708 28815
30476 36844
46054 9168
4967 34970
41763 39703
15403 23747
17970 29303
36579 18070
19316 40824
40459 44029
3823 38050
3084 19147
18056 49063
25399 16977
39334 9283
41398 29161
20384 27913
30470 31528
640 5773
1605 32691
48417 23633
27454 6779
19548 ...

output:

-9152
11
14
0
0
7
0
-1
0
0
0
-14
0
0
0
1
0
0
-1
0
0
0
0
3
0
0
0
0
0
0
0
0
0
-2
0
-1
0
0
1
0
0
-50
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
6
5
-1
0
0
1
0
0
0
0
0
-8
0
-16
0
5
0
0
0
0
0
0
-1
0
0
0
-1
0
0
-1
0
0
0
2
0
0
0
0
-2
1
0
0
-5
0
0
0
-13
0
0
0
0
-3
-3
0
0
0
0
0
-1
0
0
0
-1
-1
-1
0
-1
0
-3
0
2
1
0
0
...

result:

ok 50000 tokens

Test #80:

score: -10
Runtime Error

input:

50000 1
39371 11897
18057 28366
41597 38680
18057 27889
11426 20379
41380 30688
28903 40347
18057 25169
37754 8154
23412 45346
18057 45516
18057 33624
18057 30696
26612 23615
18718 44663
27320 18057
20424 36013
19003 29291
6016 18057
1718 5947
41466 23544
38799 26926
18057 30495
18057 14852
16829 27...

output:


result:


Subtask #7:

score: 0
Runtime Error

Test #103:

score: 25
Accepted
time: 678ms
memory: 113340kb

input:

200000 1
118863 188865
188022 168616
118976 119404
178852 33449
81624 40431
151228 160976
68943 136313
57200 117631
147789 139875
100240 55537
164811 145415
103548 186750
15010 168029
155731 107005
69836 1502
86171 122700
83448 131948
189162 94464
128210 2509
49724 183329
174782 192641
27687 71315
1...

output:

-44916
0
0
0
0
0
0
0
0
0
-1
-1
0
0
-1
0
0
0
-2
-1
0
0
1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
-1
0
0
0
0
0
0
17
0
0
0
0
0
0
-1
0
1
6
41
0
0
0
0
0
0
0
0
0
0
0
3
0
0
-1
-38
0
0
0
0
0
0
-3
0
0
0
0
0
0
0
0
-1
0
0
0
-25
0
0
0
-6
-1
0
0
0
0
-1
-1
0
-1
0
-8
0
0
0
0
0
0
-1
0
0
0
3
0
0
0
0
0
0
0
0
-2
0
0
1
...

result:

ok 200000 tokens

Test #104:

score: 0
Accepted
time: 707ms
memory: 111412kb

input:

200000 1
103058 36806
98944 9225
170214 92545
96750 194462
199969 147292
67357 143473
167591 8145
25143 108831
176035 146998
191872 102153
157796 195518
189602 112527
139590 8953
91004 39370
139847 165500
121776 127200
49688 174930
100747 89328
53647 122360
70871 38221
164904 6986
89568 54074
92205 ...

output:

-44916
0
1
0
0
0
1
0
3
0
3
0
0
2
0
1
0
0
0
-1
0
0
0
-1
0
-1
0
0
0
0
-1
0
0
0
0
0
0
0
1
0
0
0
0
0
9
1
0
0
0
0
0
0
0
0
0
1
0
0
0
-2
-1
-1
0
0
0
-3
-3
0
1
0
0
0
0
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
2
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
38
0
0
0
0
0
0
0
6
0
0
0
1
0
0
0
0
1
0
2
0
0
0
0
0
0
0
0
0
0
5
0
0
-1
-1
0...

result:

ok 200000 tokens

Test #105:

score: -25
Runtime Error

input:

200000 1
28250 161590
136522 143045
181858 25068
161590 155647
161590 197485
43365 24019
123719 161590
128919 161590
58859 80176
85441 66983
116620 163645
177760 161590
193780 161590
170319 136949
168425 147380
127765 98730
16031 33995
111500 161590
160891 80562
151520 168155
161590 88595
161590 183...

output:


result: