QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78269#4894. 学姐买瓜njwrz50 970ms21516kbC++233.3kb2023-02-17 15:41:052023-02-17 15:41:08

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 2ms
memory: 5544kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #31:

score: 50
Accepted
time: 389ms
memory: 15508kb

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

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

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

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

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

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

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

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

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: -50
Time Limit Exceeded

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

Server Time: 2024-11-30 09:30:14 | OpenSource Project