QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#81638#4894. 学姐买瓜qiuzx100 ✓996ms32812kbC++113.2kb2023-02-25 17:44:202023-02-25 17:44:20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1ms
memory: 9572kb

input:

11 13
2 4 4
1 11 12
1 1 5
1 2 3
1 2 10
2 2 8
1 6 6
2 2 10
1 6 11
2 2 3
2 2 13

output:

0
1
2
1
3

result:

ok 5 lines

Test #2:

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

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #3:

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

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #4:

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

input:

14 11
1 1 8
1 4 11
2 4 8
1 2 7
1 7 11
2 2 9
1 6 10
1 2 6
1 8 10
1 2 6
2 9 10
1 9 9
1 3 10
1 2 4

output:

0
1
0

result:

ok 3 lines

Test #5:

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

input:

2000 2000
1 1589 1640
1 1741 1765
2 191 1596
1 426 493
2 1434 1606
1 925 955
2 589 1148
2 1347 1608
2 686 1516
1 1535 1563
1 1835 1841
1 1513 1537
2 30 1710
2 123 171
2 1 2000
2 128 1310
2 270 879
1 1918 1941
2 965 1951
2 176 1452
1 1391 1421
1 614 664
2 1 2000
1 296 328
1 1378 1402
1 29 47
1 92 123...

output:

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

result:

ok 1000 lines

Test #6:

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

input:

2000 2000
1 1589 1640
1 1741 1765
2 191 1596
1 426 493
2 1434 1606
1 925 955
2 589 1148
2 1347 1608
2 686 1516
1 1535 1563
1 1835 1841
1 1513 1537
2 30 1710
2 123 171
2 1 2000
2 128 1310
2 270 879
1 1918 1941
2 965 1951
2 176 1452
1 1391 1421
1 614 664
2 1 2000
1 296 328
1 1378 1402
1 29 47
1 92 123...

output:

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

result:

ok 1000 lines

Test #7:

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

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #8:

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

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #9:

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

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #10:

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

input:

2000 2000
2 66 273
1 1 501
1 2 502
2 51 70
1 3 503
2 731 1771
1 4 504
2 149 1627
2 1792 1849
1 5 505
2 139 286
2 155 1490
2 87 1279
1 6 506
2 816 1365
2 576 783
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 7 507
1 8 508
1 9 509
2 1571 1599
1 10 510
2 1 2000
2 1 2000
2 1 2000
2 564 648
2 1215 1807...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result:

ok 1004 lines

Test #11:

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

input:

2000 2000
2 66 273
1 1 501
1 2 502
2 51 70
1 3 503
2 731 1771
1 4 504
2 149 1627
2 1792 1849
1 5 505
2 139 286
2 155 1490
2 87 1279
1 6 506
2 816 1365
2 576 783
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 7 507
1 8 508
1 9 509
2 1571 1599
1 10 510
2 1 2000
2 1 2000
2 1 2000
2 564 648
2 1215 1807...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result:

ok 1004 lines

Test #12:

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

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

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

result:

ok 1000 lines

Test #13:

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

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

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

result:

ok 1000 lines

Test #14:

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

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

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

result:

ok 1000 lines

Test #15:

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

input:

12 11
2 4 5
2 2 10
1 3 7
1 4 7
1 5 11
1 5 7
2 1 3
1 1 4
2 3 3
2 11 11
1 1 10
2 10 11

output:

0
0
0
0
0
0

result:

ok 6 lines

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #16:

score: 30
Accepted
time: 17ms
memory: 7164kb

input:

80000 80000
2 14017 46708
2 26100 26240
2 3855 12007
2 72192 75052
1 12615 30948
2 36 51149
1 47528 79363
1 68506 72310
1 31635 62123
2 7480 77998
1 52530 75803
2 1793 30290
2 47012 72210
1 63304 66834
1 24988 62161
1 34585 61735
1 2973 61060
2 23879 44146
2 11903 26606
2 11536 72847
1 47874 65933
1...

output:

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

result:

ok 39967 lines

Test #17:

score: 0
Accepted
time: 25ms
memory: 5668kb

input:

80000 80000
2 2861 34160
2 8759 15795
2 7885 64470
2 54605 64108
2 34678 46289
1 77858 79250
1 31975 45909
2 41585 66397
2 670 8018
2 21646 77764
2 59388 66346
2 11547 33881
1 33641 65830
1 20381 76117
2 1 80000
1 21230 50809
2 1 80000
2 62738 76613
1 5547 74063
1 12843 34869
1 58364 70930
2 1 80000...

output:

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

result:

ok 40238 lines

Test #18:

score: 0
Accepted
time: 13ms
memory: 5624kb

input:

80000 80000
2 2861 34160
2 8759 15795
2 7885 64470
2 54605 64108
2 34678 46289
1 77858 79250
1 31975 45909
2 41585 66397
2 670 8018
2 21646 77764
2 59388 66346
2 11547 33881
1 33641 65830
1 20381 76117
2 1 80000
1 21230 50809
2 1 80000
2 62738 76613
1 5547 74063
1 12843 34869
1 58364 70930
2 1 80000...

output:

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

result:

ok 40238 lines

Test #19:

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

input:

80000 80000
2 18977 66117
2 1 80000
2 27578 46739
2 30830 62244
2 55697 71643
2 27378 65022
1 56047 56096
2 49937 56489
2 45072 77388
2 44709 55212
1 37844 37869
2 36378 69188
1 74387 74409
2 1 80000
2 1 80000
1 1432 1471
2 64369 67027
1 24704 24715
2 4643 31966
1 35276 35326
2 7090 54798
2 25675 78...

output:

0
0
0
0
0
0
1
1
0
2
3
3
0
1
3
4
1
1
2
3
2
3
7
3
7
13
9
5
6
10
1
18
14
8
2
4
7
7
25
3
5
13
17
4
20
11
4
37
16
22
26
1
16
12
14
20
7
7
12
4
6
20
2
22
49
43
14
22
29
49
21
19
15
37
31
27
12
41
64
0
64
14
4
41
26
41
42
7
16
17
22
83
7
50
0
66
26
6
46
7
9
75
64
18
100
28
45
101
9
87
10
30
109
60
111
42
3...

result:

ok 40000 lines

Test #20:

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

input:

80000 80000
2 67953 77105
2 24204 57828
1 32435 32451
1 72390 72515
2 1 80000
1 32015 32040
2 6622 24973
2 24454 72822
1 64442 64452
1 70875 70909
2 45452 73012
1 20698 20722
2 10641 20426
2 11766 32138
1 27388 27408
1 16905 16931
1 76806 76814
1 39565 39589
2 16827 78470
2 36042 54665
1 27305 27318...

output:

0
0
2
0
3
3
0
2
10
1
6
14
4
1
10
9
0
2
4
2
11
0
11
6
12
11
7
2
2
0
20
11
1
3
29
0
9
19
30
30
17
2
3
16
29
5
0
11
18
9
20
22
6
2
6
22
11
4
19
51
4
21
56
24
27
0
16
3
3
6
8
4
19
29
54
5
35
63
20
70
22
11
43
8
39
19
3
83
18
4
40
7
59
7
27
25
1
21
11
24
16
25
44
19
25
39
39
30
15
19
57
47
57
114
86
30
5...

result:

ok 40000 lines

Test #21:

score: 0
Accepted
time: 100ms
memory: 11204kb

input:

80000 80000
2 67953 77105
2 24204 57828
1 32435 32451
1 72390 72515
2 1 80000
1 32015 32040
2 6622 24973
2 24454 72822
1 64442 64452
1 70875 70909
2 45452 73012
1 20698 20722
2 10641 20426
2 11766 32138
1 27388 27408
1 16905 16931
1 76806 76814
1 39565 39589
2 16827 78470
2 36042 54665
1 27305 27318...

output:

0
0
2
0
3
3
0
2
10
1
6
14
4
1
10
9
0
2
4
2
11
0
11
6
12
11
7
2
2
0
20
11
1
3
29
0
9
19
30
30
17
2
3
16
29
5
0
11
18
9
20
22
6
2
6
22
11
4
19
51
4
21
56
24
27
0
16
3
3
6
8
4
19
29
54
5
35
63
20
70
22
11
43
8
39
19
3
83
18
4
40
7
59
7
27
25
1
21
11
24
16
25
44
19
25
39
39
30
15
19
57
47
57
114
86
30
5...

result:

ok 40000 lines

Test #22:

score: 0
Accepted
time: 95ms
memory: 9896kb

input:

80000 80000
2 50698 64950
1 79547 79547
2 4065 38573
2 5409 32899
1 9328 9328
2 24681 34436
2 2364 64359
2 27664 56147
2 1 80000
2 1 80000
2 17386 30575
1 53323 53323
1 77467 77467
1 39684 39684
1 48202 48202
1 46370 46370
2 16758 76161
1 68737 68737
2 14967 35344
2 21887 51637
1 39740 39740
2 11908...

output:

0
0
0
0
1
0
2
2
0
4
0
3
7
4
5
4
2
1
14
13
16
8
3
7
1
16
13
22
25
8
8
3
18
11
15
0
32
7
1
0
20
4
1
4
20
49
1
6
4
4
11
2
50
31
52
27
10
29
12
55
27
6
28
6
0
40
19
62
12
36
36
22
7
37
48
36
31
9
12
4
88
2
50
89
9
8
13
89
22
92
1
17
75
82
13
64
44
43
52
102
50
46
2
17
63
41
21
78
21
0
115
48
20
7
8
117
...

result:

ok 39991 lines

Test #23:

score: 0
Accepted
time: 98ms
memory: 10172kb

input:

80000 80000
1 47823 47827
2 51702 74055
2 1 80000
1 75249 75253
2 33942 52215
2 236 78066
1 46733 46737
2 4477 54423
2 4537 73268
1 11123 11127
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 3969 3973
1 51839 51843
1 26475 26479
2 38789 69975
2 57669 71418
2 44434 69847
1 55243 55247
2 67...

output:

0
1
1
2
2
2
2
2
0
1
3
0
3
1
2
10
0
10
2
2
1
1
2
2
7
7
9
22
0
16
8
15
6
10
32
11
9
15
33
4
19
4
8
5
3
39
1
39
12
25
1
3
12
29
2
57
1
35
28
37
32
0
47
2
71
41
22
43
12
61
24
3
78
39
46
42
24
53
83
11
19
6
11
26
43
25
44
39
76
19
59
19
94
7
14
13
35
15
1
51
24
1
9
21
19
42
34
18
8
0
4
106
44
46
25
3
7
...

result:

ok 39870 lines

Test #24:

score: 0
Accepted
time: 116ms
memory: 11592kb

input:

80000 80000
1 47823 47827
2 51702 74055
2 1 80000
1 75249 75253
2 33942 52215
2 236 78066
1 46733 46737
2 4477 54423
2 4537 73268
1 11123 11127
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 3969 3973
1 51839 51843
1 26475 26479
2 38789 69975
2 57669 71418
2 44434 69847
1 55243 55247
2 67...

output:

0
1
1
2
2
2
2
2
0
1
3
0
3
1
2
10
0
10
2
2
1
1
2
2
7
7
9
22
0
16
8
15
6
10
32
11
9
15
33
4
19
4
8
5
3
39
1
39
12
25
1
3
12
29
2
57
1
35
28
37
32
0
47
2
71
41
22
43
12
61
24
3
78
39
46
42
24
53
83
11
19
6
11
26
43
25
44
39
76
19
59
19
94
7
14
13
35
15
1
51
24
1
9
21
19
42
34
18
8
0
4
106
44
46
25
3
7
...

result:

ok 39870 lines

Test #25:

score: 0
Accepted
time: 124ms
memory: 11240kb

input:

80000 80000
1 1 20001
1 2 20002
1 3 20003
2 51702 74055
2 1 80000
1 4 20004
1 5 20005
2 33942 52215
2 236 78066
1 6 20006
1 7 20007
2 4477 54423
2 4537 73268
1 8 20008
1 9 20009
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 10 20010
1 11 20011
1 12 20012
1 13 20013
1 14 20014
1 15 20015
...

output:

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

result:

ok 40000 lines

Test #26:

score: 0
Accepted
time: 108ms
memory: 11180kb

input:

80000 80000
1 1 20001
1 2 20002
2 50644 76906
2 41744 45216
2 57575 75408
2 12225 61676
1 3 20003
1 4 20004
1 5 20005
1 6 20006
1 7 20007
1 8 20008
1 9 20009
1 10 20010
1 11 20011
2 24858 75983
1 12 20012
2 1 80000
1 13 20013
2 22970 48447
1 14 20014
1 15 20015
2 66927 77660
2 24937 39575
2 53299 55...

output:

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

result:

ok 40008 lines

Test #27:

score: 0
Accepted
time: 138ms
memory: 11236kb

input:

80000 80000
1 18629 18651
1 45305 45395
1 73500 73529
2 79 79950
2 42 79979
1 3060 3093
1 7620 7697
1 23250 23317
1 8916 8933
1 42381 42392
2 50 79962
2 63 79988
2 1 79999
1 44186 44204
1 64397 64461
1 75722 75761
2 51 79932
2 40 79950
2 48025 50108
1 15925 15949
1 63914 63932
2 24 79988
2 89 79942
...

output:

3
3
8
8
8
11
11
0
13
13
16
20
21
24
28
30
30
30
30
30
31
33
34
34
35
37
40
40
40
40
40
43
43
44
50
50
51
51
52
52
52
53
55
58
59
60
60
61
61
61
66
66
66
66
67
69
70
70
71
76
76
78
79
79
79
81
81
81
83
83
32
83
83
88
88
91
94
94
94
94
96
98
98
98
98
98
98
102
103
103
105
105
105
107
108
109
109
111
1...

result:

ok 40000 lines

Test #28:

score: 0
Accepted
time: 136ms
memory: 11400kb

input:

80000 80000
1 18629 18651
1 45305 45395
1 73500 73529
2 79 79950
2 42 79979
1 3060 3093
1 7620 7697
1 23250 23317
1 8916 8933
1 42381 42392
2 50 79962
2 63 79988
2 1 79999
1 44186 44204
1 64397 64461
1 75722 75761
2 51 79932
2 40 79950
2 48025 50108
1 15925 15949
1 63914 63932
2 24 79988
2 89 79942
...

output:

3
3
8
8
8
11
11
0
13
13
16
20
21
24
28
30
30
30
30
30
31
33
34
34
35
37
40
40
40
40
40
43
43
44
50
50
51
51
52
52
52
53
55
58
59
60
60
61
61
61
66
66
66
66
67
69
70
70
71
76
76
78
79
79
79
81
81
81
83
83
32
83
83
88
88
91
94
94
94
94
96
98
98
98
98
98
98
102
103
103
105
105
105
107
108
109
109
111
1...

result:

ok 40000 lines

Test #29:

score: 0
Accepted
time: 166ms
memory: 11156kb

input:

80000 80000
1 40636 40641
1 69847 69873
1 16352 16422
1 52522 52614
2 38 79981
2 63 79902
1 30452 30467
2 47 79984
2 63 79953
1 71760 71824
2 28 79921
2 57 79987
2 15 79919
2 78 79901
2 55 79901
1 40610 40625
1 20412 20465
1 58984 59018
1 45311 45324
1 27428 27445
1 59989 60027
1 53348 53410
1 6426 ...

output:

4
4
5
5
6
6
6
6
6
14
15
15
16
17
17
18
19
20
20
20
20
22
22
22
22
22
22
25
25
27
28
28
30
32
32
37
37
38
42
42
44
48
49
49
53
53
53
57
57
61
62
62
65
67
67
67
67
67
67
67
67
67
67
67
67
76
77
78
78
78
79
79
81
83
84
84
87
87
88
88
88
88
92
95
96
99
100
100
103
103
104
104
106
106
107
109
112
112
116...

result:

ok 40000 lines

Test #30:

score: 0
Accepted
time: 142ms
memory: 11400kb

input:

80000 80000
1 40636 40641
1 69847 69873
1 16352 16422
1 52522 52614
2 38 79981
2 63 79902
1 30452 30467
2 47 79984
2 63 79953
1 71760 71824
2 28 79921
2 57 79987
2 15 79919
2 78 79901
2 55 79901
1 40610 40625
1 20412 20465
1 58984 59018
1 45311 45324
1 27428 27445
1 59989 60027
1 53348 53410
1 6426 ...

output:

4
4
5
5
6
6
6
6
6
14
15
15
16
17
17
18
19
20
20
20
20
22
22
22
22
22
22
25
25
27
28
28
30
32
32
37
37
38
42
42
44
48
49
49
53
53
53
57
57
61
62
62
65
67
67
67
67
67
67
67
67
67
67
67
67
76
77
78
78
78
79
79
81
83
84
84
87
87
88
88
88
88
92
95
96
99
100
100
103
103
104
104
106
106
107
109
112
112
116...

result:

ok 40000 lines

Subtask #3:

score: 50
Accepted

Dependency #2:

100%
Accepted

Test #31:

score: 50
Accepted
time: 138ms
memory: 11792kb

input:

300000 300000
1 65058 175646
2 84915 100033
2 1 300000
1 4571 84453
2 229719 237569
1 145712 164438
2 95823 98589
1 130465 255002
1 63938 79365
2 16862 171297
2 108832 182624
1 88047 160443
1 24866 238717
2 49449 260305
1 116709 221422
1 65757 236100
1 2820 37609
2 85634 174637
1 4878 66462
1 121731...

output:

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

result:

ok 150127 lines

Test #32:

score: 0
Accepted
time: 127ms
memory: 11696kb

input:

300000 300000
1 261847 282619
2 188893 233425
2 161068 266924
2 92909 193628
2 93783 292477
2 1 300000
1 31648 103794
2 118224 289893
1 72235 93245
1 117002 281857
1 72006 95259
1 79721 214764
2 179289 194573
1 60323 238175
1 63436 244704
2 17704 229466
2 74273 132259
1 21105 40071
1 222094 244977
2...

output:

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

result:

ok 150196 lines

Test #33:

score: 0
Accepted
time: 143ms
memory: 11816kb

input:

300000 300000
1 90191 211608
1 31308 74331
1 273258 296229
2 15812 53861
2 28629 46923
1 1940 104870
1 216952 292244
1 83679 105148
1 84949 269844
2 18620 125498
1 49661 138028
1 160082 257776
1 127685 290600
1 88550 154577
1 36885 294219
2 227655 254028
2 166773 286459
1 227312 235260
2 210094 2696...

output:

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

result:

ok 149847 lines

Test #34:

score: 0
Accepted
time: 145ms
memory: 11652kb

input:

300000 300000
2 156610 244215
2 15243 280587
1 65268 158490
2 81163 295723
1 159433 201748
1 22620 264096
1 61498 233523
2 1 300000
1 157659 222437
1 43247 107162
2 92536 200166
2 42232 156375
2 95914 202151
2 44563 162600
2 242814 274068
1 2653 197341
2 190022 251555
2 267990 272608
1 47847 268790
...

output:

0
0
0
2
0
1
1
1
0
0
0
0
0
2
1
0
1
1
2
1
1
1
2
0
1
0
0
2
0
0
3
0
1
1
2
1
1
4
0
0
0
0
1
5
4
1
0
0
5
0
2
6
1
0
7
2
7
0
2
6
0
0
0
4
1
1
0
1
1
9
3
1
6
2
6
9
1
8
1
6
9
4
1
9
2
6
0
3
6
3
2
1
1
0
1
2
0
9
4
5
4
2
4
11
5
4
6
0
11
5
3
0
9
1
1
6
0
5
5
5
3
11
6
2
1
1
4
0
2
3
2
7
1
3
11
6
7
4
0
2
4
2
7
0
0
5
0
1
...

result:

ok 149741 lines

Test #35:

score: 0
Accepted
time: 154ms
memory: 11792kb

input:

300000 300000
2 35596 226190
2 13112 136149
1 36574 174085
1 75016 178919
2 182630 197189
2 35226 186425
2 58731 275486
1 82605 247276
2 159287 223589
1 6592 49093
2 172399 208826
1 92482 239782
1 124154 252626
2 1 300000
1 44961 120743
1 137492 275950
2 169466 210086
1 195296 294267
2 48680 204085
...

output:

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

result:

ok 150354 lines

Test #36:

score: 0
Accepted
time: 159ms
memory: 11812kb

input:

300000 300000
1 115412 265834
2 163248 175538
2 79312 142564
2 197884 214065
1 177274 284370
1 61483 232573
1 62171 237721
1 88036 234283
2 79611 137048
1 1512 251436
2 1 300000
2 186476 287046
2 149667 284333
2 19805 139430
1 74511 140370
1 17725 79935
2 176790 240910
1 87211 238669
1 99810 239104
...

output:

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

result:

ok 150006 lines

Test #37:

score: 0
Accepted
time: 128ms
memory: 11624kb

input:

300000 300000
2 273445 285737
2 22208 281514
1 17120 210049
2 150367 237251
1 104033 285406
1 103253 226523
2 51616 176962
1 60888 239948
1 149053 270451
2 2705 226643
1 212244 299284
1 11863 41571
1 116357 244498
2 4033 171116
1 29025 224131
1 83273 119317
2 47781 169234
2 4486 163734
2 2467 216792...

output:

0
0
0
0
1
1
1
2
2
0
0
0
1
2
1
3
0
0
2
4
3
2
0
4
3
1
2
1
1
1
0
5
3
1
1
0
0
1
2
2
0
0
0
1
0
3
5
5
0
4
0
7
0
0
0
0
2
2
6
3
8
0
4
0
0
0
3
7
0
1
6
6
1
8
2
4
7
4
6
2
1
3
1
0
7
1
10
3
4
10
5
7
3
6
7
1
5
4
9
0
10
7
1
9
2
5
5
3
2
7
2
3
4
3
2
2
12
0
3
8
2
0
12
7
2
2
2
0
0
3
0
12
12
2
1
3
10
1
5
9
7
1
8
0
7
9
...

result:

ok 150104 lines

Test #38:

score: 0
Accepted
time: 138ms
memory: 11656kb

input:

300000 300000
2 18964 261751
2 31823 256517
2 140620 239243
2 196974 198816
2 52287 290822
2 105788 246832
2 96689 221657
1 211766 269647
1 140889 158732
1 222656 225870
2 189741 229067
1 70748 165460
2 1 300000
2 47504 254575
1 83292 139657
2 215899 238835
2 79326 153938
1 90954 280309
2 32968 1868...

output:

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

result:

ok 150243 lines

Test #39:

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

input:

300000 300000
1 98267 98286
1 135052 135085
1 135168 135183
2 156706 288194
2 19933 158498
2 45138 74042
2 135463 201496
1 205395 205407
1 172100 172110
1 228433 228473
1 76415 76451
2 124950 253147
1 125452 125488
1 140966 141021
2 249013 252433
1 213447 213505
2 211862 225988
1 16496 16522
1 66626...

output:

0
3
0
0
5
0
1
3
3
1
3
12
3
1
8
5
19
15
5
5
0
11
7
2
15
11
12
9
5
1
31
8
0
32
11
4
0
28
9
34
10
12
27
29
18
17
0
5
33
54
19
27
14
56
11
60
10
21
14
17
35
32
51
50
8
77
28
21
46
17
45
4
23
25
85
56
88
74
2
43
81
50
13
93
17
15
35
5
23
99
40
80
32
34
66
29
67
106
80
50
30
108
65
39
118
26
116
59
4
69
3...

result:

ok 150000 lines

Test #40:

score: 0
Accepted
time: 746ms
memory: 32676kb

input:

300000 300000
2 39027 216076
2 86473 234425
1 112975 113001
1 193883 193913
1 45471 45489
1 147137 147148
1 66220 66269
2 50817 290933
2 96352 236150
2 127950 240231
1 168668 168682
2 35010 108742
1 221657 221680
2 1 300000
1 275417 275456
2 18207 230476
1 15577 15639
1 83151 83172
2 120371 294704
2...

output:

0
0
4
3
2
2
7
7
5
0
1
8
6
10
9
10
7
14
14
1
11
15
11
14
0
2
12
3
9
14
1
0
9
4
5
2
18
2
6
3
4
2
23
17
4
22
7
1
5
9
42
45
19
8
30
28
32
9
9
36
34
27
40
6
16
40
13
54
26
7
31
3
45
12
22
61
3
18
13
47
21
16
39
37
71
15
16
12
7
6
32
24
13
26
37
1
5
20
10
1
38
20
86
3
29
16
24
85
33
26
38
91
32
45
93
7
84...

result:

ok 150000 lines

Test #41:

score: 0
Accepted
time: 679ms
memory: 32620kb

input:

300000 300000
1 233650 233678
1 208481 208527
1 223872 223903
1 146829 146868
2 85137 153203
1 116080 116150
2 116340 250076
2 33668 225483
1 33122 33150
1 18033 18095
1 63793 63833
2 57425 281368
1 186125 186159
1 101074 101091
2 37678 195003
2 175647 251126
2 9506 99505
1 298238 298311
2 3346 9131...

output:

1
4
4
6
5
4
3
0
7
14
2
3
2
6
7
17
13
0
1
4
0
13
14
1
17
7
25
3
13
4
6
3
3
4
25
12
16
14
0
13
14
8
0
11
1
29
13
10
4
7
16
5
7
6
22
8
26
1
18
11
49
6
15
35
16
32
17
40
19
30
55
38
32
1
10
4
18
15
9
2
17
16
43
30
34
18
7
23
11
9
20
47
33
70
5
78
36
19
30
22
2
20
29
4
31
49
84
3
30
88
42
21
72
67
49
50
...

result:

ok 150000 lines

Test #42:

score: 0
Accepted
time: 602ms
memory: 28220kb

input:

300000 300000
1 212263 212272
2 235865 257870
1 160923 160932
1 181986 181995
1 61751 61760
2 110017 134081
2 90932 225347
2 70603 174149
1 186424 186433
1 223034 223043
1 26428 26437
1 116536 116545
1 20055 20064
2 18493 64610
1 261895 261904
2 138279 287847
2 58982 222379
1 262236 262245
2 128747 ...

output:

0
0
3
1
3
6
6
4
1
8
4
0
4
2
14
9
3
17
13
10
30
19
5
12
14
11
3
20
9
6
22
33
13
18
19
12
11
15
5
21
39
6
18
15
30
18
25
39
37
30
12
54
35
25
41
4
30
37
34
37
10
51
10
8
21
12
35
31
36
41
33
71
71
33
0
6
23
33
55
10
47
41
6
44
60
33
1
60
30
40
42
22
16
5
15
17
32
34
38
92
33
53
102
96
14
46
47
11
80
4...

result:

ok 149743 lines

Test #43:

score: 0
Accepted
time: 592ms
memory: 28084kb

input:

300000 300000
1 232091 232093
2 19000 131070
1 287700 287702
1 138259 138261
2 52344 276988
1 108297 108299
2 88864 297549
1 35056 35058
1 216443 216445
2 121066 182142
1 131400 131402
2 1 300000
2 264155 273130
2 58913 119387
2 65791 241337
1 247306 247308
1 113016 113018
1 62434 62436
1 26626 2662...

output:

0
2
4
1
7
0
1
5
5
2
9
7
11
14
3
14
0
5
8
20
13
26
1
2
10
26
0
12
14
15
25
24
23
7
27
22
44
30
15
48
23
43
38
1
51
12
1
7
48
5
34
16
4
45
59
43
8
42
25
10
68
59
22
73
13
7
4
81
32
12
17
36
10
39
11
27
31
16
13
15
20
74
26
6
54
34
95
97
52
100
102
102
30
8
39
21
105
32
36
44
10
10
5
110
58
118
70
48
4...

result:

ok 149904 lines

Test #44:

score: 0
Accepted
time: 612ms
memory: 28296kb

input:

300000 300000
2 46745 122986
1 245902 245911
1 24805 24814
1 71267 71276
1 40865 40874
1 142905 142914
2 95244 200500
1 168832 168841
1 60693 60702
2 1 300000
2 105902 297268
2 1 300000
2 67275 71778
2 65698 90023
1 164021 164030
2 15182 210663
1 81908 81917
1 265494 265503
1 227863 227872
2 290917 ...

output:

0
1
7
3
7
1
1
7
0
2
6
9
3
9
4
11
13
7
15
1
0
17
4
0
6
8
21
9
18
8
21
4
24
13
19
10
14
30
13
3
10
14
32
8
7
5
2
23
25
12
22
6
7
20
7
25
22
20
11
25
20
2
34
53
37
43
61
7
9
8
50
7
15
73
14
30
63
3
1
32
8
3
41
16
34
29
12
83
20
73
76
32
44
28
16
27
49
44
28
6
13
36
32
95
30
13
15
97
24
9
97
96
0
97
6
9...

result:

ok 150035 lines

Test #45:

score: 0
Accepted
time: 496ms
memory: 32644kb

input:

300000 300000
2 17563 146496
2 123366 278094
2 186823 240349
2 160881 168157
1 1 75001
1 2 75002
2 52820 120896
2 10250 270688
1 3 75003
1 4 75004
1 5 75005
1 6 75006
1 7 75007
1 8 75008
2 1 300000
1 9 75009
1 10 75010
1 11 75011
2 80204 290393
1 12 75012
1 13 75013
2 204176 284905
1 14 75014
1 15 7...

output:

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

result:

ok 150193 lines

Test #46:

score: 0
Accepted
time: 504ms
memory: 32508kb

input:

300000 300000
2 57751 290568
2 20328 264132
1 1 75001
2 116611 240401
1 2 75002
1 3 75003
2 37309 178199
1 4 75004
2 203574 255759
2 41760 209926
2 187984 293855
2 1876 266589
2 5717 204045
1 5 75005
1 6 75006
1 7 75007
2 109777 289510
2 50292 114696
2 170110 236643
1 8 75008
1 9 75009
1 10 75010
2 ...

output:

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

result:

ok 150314 lines

Test #47:

score: 0
Accepted
time: 996ms
memory: 32608kb

input:

300000 300000
1 49074 49113
2 99 299947
1 83425 83445
1 250494 250530
2 9 299917
1 11314 11345
2 40 299933
1 98447 98537
2 89 299935
1 206417 206488
1 28953 29018
1 3349 3379
1 100987 100996
2 11 299994
2 82 299934
1 2932 2998
2 92 299910
2 53 299911
2 76 299927
1 30082 30105
1 200034 200069
1 21627...

output:

1
3
4
5
9
9
10
10
10
13
13
13
14
14
14
14
14
14
15
15
15
15
18
18
18
19
21
22
22
22
13
25
29
29
29
30
31
33
33
34
34
36
36
40
42
44
45
45
45
46
47
47
47
50
50
50
50
50
53
55
57
58
60
60
60
64
64
64
64
67
67
67
67
67
69
69
69
69
69
72
72
73
73
74
75
75
77
83
85
85
85
86
86
89
91
97
97
98
98
101
102
1...

result:

ok 150000 lines

Test #48:

score: 0
Accepted
time: 981ms
memory: 32652kb

input:

300000 300000
1 159525 159551
1 186495 186554
1 44983 45037
2 95 299936
1 75580 75610
2 40 299931
1 60382 60416
2 53 299924
1 72559 72577
2 16 299969
2 57 299919
1 190311 190360
2 56 299930
1 76460 76485
2 17 299981
2 62 299973
1 289093 289152
1 169487 169497
2 55 299944
2 79 299966
2 68 299941
2 74...

output:

3
4
5
6
6
7
8
8
10
10
10
10
11
11
11
12
12
12
14
14
15
15
16
16
16
17
18
20
20
22
22
22
24
24
25
26
26
26
28
29
29
32
32
34
36
36
36
36
39
39
39
40
40
40
40
44
45
46
46
46
46
47
47
47
49
50
54
55
57
57
59
59
61
61
62
62
62
63
63
65
65
65
65
66
66
66
66
67
67
67
67
68
69
69
69
69
70
71
71
71
72
72
77...

result:

ok 150000 lines

Test #49:

score: 0
Accepted
time: 979ms
memory: 32812kb

input:

300000 300000
1 235882 235942
1 172317 172376
2 92 299977
2 52 299981
1 100284 100332
2 7 299921
2 93 299958
1 104601 104626
2 86 299905
1 242468 242494
2 50 299940
1 84720 84742
2 42 299988
1 183978 184018
1 202543 202573
1 244037 244103
1 289655 289665
1 185476 185499
1 120266 120299
2 2 299972
1 ...

output:

2
2
3
3
4
5
6
12
14
14
14
16
16
16
16
18
18
19
19
20
21
21
21
21
22
23
23
23
24
25
28
28
28
28
32
33
33
33
36
36
36
39
39
39
40
40
42
43
44
46
47
47
47
47
50
50
52
52
52
53
54
55
55
55
56
56
64
66
66
67
67
68
68
68
70
70
70
70
71
78
78
79
80
82
82
82
82
83
83
83
84
86
86
86
92
92
94
94
94
95
95
98
9...

result:

ok 150000 lines

Test #50:

score: 0
Accepted
time: 934ms
memory: 32624kb

input:

300000 300000
2 19 299966
2 54 299971
1 237997 238032
2 99 299956
1 244360 244390
1 211248 211281
1 218579 218680
1 51295 51338
2 12 299954
1 275317 275351
1 89120 89155
1 74816 74848
2 5 299943
1 63201 63226
2 60 299938
1 151613 151632
1 33820 33840
1 109543 109625
1 12389 12472
2 35 299919
1 19960...

output:

0
0
1
5
8
9
13
14
15
15
16
16
17
17
20
21
21
21
21
21
21
22
22
23
23
23
23
23
23
26
27
27
27
27
27
30
30
33
33
34
36
36
36
38
43
43
44
47
48
50
50
51
52
52
56
61
62
62
62
65
67
67
67
70
71
73
73
73
73
73
73
73
73
74
77
78
78
80
82
82
83
84
85
85
87
90
90
90
90
90
90
91
91
91
91
91
91
93
93
97
97
98
...

result:

ok 150000 lines
English 繁體中文 简体中文

Server Time: 2024-11-30 06:48:41 | OpenSource Project