QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94675#4895. Lovely Dogsslime65 909ms128336kbC++144.5kb2023-04-07 14:59:452023-04-07 14:59:49

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 3ms
memory: 42640kb

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: 42672kb

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: 4ms
memory: 42632kb

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: 4ms
memory: 42776kb

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: 3ms
memory: 42696kb

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: 12ms
memory: 40652kb

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: 4ms
memory: 42708kb

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: 4ms
memory: 42752kb

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: 6ms
memory: 43388kb

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: 7ms
memory: 43196kb

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: 8ms
memory: 42708kb

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: 4ms
memory: 43048kb

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: 8ms
memory: 40752kb

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: 6ms
memory: 42804kb

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: 42712kb

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: 3ms
memory: 42788kb

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: 9ms
memory: 42712kb

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: 10ms
memory: 43036kb

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: 44768kb

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: 1ms
memory: 42720kb

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: 6ms
memory: 43152kb

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: 3ms
memory: 40756kb

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: 8ms
memory: 43156kb

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: 13ms
memory: 43172kb

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: 15ms
memory: 43300kb

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: 9ms
memory: 43164kb

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: 6ms
memory: 43888kb

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: 4ms
memory: 43668kb

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: 10ms
memory: 41360kb

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: 12ms
memory: 44112kb

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: 11ms
memory: 43436kb

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: 8ms
memory: 43352kb

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: 10ms
memory: 41432kb

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: 10ms
memory: 44140kb

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: 7ms
memory: 43364kb

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: 4ms
memory: 43972kb

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: 10ms
memory: 43452kb

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: 10ms
memory: 44280kb

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: 8ms
memory: 43552kb

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: 8ms
memory: 43960kb

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: 8ms
memory: 41428kb

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: 8ms
memory: 41368kb

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: 10ms
memory: 43480kb

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: 13ms
memory: 44188kb

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: 457ms
memory: 104744kb

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: 481ms
memory: 105472kb

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: 470ms
memory: 105528kb

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: 453ms
memory: 105404kb

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: 481ms
memory: 105512kb

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: 15
Accepted

Test #55:

score: 15
Accepted
time: 470ms
memory: 105388kb

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: 472ms
memory: 104788kb

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: 455ms
memory: 105380kb

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: 0
Accepted
time: 624ms
memory: 114776kb

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:

685522
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
1
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
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
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
1
1
0
0
0
0
0
0
0
0
1
1
0...

result:

ok 200000 tokens

Test #59:

score: 0
Accepted
time: 619ms
memory: 114844kb

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:

685522
1
0
0
1
0
1
1
1
1
0
1
0
1
1
0
0
1
0
0
1
1
1
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
1
0
0
0
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1...

result:

ok 200000 tokens

Test #60:

score: 0
Accepted
time: 636ms
memory: 121956kb

input:

200000 3
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:

57126
0
1
0
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
1
0
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
0
1
0
0
1
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
1
0
1
1
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
0
0
1
1
0
0
0
1
1
0
1
...

result:

ok 200000 tokens

Test #61:

score: 0
Accepted
time: 673ms
memory: 125532kb

input:

200000 4
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:

288980
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
0
0
0
1
1
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
1...

result:

ok 200000 tokens

Test #62:

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

input:

200000 5
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:

63577
1
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
...

result:

ok 200000 tokens

Test #63:

score: 0
Accepted
time: 753ms
memory: 127364kb

input:

200000 6
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:

204579
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1...

result:

ok 200000 tokens

Test #64:

score: 0
Accepted
time: 766ms
memory: 127940kb

input:

200000 7
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:

86937
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
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 200000 tokens

Test #65:

score: 0
Accepted
time: 909ms
memory: 128108kb

input:

200000 8
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:

174250
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #66:

score: 0
Accepted
time: 774ms
memory: 128160kb

input:

200000 9
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:

109811
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

result:

ok 200000 tokens

Test #67:

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

input:

200000 10
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 6...

output:

160094
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1...

result:

ok 200000 tokens

Test #68:

score: 0
Accepted
time: 764ms
memory: 127684kb

input:

200000 11
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 6...

output:

126754
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #69:

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

input:

200000 12
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 6...

output:

153287
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #70:

score: 0
Accepted
time: 717ms
memory: 128068kb

input:

200000 13
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 6...

output:

134751
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #71:

score: 0
Accepted
time: 727ms
memory: 127480kb

input:

200000 14
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 6...

output:

148021
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #72:

score: 0
Accepted
time: 698ms
memory: 128188kb

input:

200000 15
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 6...

output:

139082
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #73:

score: 0
Accepted
time: 700ms
memory: 128076kb

input:

200000 16
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 6...

output:

144986
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #74:

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

input:

200000 17
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 6...

output:

141865
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #75:

score: 0
Accepted
time: 712ms
memory: 128140kb

input:

200000 18
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 6...

output:

143935
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #76:

score: 0
Accepted
time: 686ms
memory: 128336kb

input:

200000 19
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 6...

output:

142672
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Test #77:

score: 0
Accepted
time: 701ms
memory: 128132kb

input:

200000 20
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 6...

output:

143459
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 200000 tokens

Subtask #6:

score: 10
Accepted

Test #78:

score: 10
Accepted
time: 192ms
memory: 61800kb

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: 167ms
memory: 62140kb

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: 0
Accepted
time: 115ms
memory: 60264kb

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:

-9152
0
0
-1472
-7389
-6321
0
-4854
-2735
0
0
0
0
-3769
-2558
0
0
-1531
-2588
-2908
0
-6720
0
0
0
-9803
0
0
0
0
-5494
-2885
-1898
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-3164
0
0
0
0
0
-3224
-4062
-1307
-1030
0
-4877
0
0
-6232
0
0
0
0
-3739
-1918
-4896
0
0
0
-5332
-8995
-1790
0
0
-6320
0
0
-5089
0
-6664
-9...

result:

ok 50000 tokens

Test #81:

score: 0
Accepted
time: 248ms
memory: 66280kb

input:

50000 1
33407 5182
3870 21606
16080 48453
2777 4478
49747 843
42539 32472
2195 15316
9184 16559
39787 27989
15822 46476
3462 8502
15130 37017
31019 7086
13437 19984
3 20139
21162 27689
1067 27927
37709 11407
38509 34963
36180 28194
10151 38894
21219 29603
18000 26175
48974 14856
22675 18606
44861 24...

output:

-9152
0
0
0
-2
-1
0
0
0
0
0
0
0
0
0
0
0
0
-2
0
0
2
0
0
-4
0
0
0
1
0
0
0
0
0
0
0
0
0
11
-2
0
0
0
0
-2
0
31
0
-2
0
0
0
0
-1
0
0
-1
0
-4
-1
-1
0
-1
0
0
0
-5
-1
0
0
0
0
-3
0
-1
-2
-1
0
1
-1
0
0
-2
0
-4
0
0
0
0
0
-1
-5
0
-1
0
0
7
-1
-11
0
2
-1
0
-5
0
0
0
-1
4
0
0
0
0
0
0
0
-3
0
-33
0
0
2
-1
-5
0
0
0
-1
0...

result:

ok 50000 tokens

Test #82:

score: 0
Accepted
time: 226ms
memory: 66860kb

input:

50000 2
33498 4348
23123 14835
39691 37408
16639 34690
11658 6884
18384 37709
34876 362
31285 46209
46969 43774
42016 8213
20575 17772
6850 7416
22841 15580
29655 11944
39386 14476
43195 12555
17750 39637
38370 1807
23684 7842
15935 30198
37729 13374
37344 19025
18023 42781
2091 42469
20928 26586
34...

output:

132856
19
0
0
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
0
1
1
30
1
1
1
3
0
1
4
1
1
1
44
0
1
1
14
6
3
0
1
3
0
0
1
0
0
1
8
0
1
1
1
119
1
1
1
1
2
3
5
-1
1
-2
1
1
0
1
2
1
2
1
1
1
1
1
2
0
9
0
1
1
0
0
1
2
3
7
2
1
56
8
1
1
0
22
1
1
1
0
2
7
10
1
23
0
1
1
1
0
1
1
1
1
1
0
0
1
0
2
1
1
1
5
1
1
0
1
0
0
0
1
0
1
1
1
6
4...

result:

ok 50000 tokens

Test #83:

score: 0
Accepted
time: 277ms
memory: 70320kb

input:

50000 3
2197 38217
46761 30089
46038 49892
40751 49695
12716 11374
46387 35267
44578 48391
31915 4177
27631 44787
5472 47601
2696 24412
34415 854
31686 8645
32438 47873
15844 8092
20099 37483
31858 40715
49343 18475
15451 32156
19723 20620
3387 44439
4994 10604
19669 42347
39388 6540
31228 12393
117...

output:

7883
10
4
0
3
0
0
0
2
0
1
1
7
2
5
2
2
1
2
1
1
1
1
3
7
1
1
0
3
5
0
1
7
1
0
3
8
1
1
0
0
1
0
1
0
1
0
0
1
1
1
0
0
1
7
1
2
0
1
21
1
1
2
2
50
2
0
8
2
1
1
1
1
4
1
0
1
1
3
1
3
2
1
1
1
1
1
1
0
3
0
1
3
0
1
1
3
1
2
3
2
1
1
0
1
0
3
3
3
0
1
0
1
1
21
17
1
2
0
3
25
1
5
1
-1
0
1
0
8
1
1
1
1
2
1
-1
2
0
1
1
1
3
2
0
0...

result:

ok 50000 tokens

Test #84:

score: 0
Accepted
time: 306ms
memory: 72016kb

input:

50000 4
19179 18268
14798 46951
25900 20679
30994 36099
12554 48166
27677 31985
44627 25537
43523 21523
42118 48501
40332 49984
7319 34492
3601 25176
47666 39140
43378 38712
34585 32082
880 824
45859 46998
43250 30136
28243 15080
27583 15609
40535 27408
8327 11651
4436 16972
44961 17114
2692 9085
26...

output:

59834
6
47
1
1
1
2
1
3
1
0
2
0
0
1
1
0
1
7
2
2
1
1
3
2
2
1
1
1
6
6
3
1
1
0
1
3
1
9
1
1
5
1
4
4
166
1
3
1
3
0
1
2
1
4
1
1
0
2
1
1
1
1
0
2
2
1
4
2
3
2
0
1
1
2
19
1
1
1
1
3
5
1
6
1
1
1
18
45
1
6
1
1
341
21
0
3
1
22
1
1
3
0
2
1
0
10
1
1
1
4
3
1
15
1
1
1
2
4
1
1
1
2
3
0
1
0
1
0
1
113
1
1
3
1
1
0
31
1
1
1...

result:

ok 50000 tokens

Test #85:

score: 0
Accepted
time: 291ms
memory: 72324kb

input:

50000 5
20995 9189
32758 30256
19089 40926
22253 44463
48087 16308
12133 19367
33350 49102
23654 6587
40501 7979
42958 48490
17344 26607
16978 30545
5834 42385
24833 189
20347 10449
32341 47219
42919 7466
44409 35693
37687 24577
7764 30265
29176 33496
32208 2303
34472 49595
6712 43752
22693 40343
97...

output:

7402
3
7
0
2
1
24
1
3
4
1
1
1
1
3
1
12
3
1
89
1
10
12
3
2
1
0
0
0
1
1
2
0
0
5
3
2
2
3
1
3
5
1
1
0
1
1
1
1
176
12
1
-1
1
3
1
1
5
0
1
3
1
0
1
46
1
31
19
2
1
1
1
0
7
0
1
3
4
1
1
1
1
4
1
1
1
4
0
1
1
0
1
1
0
3
1
3
20
1
0
0
1
1
1
0
3
23
0
1
1
1
1
1
28
3
1
5
1
1
1
32
6
0
0
1
1
1
1
1
1
1
1
3
11
2
1
1
0
1
1
...

result:

ok 50000 tokens

Test #86:

score: 0
Accepted
time: 289ms
memory: 72448kb

input:

50000 6
31908 33386
49241 47175
46270 43552
34574 29983
42535 46729
23227 48503
5931 48865
14203 546
22429 40164
37439 34806
15843 25371
17077 31877
21349 41019
34744 8498
17287 11543
21819 30514
9452 10202
5375 13790
30192 3154
25011 5195
21285 29602
10997 20058
15905 10404
47942 8084
9902 7552
115...

output:

42262
2
6
3
1
3
1
1
1
23
1
1
3
5
1
3
1
1
3
9
2
0
78
1
5
3
0
4
1
1
1
2
22
1
2
2
5
1
1
12
2
12
2
1
1
1
2
1
3
1
1
1
1
1
1
8
4
3
4
3
1
1
7
0
3
5
6
0
2
41
4
50
1
1
0
1
3
13
3
1
1
1
0
2
1
61
1
6
1
5
1
3
9
1
2
1
1
9
0
27
11
3
6
1
1
5
3
3
1
1
1
1
0
1
2
1
13
1
2
1
3
4
2
0
1
1
9
1
1
20
137
7
1
1
1
3
3
0
1
3
1...

result:

ok 50000 tokens

Test #87:

score: 0
Accepted
time: 276ms
memory: 72848kb

input:

50000 7
46824 13146
26398 10158
19679 40331
26927 1716
8856 25050
19765 27981
34921 27155
45110 45493
11643 16036
46933 29403
34247 2725
38874 47222
47694 25632
20592 1078
28604 43764
34431 37920
38802 5420
6694 16883
7669 32752
30044 22914
49240 44940
36453 18810
26219 44614
25827 41148
21536 16108...

output:

14995
1
1
13
12
1
1
1
6
9
1
7
1
1
1
1
4
1
2
1
1
1
1
1
1
4
4
1
2
306
3
3
1
4
3
1
2
4
15
1
1
2
1
92
3
1
1
1
19
3
3
1
2
1
1
1
1
0
3
6
1
2
1
3
1
1
2
1
1
1
1
1
1
3
2
0
6
1
2
47
1
2
1
1
18
2
1
3
1
1
3
3
12
1
1
4
2
1
6
12
1
1
2
3
1
3
1
1
191
5
9
3
1
1
6
1
2
2
1
3
37
1
1
1
1
3
1
3
2
1
3
0
1
1
3
2
1
1
3
9
2
...

result:

ok 50000 tokens

Test #88:

score: 0
Accepted
time: 293ms
memory: 72728kb

input:

50000 8
40414 46108
6563 44339
5249 42889
48085 742
5326 25720
39972 47695
4824 13734
15699 4408
39073 6823
40319 24085
37921 37926
24002 31240
9166 43485
20077 47996
7345 46960
27831 3952
38685 3875
9092 39283
32187 14265
20152 25343
40934 17906
27048 42847
35751 36532
44169 9435
1094 30392
37684 1...

output:

36061
4
2
6
1
1
3
4
1
1
1
2
1
1
44
42
1
7
2
1
4
6
4
23
1
1
1
1
3
1
1
1
1
1
1
1
1
1
5
1
1
2
1
1
1
1
235
3
6
1
1
6
1
3
2
16
29
3
2
24
4
1
1
1
1
7
1
3
1
1
2
7
1
65
1
5
1
3
1
1
1
1
4
1
1
1
3
0
1
1
1
3
1
2
7
1
11
1
2
1
3
1
1
1
2
2
1
1
1
3
3
1
6
1
10
1
8
1
1
0
4
1
1
3
2
1
5
1
3
3
1
1
4
1
1
1
12
6
4
4
1
1
...

result:

ok 50000 tokens

Test #89:

score: 0
Accepted
time: 286ms
memory: 72900kb

input:

50000 9
16967 39222
17882 38525
13855 16511
23141 43951
21086 22360
24699 41771
32218 26648
43003 35619
19006 21571
39651 36334
7738 36904
17248 41538
18239 5582
34984 31735
29520 26503
38869 35064
47998 2391
30408 16386
17201 22320
26029 40537
15268 18317
7182 8099
34548 29754
27724 15815
5003 4440...

output:

21916
1
3
1
1
1
1
27
810
1
1
3
2
1
4
1
3
1
1
1
3
1
1
70
1
72
11
1
1
7
1
1
1
1
24
1
1
4
3
14
16
3
1
1
1
1
3
2
1
11
1
1
1
3
2
1
1
1
3
1
8
1
9
4
1
3
13
1
1
8
1
1
5
3
1
4
1
1
1
1
1
7
12
146
19
2
1
11
0
6
10
1
3
1
36
1
1
2
1
1
1
1
4
6
1
2
1
1
1
3
1
1
3
1
1
9
1
3
0
10
6
2
1
3
1
1
1
33
1
1
2
1
1
1
3
1
1
3
...

result:

ok 50000 tokens

Test #90:

score: 0
Accepted
time: 287ms
memory: 72520kb

input:

50000 10
38285 4079
28371 40235
9193 17052
45360 2691
27650 18138
4679 3817
41948 47432
41386 38741
44775 49416
18912 29449
1096 34122
251 42661
21469 18881
7411 23008
7337 1671
26603 16447
33124 31934
18239 17338
9980 49359
13324 22500
27557 20723
44832 25663
16620 27850
3904 15972
46767 33864
1345...

output:

33070
1
10
1
1
7
1
1
7
1
1
1
1
7
19
3
3
1
35
3
2
1
1
1
6
1
1
3
2
2
4
1
1
1
9
1
1
1
1
1
1
2
1
1
1
11
2
3
11
1
6
3
6
1
1
39
1
1
1
1
6
1
1
1
2
1
2
1
1
1
29
2
1
1
1
1
3
1
1
2
1
50
1
3
5
1
3
1
3
1
1
1
2
4
1
1
1
3
1
6
1
1
6
1
1
3
1
1
2
1
3
3
1
1
1
2
1
1
1
3
5
1
4
1
2
1
3
3
4
8
6
3
1
1
1
1
1
7
3
3
6
1
1
1
...

result:

ok 50000 tokens

Test #91:

score: 0
Accepted
time: 284ms
memory: 73168kb

input:

50000 11
6429 33902
38803 17805
38108 28941
15398 29325
12803 32908
29926 5003
41570 33458
15598 43284
9793 12022
20324 38273
17214 39132
32099 49400
36160 41982
16462 24380
15417 2921
48072 45827
41897 27800
15031 27673
41800 44688
19367 38089
32393 45020
2178 26487
9983 47472
15902 47858
21441 470...

output:

25226
1
1
3
1
11
1
26
85
1
12
3
6
1
3
3
1
1
1
5
12
8
1
1
1
1
1
1
1
1
1
2
4
37
1
497
10
1
1
0
1
3
3
1
1
1
1
16
3
1
8
1
1
1
0
3
3
1
1
2
3
1
4
34
3
3
2
4
1
1
1
6
1
7
1
1
1
1
1
1
1
1
1
8
6
3
1
167
2
17
4
1
1
1
1
1
6
2
123
0
7
0
6
1
1
2
1
32
1
1
3
1
3
4
10
1
1
4
3
1
1
9
1
4
1
1
1
1
4
1
6
1
1
1
1
1
1
4
1
...

result:

ok 50000 tokens

Test #92:

score: 0
Accepted
time: 290ms
memory: 73064kb

input:

50000 12
13259 35129
39180 22973
44242 25473
19122 30008
12125 6677
16061 15260
4175 37168
16405 177
47099 45447
26441 24811
23943 38066
49676 18997
11214 761
40104 20769
24554 5185
3677 18192
10341 12206
5248 19485
12934 24828
32762 22526
9105 2111
38983 24995
27791 25980
30497 31519
34332 46185
32...

output:

30873
5
2
1
7
1
1
1
1
3
3
1
1
9
1
3
3
3
1
3
2
6
1
2
7
12
1
1
1
2
10
78
1
2
73
1
1
1
1
1
11
3
3
4
3
1
6
3
1
3
6
1
1
6
3
1
1
1
11
1
1
3
1
1
3
1
2
1
1
1
1
1
12
19
2
1
2
2
1
3
6
54
1
4
2
4
1
3
3
1
3
1
1
1
3
2
1
1
2
1
1
10
1
5
1
1
5
1
9
2
1
3
3
5
2
1
1
1
3
1
1
12
1
1
1
1
8
1
11
5
16
1
6
2
15
3
4
1
1
1
1
...

result:

ok 50000 tokens

Test #93:

score: 0
Accepted
time: 293ms
memory: 72660kb

input:

50000 12
31081 18764
49230 31095
26731 9915
678 45639
46459 4338
7810 43284
38682 17373
15350 45809
39528 4159
18325 16769
29463 26664
26712 49813
16851 27840
38205 29135
4096 34795
10470 15186
6547 807
21392 49162
12137 23663
2925 46736
13349 40767
21900 24264
19500 23764
31761 42185
24312 3867
492...

output:

30873
15
10
1
2
1
1
3
8
1
1
3
6
1
1
1
21
1
1
2
2
1
6
1
1
1
1
1
1
1
1
1
1
1
15
2
1
1
1
8
3
5
3
1
39
2
1
7
1
1
1
3
1
61
2
1
1
0
1
1
7
3
1
1
1
1
1
1
1
2
7
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
16
1
1
4
8
1
7
6
1
246
1
1
4
10
2
11
1
3
3
5
0
1
7
1
0
1
1
1
3
3
4
29
2
1
3
4
3
3
1
6
3
3
7
1
22
1
1
1
1
1
1
1
1
3
3...

result:

ok 50000 tokens

Test #94:

score: 0
Accepted
time: 165ms
memory: 68972kb

input:

50000 12
13533 45501
30989 9113
44634 2087
15469 46531
3154 42900
10805 42900
15121 33901
33514 5165
11664 34318
42393 42900
42900 26724
25568 42900
19249 42900
15936 42900
20199 49946
32661 42900
33856 17983
38811 42900
36099 2022
26708 48975
17474 49059
42900 1927
31598 23466
23340 48363
45352 181...

output:

30873
19232
17865
1
1
1
1
31353
1
1
15480
31112
1
1
16150
1
1
1
1
31080
1
1
1
31228
1
11978
12224
1
1
14099
32888
1
1
1
1
31233
1
1
19524
1
12373
1
16910
23542
32353
1
1
1
1
1
1
1
1
1
17624
1
1
1
1
12299
12245
25727
12026
1
1
1
1
1
1
28692
19904
17420
1
1
1
18131
1
17416
1
1
1
1
1
16289
31167
1
1
10...

result:

ok 50000 tokens

Test #95:

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

input:

50000 12
39400 42267
47867 25188
10945 7251
22185 28248
27547 4665
34352 7411
45792 38710
43818 20817
12262 12604
7844 7973
9707 14786
1841 20142
1598 38984
6609 7136
12077 549
16669 7370
25539 26644
27011 13629
19061 32219
31099 32941
19802 41103
22154 6044
15739 41878
34151 22554
4472 7272
31301 4...

output:

30873
1
1
16
1
2
1
1
4
1
2
4
1
15
1
2
12
8
4
1
1
6
2
2
2
20
1
1
8
6
4
4
1
1
8
16
1
20
1
1
12
1
1
1
8
4
8
4
1
8
4
1
1
1
1
1
1
6
1
1
1
1
6
1
138
1
6
1
1
20
1
5
1
2
1
1
16
1
56
28
1
1
2
8
20
1
6
40
1
2
8
8
32
100
2
1
1
1
2
2
2
1
1
1
2
1
1
6
1
1
122
1
1
1
1
8
1
1
1
12
16
1
1
2
8
2
1
4
16
1
1
2
56
2
6
1
...

result:

ok 50000 tokens

Test #96:

score: 0
Accepted
time: 275ms
memory: 71092kb

input:

50000 13
8307 34619
43948 31174
8159 48473
5457 26738
47721 45821
46983 33537
20760 16216
29900 16196
14602 5556
22096 30653
14505 33830
49127 19708
23426 3324
37742 3331
31664 9615
12683 42916
40734 8484
9022 25586
45909 43766
19564 9549
18611 14219
11415 1551
38598 39794
4514 26163
48574 7983
4939...

output:

27126
1
3
20
6
2
1
1
1
3
1
1
1
1
5
1
1
28
32
3
3
6
15
5
25
6
1
1
49
6
6
1
3
48
1
1
1
1
1
1
1
1
3
1
6
1
3
1
2
1
1
1
1
3
1
1
6
6
1
4
1
1
23
2
29
4
1
1
1
1
6
1
10
1
1
1
1
1
1
1
1
1
1
1016
2
1
1
1
1
17
1
1
3
24
1
2
1
1
1
2
1
4
1
1
1
2
1
1
3
1
1
1
2
3
3
1
1
3
2
19
10
6
1
3
10
1
6
5
4
8
1
6
1
1
2
6
1
1
1
...

result:

ok 50000 tokens

Test #97:

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

input:

50000 14
47819 37980
23326 2382
6047 10942
23138 37656
21000 19156
22301 18894
2210 13834
35124 7343
11943 42261
9471 22816
21478 2276
30141 6228
13983 24782
16067 32518
49239 18007
35308 159
23868 19589
45491 43188
2716 7941
26308 14752
20490 20980
31490 22134
41141 21777
39344 3792
20972 29558
313...

output:

29593
1
1
1
1
1
6
9
1
1
3
1
1
6
1
1
2
1
6
2
59
1
1
1
1
1
2
1
3
3
1
1
2
1
1
1
1
3
1
1
1
8
2
1
12
1
1
1
1
4
3
1
1
9
1
1
13
10
2
1
32
4
11
1
3
12
1
2
2
1
3
6
2
1
3
1
1
1
9
1
4
1
2
3
1
1
3
1
1
4
6
1
3
2
17
1
1
4
3
1
3
1
6
3
3
75
1
1
1
3
6
1
1
1
4
4
4
6
1
6
8
1
1
5
1
1
1
2
1
2
3
1
1
2
1
1
1
3
2
7
1
1
1
1...

result:

ok 50000 tokens

Test #98:

score: 0
Accepted
time: 287ms
memory: 72976kb

input:

50000 15
48750 23412
9119 13140
41136 30081
38135 23987
44796 6765
5105 44389
10892 36684
1476 42998
30485 13121
35294 22816
7709 21761
26990 19205
11961 18777
520 44042
1447 12906
21519 46923
41026 9729
48599 10005
11671 43078
24313 45686
27158 11132
12914 37501
19271 3151
1146 12414
27934 26463
35...

output:

28323
4
1
1
1
1
7
1
12
1
1
6
10
1
1
1
2
13
1
2
1
1
4
1
6
3
2
2
14
1
3
1
1
1
1
10
1
1
3
1
4
5
3
3
2
7
4
3
1
10
1
1
7
36
1
1
1
1
2
1
15
3
1
11
1
1
1
7
1
1
1
1
1
2
2
1
14
1
1
2
1
1
2
3
3
1
18
6
1
1
1
3
1
1
1
2
115
1
1
1
1
1
1
1
1
1
3
3
3
15
1
1
1
0
3
1
1
1
35
1
36
2
1
2
6
1
5
11
1
8
16
2
1
7
1
4
21
22
...

result:

ok 50000 tokens

Test #99:

score: 0
Accepted
time: 274ms
memory: 73476kb

input:

50000 15
20211 8483
37218 28734
29875 6558
46450 13319
39273 43789
17836 41412
47117 46017
49949 22458
44448 12551
3297 2513
16997 28025
20623 40274
18819 5995
5967 5322
47989 10059
5192 16335
2495 39917
25930 9070
41636 36378
14538 8319
19642 24118
26120 39198
27210 35544
37899 7585
42446 42130
226...

output:

28323
1
1
10
4
1
35
8
1
1
16
1
18
27
1
3
1
1
1
3
4
7
4
11
13
2
10
1
1
6
1
3
1
864
3
1
1
1
4
1
16
10
4
1
3
1
7
3
3
5
1
1
2
6
2
3
1
1
7
1
1
6
3
1
45
1
3
1
2
64
3
1
43
2
1
2
3
2
1
3
14
1
14
1
6
6
2
1
8
1
4
3
1
1
1
1
1
2
2
1
1
4
1
1
85
5
1
11
1
2
1
4
4
1
3
1
1
1
1
1
1
10
2
3
1
3
3
1
1
4
2
3
6
1
1
1
3
1
...

result:

ok 50000 tokens

Test #100:

score: 0
Accepted
time: 180ms
memory: 69392kb

input:

50000 15
19917 5967
38712 24774
19917 33781
21577 19917
13256 47200
48748 19917
37061 32076
24990 20169
26010 19917
19917 21862
1877 34505
3276 30721
15456 44107
30391 19917
19917 21070
33205 41306
11260 36610
48769 39395
19917 20531
23169 43256
10590 41225
44793 42688
41902 4317
19917 24884
16221 1...

output:

28323
20083
24431
16334
1
1
20762
22193
18981
26198
24006
1
1
1
1
1
1
1
1
22151
1
20740
1
1
22851
1
1
1
23981
1
1
1
1
1
1
1
1
1
18709
1
20806
1
1
1
1
21868
23509
23326
1
1
1
28120
1
1
1
20960
18678
24981
24370
1
1
26862
1
1
24094
1
1
22750
21961
1
29455
1
24500
1
28189
1
1
26470
24458
1
1
18791
2445...

result:

ok 50000 tokens

Test #101:

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

input:

50000 15
22152 17142
36465 8846
36003 8852
31325 8805
32466 24486
25158 46033
47997 34013
49511 36000
49869 11404
30912 28487
4151 6474
7617 2603
10957 30344
38946 23144
24587 23391
15225 44634
38363 27535
8519 41105
3066 28510
46576 9188
48148 30825
48382 29075
30261 17701
19577 34734
13368 36009
3...

output:

28323
2
2
15
1
2
8
1
4
1
6
8
32
1
1
1
1
2
1
4
1
4
1
12
1
1
1
2
4
1249
3
1
1
2
5
1
2
8
1
8
1
1
20
2
1
4
1
8
1
2
4
1
12
1
2
1
20
2
1
16
16
2
8
6
1
6
1
2
1
2
1
1
2
1
1
1
8
8
20
1
4
1
20
2
2
12
2
1
1
28
2
1
1
4
20
36
6
2
1
8
2
1
8
2
2
36
2
8
6
12
2
4
8
4
4
44
1
1
20
44
1
1
2
1
2
1
1
2
6
4
1
28
1
2
16
1
...

result:

ok 50000 tokens

Test #102:

score: 0
Accepted
time: 271ms
memory: 73120kb

input:

50000 16
27833 20010
10623 10404
44763 5384
28429 19036
42535 12462
3036 12613
49359 32692
193 4881
16077 42882
41417 30906
3274 2972
19655 32252
29903 49574
40218 1403
18118 19303
47903 27800
33080 11043
34495 3828
40146 26653
21851 1564
9086 18764
28466 16633
5868 40876
46324 36429
2683 46796
4187...

output:

29113
2
17
1
1
1
2
1
1
1
5
6
1
1
3
4
184
8
4
1
9
1
1
2
25
1
2
6
1
2
4
5
6
1
1
4
1
2
6
1
1
117
2
2
3
1
75
2
1
3
1
1
1
6
1
1
1
1
1
1
15
1
3
1
1
1
2
1
1
4
1
1
1
6
3
1
1
1
1
8
1
1
2
12
4
1
3
1
1
1
1
2
1
6
1
1
6
1
3
3
3
1
1
1
3
1
1
1
3
1
1
3
5
19
1
1
9
8
2
1
1
1
1
1
21
1
60
2
1
6
8
1
4
7
1
1
3
1
3
1
1
1
...

result:

ok 50000 tokens

Subtask #7:

score: 0
Time Limit Exceeded

Test #103:

score: 0
Time Limit Exceeded

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:
English 繁體中文 简体中文

Server Time: 2024-12-02 20:59:43 | OpenSource Project