QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267957#6608. Descent of Dragonsuoj#TL 3406ms23548kbC++172.2kb2023-11-27 21:34:432023-11-27 21:34:43

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11700kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:


result: