QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120216#6608. Descent of DragonswlxhkkAC ✓409ms253220kbC++141.7kb2023-07-06 15:02:402023-07-06 15:03:48

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9708kb

input:

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

output:

0
3

result:

ok 2 number(s): "0 3"

Test #2:

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

input:

1000 1000
2 234 913
1 693 735 47
1 702 959 94
2 273 286
1 814 896 47
1 560 566 15
1 46 699 97
2 494 527
1 721 879 68
1 87 437 26
1 163 938 15
1 816 912 58
2 284 670
2 713 763
1 49 542 13
1 669 874 41
2 795 855
1 601 962 93
1 413 747 50
1 528 710 73
2 255 435
1 329 871 86
1 24 236 48
1 22 48 41
1 29 ...

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
1
0
0
1
0
1
0
0
0
0
0
2
2
0
2
0
0
0
0
2
0
2
2
2
2
2
2
2
2
2
2
0
0
2
0
0
0
3
3
3
0
0
0
1
1
1
3
2
2
2
2
3
1
3
2
2
3
3
2
2
1
3
2
3
3
3
3
3
3
3
2
2
3
3
2
3
2
1
3
3
2
1
3
3
3
1
1
2
2
3
2
1
1
3
3
2
2
2
3
2
3
2
3
2
2
3
3
2
2
1
2
3
2
3
4
4
4
4
2
4
2
4
4
4
...

result:

ok 198 numbers

Test #3:

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

input:

1000 1000
1 26 189 2
1 485 923 7
1 108 839 9
1 200 260 8
1 196 296 1
1 894 897 7
1 215 510 3
1 117 333 9
2 395 646
1 548 762 8
1 317 340 0
1 354 879 0
1 294 373 8
1 277 979 5
1 10 295 8
2 769 784
1 271 850 4
1 233 440 4
1 416 542 3
1 454 470 7
1 439 956 5
1 644 722 1
1 732 951 4
1 423 768 5
1 43 962...

output:

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

result:

ok 197 numbers

Test #4:

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

input:

1000 1000
1 646 946 11
1 192 372 8
1 14 516 45
2 664 910
1 164 693 0
1 285 411 16
1 682 888 40
2 153 569
1 407 481 18
1 961 985 4
1 22 904 11
1 195 213 34
2 46 767
1 73 106 5
1 172 573 38
1 277 322 9
1 230 555 29
1 882 882 18
1 140 276 7
1 15 102 21
1 319 383 29
1 289 814 22
1 795 905 45
1 205 415 3...

output:

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

result:

ok 187 numbers

Test #5:

score: 0
Accepted
time: 22ms
memory: 11856kb

input:

70000 80000
2 9805 11304
1 2826 15704 47
1 13625 31020 42
1 13179 20404 49
1 10844 24118 49
1 5973 11929 1
1 26374 29887 7
1 12989 17431 46
1 5119 9903 44
1 12753 18942 7
2 12261 29009
1 1028 15183 30
1 2757 18390 35
1 5345 15962 24
1 1488 15535 42
1 23143 30796 19
2 15847 29111
1 3632 12377 38
1 31...

output:

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

result:

ok 16106 numbers

Test #6:

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

input:

700 100000
1 106 184 1711
1 455 503 1417
2 14 181
1 292 327 1563
1 54 457 88
1 99 124 1077
1 177 290 1016
1 174 615 605
2 166 641
1 368 431 492
1 118 416 1747
1 179 431 1019
1 101 525 860
1 331 670 1482
1 170 336 1031
1 20 310 1961
2 144 179
2 247 505
1 219 693 1602
1 355 602 485
1 33 117 1344
1 198...

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 20052 numbers

Test #7:

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

input:

789 99938
2 422 480
1 504 725 222
1 189 379 3
2 48 266
2 417 466
1 665 692 242
1 433 457 88
1 161 462 172
1 240 785 386
1 198 315 421
1 31 605 58
1 259 703 125
1 449 566 122
1 237 478 336
1 500 580 4
2 281 499
2 375 743
2 442 588
1 345 417 103
2 292 400
1 128 503 115
1 680 711 560
2 244 781
1 123 78...

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

result:

ok 20204 numbers

Test #8:

score: 0
Accepted
time: 20ms
memory: 16336kb

input:

99995 99859
1 13072 21217 97
1 12762 21654 161
1 18401 22241 147
1 21697 24548 23
2 11234 22483
1 12618 22129 50
1 9645 11630 145
1 1809 17987 45
2 2009 32205
2 11555 26878
1 16164 26055 120
1 9510 21660 11
1 8601 22705 162
1 12315 19834 16
2 26182 32571
1 16143 22202 91
1 974 23764 117
1 13364 2069...

output:

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

result:

ok 19949 numbers

Test #9:

score: 0
Accepted
time: 20ms
memory: 12948kb

input:

99969 99676
1 17116 30053 43
1 22112 22674 12
1 22594 31672 45
2 9716 29330
1 10814 14072 53
1 1664 12710 69
2 10379 18258
1 23738 25816 40
1 12778 19791 9
1 22701 30742 29
1 5352 30444 3
1 13221 31848 14
2 6657 17637
1 10006 11541 76
2 3728 13940
1 3287 5383 17
2 26670 29682
1 451 22976 89
1 11901 ...

output:

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

result:

ok 19882 numbers

Test #10:

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

input:

99950 99953
2 26404 30424
1 4548 24449 439
1 388 22858 665
1 2286 24182 783
1 21798 24148 210
1 22029 26217 683
1 10929 15038 375
1 11054 18990 871
1 13663 20854 715
1 25448 32225 552
1 22050 23951 336
1 16658 26554 129
2 25599 26842
1 14839 27212 722
1 13120 29334 536
1 6347 8250 352
1 25235 29500 ...

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

result:

ok 19899 numbers

Test #11:

score: 0
Accepted
time: 38ms
memory: 41852kb

input:

59959 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 11 11 0
1 13 13 0
1 15 15 0
1 17 17 0
1 19 19 0
1 21 21 0
1 23 23 0
1 25 25 0
1 27 27 0
1 29 29 0
1 31 31 0
1 33 33 0
1 35 35 0
1 37 37 0
1 39 39 0
1 41 41 0
1 43 43 0
1 45 45 0
1 47 47 0
1 49 49 0
1 51 51 0
1 53 53 0
1 55 55 0
1 57 57 0
1 59 59...

output:

2
3
4
5
6
7
8
9
9
11
12
13
14
15
16
17
17
18
20
21
22
23
24
25
26
27
28
28
30
31
32
33
34
35
36
37
38
39
40
41
42
43
43
45
45
46
48
49
50
51
52
53
54
55
56
57
58
58
59
61
62
63
64
65
66
67
67
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
83
85
85
87
88
89
90
91
92
93
94
95
96
97
98
99
100
100
102
102...

result:

ok 23340 numbers

Test #12:

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

input:

9920 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 11 11 0
1 13 13 0
1 15 15 0
1 17 17 0
1 19 19 0
1 21 21 0
1 23 23 0
1 25 25 0
1 27 27 0
1 29 29 0
1 31 31 0
1 33 33 0
1 35 35 0
1 37 37 0
1 39 39 0
1 41 41 0
1 43 43 0
1 45 45 0
1 47 47 0
1 49 49 0
1 51 51 0
1 53 53 0
1 55 55 0
1 57 57 0
1 59 59 ...

output:

2
3
3
5
6
7
8
8
10
11
12
13
14
15
16
17
18
18
20
21
21
23
24
25
26
27
28
29
30
31
32
33
34
35
36
1
38
39
40
41
42
42
44
45
46
47
47
49
50
50
52
53
54
55
56
57
58
59
60
60
62
63
64
65
66
67
68
69
70
71
71
73
74
75
76
77
78
79
79
81
82
82
84
85
86
87
87
89
90
91
91
2
94
95
96
97
98
99
100
101
102
103
...

result:

ok 31680 numbers

Test #13:

score: 0
Accepted
time: 38ms
memory: 36720kb

input:

49953 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 11 11 0
1 13 13 0
1 15 15 0
1 17 17 0
1 19 19 0
1 21 21 0
1 23 23 0
1 25 25 0
1 27 27 0
1 29 29 0
1 31 31 0
1 33 33 0
1 35 35 0
1 37 37 0
1 39 39 0
1 41 41 0
1 43 43 0
1 45 45 0
1 47 47 0
1 49 49 0
1 51 51 0
1 53 53 0
1 55 55 0
1 57 57 0
1 59 59...

output:

2
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
19
21
22
23
23
24
26
27
28
29
30
31
32
32
34
34
36
37
38
38
40
41
41
43
43
45
46
46
48
49
50
51
52
53
53
55
56
57
58
59
60
61
62
62
64
65
65
66
68
69
70
71
72
73
74
75
76
76
78
79
79
81
82
83
84
85
86
87
88
89
90
91
92
92
94
95
96
96
98
99
99
101
102
103...

result:

ok 25007 numbers

Test #14:

score: 0
Accepted
time: 38ms
memory: 32852kb

input:

19937 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 11 11 0
1 13 13 0
1 15 15 0
1 17 17 0
1 19 19 0
1 21 21 0
1 23 23 0
1 25 25 0
1 27 27 0
1 29 29 0
1 31 31 0
1 33 33 0
1 35 35 0
1 37 37 0
1 39 39 0
1 41 41 0
1 43 43 0
1 45 45 0
1 47 47 0
1 49 49 0
1 51 51 0
1 53 53 0
1 55 55 0
1 57 57 0
1 59 59...

output:

2
3
4
5
5
6
8
9
10
11
12
12
14
15
16
17
18
19
20
20
22
23
24
25
26
27
28
29
29
31
32
33
34
34
36
37
38
38
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
55
57
58
59
60
60
61
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
80
82
83
83
85
85
87
88
89
90
91
92
92
93
95
95
97
97
99
100
101
102
10...

result:

ok 30010 numbers

Test #15:

score: 0
Accepted
time: 36ms
memory: 44616kb

input:

99888 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 11 11 0
1 13 13 0
1 15 15 0
1 17 17 0
1 19 19 0
1 21 21 0
1 23 23 0
1 25 25 0
1 27 27 0
1 29 29 0
1 31 31 0
1 33 33 0
1 35 35 0
1 37 37 0
1 39 39 0
1 41 41 0
1 43 43 0
1 45 45 0
1 47 47 0
1 49 49 0
1 51 51 0
1 53 53 0
1 55 55 0
1 57 57 0
1 59 59...

output:

2
3
4
4
6
7
8
8
10
11
12
13
14
14
16
17
17
19
19
20
21
23
24
24
26
26
28
29
30
31
32
33
34
35
36
37
38
38
40
41
42
43
44
45
46
47
47
49
50
51
52
53
54
55
55
57
58
59
60
61
62
62
64
65
66
66
68
69
70
71
72
73
74
75
75
77
77
79
80
80
82
83
84
85
86
87
88
89
89
91
92
93
94
95
0
97
98
99
100
101
102
103...

result:

ok 16685 numbers

Test #16:

score: 0
Accepted
time: 29ms
memory: 44588kb

input:

99900 100000
1 2 2 0
1 3 3 0
1 5 5 0
1 7 7 0
1 9 9 0
1 13 13 0
1 14 14 0
1 15 15 0
1 16 16 0
1 17 17 0
1 18 18 0
1 22 22 0
1 26 26 0
1 28 28 0
1 34 34 0
1 38 38 0
1 41 41 0
1 42 42 0
1 43 43 0
1 44 44 0
1 47 47 0
1 48 48 0
1 50 50 0
1 52 52 0
1 53 53 0
1 57 57 0
1 58 58 0
1 63 63 0
1 64 64 0
1 66 66...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
19
20
22
22
23
25
26
27
28
29
30
30
32
33
34
35
36
36
38
39
40
40
42
43
43
45
46
47
47
48
50
51
52
52
54
55
56
57
58
58
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
74
75
77
77
79
80
81
81
83
83
84
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 16657 numbers

Test #17:

score: 0
Accepted
time: 32ms
memory: 37152kb

input:

49880 100000
1 1 1 0
1 3 3 0
1 5 5 0
1 6 6 0
1 7 7 0
1 8 8 0
1 10 10 0
1 11 11 0
1 12 12 0
1 13 13 0
1 15 15 0
1 16 16 0
1 18 18 0
1 20 20 0
1 23 23 0
1 25 25 0
1 28 28 0
1 29 29 0
1 30 30 0
1 31 31 0
1 34 34 0
1 36 36 0
1 37 37 0
1 38 38 0
1 41 41 0
1 44 44 0
1 46 46 0
1 47 47 0
1 50 50 0
1 51 51 0...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
37
39
40
41
42
43
44
45
46
47
48
49
49
50
51
53
53
55
56
56
58
59
60
61
62
63
64
65
66
66
67
69
70
70
72
73
74
74
76
77
78
79
80
80
82
83
84
85
85
87
88
89
90
91
91
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 25050 numbers

Test #18:

score: 0
Accepted
time: 32ms
memory: 39104kb

input:

69991 100000
1 1 1 0
1 2 2 0
1 3 3 0
1 4 4 0
1 7 7 0
1 8 8 0
1 10 10 0
1 11 11 0
1 13 13 0
1 14 14 0
1 16 16 0
1 18 18 0
1 21 21 0
1 22 22 0
1 23 23 0
1 28 28 0
1 29 29 0
1 30 30 0
1 31 31 0
1 32 32 0
1 33 33 0
1 35 35 0
1 36 36 0
1 38 38 0
1 41 41 0
1 43 43 0
1 44 44 0
1 45 45 0
1 47 47 0
1 51 51 0...

output:

1
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
17
19
19
20
22
23
24
25
26
27
28
29
29
30
31
33
34
35
36
37
38
39
40
41
42
43
44
44
45
47
47
49
49
51
51
53
54
54
56
56
57
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
89
91
92
93
94
95
96
97
98
99
99
100
102
103...

result:

ok 21745 numbers

Test #19:

score: 0
Accepted
time: 48ms
memory: 27600kb

input:

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

output:

400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000
400000...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 30ms
memory: 25892kb

input:

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

output:

499999

result:

ok 1 number(s): "499999"

Test #21:

score: 0
Accepted
time: 237ms
memory: 141868kb

input:

500000 500000
1 2 499999 0
2 10619 21321
1 2 499999 1
2 4541 27098
1 2 499999 2
2 14049 25964
1 2 499999 3
2 14009 21766
1 2 499999 4
2 21969 25034
1 2 499999 5
2 20318 26424
1 2 499999 6
2 5476 13830
1 2 499999 7
2 11376 20544
1 2 499999 8
2 23825 31130
1 2 499999 9
2 13392 21583
1 2 499999 10
2 14...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 250000 numbers

Test #22:

score: 0
Accepted
time: 204ms
memory: 246200kb

input:

500000 500000
1 2 499999 0
1 2 499999 1
1 2 499999 2
1 2 499999 3
1 2 499999 4
1 2 499999 5
1 2 499999 6
1 2 499999 7
1 2 499999 8
1 2 499999 9
1 2 499999 10
1 2 499999 11
1 2 499999 12
1 2 499999 13
1 2 499999 14
1 2 499999 15
1 2 499999 16
1 2 499999 17
1 2 499999 18
2 10457 32743
1 2 499999 19
1 ...

output:

19
37
55
74
93
112
131
150
169
188
207
226
245
264
282
301
320
339
358
377
396
414
433
451
470
489
507
526
545
564
583
602
620
639
658
677
696
715
734
753
772
791
810
829
848
867
886
905
924
943
962
981
1000
1019
1037
1056
1075
1093
1112
1131
1150
1169
1188
1207
1226
1245
1264
1283
1302
1320
1339
13...

result:

ok 25000 numbers

Test #23:

score: 0
Accepted
time: 193ms
memory: 253220kb

input:

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

output:

198
395
593
790
986
1184
1381
1578
1776
1973
2171
2368
2566
2764
2961
3158
3355
3553
3752
3949
4148
4342
4541
4738
4935
5132
5330
5528
5727
5924
6121
6317
6511
6709
6907
7105
7300
7495
7693
7889
8087
8284
8483
8678
8873
9070
9268
9465
9662
9861
10058
10257
10456
10654
10851
11049
11247
11444
11643
1...

result:

ok 2500 numbers

Test #24:

score: 0
Accepted
time: 220ms
memory: 27188kb

input:

500000 500000
2 5867 16765
2 16336 21829
2 365 8332
2 3476 23772
2 10061 29281
2 15154 17920
2 2730 26190
2 12206 20311
2 2796 7854
2 2879 3416
2 7367 19361
2 17713 29916
2 17591 23746
2 968 20791
2 11065 27307
2 6781 29041
2 304 6595
2 8136 21365
2 902 8024
2 19579 21294
2 7406 25110
2 355 14556
2 ...

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 497500 numbers

Test #25:

score: 0
Accepted
time: 217ms
memory: 28840kb

input:

500000 500000
2 4822 16785
2 2369 25217
2 29484 31892
2 9679 18680
2 5940 30047
2 15418 17033
2 4491 27164
2 14287 26036
2 20101 32632
2 12955 14400
2 10324 13942
2 6467 9498
2 6905 24563
2 1518 17570
2 5487 18546
2 2530 14279
2 18354 29838
2 190 29442
2 13237 24575
2 8205 16000
2 10698 20134
2 387 ...

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 497500 numbers

Test #26:

score: 0
Accepted
time: 56ms
memory: 29220kb

input:

499651 499819
1 6400 24883 122
1 25671 32598 50
1 16299 21284 409
2 11936 12350
1 18246 24697 258
1 14883 15687 52
1 3351 17757 737
1 8762 32048 62
1 6469 23595 583
1 9276 24906 547
1 29062 29615 962
1 16868 28904 45
1 14750 20861 536
1 22719 28644 948
1 2362 31514 599
1 5402 15020 16
1 15651 25544 ...

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

result:

ok 99831 numbers

Test #27:

score: 0
Accepted
time: 88ms
memory: 28416kb

input:

499632 499865
1 2751 5423 914
1 596 8107 930
1 16563 23046 383
1 9004 18074 636
2 2005 12216
2 6668 25007
1 14537 17179 901
1 24269 26767 796
1 10407 31672 290
1 3983 19839 531
1 15446 24964 438
1 1678 32722 575
2 2115 30066
2 20764 28552
2 3136 23085
2 18900 22477
1 19360 21930 839
1 17983 22174 36...

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 99867 numbers

Test #28:

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

input:

499619 499639
2 3372 11242
1 4748 29166 105
2 12596 16739
1 24692 32033 889
1 3785 15802 566
1 1191 19618 296
1 1467 28646 267
1 6003 7505 39
2 4288 14979
1 9027 9373 298
1 27159 28022 845
1 1809 26567 395
1 3414 26859 434
1 3994 7255 976
2 8663 32144
1 10491 11915 292
1 12799 31753 486
1 245 1124 2...

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

result:

ok 100323 numbers

Test #29:

score: 0
Accepted
time: 102ms
memory: 26432kb

input:

499596 499704
1 7976 17908 340
2 8675 18383
1 11560 17048 428
2 12185 16197
1 13706 16600 399
1 7991 29681 862
2 7754 19555
1 14779 19129 9
2 9514 31173
1 16722 23764 491
1 14525 22217 614
1 11283 27405 439
2 17063 24320
2 17599 30559
1 10943 14288 446
1 4742 17336 157
1 9 30888 976
1 17750 27329 68...

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

result:

ok 166486 numbers

Test #30:

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

input:

499573 499501
2 12579 24574
1 15555 20952 92
2 10525 17356
1 1538 7702 79
2 11611 29415
2 6975 21087
1 20198 26844 28
1 5552 19193 51
1 8727 15042 98
1 5386 7452 55
2 12179 16412
1 107 5707 43
1 21641 24359 11
2 5280 24915
1 14632 16599 16
2 2527 17287
1 5802 18715 78
1 15404 27570 75
1 17320 28610 ...

output:

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

result:

ok 166769 numbers

Test #31:

score: 0
Accepted
time: 89ms
memory: 26596kb

input:

499550 499799
1 17182 31240 2778
1 461 20170 2068
2 17664 19462
1 25542 31975 93
1 298 9463 2690
2 3764 21590
1 22962 31505 1577
2 3487 9608
2 7941 30792
1 19776 30949 1420
1 9832 10607 1296
2 21699 29082
2 9380 24399
1 9310 19270 1727
1 18321 18910 618
1 20487 29833 492
2 6542 31980
1 3478 9094 202...

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 166390 numbers

Test #32:

score: 0
Accepted
time: 195ms
memory: 192444kb

input:

399923 500000
1 1 1 0
1 2 2 0
1 5 5 0
1 6 6 0
1 7 7 0
1 8 8 0
1 9 9 0
1 10 10 0
1 12 12 0
1 13 13 0
1 17 17 0
1 19 19 0
1 22 22 0
1 23 23 0
1 24 24 0
1 25 25 0
1 27 27 0
1 28 28 0
1 30 30 0
1 32 32 0
1 34 34 0
1 36 36 0
1 41 41 0
1 44 44 0
1 45 45 0
1 46 46 0
1 49 49 0
1 51 51 0
1 52 52 0
1 55 55 0
...

output:

2
3
4
5
6
7
8
9
10
11
12
13
13
15
16
17
18
19
20
21
22
23
24
24
26
27
28
29
30
31
32
32
34
35
36
37
38
39
40
41
41
43
44
44
45
47
48
49
50
50
52
53
54
55
55
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
74
75
77
78
79
80
81
81
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
99
100
102
103...

result:

ok 99997 numbers

Test #33:

score: 0
Accepted
time: 210ms
memory: 193104kb

input:

399907 500000
1 1 1 0
1 2 2 0
1 3 3 0
1 4 4 0
1 5 5 0
1 6 6 0
1 7 7 0
1 8 8 0
1 12 12 0
1 14 14 0
1 17 17 0
1 21 21 0
1 22 22 0
1 25 25 0
1 29 29 0
1 34 34 0
1 38 38 0
1 40 40 0
1 41 41 0
1 42 42 0
1 43 43 0
1 44 44 0
1 46 46 0
1 50 50 0
1 51 51 0
1 52 52 0
1 54 54 0
1 55 55 0
1 56 56 0
1 60 60 0
1 ...

output:

2
3
4
5
5
7
7
9
9
11
12
13
14
15
16
17
18
19
19
21
22
23
24
24
26
27
28
29
30
31
32
33
34
35
36
37
38
39
39
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
59
61
62
63
64
65
66
66
68
69
70
71
72
73
74
75
75
77
77
79
79
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103...

result:

ok 100013 numbers

Test #34:

score: 0
Accepted
time: 203ms
memory: 191592kb

input:

399891 500000
1 1 1 0
1 3 3 0
1 5 5 0
1 6 6 0
1 8 8 0
1 12 12 0
1 15 15 0
1 17 17 0
1 18 18 0
1 19 19 0
1 21 21 0
1 22 22 0
1 23 23 0
1 25 25 0
1 26 26 0
1 28 28 0
1 29 29 0
1 30 30 0
1 33 33 0
1 39 39 0
1 43 43 0
1 45 45 0
1 53 53 0
1 57 57 0
1 58 58 0
1 60 60 0
1 67 67 0
1 69 69 0
1 70 70 0
1 71 7...

output:

1
3
4
5
6
7
8
8
9
11
12
13
13
15
16
17
17
18
20
21
22
23
24
25
26
27
28
29
29
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
50
52
53
54
55
56
57
58
58
60
61
62
63
64
65
66
67
68
69
70
71
71
73
74
75
76
77
78
79
80
81
81
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103...

result:

ok 99983 numbers

Test #35:

score: 0
Accepted
time: 229ms
memory: 192304kb

input:

399881 500000
1 2 2 0
1 3 3 0
1 5 5 0
1 7 7 0
1 13 13 0
1 15 15 0
1 17 17 0
1 18 18 0
1 19 19 0
1 23 23 0
1 24 24 0
1 25 25 0
1 26 26 0
1 27 27 0
1 30 30 0
1 32 32 0
1 33 33 0
1 35 35 0
1 38 38 0
1 42 42 0
1 45 45 0
1 46 46 0
1 48 48 0
1 50 50 0
1 54 54 0
1 58 58 0
1 59 59 0
1 63 63 0
1 68 68 0
1 70...

output:

2
3
4
5
6
6
8
9
10
10
12
12
14
15
16
17
18
19
20
21
22
23
24
24
26
27
28
29
30
31
32
33
34
35
35
37
38
38
39
41
42
42
44
45
46
47
48
48
50
51
51
53
54
54
56
57
58
59
60
61
62
63
64
64
66
67
68
69
70
71
71
73
74
75
76
77
77
79
80
81
81
83
84
85
86
87
88
89
90
91
91
93
94
95
96
97
98
99
99
101
101
103...

result:

ok 100006 numbers

Test #36:

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

input:

1 1
2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #37:

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

input:

500000 3
2 500000 500000
2 1 500000
2 1 1

output:

0
0
0

result:

ok 3 number(s): "0 0 0"

Test #38:

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

input:

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

output:

0
1
1
0
1
2
2
0
2

result:

ok 9 numbers

Test #39:

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

input:

1 2
1 1 1 500000
2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #40:

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

input:

500000 500000
1 489464 490018 0
2 1858 2407
2 175928 176164
2 295106 295546
2 229964 230543
1 445895 446455 0
2 296230 296991
2 499355 499541
2 91589 91864
2 242545 243515
2 194955 195156
2 65058 65157
2 341384 341778
2 319201 319352
1 481025 481258 0
1 473663 473725 0
1 60728 61688 0
1 468349 46865...

output:

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

result:

ok 249853 numbers

Test #41:

score: 0
Accepted
time: 186ms
memory: 26964kb

input:

500000 500000
2 321113 322694
1 107104 108663 0
1 380740 383552 0
1 480672 481455 0
2 375463 379713
2 179483 180848
2 312113 313583
2 137576 141661
1 284271 286518 0
2 48335 48376
1 442676 445803 0
2 424492 427789
2 44955 48337
1 65193 65495 0
1 421061 422740 0
1 78313 80591 0
1 373143 376495 0
2 40...

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

result:

ok 249849 numbers

Test #42:

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

input:

500000 500000
1 4514 499928 0
1 459701 462408 0
1 427807 430558 0
2 398886 398908
1 208323 214049 0
1 204464 207358 0
2 302368 307562
1 225441 234057 0
1 304487 306034 0
1 22372 30090 0
2 238482 246254
1 154724 163086 0
1 362484 363303 0
2 372432 377389
2 226791 235047
2 233475 237248
2 245848 24815...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
...

result:

ok 250076 numbers

Test #43:

score: 0
Accepted
time: 201ms
memory: 26728kb

input:

500000 500000
1 140047 140624 0
2 342675 343304
2 295553 308252
1 432489 474085 0
1 104731 108870 0
1 171755 193082 0
2 384681 385561
1 381451 426863 0
1 428273 467232 0
1 235587 262756 0
2 171042 184307
2 277582 320918
2 141384 183871
2 445184 465983
1 206979 219902 0
2 139375 152883
1 258023 27256...

output:

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

result:

ok 250083 numbers

Test #44:

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

input:

500000 500000
1 24104 458045 0
2 34001 41386
2 77994 478058
1 460353 482902 0
2 160522 216824
1 81667 105187 0
2 182555 191602
1 80980 101612 0
1 325475 332593 0
1 181954 250977 0
2 52839 66556
1 42679 85290 0
2 277084 352984
1 325474 404520 0
1 248548 295179 0
1 28767 79302 0
2 408433 484237
2 9775...

output:

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

result:

ok 249817 numbers

Test #45:

score: 0
Accepted
time: 215ms
memory: 27228kb

input:

500000 500000
2 10400 128835
2 130176 158006
1 248410 409629 0
2 186258 490874
2 118269 337067
1 97274 194713 0
1 69799 138302 0
2 378745 495562
2 175516 323061
2 409631 423724
2 245501 393023
1 3676 73903 0
1 158726 276315 0
1 282758 336884 0
2 277034 390275
2 90085 187772
1 147878 276000 0
1 35992...

output:

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

result:

ok 249944 numbers

Test #46:

score: 0
Accepted
time: 309ms
memory: 65972kb

input:

500000 500000
2 269562 270033
2 171488 171538
1 78972 79809 0
1 320657 321364 0
1 116003 116363 0
2 232560 232656
1 395819 396765 0
1 53569 54145 0
2 274743 274831
2 173933 174364
2 113889 113926
2 128141 128296
2 249224 250026
1 58844 59243 0
1 51034 51302 0
2 230932 231027
1 87472 87819 0
2 286907...

output:

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

result:

ok 249764 numbers

Test #47:

score: 0
Accepted
time: 313ms
memory: 46420kb

input:

500000 500000
1 77072 78687 0
1 295701 298663 0
1 336518 338863 0
1 482922 487104 0
1 156196 160008 0
1 302302 307135 0
2 187122 187936
2 246379 247984
1 175163 176906 0
1 228540 232010 0
2 2224 2447
1 315123 318266 0
1 165602 166801 0
2 299532 304475
2 352132 355590
1 78415 79543 1
1 188574 191584 ...

output:

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

result:

ok 249847 numbers

Test #48:

score: 0
Accepted
time: 259ms
memory: 46416kb

input:

500000 500000
2 434522 440751
1 160944 165081 0
2 205953 210630
1 348160 351478 0
2 24831 28169
2 177698 181188
1 31034 40043 0
2 245815 246691
2 392263 392598
2 282045 288442
1 37683 38792 1
1 344655 353533 1
1 92742 96173 0
2 242414 249107
1 285776 293648 0
2 68565 73918
2 233098 239192
1 460139 4...

output:

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

result:

ok 250235 numbers

Test #49:

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

input:

500000 500000
1 266171 266810 0
2 172764 195152
1 134957 180833 0
2 131355 150434
2 228992 265143
1 241600 259871 0
1 31340 35291 0
2 466693 496378
2 376602 417364
1 245152 266358 1
2 406683 416375
1 181115 199434 0
1 46960 51493 0
2 178813 199207
1 128993 160952 1
1 236303 267725 2
1 230776 268360 ...

output:

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

result:

ok 250061 numbers

Test #50:

score: 0
Accepted
time: 263ms
memory: 33756kb

input:

500000 500000
1 169179 208578 0
2 350069 408934
2 61784 468228
2 13565 34232
2 365709 370420
1 77481 477822 1
2 306206 392915
2 390986 479677
2 8167 43624
1 5490 419382 2
1 197672 296103 3
2 231494 255226
1 278995 285856 0
2 220249 264630
2 291620 327705
2 93813 497915
2 32969 462557
1 3777 474490 4...

output:

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

result:

ok 249811 numbers

Test #51:

score: 0
Accepted
time: 245ms
memory: 33316kb

input:

500000 500000
2 309297 415027
2 105111 145934
1 432409 457236 0
2 18247 353282
2 72400 206915
2 183667 187688
1 432317 464596 1
1 168169 483684 1
2 31254 63873
2 188325 414918
1 114883 368194 0
1 102556 293745 1
2 417669 442167
2 259349 325055
1 144032 469769 2
2 194125 307052
1 251597 282382 3
2 30...

output:

0
0
0
0
0
0
0
2
2
3
3
1
5
3
6
0
6
6
6
6
7
3
3
7
7
7
7
0
3
3
8
8
8
4
2
8
3
8
4
3
5
5
1
5
9
5
5
5
3
12
5
1
5
13
13
15
5
5
17
5
2
4
17
17
17
5
4
17
6
4
6
4
18
2
18
6
3
6
18
18
7
7
18
18
3
18
18
18
18
18
18
18
18
7
3
5
18
18
18
7
21
3
22
3
4
3
23
8
2
23
23
23
7
23
23
4
7
2
25
26
6
26
26
4
26
26
7
27
27
...

result:

ok 249835 numbers

Test #52:

score: 0
Accepted
time: 339ms
memory: 79360kb

input:

500000 500000
1 396520 397139 0
2 31969 32835
1 238070 238637 0
1 182959 183199 0
2 237882 237946
1 333379 334151 0
2 418111 418884
1 36766 37118 0
1 485461 485899 0
1 271563 272487 0
1 180957 181075 0
2 287804 287969
1 473198 473573 0
1 49197 49843 0
2 390159 390437
2 494259 494738
1 48479 49354 1
...

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

result:

ok 248201 numbers

Test #53:

score: 0
Accepted
time: 305ms
memory: 59524kb

input:

500000 500000
2 293577 296365
2 222443 222664
2 363186 367762
2 264391 265125
1 358091 359483 0
2 238723 239619
2 85065 87075
2 415622 417727
2 22456 27288
1 20398 22314 0
2 446992 448075
1 314688 317934 0
1 155054 156327 0
1 261614 265078 0
2 316264 317019
1 148582 149729 0
1 367759 369675 0
1 3872...

output:

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

result:

ok 248145 numbers

Test #54:

score: 0
Accepted
time: 304ms
memory: 52092kb

input:

500000 500000
2 131177 133923
2 361422 363020
2 264683 268793
2 130366 133803
2 142850 145680
2 447136 454443
2 286370 296094
1 90776 99710 0
2 250895 254846
2 174545 182875
2 173938 181112
2 221623 224655
1 266542 266582 0
2 132275 138344
2 107543 109277
2 68067 77119
1 235863 238601 0
1 8343 11085...

output:

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

result:

ok 250599 numbers

Test #55:

score: 0
Accepted
time: 265ms
memory: 41224kb

input:

500000 500000
1 47103 79904 0
2 113362 146371
2 200559 241131
1 333428 380487 0
2 423204 438774
2 329143 365075
2 228311 260952
1 5159 455482 1
2 421171 434300
2 132253 136300
1 443174 463270 0
2 449400 486298
2 453135 498665
1 430430 451561 1
1 201170 208455 0
1 297247 324998 0
1 250266 264687 0
1 ...

output:

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

result:

ok 250647 numbers

Test #56:

score: 0
Accepted
time: 272ms
memory: 34184kb

input:

500000 500000
2 121997 205564
2 331490 331867
1 306280 334793 0
2 235778 265746
1 26465 451255 1
1 371053 413845 0
1 188312 233013 0
2 123191 131116
1 383755 397821 1
1 159394 204245 1
1 199063 218944 2
2 13483 456600
2 52700 82939
2 44459 113897
1 51258 492470 3
2 369193 468230
1 367431 369234 0
1 ...

output:

0
0
0
0
3
0
0
2
0
4
0
0
0
1
5
1
2
5
2
7
0
7
3
7
7
0
0
7
7
2
3
8
3
4
8
8
2
2
3
3
5
2
0
8
4
5
7
2
8
8
7
8
8
0
7
3
8
0
8
8
3
6
6
11
3
7
7
7
6
12
5
4
3
8
3
15
11
0
10
12
17
18
11
18
12
11
18
7
12
3
20
13
7
4
13
6
20
8
3
20
8
7
8
8
21
11
3
9
5
12
9
9
13
7
4
8
14
9
9
6
6
9
24
13
17
24
5
9
5
24
2
13
24
1
1...

result:

ok 248197 numbers

Test #57:

score: 0
Accepted
time: 247ms
memory: 33964kb

input:

500000 500000
2 315918 482864
1 81856 439915 0
2 57887 380533
1 159288 297481 1
1 140548 141132 1
2 241654 415632
1 188139 461631 2
2 150470 375089
1 64549 195175 3
2 57593 201120
2 83811 224188
1 153379 430452 4
1 171867 420901 5
1 333750 392968 1
2 142562 245516
2 75139 493427
1 252555 312043 3
2 ...

output:

0
1
2
3
4
4
6
6
2
0
6
6
2
7
3
7
3
1
2
9
5
10
10
2
5
10
2
2
12
12
2
1
2
12
12
2
14
15
4
4
7
6
4
17
17
17
17
17
9
9
6
9
6
9
0
9
18
6
18
18
19
4
9
7
20
9
9
20
7
9
9
3
24
3
26
26
10
7
7
27
0
27
7
1
27
7
27
12
28
3
8
28
29
8
31
3
8
34
9
5
35
37
37
0
38
10
3
38
38
39
0
15
41
41
3
44
12
12
44
1
45
12
17
5
...

result:

ok 248150 numbers

Test #58:

score: 0
Accepted
time: 409ms
memory: 92872kb

input:

500000 500000
1 175178 175937 0
1 413768 414470 0
1 456143 456925 0
2 38628 39000
1 351227 351964 0
1 67912 68130 0
1 386229 386625 0
2 441862 442114
2 232675 233166
1 332814 333347 0
2 112889 113313
2 335257 335585
2 309282 309528
2 215064 215948
2 76751 77268
1 226332 226491 0
2 59070 59130
1 2445...

output:

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

result:

ok 250017 numbers

Test #59:

score: 0
Accepted
time: 357ms
memory: 78488kb

input:

500000 500000
2 315297 318250
1 149720 152467 0
2 2189 497902
1 330569 334534 0
1 323205 324032 0
1 241899 246437 0
2 124778 127151
2 23911 25123
1 141540 143453 0
1 392808 394913 0
2 78220 81359
1 479749 481628 0
1 154774 157014 0
2 142482 145717
2 463997 467603
1 255879 260577 0
2 224019 228871
1 ...

output:

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

result:

ok 249995 numbers

Test #60:

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

input:

500000 500000
1 165999 174665 0
1 159644 161727 0
1 221932 226286 0
2 45778 54721
2 383773 383858
2 327211 328084
1 404761 411928 0
1 39399 46771 0
2 245383 246258
1 278201 281382 0
1 307224 315101 0
2 166088 167862
2 442021 443665
2 128326 129434
1 178410 178629 0
1 1199 5179 0
2 89538 90138
2 4251...

output:

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

result:

ok 249884 numbers

Test #61:

score: 0
Accepted
time: 305ms
memory: 58932kb

input:

500000 500000
1 26866 59135 0
2 134202 156555
1 64856 68701 0
2 212487 218359
2 109678 122438
1 246963 274479 0
1 374217 421976 0
1 312718 359412 0
1 474177 496332 0
1 479280 487324 1
2 445997 464719
2 16917 28504
1 250368 284479 1
1 427005 454518 0
1 308644 321181 1
1 225443 254743 2
1 313013 34109...

output:

0
0
0
0
1
2
2
0
1
0
0
3
2
4
1
1
1
1
3
5
1
3
0
3
1
3
2
0
2
0
2
2
2
2
2
7
2
2
2
0
0
3
10
3
1
2
0
3
4
11
0
11
11
2
2
2
1
2
0
0
2
1
12
12
5
0
3
3
3
5
4
7
0
4
6
2
4
0
5
2
3
14
14
14
5
4
1
2
5
8
3
8
2
4
8
8
8
8
3
19
5
5
5
8
8
11
6
1
5
4
19
5
12
7
19
10
3
4
8
5
6
5
1
20
21
12
5
3
4
5
4
1
1
6
6
3
8
0
2
5
2
...

result:

ok 249856 numbers

Test #62:

score: 0
Accepted
time: 314ms
memory: 50592kb

input:

500000 500000
2 385067 484526
1 471712 487744 0
2 62460 478150
1 327735 402036 0
2 323885 393068
2 244578 262970
2 28095 455562
1 231200 278471 0
1 4515 459512 1
2 133427 200082
1 308048 339857 2
1 258088 345675 3
1 21391 462198 4
1 124323 217524 0
2 245893 314330
2 417264 421184
2 232631 240992
1 3...

output:

0
1
1
0
1
0
2
0
2
5
2
5
0
5
3
2
6
2
7
0
2
7
1
1
7
3
1
1
3
5
6
0
4
4
9
5
5
3
10
6
10
10
0
4
2
10
2
2
2
5
10
7
10
7
7
5
5
0
9
11
7
5
9
7
1
11
3
2
6
3
0
4
9
3
3
6
0
11
8
13
3
2
4
13
7
3
3
13
8
4
15
15
16
8
4
15
17
8
5
17
16
8
3
3
17
10
17
0
17
17
8
9
8
2
3
7
23
5
11
5
0
1
8
2
1
25
11
26
3
16
1
2
5
8
28...

result:

ok 250011 numbers

Test #63:

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

input:

500000 500000
2 218434 248558
1 273741 301881 0
2 151717 434105
2 28721 433219
2 71014 175890
1 64234 256468 0
2 111879 299005
2 75381 443352
1 233652 402097 1
2 212384 245696
2 830 205361
2 139742 169995
2 177760 341446
1 32886 61005 0
2 417257 444757
1 45527 395970 2
1 3721 114055 1
1 219522 37159...

output:

0
1
1
0
1
1
2
1
1
2
0
1
2
0
2
1
2
1
1
0
8
1
1
11
1
12
11
12
12
1
2
12
14
14
14
2
14
3
17
7
18
3
19
2
21
4
24
25
25
25
5
1
3
3
5
7
1
5
7
3
7
27
7
7
4
4
30
7
7
11
4
32
5
7
7
36
36
36
2
39
40
6
4
41
41
5
10
43
43
5
1
44
44
2
4
4
48
48
48
51
51
11
51
11
32
51
51
6
51
51
32
7
52
52
11
11
6
53
12
53
11
5
...

result:

ok 249992 numbers
English 繁體中文 简体中文

服务器时间: 2024-12-12 00:40:03 | 开源项目