QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245197#2644. Cats or Dogsznstz100 ✓377ms50736kbC++204.6kb2023-11-09 19:43:312023-11-09 19:43:31

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 1ms
memory: 8796kb

input:

2
2 1
75
1 2
1 1
3 1
3 2
1 1
2 2
3 1
3 2
2 2
3 2
1 1
3 1
1 2
2 1
3 2
2 2
3 2
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
2 2
3 2
3 1
2 1
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
3 1
1 1
1 2
3 1
3 2
2 1
1 2
3 1
2 1
3 2
2 2
3 1
2 1
3 2
2 2
3 2
2 2
3 1
3 2
1 1
3 1
2 2
1 1
3 1
1 1
3 2
2 2
3 2
3 1
2 2
2 1
3 1
2 1
3 2
1 2
3 1...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0

result:

ok 75 lines

Test #2:

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

input:

9
5 3
4 9
5 4
4 1
5 7
7 6
4 8
2 3
32
2 9
2 5
1 1
2 2
1 4
1 3
3 3
2 3
3 1
2 7
3 4
1 4
3 2
3 7
1 6
3 4
2 7
2 8
3 7
3 9
3 5
1 4
3 6
2 1
1 7
3 4
3 8
1 2
3 2
3 3
3 7
1 9

output:

0
0
1
1
2
4
2
2
2
2
0
2
2
2
3
1
1
1
1
1
1
2
2
3
3
1
1
2
1
1
0
1

result:

ok 32 lines

Test #3:

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

input:

15
2 15
7 14
9 1
15 11
3 14
2 5
13 3
3 2
12 11
6 14
8 10
8 5
13 1
7 4
43
1 14
1 11
1 12
1 6
2 1
2 7
3 14
3 6
2 9
3 9
2 2
3 2
2 8
2 2
3 7
2 3
3 3
2 5
1 6
2 3
3 11
1 13
1 9
1 4
2 11
3 1
3 9
3 11
3 5
3 13
3 4
2 7
3 3
1 11
1 4
3 4
2 13
3 2
2 15
1 9
1 4
3 9
3 13

output:

0
0
0
0
1
2
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
4
5
5
5
3
3
3
3
2
2
2
2
2
3
2
2
2
2
3
4
3
3

result:

ok 43 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 11196kb

input:

9
9 2
5 7
1 7
2 1
9 3
1 4
6 7
6 8
100
2 6
2 8
2 7
1 9
2 2
3 6
2 5
1 1
2 6
3 8
1 4
3 9
2 8
3 8
3 1
2 9
3 5
1 8
3 9
3 4
2 5
2 3
3 6
2 4
3 2
3 5
3 7
3 3
1 1
2 9
2 7
2 3
3 9
2 5
2 2
3 7
2 9
3 1
3 5
1 5
3 5
3 2
2 6
1 7
3 8
3 9
3 7
3 3
3 6
2 5
1 9
3 9
1 9
1 8
3 9
2 1
1 2
3 5
1 7
3 8
2 9
3 2
3 7
2 7
3 9
1 ...

output:

0
0
0
1
1
1
1
3
3
3
3
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
2
4
4
4
4
4
3
3
1
1
1
1
1
1
3
2
2
0
0
0
0
1
0
1
2
1
1
2
2
2
2
3
1
0
0
0
1
1
1
4
4
4
2
2
2
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0

result:

ok 100 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 12540kb

input:

11
4 11
1 7
10 11
7 4
5 3
1 8
7 2
1 9
5 8
6 5
91
2 8
1 11
3 8
2 7
2 8
2 6
1 5
1 9
2 10
3 10
2 1
3 6
2 10
3 7
1 3
1 7
3 7
3 10
3 5
3 1
3 8
1 1
2 8
1 6
3 3
1 7
3 7
2 7
3 8
2 5
3 9
2 10
1 2
3 5
2 8
3 10
2 9
1 3
3 6
1 6
3 7
1 7
3 2
2 10
3 9
3 8
1 2
1 8
1 4
3 10
3 8
3 7
2 5
2 7
3 3
3 7
2 8
3 1
3 2
2 2
2 ...

output:

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

result:

ok 91 lines

Test #6:

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

input:

15
11 1
8 1
9 11
8 12
14 12
13 15
7 13
4 15
3 4
5 9
15 2
4 12
15 10
6 11
100
1 1
2 11
2 7
3 7
3 1
1 9
2 5
1 6
2 12
2 13
2 1
3 13
3 1
3 9
2 14
1 9
2 7
2 13
3 14
3 5
2 1
3 9
1 3
1 10
2 9
3 11
3 3
3 1
2 2
3 12
1 5
1 15
1 4
3 10
3 7
3 9
2 1
1 14
3 13
1 10
3 15
3 10
1 8
2 12
3 5
3 8
2 15
3 1
1 5
3 5
3 12...

output:

0
1
2
1
0
1
2
3
3
3
3
3
3
1
1
3
3
3
3
2
2
1
2
3
3
3
2
2
2
2
3
4
4
4
4
2
4
4
3
3
3
3
3
6
6
4
4
4
4
4
1
1
1
3
3
2
3
3
3
3
3
3
3
3
4
4
4
6
6
4
6
4
4
3
3
4
4
4
3
2
2
1
2
3
3
2
3
5
5
6
6
7
6
6
7
6
7
6
6
6

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 10992kb

input:

15
7 1
9 11
10 1
9 13
15 11
10 4
10 6
6 13
4 2
5 15
12 9
14 11
3 11
8 11
100
1 12
1 15
1 8
1 13
1 10
3 13
1 11
1 1
1 13
3 8
2 4
1 6
3 12
3 6
1 14
3 13
3 10
3 1
1 13
1 8
2 6
3 6
1 9
1 6
2 1
3 13
1 2
3 8
3 14
3 1
1 12
1 5
3 4
3 12
1 10
3 10
3 9
3 6
1 3
1 9
3 11
2 13
2 10
2 1
3 15
2 15
3 10
1 6
2 10
3 ...

output:

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

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 1ms
memory: 12188kb

input:

15
4 7
13 2
8 15
5 11
14 4
5 9
15 2
14 12
6 14
11 10
11 8
3 13
12 9
1 12
100
1 10
2 11
1 7
2 5
1 2
1 14
1 15
3 5
3 10
1 9
3 9
1 1
2 3
1 13
1 5
3 5
2 4
2 6
3 15
2 12
1 10
3 1
3 4
2 4
3 7
3 3
3 4
1 8
2 7
3 14
3 12
2 14
2 1
2 12
2 9
3 14
2 15
3 11
3 9
3 13
2 9
1 14
3 15
3 8
2 4
3 2
1 2
3 1
3 2
3 10
3 1...

output:

0
1
2
2
3
3
3
3
2
2
2
2
3
3
3
3
5
6
6
7
8
7
5
7
6
5
4
4
5
2
2
2
2
2
2
2
4
3
3
3
3
6
4
4
4
4
4
4
4
3
0
1
1
1
1
1
1
1
1
1
2
1
4
5
2
2
4
4
2
3
5
5
5
5
5
3
3
3
2
3
3
4
3
3
4
5
5
5
3
5
5
4
4
4
2
2
2
2
3
3

result:

ok 100 lines

Test #9:

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

input:

15
11 1
11 9
14 5
14 7
12 6
9 7
10 14
13 5
6 2
4 13
4 3
3 6
6 8
15 3
100
1 3
2 13
2 4
1 14
1 15
3 14
1 11
2 9
2 5
3 4
1 10
3 11
1 7
3 7
1 2
3 3
3 13
3 9
1 1
1 11
1 8
2 9
1 13
3 11
1 12
3 12
1 11
3 1
2 3
3 9
1 4
3 13
2 7
3 8
3 4
3 5
3 3
1 9
2 3
3 2
1 12
1 6
3 10
2 13
3 9
3 6
3 13
1 4
2 8
3 3
1 13
3 4...

output:

0
1
1
2
2
1
2
2
2
2
3
2
3
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
6
5
5
5
6
6
4
4
2
2
4
3
4
4
3
3
3
3
3
5
5
3
3
3
3
3
3
3
4
4
4
3
3
2
2
2
2
2
2
2
2
3
3
3
4
4
4
7
4
4
4
4
4
4
3
2
3
5
5
5
5
5
5
5
5
4
3
3
3
3
3
2

result:

ok 100 lines

Test #10:

score: 0
Accepted
time: 1ms
memory: 12612kb

input:

15
14 12
4 1
8 7
9 5
3 7
2 12
1 13
2 10
9 12
7 9
7 4
6 10
11 3
15 13
100
1 5
1 13
2 10
2 3
3 3
2 14
1 2
1 9
3 9
3 5
3 2
3 14
2 9
3 13
1 15
3 9
2 11
1 4
3 4
1 7
2 13
2 14
3 11
3 10
3 14
1 3
3 13
2 9
3 9
3 7
1 6
1 10
3 15
2 15
2 5
1 2
3 6
3 3
3 2
2 13
1 6
2 14
2 2
3 13
3 6
3 2
1 12
2 4
3 4
2 11
3 10
2...

output:

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

result:

ok 100 lines

Test #11:

score: 0
Accepted
time: 2ms
memory: 11316kb

input:

15
13 11
11 8
12 8
12 5
5 6
6 14
7 14
7 9
4 9
4 3
10 3
15 10
15 1
2 1
64
1 9
1 11
2 10
1 14
3 11
2 12
2 2
1 5
2 8
2 7
3 14
3 7
1 15
2 11
2 14
3 10
1 3
3 2
2 2
3 3
3 9
2 9
3 2
3 11
1 2
3 2
1 4
1 6
2 1
2 10
1 11
3 1
1 2
2 7
3 8
3 14
3 9
3 4
1 8
3 2
3 5
1 13
3 15
3 10
3 6
3 11
2 9
3 13
3 9
2 9
1 11
3 7...

output:

0
0
1
1
1
2
2
2
2
4
4
2
4
4
6
4
4
3
4
4
4
4
3
3
3
3
3
3
4
6
7
6
6
6
6
6
6
4
4
4
4
4
3
3
1
1
1
1
1
1
1
1
2
2
4
4
3
1
3
3
3
3
3
5

result:

ok 64 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 9584kb

input:

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

output:

0

result:

ok single line: '0'

Test #13:

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

input:

2
1 2
47
1 2
3 2
1 2
1 1
3 2
2 2
3 1
1 1
3 2
3 1
1 1
3 1
1 1
3 1
2 1
3 1
1 2
2 1
3 2
1 2
3 2
1 2
3 2
1 2
3 1
2 1
3 1
3 2
1 2
1 1
3 2
1 2
3 1
3 2
2 1
1 2
3 1
3 2
1 1
2 2
3 1
2 1
3 2
2 2
3 2
3 1
2 1

output:

0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0

result:

ok 47 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 8740kb

input:

2
2 1
64
1 1
2 2
3 2
2 2
3 1
1 1
3 2
1 2
3 2
3 1
2 2
3 2
2 2
3 2
1 1
1 2
3 1
2 1
3 2
3 1
2 2
3 2
1 2
3 2
2 2
3 2
2 2
1 1
3 2
3 1
2 2
1 1
3 2
3 1
2 2
1 1
3 2
1 2
3 1
2 1
3 2
2 2
3 2
3 1
1 2
3 2
1 1
1 2
3 1
2 1
3 1
2 1
3 2
2 2
3 1
1 1
3 2
1 2
3 1
3 2
2 2
3 2
1 2
3 2

output:

0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0

result:

ok 64 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 12212kb

input:

3
2 1
1 3
55
2 2
1 3
3 2
2 1
3 1
2 2
3 2
1 1
2 2
3 1
3 3
2 1
3 2
2 3
3 1
2 1
3 3
1 2
1 3
3 2
3 3
2 2
3 1
3 2
1 1
3 1
2 3
3 3
2 1
3 1
2 3
3 3
1 2
3 2
2 2
1 1
3 1
1 1
2 3
3 3
1 3
3 2
3 3
3 1
1 1
1 3
2 2
3 2
1 2
3 2
3 1
3 3
1 3
1 1
3 1

output:

0
1
0
1
0
1
0
0
1
1
0
0
0
0
0
0
0
1
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0

result:

ok 55 lines

Test #16:

score: 0
Accepted
time: 1ms
memory: 11328kb

input:

14
14 13
13 11
5 13
13 4
3 13
10 13
13 7
13 6
12 13
1 13
8 13
13 9
13 2
97
2 9
1 5
1 2
2 4
2 12
3 4
3 5
1 11
1 5
2 6
2 14
3 14
3 2
3 6
2 6
3 9
3 5
1 1
2 10
3 1
1 13
3 6
1 8
3 13
1 2
1 14
3 12
2 4
2 13
2 3
1 1
2 12
3 10
3 4
2 7
3 1
3 12
3 3
1 3
2 10
2 1
1 4
2 5
3 3
2 9
1 6
3 4
2 4
3 4
3 10
3 14
1 4
2...

output:

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

result:

ok 97 lines

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 30
Accepted
time: 3ms
memory: 10080kb

input:

740
717 38
630 627
569 28
124 227
518 170
590 737
104 464
108 665
489 99
713 3
374 54
21 280
250 436
400 128
558 687
286 521
327 687
101 675
516 713
141 91
30 613
419 225
218 505
274 545
254 567
609 525
3 231
528 509
612 690
262 105
275 68
192 23
383 631
365 127
372 662
248 182
143 495
130 415
249 3...

output:

0
0
0
0
1
1
1
2
3
3
3
3
3
4
4
4
5
5
5
6
6
7
7
8
8
9
10
11
11
11
12
12
12
13
13
14
14
15
15
15
15
15
15
16
16
17
17
17
18
19
19
19
19
20
20
20
20
20
21
22
22
23
23
22
22
22
22
22
24
23
24
25
26
26
26
26
26
27
27
28
28
30
31
32
32
32
33
33
34
34
34
35
36
35
35
36
37
37
38
38
38
39
39
39
40
41
41
42
42...

result:

ok 747 lines

Test #18:

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

input:

931
627 537
349 208
170 929
859 502
311 847
576 917
73 266
550 460
924 311
107 638
440 176
866 795
536 615
844 605
325 775
27 276
2 663
294 123
608 357
857 880
678 391
241 725
492 366
829 501
123 921
633 176
605 746
924 910
526 370
193 107
158 166
142 536
817 171
440 422
267 390
664 703
441 687
762 ...

output:

0
1
1
1
2
2
2
2
3
4
4
4
4
4
4
4
6
6
6
7
7
7
7
8
8
9
9
9
9
9
10
10
10
10
11
11
11
12
12
12
12
14
14
14
14
14
14
16
17
17
17
17
18
18
18
18
18
18
18
18
18
18
19
19
20
21
22
23
23
24
24
24
24
25
24
24
24
25
26
25
25
25
25
25
25
25
25
25
25
25
25
25
26
26
26
26
27
27
27
27
25
25
26
26
26
27
27
27
27
27
...

result:

ok 730 lines

Test #19:

score: 0
Accepted
time: 2ms
memory: 11508kb

input:

784
391 610
341 483
415 48
156 42
337 734
339 95
110 4
388 420
408 656
284 447
552 112
781 108
761 603
188 121
267 633
595 169
129 470
112 194
275 195
197 174
477 245
118 766
158 324
670 562
10 429
634 450
649 465
316 424
149 52
25 612
240 639
508 535
348 78
337 120
689 450
538 178
234 240
206 516
7...

output:

0
0
0
0
1
1
1
1
1
1
1
2
2
2
2
2
2
3
4
4
5
7
7
7
9
10
11
12
13
13
13
13
13
13
13
13
14
15
15
16
17
18
18
20
20
20
20
20
21
20
20
20
20
21
21
22
23
23
24
25
24
24
24
24
24
25
26
26
26
27
27
27
27
28
28
28
28
29
29
30
30
31
33
33
34
36
36
36
37
38
38
38
41
41
41
41
42
43
43
43
43
44
44
45
45
45
45
45
4...

result:

ok 426 lines

Test #20:

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

input:

271
194 12
60 142
221 59
149 143
196 56
33 211
109 166
78 264
111 27
121 246
78 256
234 243
156 152
144 129
166 102
175 244
36 168
220 138
244 117
266 15
263 258
213 59
60 180
177 155
44 71
47 64
118 22
54 116
43 72
167 227
169 138
225 214
182 63
100 7
149 28
219 175
25 57
117 192
226 12
10 6
86 131...

output:

0
1
1
1
1
1
2
2
2
2
3
3
3
4
5
6
6
6
6
7

result:

ok 20 lines

Test #21:

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

input:

273
191 151
104 115
271 19
262 261
75 226
154 100
38 50
20 70
82 255
117 152
249 223
119 87
103 186
126 145
52 142
231 190
157 87
194 1
192 60
201 12
106 266
103 116
171 176
167 187
243 143
72 63
148 262
250 112
73 224
252 90
217 42
257 123
168 145
93 110
17 187
67 90
171 255
271 64
74 12
224 75
62 ...

output:

0
1
1
1
2
3
3
3
3
4
4
4
4
5
6
7
7
7
7
7
7
8
9
9
9
8
9
9
9
9
9
10
10
10
10
10
11
11
11
11
13
13
14
14
15
15
15
15
15
16
17
17
18
19
19
19
17
18
18
18
18
18
20
20
20
20
20
20
20
20
21
20
19
19
19
20
18
18
18
20
22
22
24
24
25
26
26
26
26
28
28
28
29
29
31
31
31
31
31
31
31
33
34
35
35
35
35
35
35
35
3...

result:

ok 387 lines

Test #22:

score: 0
Accepted
time: 2ms
memory: 9476kb

input:

337
281 1
334 256
301 20
260 129
24 120
45 73
123 95
138 276
275 271
71 202
182 85
320 159
72 223
332 299
287 165
63 328
282 197
104 252
253 182
29 212
65 201
133 65
115 306
46 10
237 269
182 69
32 252
240 304
257 71
326 214
84 282
322 253
164 298
22 127
66 303
165 307
143 188
137 319
280 82
274 282...

output:

0
1
1
1
1
2
3
3
3
3
3
4
4
4
4
5
5
5
5
5
5
6
6
7
7
7
8
9
9
9
9
9
9
9
9
9
9
11
11
11
14
15
15
17
17
17
17
16
16
16
16
16
16
16
16
17
17
17
17
18
18
18
18
18
18
18
19
19
19
19
19
20
20
20
21
21
21
21
22
24
25
25
26
25
25
25
24
27
27
28
28
30
30
31
32
33
33
31
31
32
32
32
32
32
32
33
33
34
34
34
34
34
3...

result:

ok 406 lines

Test #23:

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

input:

836
13 417
571 248
553 631
647 660
177 257
405 507
451 127
210 228
578 580
711 475
100 289
352 347
112 384
90 276
169 198
49 530
244 102
454 593
106 7
358 663
656 542
294 517
702 422
49 710
421 218
776 370
428 498
37 636
487 574
272 597
699 749
313 515
791 484
185 75
346 445
473 19
659 512
453 673
1...

output:

0
1
1
2
2
2
2
3
4
4
4
4
6
7
7
8
8
8
9
9
9
10
10
12
13
13
13
13
13
14
15
15
15
15
15
15
15
16
16
17
17
17
17
17
18
18
18
18
19
20
20
21
21
21
21
21
21
21
21
21
21
21
21
22
22
22
22
21
21
21
21
21
21
21
21
20
20
21
21
22
22
22
24
24
25
25
25
25
26
26
26
26
27
27
28
28
28
28
29
29
29
30
30
30
30
30
30
...

result:

ok 962 lines

Test #24:

score: 0
Accepted
time: 2ms
memory: 12252kb

input:

778
522 567
760 407
315 542
368 92
255 760
232 666
468 222
139 155
554 201
561 180
402 136
718 419
605 678
54 674
722 746
478 441
702 620
567 147
647 104
264 74
477 541
212 629
241 93
703 47
564 587
610 167
556 75
110 589
701 128
513 32
135 221
124 424
120 300
670 122
624 418
360 434
87 123
46 628
6...

output:

0
0
1
1
2
2
2
2
3
3
3
3
3
5
5
5
5
5
6
6
7
7
7
7
7
7
8
9
9
9
9
9
9
9
9
9
11
12
11
14
15
15
15
15
15
16
18
18
18
20
20
20
20
20
20
21
21
23
22
22
22
21
21
21
22
22
22
22
23
23
23
23
24
24
25
25
26
27
27
27
27
28
28
29
29
29
29
30
30
30
30
31
32
32
33
34
35
35
35
35
36
37
37
36
36
36
36
37
38
40
40
39
...

result:

ok 838 lines

Test #25:

score: 0
Accepted
time: 2ms
memory: 9904kb

input:

409
172 390
258 268
312 267
379 199
379 282
322 36
89 52
364 32
294 321
25 348
305 54
188 343
131 293
323 220
383 201
202 333
5 231
168 141
145 215
308 115
407 175
201 298
352 91
162 127
255 331
3 127
16 118
403 96
294 301
132 50
122 119
247 301
118 174
309 58
73 1
208 116
171 156
137 5
340 86
77 19...

output:

0
1
1
2
2
2
2
2
3
3
3
4
5
5
6
6
6
6
6
6
6
6
5
5
4
4
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
6
6
7
7
7
8
9
9
10
11
11
12
13
13
13
13
13
14
14
14
14
15
16
18
19
19
18
19
20
21
21
21
21
21
22
23
23
24
24
24
24
26
26
26
27
27
28
29
30
30
31
31
31
31
30
31
31
32
34
34
34
36
37
39
39
39
39
39
39
40
41
41
41
43
43
4...

result:

ok 753 lines

Test #26:

score: 0
Accepted
time: 2ms
memory: 12292kb

input:

435
392 219
251 271
361 365
282 190
343 388
272 224
355 240
333 29
115 127
148 42
70 195
266 9
20 120
226 321
277 184
107 12
46 228
378 342
97 94
244 58
220 416
45 365
435 63
140 357
399 273
203 264
317 266
318 307
400 312
141 106
295 326
8 43
33 101
125 118
329 290
353 12
163 341
347 160
33 269
238...

output:

0
1
1
1
1
1
1
1
1
1
2
3
4
4
4
4
5
7
8
9
10
10
10
10
10
10
10
11
11
11
11
11
11
12
12
14
14
15
15
15
15
15
16
16
17
17
18
18
18
18
19
18
20
22
22
22
22
22
22
22
22
23
24
24
24
24
24
24
24
24
24
24
25
25
23
23
23
23
22
23
24
24
25
25
25
25
27
28
27
28
29
29
28
28
29
29
30
31
31
31
32
32
35
32
32
31
31...

result:

ok 294 lines

Test #27:

score: 0
Accepted
time: 2ms
memory: 9992kb

input:

276
105 115
115 80
80 262
259 262
83 259
131 83
149 131
167 149
34 167
34 3
3 44
44 229
261 229
200 261
200 202
11 202
11 257
257 74
17 74
128 17
128 155
155 42
42 185
185 54
271 54
271 92
99 92
99 181
193 181
29 193
211 29
249 211
196 249
168 196
168 18
179 18
179 120
120 97
192 97
81 192
26 81
62 ...

output:

0
1
1
1
3
3
3
3
1
1
1
1
2
2
2
2
2
3
3
3
3
3
5
5
5
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
9
9
9
9
11
11
13
13
13
15
15
15
17
19
21
23
23
23
23
23
23
23
25
27
27
29
29
31
31
31
31
31
31
31
31
31
31
31
33
33
35
35
35
35
35
35
35
35
35
35
35
35
37
37
37
37
37
37
37
37
39
39
41
41
41
43
43
41
41
43
43
43
45
45
...

result:

ok 300 lines

Test #28:

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

input:

828
810 398
398 519
519 159
159 745
737 745
737 552
552 38
277 38
277 258
258 196
196 807
365 807
365 765
765 339
301 339
301 463
463 427
276 427
734 276
734 244
98 244
498 98
403 498
403 139
139 415
334 415
687 334
687 41
172 41
172 470
814 470
701 814
701 740
740 43
630 43
270 630
270 471
471 9
9 ...

output:

0
0
0
0
2
3
4
4
4
4
4
4
6
6
6
6
6
6
8
8
8
10
12
12
12
14
16
16
16
18
18
18
18
18
18
18
16
16
18
18
20
20
22
22
22
22
22
24
24
24
24
24
24
24
26
26
28
28
28
28
28
28
28
28
28
28
28
28
30
30
30
32
32
32
32
32
32
32
32
34
34
34
34
34
36
35
35
35
37
39
39
39
39
39
39
39
39
39
39
39
41
39
39
39
41
43
43
...

result:

ok 184 lines

Test #29:

score: 0
Accepted
time: 2ms
memory: 11672kb

input:

820
651 295
78 651
8 78
470 8
451 470
727 451
727 445
445 117
202 117
202 802
802 71
17 71
17 812
812 472
472 3
171 3
171 166
166 715
173 715
173 168
168 410
410 744
744 416
416 85
85 27
485 27
485 149
149 496
528 496
818 528
103 818
97 103
97 217
217 139
653 139
471 653
471 264
264 561
297 561
603 ...

output:

0
0
0
1
1
1
1
1
3
3
3
5
5
5
5
5
7
7
7
7
7
7
7
9
7
7
7
9
9
9
11
11
13
15
15
15
15
15
17
17
17
19
21
21
23
23
23
23
23
23
23
23
23
23
25
27
27
27
27
29
29
31
31
31
31
31
31
33
35
35
37
37
37
37
37
37
37
37
37
39
39
41
41
41
41
39
39
41
41
41
41
41
41
43
43
43
43
43
43
43
43
45
45
45
45
45
45
45
47
47
...

result:

ok 1000 lines

Test #30:

score: 0
Accepted
time: 2ms
memory: 10960kb

input:

220
164 138
81 138
174 138
213 138
60 138
16 138
138 32
26 138
138 44
138 29
45 138
138 182
13 138
138 151
138 6
138 93
206 138
80 138
138 90
138 207
138 150
138 100
8 138
138 106
138 27
138 212
217 138
161 138
138 122
138 133
94 138
120 138
138 42
121 138
5 138
136 138
138 135
138 66
138 51
55 138
...

output:

0
0
1
1
2
2
3
3
3
3
4
5
5
6
6
6
7
7
8
8
8
9
10
10
11
12
13
14
14
15
15
16
16
16
16
16
17
18
18
19
19
20
21
21
21
21
22
23
23
24
24
25
25
25
25
25
25
24
24
24
25
25
25
25
25
26
27
28
29
30
30
29
30
29
29
30
31
32
31
31
31
31
32
32
31
32
33
33
34
34
34
34
34
34
33
34
35
36
36
37
37
37
38
37
37
36
35
3...

result:

ok 561 lines

Test #31:

score: 0
Accepted
time: 2ms
memory: 11244kb

input:

800
72 287
596 287
693 287
655 287
168 287
325 287
287 795
774 287
287 118
429 287
287 575
287 247
287 155
119 287
287 447
287 374
287 378
344 287
587 287
287 607
287 389
324 287
287 137
51 287
287 215
287 142
260 287
149 287
287 245
192 287
287 577
287 559
573 287
159 287
287 502
754 287
346 287
28...

output:

0
0
1
1
1
1
1
1
1
1
1
2
3
4
5
6
6
7
8
8
9
9
10
10
11
12
13
14
14
14
15
16
16
16
17
18
18
18
18
19
19
19
19
19
20
21
22
22
22
23
24
25
25
25
25
26
27
28
29
29
30
31
31
32
32
33
33
34
34
34
34
34
35
35
34
35
36
36
36
36
37
38
38
38
38
38
38
37
38
39
39
39
39
39

result:

ok 94 lines

Test #32:

score: 0
Accepted
time: 2ms
memory: 11068kb

input:

292
107 53
176 53
53 1
267 53
157 53
53 213
53 19
53 43
53 172
53 169
2 53
63 53
53 150
188 53
53 255
53 50
225 53
53 158
53 216
38 53
272 53
121 53
53 92
49 53
3 53
53 209
53 75
143 53
95 53
275 53
53 178
53 282
53 236
31 53
53 263
119 53
290 53
226 53
53 214
53 10
53 229
262 53
149 53
193 53
23 53...

output:

0
1
1
2
2
3
3
3
4
4
4
4
5
5
6
7
7
7
8
8
9
9
9
10
11
12
13
13
14
15
15
16
15
16
16
17
17
17
17
18
18
18
17
18
18
18
18
18
19
19
18
18
18
19
19
19
19
20
21
21
22
23
23
23
24
25
25
25
25
25
25
25
25
24
23
23
24
25
26
27
28
28
29
30
31
31
32
32
32
32
32
31
30
29
29
29
30
31
31
32
33
32
32
32
31
31
31
32...

result:

ok 703 lines

Subtask #3:

score: 62
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #33:

score: 62
Accepted
time: 218ms
memory: 18416kb

input:

50516
80 25781
27578 39138
42128 34705
31858 9513
10874 47059
13846 22138
6315 27891
44827 23006
44544 26597
9205 1572
3857 18166
28675 43775
6486 15805
23949 32263
42848 17311
21484 155
27144 42220
30798 6582
3641 36355
1695 8694
15029 38762
38309 25196
45604 11904
13989 4290
39713 48125
36823 9220...

output:

0
1
1
1
1
1
1
1
1
1
2
2
3
3
3
4
5
5
6
6
6
7
7
7
7
7
8
8
9
9
10
11
11
11
11
12
12
12
12
12
12
13
13
13
13
13
13
13
13
14
14
15
15
15
15
16
16
16
16
16
16
17
17
17
17
17
17
17
18
19
19
19
19
20
20
20
20
20
21
22
24
24
25
25
25
26
26
26
27
28
28
29
29
30
30
30
31
31
31
32
32
33
34
34
35
36
36
36
37
37
...

result:

ok 71575 lines

Test #34:

score: 0
Accepted
time: 91ms
memory: 18316kb

input:

64751
25784 29845
52227 15232
40178 12895
31401 25552
49760 21095
19283 7328
33954 21031
39763 26317
56145 4943
7712 35309
18204 13805
49481 12750
46568 39408
12560 57550
45973 54006
54495 58323
15480 41671
33291 58422
42686 49521
22672 16677
12196 13804
8407 29885
21892 39635
43939 37544
33760 4399...

output:

0
1
1
2
2
2
2
2
2
3
4
5
6
6
6
7
7
7
8
8
8
9
9
9
9
9
10
10
11
12
13
13
13
13
13
13
14
14
14
15
16
16
17
18
19
19
20
20
21
22
22
22
24
25
25
25
26
26
27
27
28
28
28
28
28
28
28
28
28
29
30
30
31
31
31
32
32
32
33
34
34
34
34
34
34
34
35
35
35
35
35
36
37
37
37
38
39
39
39
40
41
41
42
42
43
43
43
43
43...

result:

ok 16393 lines

Test #35:

score: 0
Accepted
time: 198ms
memory: 17820kb

input:

32941
19262 18022
22650 26897
2720 5788
16303 30892
5160 9342
8004 3968
4830 7751
4232 6863
1500 962
11581 18075
16789 11665
26963 6829
16738 16646
16240 7963
8115 26066
18788 14299
17974 10711
28476 29408
6449 3806
1583 17763
6872 21285
22048 15108
15787 4465
1618 17166
5081 21121
864 21905
17720 1...

output:

0
1
1
1
1
1
2
3
3
3
3
3
3
3
4
4
5
5
5
6
6
7
7
7
8
8
8
8
8
8
9
9
9
9
10
11
11
11
11
11
11
11
11
12
12
12
12
13
13
13
13
13
13
14
14
14
15
15
15
16
17
17
18
18
19
19
19
19
20
20
20
20
21
21
21
21
22
22
23
24
25
26
26
27
28
28
28
28
28
28
28
29
29
29
29
29
30
31
32
32
32
32
33
33
34
35
34
34
35
36
37
3...

result:

ok 82276 lines

Test #36:

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

input:

89007
66462 52098
56686 36422
44080 28158
25374 88850
73329 68511
30076 47185
84566 68255
75056 33428
66924 12539
193 16757
21801 87680
24170 27567
76423 11834
80449 19896
7745 73892
15420 7079
83777 52300
26437 48481
19067 60147
80049 75833
80111 88527
11442 87475
75021 66542
21758 29281
20382 5232...

output:

0
1
1
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
7
7
7
7
8
8
8
8
9
9
10
10
10
10
11
11
11
11
11
11
11
11
11
12
13
13
13
13
13
14
15
15
16
17
17
17
18
18
19
20
21
21
22
22
23
23
24
24
25
26
27
28
29
30
30
30
31
31
31
31
32
32
32
32
32
32
33
34
35
35
36
36
37
37
38
38
38
38
38
38
38
38
38
39
39
39
39
39
39
4...

result:

ok 96777 lines

Test #37:

score: 0
Accepted
time: 23ms
memory: 15512kb

input:

30249
30050 7427
3523 1139
1712 12940
25901 3227
4748 15102
26900 5746
20432 5216
16950 21693
48 22235
16407 13800
29305 24899
16654 21257
16651 23443
6892 11891
1252 25637
23705 5939
29630 23657
28013 24323
365 20625
28835 28755
26823 3781
12543 22494
19947 28906
529 2364
9553 18068
11995 14399
143...

output:

0
1
1
1
1
2
2
3
3
3
4
4
4
4
5
5
5
6
7
8
8
8
9
9
9
10
11
11
11
12
12
13
13
13
14
14
14
14
14
14
14
14
15
16
16
16
17
18
19
19
20
20
20
21
21
22
22
22
22
22
22
23
23
23
24
24
24
24
25
26
26
26
26
27
28
28
28
28
29
29
29
30
31
31
31
32
32
32
32
32
32
33
34
35
36
36
36
36
36
36
36
36
36
36
36
37
38
38
3...

result:

ok 246 lines

Test #38:

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

input:

100000
61089 12482
40773 93210
19867 2482
11583 16468
900 90526
4189 11491
73272 16435
98090 32729
4401 14531
44086 77704
62195 58662
17364 52041
55521 36051
68027 97241
68645 93707
58310 27575
34668 92335
78932 42120
25896 84901
26120 80980
8076 87255
98121 57286
56660 71635
86148 31471
91962 33036...

output:

0
1
1
1
2
2
2
2
2
2
3
3
4
5
5
5
5
5
6
7
7
7
7
7
8
8
8
8
8
9
9
9
10
11
11
12
13
13
13
13
13
13
13
13
14
15
16
17
17
18
18
18
19
20
20
21
22
22
22
22
22
23
23
23
24
24
24
24
24
25
26
26
26
26
26
27
27
27
27
28
28
29
29
30
30
31
31
31
31
31
32
32
33
33
34
35
35
36
37
37
37
37
38
38
38
38
39
39
39
40
40...

result:

ok 100000 lines

Test #39:

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

input:

100000
79591 47734
63178 11310
451 72892
74033 90949
44881 37493
15808 90886
43652 25218
71981 93702
86518 50664
85329 7898
68706 79983
26123 73502
55273 76390
92925 90193
8878 74141
60909 98135
92698 51881
90886 49942
67160 42339
67892 10809
98714 13417
28107 22896
95346 68892
18561 19854
46618 354...

output:

0
0
1
1
1
1
1
2
3
3
3
3
3
3
3
4
5
5
6
6
6
6
6
7
7
8
8
8
8
8
9
9
9
9
10
11
11
12
12
13
13
14
14
14
14
15
15
16
16
16
17
17
17
17
18
18
19
20
20
20
20
21
22
22
22
23
24
25
25
25
25
25
25
25
25
25
26
27
28
28
28
29
29
30
30
31
31
31
31
31
32
33
34
34
35
36
36
37
37
37
38
38
39
40
40
40
40
41
41
41
41
4...

result:

ok 100000 lines

Test #40:

score: 0
Accepted
time: 370ms
memory: 24368kb

input:

100000
6571 54579
90042 40283
92739 95316
87672 59038
39890 10072
71534 97090
52505 22498
36012 76267
33177 44027
18568 76005
34524 91919
32921 27517
72970 79694
87007 70789
58453 65003
60217 34324
95950 960
53293 37860
35725 18985
57188 9811
22669 41540
71530 92066
76397 39959
44754 81337
1744 8289...

output:

0
0
0
0
0
0
0
0
0
1
1
2
3
4
4
4
4
4
4
5
5
5
5
5
6
7
7
7
8
8
9
9
9
10
10
10
10
11
11
12
12
12
12
12
13
13
14
15
15
16
16
16
17
17
17
17
17
17
18
18
18
19
20
21
21
21
21
21
22
22
22
23
24
24
24
24
25
25
26
26
26
26
26
26
26
26
26
27
28
28
29
30
30
30
30
30
31
31
32
33
33
33
34
34
34
34
34
35
36
36
36
...

result:

ok 100000 lines

Test #41:

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

input:

100000
84846 36443
30407 16881
46152 42374
99655 48568
8319 28054
43251 17157
28312 66561
78196 1953
79874 18303
49497 32982
48972 53037
38482 692
33033 59981
33720 67982
68883 47396
65315 43451
60997 71291
51410 55285
69600 14527
45671 95645
1287 87010
81512 15093
13923 23991
33824 14948
86591 7877...

output:

0
0
1
2
2
2
2
2
3
3
3
5
5
5
5
5
6
6
6
6
7
7
7
8
8
9
10
10
10
10
10
10
10
10
10
10
11
12
12
12
12
12
13
14
15
16
16
16
16
16
17
17
17
17
17
18
18
18
18
18
18
19
20
20
20
20
20
21
22
22
22
22
22
23
24
25
25
25
26
27
28
28
28
28
28
28
28
28
28
28
28
28
28
29
29
30
30
31
31
31
31
32
33
33
33
33
34
35
35...

result:

ok 100000 lines

Test #42:

score: 0
Accepted
time: 355ms
memory: 25672kb

input:

100000
55409 88254
70877 69362
70118 54535
38530 49148
16433 80816
33695 32076
59078 512
63318 72299
75959 99423
12910 16389
20575 39229
26770 10633
93850 63820
89235 57997
21642 39105
1602 65064
9684 51863
7575 77110
13601 83307
12909 7992
7774 15649
96931 76081
22940 47422
83356 86122
78544 64619
...

output:

0
1
1
1
1
2
3
3
3
4
5
5
6
6
7
7
7
7
7
7
7
7
7
7
7
7
8
9
9
10
11
11
12
12
12
12
12
13
13
13
13
14
14
14
14
14
15
16
17
17
17
17
17
17
18
18
19
19
20
20
20
21
22
22
22
22
22
22
22
23
23
23
24
24
24
25
25
26
26
26
27
27
27
27
28
28
28
29
30
31
32
32
33
34
34
34
34
34
35
36
36
36
37
37
38
38
38
38
39
39...

result:

ok 100000 lines

Test #43:

score: 0
Accepted
time: 358ms
memory: 26060kb

input:

100000
13654 17718
54743 97906
42454 86734
69907 30550
21140 25734
76140 73805
93465 3987
93069 96061
71152 26254
94085 50769
58539 29718
77765 95673
94812 24393
22596 43208
59805 45519
32891 62517
96009 31280
650 10042
22528 92440
34865 75448
3975 11834
93271 23761
43654 98218
73287 84845
28328 161...

output:

0
1
1
1
2
3
4
4
5
5
5
5
6
6
6
6
7
7
7
7
8
8
9
9
9
9
9
10
11
11
11
12
13
13
13
13
13
13
13
14
14
14
15
15
15
16
16
16
16
16
17
18
19
19
19
19
20
20
20
20
20
20
21
21
21
21
21
22
22
22
23
23
23
23
23
23
23
23
23
23
23
23
24
25
25
25
25
25
25
26
27
27
28
28
28
28
28
29
29
29
30
30
30
30
30
31
33
33
33
...

result:

ok 100000 lines

Test #44:

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

input:

100000
64631 30732
39826 35230
74404 87158
16077 96860
29412 49413
38455 5976
93264 44564
55353 27568
98241 54915
44415 90182
4119 44535
64252 21631
59062 52215
7845 36807
75876 47280
87409 97900
73997 5683
82560 27487
61695 59698
1457 3318
70478 60710
19977 36333
49169 80076
13235 60352
96163 27203...

output:

0
0
0
0
0
0
0
1
1
1
1
1
2
2
3
4
5
6
7
7
7
7
8
8
8
8
8
8
9
9
10
11
11
12
12
12
13
13
13
13
13
14
14
14
14
15
15
15
16
17
18
18
19
19
19
19
20
20
20
21
21
21
22
23
24
25
25
25
25
25
26
26
26
26
26
27
29
29
29
29
29
29
29
29
29
29
29
29
29
29
29
29
29
29
30
30
30
30
31
32
32
33
33
33
33
33
33
33
34
34
...

result:

ok 100000 lines

Test #45:

score: 0
Accepted
time: 365ms
memory: 24504kb

input:

100000
36823 8393
92954 58110
66049 21194
38476 6391
67138 83010
45204 99963
40738 5928
32508 63535
14092 43636
68403 18880
92113 61892
29738 64893
27845 81305
10167 32921
85313 52919
15541 91562
74239 82281
4995 96269
98081 10650
64641 50975
2859 9116
95830 92005
59300 91109
17004 78533
94809 40910...

output:

0
0
1
2
2
2
2
2
3
4
4
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
7
7
8
8
9
9
9
10
11
12
12
13
13
13
14
15
15
16
16
16
16
16
17
18
19
19
19
20
20
20
20
20
21
21
21
21
21
22
22
23
23
23
23
23
24
25
25
26
26
26
26
26
26
27
27
27
27
27
28
28
28
29
29
29
30
30
31
31
31
31
31
32
33
33
33
34
34
35
35
36
36
37
38
38
3...

result:

ok 100000 lines

Test #46:

score: 0
Accepted
time: 367ms
memory: 25860kb

input:

100000
63142 74339
89128 77198
32785 64047
76775 40174
16509 43835
34424 63119
14990 81905
91152 95802
92874 90747
54952 84349
62844 41290
83358 9131
34708 68594
72659 94617
21029 13163
5164 15618
46982 62770
31602 81348
96178 57797
82993 3329
84648 40747
78780 46687
93547 97098
33895 83529
67522 39...

output:

0
0
0
0
0
0
1
1
1
1
2
2
2
3
3
3
4
4
5
5
5
6
6
7
7
7
8
8
8
9
10
11
11
11
11
11
12
12
13
14
14
14
15
16
17
17
17
17
17
18
19
21
21
22
22
22
22
22
23
24
24
24
24
24
24
24
24
24
24
24
24
25
26
27
27
27
27
27
27
28
28
28
28
28
28
28
28
28
28
28
28
29
29
30
30
31
31
31
32
33
33
34
35
36
36
36
36
37
37
37
...

result:

ok 100000 lines

Test #47:

score: 0
Accepted
time: 365ms
memory: 26196kb

input:

100000
99595 76636
33222 54597
60723 6233
4209 19506
29822 55272
71045 20181
38523 51995
12612 33189
92220 88908
5779 40219
96185 53750
97883 60695
62573 37753
68810 13273
94456 54426
69199 6120
13499 85216
52992 29135
79167 14232
98231 27387
28014 57395
95025 57982
22936 78563
12654 45999
26064 715...

output:

0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
3
4
4
4
4
5
6
6
6
7
7
7
8
9
9
9
9
9
11
11
11
11
12
12
12
13
13
14
15
15
15
16
16
16
16
16
17
17
17
17
17
18
18
18
18
18
19
20
21
22
22
22
23
23
23
23
23
24
24
24
25
25
25
25
25
25
26
27
27
27
28
28
29
29
29
29
29
29
29
29
29
29
29
30
30
31
31
32
32
33
34
35
35
36
36
36
...

result:

ok 100000 lines

Test #48:

score: 0
Accepted
time: 122ms
memory: 24564kb

input:

71306
63009 49939
64762 63009
63009 10710
41984 63009
63009 23065
63009 8743
63009 44598
63009 46684
41843 63009
63009 15186
63009 55731
63009 37756
55306 63009
63009 27122
62430 63009
30806 63009
63009 50237
25264 63009
40532 63009
63009 54237
30716 63009
61114 63009
21150 63009
11807 63009
63009 5...

output:

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

result:

ok 67069 lines

Test #49:

score: 0
Accepted
time: 140ms
memory: 25256kb

input:

91466
44265 64887
44265 32833
44265 21535
14047 44265
81215 44265
17730 44265
44265 46466
57744 44265
20546 44265
44265 28019
44265 84659
44265 29214
50215 44265
45394 44265
44265 47447
30108 44265
49967 44265
58742 44265
27319 44265
4221 44265
19260 44265
14999 44265
41032 44265
44265 67361
79693 4...

output:

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

result:

ok 67346 lines

Test #50:

score: 0
Accepted
time: 39ms
memory: 16680kb

input:

17122
10088 13380
10088 120
10088 10507
1995 10088
7836 10088
2317 10088
15128 10088
10088 1300
13159 10088
10088 6053
10088 9018
478 10088
4858 10088
9608 10088
10088 13844
7745 10088
10312 10088
8016 10088
1092 10088
10088 8756
6421 10088
10088 15568
10088 2865
2426 10088
10088 10255
6894 10088
10...

output:

0
0
0
1
2
2
3
4
4
5
5
5
5
6
6
7
8
9
9
9
9
10
10
10
10
11
11
12
13
13
13
14
15
16
16
17
18
18
18
18
18
19
20
20
20
20
21
21
21
21
21
22
21
21
21
21
21
22
22
23
23
23
24
24
25
25
26
26
26
27
28
28
28
29
29
30
30
31
31
32
33
34
34
34
34
35
35
36
37
37
38
38
39
40
41
42
43
44
44
45
46
47
47
47
47
48
49
...

result:

ok 33978 lines

Test #51:

score: 0
Accepted
time: 60ms
memory: 17740kb

input:

35306
30874 10771
30874 22298
30874 22756
30874 5898
12173 30874
11865 30874
30874 5423
30874 13729
30874 25679
27850 30874
30874 11012
30874 20936
30874 4182
31875 30874
15517 30874
30874 2415
30874 13
30874 17447
29626 30874
2533 30874
22863 30874
30874 12220
27763 30874
20085 30874
30874 27247
35...

output:

0
0
0
1
2
3
3
4
4
5
5
6
6
6
7
8
8
8
8
8
9
9
10
11
11
12
13
13
14
14
15
15
16
17
17
18
18
18
18
19
20
20
20
20
20
20
20
21
22
23
23
24
25
25
25
26
27
27
28
28
28
29
29
29
30
30
31
32
32
32
33
33
33
34
34
35
35
35
36
36
37
37
37
37
38
39
40
41
42
42
43
44
44
44
44
45
46
46
46
46
47
48
48
49
49
50
50
5...

result:

ok 30800 lines

Test #52:

score: 0
Accepted
time: 21ms
memory: 12152kb

input:

18248
17968 9870
6349 17968
17968 2862
17968 14692
15172 17968
17968 8772
17968 5995
17968 16975
16891 17968
17968 1750
12208 17968
1452 17968
4597 17968
17968 11858
15197 17968
16778 17968
17968 698
17968 7377
17968 1051
17968 3267
15593 17968
9808 17968
17968 239
17968 5663
16612 17968
2524 17968
...

output:

0
0
1
2
2
2
3
4
4
4
5
5
6
7
7
8
8
9
9
10
10
10
10
11
12
12
13
13
13
14
14
14
15
15
15
15
16
16
16
17
17
18
18
19
20
20
21
22
22
22
22
22
22
23
24
24
24
25
26
26
26
26
27
28
28
28
28
28
28
28
29
29
29
29
29
30
30
30
30
31
31
32
32
33
34
35
36
36
37
37
37
38
39
40
41
41
42
42
42
42
42
42
43
44
45
45
4...

result:

ok 12128 lines

Test #53:

score: 0
Accepted
time: 182ms
memory: 23552kb

input:

99277
86687 19783
60338 22870
92679 28565
83393 30034
6102 31109
61831 68830
9785 2319
52331 82668
60595 22858
2176 75676
71188 61193
44356 37746
18720 29842
24200 4872
3335 48253
43339 47399
53206 90118
74242 43396
28605 42402
77705 48706
37868 51780
70225 55437
37950 14619
34216 31227
9084 92532
1...

output:

0
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
3
3
3
4
4
5
5
5
5
6
6
7
7
7
8
9
9
9
9
9
10
11
11
11
11
11
11
12
13
13
13
14
14
14
14
15
15
15
15
16
17
17
17
17
18
18
19
20
20
21
21
22
22
22
22
23
23
24
25
25
26
27
28
29
29
30
30
30
30
31
31
31
31
31
31
31
31
31
31
31
31
32
32
32
32
32
32
32
33
33
34
34
34
35
35
35
...

result:

ok 34808 lines

Test #54:

score: 0
Accepted
time: 119ms
memory: 17360kb

input:

41475
24075 31245
32507 7214
12739 26155
39406 17855
32750 5055
36664 26450
40683 13541
4256 29146
17435 35793
19689 27888
23572 18901
29810 8743
15641 14546
17262 35685
17344 38600
26505 24939
10079 34123
26149 27409
4332 12700
7652 32082
29327 28559
2590 40770
26563 12112
13029 24389
23477 34415
1...

output:

0
0
1
2
2
2
3
4
4
4
5
5
5
6
6
6
6
6
6
7
7
8
8
9
9
9
9
9
9
9
9
9
10
11
11
12
12
12
13
13
13
13
14
14
14
15
15
16
16
17
17
17
17
18
19
19
20
21
22
22
22
22
22
22
22
22
22
22
23
23
23
23
23
24
24
24
24
24
25
26
26
27
28
28
28
28
28
28
28
28
28
28
29
29
29
30
30
31
31
31
31
31
31
32
32
32
32
32
33
33
34...

result:

ok 37027 lines

Test #55:

score: 0
Accepted
time: 300ms
memory: 21972kb

input:

66531
11043 53806
24827 29883
8058 19534
62804 1115
56758 18331
50034 49073
50130 10189
17061 50179
25716 57268
22896 21444
63045 58968
15630 51371
53775 28490
26686 13511
38259 44753
16448 29835
44980 47920
18938 54902
53997 56038
16699 8123
36516 56502
9631 15533
39770 28220
57415 37485
27552 2695...

output:

0
0
0
1
1
2
3
3
3
3
4
4
5
5
5
5
5
6
6
7
7
8
8
8
9
10
10
10
10
10
10
10
11
11
12
13
13
13
14
14
14
14
14
14
15
15
16
17
18
18
18
18
18
19
19
19
19
20
20
21
22
22
23
24
25
25
25
26
27
28
28
28
28
29
29
29
29
30
30
31
31
31
31
31
31
32
32
33
33
33
33
33
33
33
33
34
35
36
36
37
37
37
38
39
39
40
40
40
4...

result:

ok 99179 lines

Test #56:

score: 0
Accepted
time: 188ms
memory: 18416kb

input:

43952
34667 20213
16011 904
36060 17876
40426 17735
14298 26835
19546 34285
17222 32754
27101 25738
7156 6832
13018 41457
30684 33987
14282 11369
42827 804
7837 25164
39856 39136
12131 22747
27919 30216
9908 30456
22705 21042
37321 37370
23842 12661
10992 13885
36258 12689
15659 36767
12069 3205
243...

output:

0
0
1
1
1
1
1
1
1
2
3
3
3
3
3
3
4
4
4
4
4
5
6
6
7
7
7
7
7
7
7
8
9
9
9
10
11
12
12
12
12
12
13
13
13
13
13
13
13
13
13
13
14
14
14
14
14
14
14
14
14
14
14
15
16
16
16
16
16
16
16
16
17
17
17
17
18
18
18
19
19
20
20
20
20
21
22
22
23
23
24
25
26
27
28
29
30
30
31
32
32
32
33
34
35
35
36
35
36
37
37
37...

result:

ok 63798 lines

Test #57:

score: 0
Accepted
time: 255ms
memory: 23468kb

input:

89393
45348 59642
18683 74373
57905 55021
22451 43313
11569 33508
54035 80705
47110 28069
34424 13516
66367 10409
32607 15663
72491 16697
87732 24097
15470 24282
43805 74220
78833 10084
61753 17255
26223 6403
61748 887
12360 855
53104 42416
632 20646
49250 76323
81160 57574
41091 8157
34161 2924
238...

output:

0
1
1
2
2
2
3
3
4
4
5
5
5
4
4
4
4
4
5
5
5
5
6
6
6
6
6
7
7
8
9
9
9
9
10
10
11
11
11
11
12
12
12
13
14
14
14
15
15
15
14
14
15
15
16
16
16
16
17
18
18
17
17
17
17
17
17
18
18
18
18
18
19
19
19
20
20
20
21
22
22
22
22
23
24
24
24
24
25
25
26
26
26
26
27
26
27
27
28
29
29
29
28
28
28
28
28
28
28
28
28
2...

result:

ok 73941 lines

Test #58:

score: 0
Accepted
time: 33ms
memory: 18476kb

input:

41827
2562 6004
39588 6004
39259 6004
70 6004
6004 20220
8283 6004
7772 6004
23520 6004
16997 6004
6004 9032
21510 6004
6004 997
6004 8293
516 6004
6004 31829
6004 35947
21758 6004
22422 6004
14087 6004
5894 6004
17442 6004
6004 37292
27612 6004
6004 30472
6004 4774
24770 6004
6004 41165
23623 6004
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 7638 lines

Test #59:

score: 0
Accepted
time: 52ms
memory: 18228kb

input:

31416
8043 6909
16254 6909
10858 6909
6909 9520
29349 6909
6909 20451
6909 13145
6909 25110
22546 6909
3615 6909
13519 6909
6909 28563
15428 6909
6909 26064
6909 24246
22742 6909
6909 11747
25075 6909
25858 6909
31238 6909
6909 13438
26445 6909
24747 6909
24435 6909
15948 6909
6909 4524
6909 16417
6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 39615 lines

Test #60:

score: 0
Accepted
time: 110ms
memory: 25888kb

input:

80207
77804 48845
48845 31941
48845 55434
48845 9042
48845 74694
48845 59553
55384 48845
20227 48845
48845 30634
48845 12646
9623 48845
48845 57500
48845 33353
48845 80133
48845 48022
30698 48845
25051 48845
51964 48845
48845 24187
31855 48845
48845 25627
48845 47017
71512 48845
48845 31340
49037 48...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 78603 lines

Test #61:

score: 0
Accepted
time: 129ms
memory: 25152kb

input:

83267
76859 63057
76859 63818
51658 76859
28077 76859
76859 28504
76859 54657
53376 76859
51818 76859
4952 76859
8256 76859
76859 3907
76859 72493
52803 76859
76859 77752
76859 1700
10934 76859
76859 79743
76859 4891
76859 2858
76859 12405
76859 32901
46680 76859
7313 76859
76859 69020
76859 27653
7...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 87413 lines

Test #62:

score: 0
Accepted
time: 87ms
memory: 24224kb

input:

68648
57337 22055
35648 22055
36413 22055
38493 22055
22055 58900
22055 60249
22055 39803
22055 60392
22055 24903
56603 22055
58889 22055
27543 22055
22055 11054
29248 22055
22055 13597
26653 22055
54338 22055
22055 63914
61864 22055
60623 22055
10433 22055
22055 50922
22055 63056
33437 22055
22055 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 46420 lines

Test #63:

score: 0
Accepted
time: 41ms
memory: 26540kb

input:

54669
37602 23791
18048 37602
43468 18048
43468 39298
30872 39298
9482 30872
28693 9482
28693 15743
6424 15743
24641 6424
29731 24641
16261 29731
16261 52775
18540 52775
16153 18540
16153 19839
33457 19839
6724 33457
6724 33759
18887 33759
42784 18887
42784 336
336 37806
37806 29905
29905 24247
2424...

output:

0
0
1
1
0
0
0
0
0
0
2
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
2
0
0
0
0
0
0
0
2
2
2
1
0
0
0
1
2
2
1
0
0
1
0
0
1
1
1
1
0
0
0
1
1
2
2
2
2
2
2
2
0
2
2
1
2
3
1
1
3
3
2
1
2
0
1
1
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
2
1
0
1
0
1
1
2
2
2
0
0
0
0
0
1
0
0
1
1
0
0
2
1
0
0
...

result:

ok 15887 lines

Test #64:

score: 0
Accepted
time: 50ms
memory: 31736kb

input:

58788
53833 50471
1193 50471
48316 1193
50905 48316
40613 50905
40613 50866
40524 50866
45132 40524
45132 40322
40322 50903
50903 25666
34442 25666
34442 18939
38484 18939
38484 54990
54990 28856
43363 28856
43363 34229
34229 28579
28579 57401
34885 57401
34885 19689
49476 19689
49476 26210
23429 26...

output:

0
1
2
1
1
1
0
1
1
0
0
0
1
2
1
1
2
2
2
1
1
0
0
1
2
3
1
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
1
1
2
2
1
1
0
0
0
0
0
1
3
3
1
1
1
0
0
0
0
0
0
0
0
1
3
2
3
2
2
1
1
1
1
2
1
2
2
1
1
2
0
0
0
0
0
0
1
0
0
0
1
1
2
1
1
0
0
0
0
0
2
2
0
2
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
1
2
2
2
0
0
1
0
1
...

result:

ok 20098 lines

Test #65:

score: 0
Accepted
time: 73ms
memory: 44008kb

input:

98779
20441 91794
91794 13229
13229 10692
90065 10692
28517 90065
81775 28517
34689 81775
34689 28790
28790 17281
17281 3495
40355 3495
8931 40355
8538 8931
8538 964
83889 964
83889 22016
95225 22016
9685 95225
4296 9685
70270 4296
27462 70270
27462 68599
68599 11539
11539 20325
20325 24211
77531 24...

output:

0
0
0
1
1
1
1
1
2
0
0
0
0
0
0
1
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
1
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
1
1
1
1
1
1
1
0
1
0
0
1
1
1
1
1
1
1
1
2
2
1
2
0
0
0
0
0
1
1
1
0
0
1
1
2
0
2
1
2
0
1
1
3
1
1
1
0
0
0
0
0
1
1
2
1
1
2
2
2
2
2
1
...

result:

ok 12700 lines

Test #66:

score: 0
Accepted
time: 39ms
memory: 16440kb

input:

20663
17850 18118
15163 17850
11431 15163
11431 10728
11805 10728
11805 18328
18328 11088
11088 13623
20367 13623
9279 20367
9279 1850
1850 2779
3814 2779
15636 3814
15636 9439
9439 19149
19149 2366
2366 12871
13363 12871
13363 13980
13980 16717
2098 16717
2098 484
484 1137
1137 18089
10866 18089
10...

output:

0
1
2
2
2
2
1
1
1
1
1
1
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
3
3
2
0
0
0
0
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
2
2
0
0
1
1
1
0
1
1
1
0
1
2
0
0
0
1
1
1
1
1
1
1
1
1
1
1
2
1
0
0
0
0
0
0
1
0
0
1
0
1
1
1
3
1
2
1
1
1
1
1
1
1
1
0
0
0
0
2
2
2
2
1
2
2
2
1
1
1
1
1
0
1
1
1
1
1
1
2
1
2
0
0
1
0
1
2
2
0
0
0
0
...

result:

ok 58653 lines

Test #67:

score: 0
Accepted
time: 62ms
memory: 34776kb

input:

67446
12735 48517
12735 17324
56336 17324
56336 65020
65020 46697
3555 46697
51336 3555
51336 33642
33642 62256
21308 62256
21308 25802
61257 25802
42827 61257
13974 42827
13974 12092
39820 12092
52639 39820
38074 52639
38074 59424
59424 8945
8945 26631
26631 8141
8141 19449
29241 19449
29241 65962
...

output:

0
0
0
0
0
1
0
1
1
1
1
1
2
2
2
2
2
2
2
0
0
0
1
1
0
1
2
1
1
1
2
3
1
0
0
0
1
1
1
2
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
2
2
2
0
2
3
3
3
2
2
2
0
0
1
0
0
0
0
1
3
3
3
3
3
2
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
1
1
3
1
1
0
0
0
0
1
1
2
2
0
0
0
2
0
0
0
0
0
1
0
0
1
1
1
3
2
2
1
0
1
2
2
2
2
1
1
1
...

result:

ok 30165 lines

Test #68:

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

input:

99776
652 84599
54308 84599
86978 54308
86978 30490
46456 30490
43610 46456
43610 66429
50982 66429
76029 50982
80331 76029
84543 80331
84543 40157
40157 42038
61985 42038
61985 39931
2932 39931
2932 8426
8426 58954
52538 58954
52538 65420
65420 91656
91656 72068
68956 72068
61323 68956
61323 58700
...

output:

0
1
1
2
2
2
1
1
2
1
0
2
2
2
2
1
2
2
2
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
2
2
2
2
2
2
0
0
0
0
1
2
2
2
1
1
1
1
1
1
3
3
2
2
3
3
2
2
0
1
3
1
1
1
1
1
1
1
0
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
3
1
3
3
3
3
3
3
3
2
2
1
1
1
1
1
1
2
2
2
4
4
4
4
2
2
2
2
2
2
2
2
4
4
2
2
2
2
4
2
2
2
2
2
...

result:

ok 67004 lines

Test #69:

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

input:

5354
388 639
918 388
433 918
2848 433
3353 2848
3353 4670
4670 2511
2511 793
4803 793
2631 4803
2631 3021
3021 2873
2431 2873
1189 2431
2609 1189
2609 4577
4298 4577
1924 4298
2968 1924
2968 3314
3314 5237
3293 5237
3900 3293
3900 1509
3710 1509
3429 3710
3429 51
51 366
366 1057
1057 581
581 2688
15...

output:

0
0
0
0
0
1
0
0
2
2
2
4
5
5
3
2
2
4
2
2
4
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
0
1
1
2
1
1
0
0
1
1
3
2
2
2
2
2
2
1
0
0
0
2
2
0
0
0
0
0
0
0
0
0
0
0
0
2
4
6
6
4
6
4
4
6
4
6
6
6
4
4
2
0
0
0
0
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
0
1
1
2
2
2
4
4
2
2
2
2
2
2
2
2
2
2
0
2
4
2
2
2
2
2
2
2
0
0
0
2
2
2
4
2
2
2
2
3
3
...

result:

ok 35533 lines

Test #70:

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

input:

609
219 257
219 566
566 578
578 73
386 73
386 129
129 523
536 523
536 299
572 299
50 572
50 519
519 437
7 437
7 55
116 55
101 116
378 101
434 378
434 473
473 549
609 549
609 409
427 409
267 427
297 267
501 297
469 501
33 469
33 553
399 553
177 399
177 56
533 56
533 408
176 408
352 176
352 242
376 24...

output:

0
0
0
0
0
1
2
2
1
1
0
1
2
2
4
4
4
4
2
1
3
5
6
4
2
1
0
2
2
4
4
4
3
4
2
2
2
2
2
4
2
0
0
0
1
1
2
2
2
2
1
1
1
1
2
2
2
2
3
3
3
3
3
3
1
1
1
1
1
1
1
1
0
1
2
2
2
2
2
2
4
2
2
2
4
4
4
3
3
3
5
5
3
2
2
2
2
3
3
3
3
3
3
2
1
2
2
2
2
2
1
1
1
1
1
3
4
4
4
2
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
2
2
1
1
3
2
2
3
3
3
5
4
3
2
3
...

result:

ok 9499 lines

Test #71:

score: 0
Accepted
time: 49ms
memory: 24576kb

input:

39304
8054 33585
35776 33585
2060 35776
20417 2060
20417 33769
34423 33769
33966 34423
12431 33966
12431 37091
25306 37091
25306 5438
5438 12233
38094 12233
38094 18073
18848 18073
15508 18848
15508 12883
12883 14098
1813 14098
1813 8502
24085 8502
24085 694
11046 694
11046 19742
19742 12976
12976 2...

output:

0
1
2
2
2
2
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
3
2
2
4
4
3
3
4
3
4
5
3
1
1
1
1
0
0
0
0
0
0
0
0
1
2
2
1
2
1
1
1
1
1
1
2
2
2
2
2
4
5
5
5
3
3
5
5
3
3
3
1
1
1
3
3
3
3
5
3
3
3
3
3
3
1
1
1
1
3
3
3
3
1
1
1
1
1
0
0
0
2
2
2
2
2
2
2
2
2
2
2
2
1
1
3
3
3
3
3
1
0
0
0
2
4
6
5
6
6
4
2
4
3
3
...

result:

ok 43100 lines

Test #72:

score: 0
Accepted
time: 74ms
memory: 40804kb

input:

73672
21791 31052
36958 31052
17765 36958
17765 50490
65945 50490
65945 56562
56562 49116
2327 49116
53570 2327
29057 53570
29057 7270
7270 49436
49436 36098
36098 15992
15992 68403
29632 68403
29632 26491
26491 25926
25926 35254
36418 35254
36418 49988
65241 49988
3945 65241
19641 3945
27287 19641
...

output:

0
1
0
1
1
1
2
2
1
3
3
3
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
3
3
1
1
0
1
0
2
2
2
2
1
1
1
2
1
0
1
1
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
3
3
3
3
1
1
1
1
1
1
1
1
3
5
4
5
6
6
6
4
4
4
3
3
3
3
3
1
1
3
3
3
3
3
1
0
0
0
0
0
0
2
2
0
0
0
0
2
0
0
0
0
2
1
2
1
2
2
4
4
4
4
4
4
4
4
4
4
2
2
2
...

result:

ok 50507 lines

Test #73:

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

input:

100000
55589 44363
73232 44363
73232 18270
18270 53179
53179 85490
85490 33890
33890 76258
37862 76258
37862 85015
50219 85015
50219 64557
15288 64557
29902 15288
29902 85241
80558 85241
80558 82375
82375 33128
33128 11095
11095 23171
23171 22189
22189 15382
15382 31754
54741 31754
78101 54741
78101...

output:

0
1
2
3
1
3
3
3
2
2
2
2
2
2
2
0
0
1
1
1
1
1
3
3
3
2
2
2
2
2
2
2
2
2
0
1
1
1
1
1
2
2
2
0
0
0
1
3
3
3
3
3
3
5
7
7
6
4
4
4
4
4
4
2
2
2
2
2
4
4
4
3
3
4
4
2
4
4
4
3
4
3
1
0
0
1
1
1
1
0
0
0
2
0
1
1
2
2
1
2
2
2
2
0
0
0
0
1
2
3
3
3
3
3
1
1
1
0
0
0
2
1
1
1
1
1
2
2
2
2
1
2
2
3
3
3
3
3
3
3
4
4
4
3
4
4
4
2
2
2
...

result:

ok 100000 lines

Test #74:

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

input:

100000
73270 59619
73270 48026
40173 48026
40173 61339
85414 61339
50144 85414
50144 48273
48273 71431
35828 71431
35828 21914
11301 21914
11301 85678
85678 35050
23282 35050
55909 23282
57950 55909
57950 28024
22497 28024
48618 22497
83481 48618
89540 83481
62990 89540
9792 62990
9792 4008
4008 277...

output:

0
0
2
2
2
1
1
1
3
2
2
3
3
3
4
4
3
3
3
3
1
1
3
3
2
1
1
1
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
2
2
2
2
2
3
5
3
2
1
1
3
2
0
1
3
5
3
1
1
1
1
1
1
1
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
0
0
1
1
1
2
0
0
0
1
1
0
2
1
...

result:

ok 100000 lines

Test #75:

score: 0
Accepted
time: 121ms
memory: 50212kb

input:

100000
24890 72035
56777 72035
56777 52659
1916 52659
75583 1916
75583 1257
91816 1257
91816 98117
73133 98117
73133 23515
70309 23515
70309 82226
49409 82226
49409 5306
94283 5306
9360 94283
9360 24159
24159 48188
21339 48188
21339 4437
4437 81572
81572 50955
50955 95364
95364 44557
74973 44557
749...

output:

0
0
2
1
2
2
0
2
1
1
1
1
3
1
0
1
2
4
4
3
3
3
3
3
4
2
3
3
3
3
3
4
4
4
2
1
1
2
2
2
2
2
2
2
2
2
2
2
4
4
5
5
5
3
3
1
1
1
3
1
3
3
1
1
1
1
1
1
1
1
3
3
3
3
3
1
1
1
1
1
1
3
1
3
3
1
1
1
0
1
1
1
1
1
2
0
2
1
2
3
1
1
1
1
1
0
0
0
0
1
1
1
3
5
5
4
4
2
2
2
2
0
0
0
0
0
0
1
1
1
1
1
3
3
3
3
3
3
3
1
1
3
1
2
2
2
2
2
1
2
...

result:

ok 100000 lines

Test #76:

score: 0
Accepted
time: 125ms
memory: 45600kb

input:

100000
88392 51673
50471 51673
94652 50471
94652 50910
65687 50910
65687 8825
42896 8825
42896 67282
67282 54151
54151 87177
74321 87177
40440 74321
40440 5018
12449 5018
78529 12449
78529 11718
55445 11718
55445 5287
33416 5287
48515 33416
19764 48515
24006 19764
24006 21386
21386 23055
96611 23055...

output:

0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
1
2
3
3
3
3
3
2
2
3
2
2
0
1
0
2
2
2
2
3
1
1
2
0
0
0
0
2
2
1
1
0
0
0
0
1
0
0
2
1
0
1
2
1
1
1
1
1
1
0
0
0
0
0
0
0
2
2
2
2
2
2
2
1
2
2
2
2
2
1
2
0
0
1
0
0
0
0
0
1
0
0
1
1
3
2
2
2
3
3
3
3
3
3
4
3
3
3
3
2
2
3
3
3
3
3
2
2
2
2
2
2
2
2
1
1
1
1
2
1
1
1
3
5
5
3
4
4
...

result:

ok 100000 lines

Test #77:

score: 0
Accepted
time: 176ms
memory: 39152kb

input:

100000
78857 75425
49906 78857
49906 60617
60617 96006
96006 54622
58400 54622
58400 7882
7882 13917
86931 13917
42719 86931
65648 42719
65648 26369
26369 95282
32600 95282
32600 36150
36150 24955
32768 24955
85567 32768
85567 856
856 97617
97634 97617
48631 97634
48631 76383
69260 76383
27497 69260...

output:

0
0
0
0
2
1
0
0
0
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
4
4
4
4
4
5
5
3
4
4
4
4
2
2
2
2
1
1
3
1
1
0
0
0
2
2
4
2
3
3
1
0
0
0
0
1
2
2
1
2
2
2
1
1
0
0
0
0
0
0
0
0
0
0
0
2
2
2
2
2
2
2
2
2
2
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
1
1
1
1
2
2
2
2
2
2
2
3
3
3
3
3
3
3
1
1
1
1
3
3
2
2
2
0
0
0
0
0
0
2
...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed