QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460962#8354. T2houzhiyuan100 ✓384ms34628kbC++141.6kb2024-07-02 14:22:102024-07-02 14:22:11

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 2ms
memory: 3656kb

input:

3205 5000 5000
1 1
2 1
3 1
7 1
8 1
9 1
10 1
11 1
12 2
13 1
14 2
16 1
17 2
20 3
22 1
24 1
26 2
27 1
30 1
32 2
33 1
34 1
41 1
44 2
49 2
51 1
54 2
58 2
61 2
65 2
66 1
68 2
70 1
71 2
72 2
74 8
75 3
76 5
77 1
78 7
79 5
80 5
81 1
82 2
84 1
86 6
87 6
88 3
89 9
90 5
91 1
92 2
93 3
95 7
96 2
97 2
98 8
99 8
1...

output:

81
69
32
40
42
90
32
83
44
50
91
70
53
65
82
50
68
59
86
38
67
70
79
45
50
65
88
43
37
74
29
63
73
7
53
57
75
20
44
50
47
36
73
55
30
42
78
75
47
80
66
87
36
21
73
23
88
37
68
53
57
28
46
59
56
69
28
84
26
41
64
59
35
60
5
42
35
74
63
54
87
73
83
59
39
38
45
48
89
69
62
23
82
84
31
85
56
87
81
80
66...

result:

ok 2487 lines

Test #2:

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

input:

162 5000 5000
836 4
837 5
838 5
839 5
840 4
841 4
842 4
843 4
844 4
845 4
846 5
847 4
848 4
849 5
850 4
851 5
852 5
853 4
854 5
855 4
856 5
857 4
858 4
859 4
860 5
861 5
862 4
863 4
864 4
865 5
866 5
867 4
868 5
869 4
870 4
871 5
872 4
873 4
874 5
875 4
876 4
877 5
878 5
879 4
880 4
881 5
882 5
883 ...

output:

5
0
0
3
0
5
5
0
0
4
5
0
0
0
4
3
0
5
4
0
0
0
0
0
0
4
0
0
4
0
0
5
0
0
3
3
0
0
3
0
0
4
4
0
3
3
0
4
0
0
0
4
0
0
0
0
0
0
0
0
5
0
0
0
0
0
3
0
0
0
4
0
0
5
0
0
3
5
4
0
0
3
0
4
5
4
0
0
5
4
0
0
0
0
3
0
0
0
4
5
5
5
0
4
4
4
3
5
5
5
0
3
0
3
0
4
0
4
5
3
0
0
0
3
0
5
3
0
0
0
0
0
3
0
0
4
0
0
0
0
3
4
5
3
0
4
5
3
5
0
...

result:

ok 4838 lines

Test #3:

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

input:

3182 5000 5000
1 2597
2 404
3 409
4 220
5 604
6 248
7 48
8 145
9 97
10 356
11 111
12 158
13 192
14 309
15 168
16 251
17 234
18 68
19 223
20 111
21 235
22 152
23 188
24 48
25 75
26 9
27 34
28 153
29 58
30 18
31 153
32 76
33 150
34 52
35 121
36 37
37 7
38 79
39 96
40 101
41 8
42 66
43 61
44 77
45 83
4...

output:

404
464
0
894
701
60
758
461
758
413
758
59
708
607
551
724
59
304
97
403
290
193
194
0
242
49
49
2
363
301
146
205
363
9
97
146
335
333
335
99
410
354
243
343
97
334
343
211
211
1
236
142
9
134
194
148
60
134
168
128
94
101
0
168
76
165
101
100
61
156
95
2
111
109
152
51
9
9
110
63
20
72
44
44
71
5...

result:

ok 1818 lines

Test #4:

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

input:

3205 5000 5000
1 1
3 1
6 2
7 1
9 1
12 1
15 1
16 1
18 1
19 1
30 1
37 2
39 1
40 1
43 1
47 1
50 1
52 1
54 1
59 1
63 1
65 1
66 1
70 1
71 52
72 42
73 55
74 37
75 42
76 38
77 36
78 22
79 56
80 12
81 29
82 10
83 53
84 40
85 42
86 39
87 54
88 6
89 2
90 36
91 29
92 6
93 4
94 23
95 20
96 43
97 13
98 1
99 1
10...

output:

39
79
68
18
80
74
23
15
23
39
22
35
60
24
42
67
33
52
16
82
39
41
49
46
67
80
53
74
41
64
45
51
73
73
58
68
68
41
78
57
12
6
57
81
76
38
14
66
53
76
64
40
76
25
18
16
38
59
26
48
80
79
28
66
37
34
43
22
59
80
21
19
44
65
42
63
65
22
73
60
26
63
80
21
69
11
20
14
73
31
78
53
64
16
73
78
80
32
16
40
5...

result:

ok 4030 lines

Test #5:

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

input:

3240 5000 5000
1 4544
2 2194
3 616
4 99
5 68
6 558
7 36
8 322
9 394
10 113
11 314
12 396
13 221
14 349
15 49
16 219
17 42
18 239
19 178
20 146
21 48
22 96
23 205
24 162
25 14
26 188
27 58
28 71
29 65
30 16
31 111
32 51
33 119
34 63
35 32
36 75
37 100
38 90
39 65
40 44
41 7
42 82
43 62
44 26
45 84
46...

output:

203
819
2293
2195
224
720
99
822
252
933
784
953
224
618
252
316
423
726
358
761
218
775
421
558
219
217
220
594
203
0
68
217
594
660
252
558
316
335
771
207
204
36
296
565
744
728
7
332
285
186
332
280
216
220
239
240
626
249
558
680
678
272
636
246
562
633
275
348
87
3
68
246
288
249
87
72
69
85
7...

result:

ok 2448 lines

Test #6:

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

input:

3130 5000 5000
1 3
2 1
4 1
5 1
6 1
8 1
9 3
10 2
11 2
13 1
14 2
15 2
17 1
19 1
23 1
24 1
25 1
27 2
30 1
33 2
34 1
35 1
36 1
37 2
38 1
39 3
40 1
41 1
43 2
45 1
46 1
48 1
49 2
50 1
51 1
52 1
53 3
54 2
58 1
60 1
62 1
63 1
64 1
65 1
66 1
68 2
69 2
71 4
72 7
74 3
75 6
77 3
78 9
79 6
80 3
81 7
82 8
83 6
84...

output:

22
27
81
59
54
9
53
82
69
28
52
69
51
47
75
57
72
72
50
31
37
7
35
26
36
4
23
16
35
20
57
60
48
29
21
22
49
60
17
23
7
18
44
14
45
27
41
63
25
12
35
43
56
45
61
53
52
21
26
21
20
55
1
47
25
37
13
23
49
15
26
38
50
11
53
27
42
22
51
50
31
55
56
49
14
9
34
41
33
20
49
46
2
46
13
38
37
29
43
14
28
11
3...

result:

ok 1870 lines

Test #7:

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

input:

3220 5000 5000
1 1716
2 2046
3 1005
4 308
5 629
6 117
7 344
8 562
9 27
10 244
11 177
12 141
13 330
14 87
15 306
16 219
17 211
18 145
19 254
20 58
21 215
22 37
23 135
24 194
25 38
26 12
27 175
28 97
29 39
30 89
31 72
32 64
33 7
34 62
35 30
36 130
37 132
38 12
39 21
40 26
41 68
42 110
43 21
44 108
45 ...

output:

311
2184
2051
117
1860
1743
115
1762
1755
1837
50
1831
1767
1921
1780
2061
1837
28
1719
47
2063
1767
2099
2073
87
115
1718
3
115
1719
1842
1756
1723
40
1756
1758
1843
2100
27
88
2064
1803
28
1781
1842
1716
27
117
1718
1781
1
2345
65
48
28
3
1843
34
2346
1868
1743
88
1803
34
2063
2345
1810
2060
1746
...

result:

ok 3964 lines

Test #8:

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

input:

3157 5000 5000
2 1
4 1
5 1
8 2
10 1
16 1
18 1
22 1
24 1
25 1
26 2
29 2
34 1
36 1
40 1
42 2
43 1
45 2
46 1
47 1
49 3
51 1
55 1
57 1
67 3
68 1
70 1
71 12
72 18
73 15
74 49
75 15
76 12
77 49
78 9
79 5
80 46
81 38
82 4
83 46
84 58
85 26
86 14
87 13
88 39
89 5
90 51
91 24
92 44
93 51
94 19
95 10
96 16
97...

output:

62
82
36
41
48
71
71
83
78
64
16
80
27
72
72
37
0
30
61
35
70
5
19
56
48
19
49
57
40
24
76
45
69
48
45
42
25
63
13
42
38
45
54
42
45
75
6
34
45
58
5
78
64
56
17
74
70
72
41
69
33
70
64
33
26
77
27
19
36
37
5
29
66
38
20
54
23
34
33
55
18
20
52
67
25
5
8
27
22
41
29
41
72
18
43
21
29
5
49
11
39
60
49...

result:

ok 2523 lines

Test #9:

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

input:

3233 5000 5000
1 4147
2 1080
3 1621
4 237
5 939
6 694
7 374
8 42
9 501
10 222
12 195
13 208
14 75
15 298
16 141
17 213
18 232
19 196
20 65
21 91
22 4
23 48
24 200
25 53
26 139
27 80
28 109
29 19
30 132
31 123
32 43
33 16
34 129
35 138
36 85
37 112
38 44
39 44
40 42
41 103
42 76
43 43
44 19
45 65
46 ...

output:

701
316
247
463
703
261
104
26
240
698
164
240
703
193
76
53
7
52
53
71
28
8
20
9
194
200
26
217
198
151
162
163
143
167
163
152
113
58
7
87
167
47
104
143
58
200
163
201
1
71
145
24
57
38
38
41
66
72
24
145
63
147
47
5
136
78
61
5
71
29
72
19
3
24
66
78
84
3
84
50
70
74
0
68
82
3
90
17
9
87
2
5
17
...

result:

ok 1767 lines

Test #10:

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

input:

411 5000 5000
1253 3
1254 3
1255 3
1256 3
1257 3
1258 3
1259 3
1260 3
1261 3
1262 3
1263 3
1264 3
1265 3
1266 3
1267 3
1268 3
1269 3
1270 3
1271 3
1272 3
1273 3
1274 3
1275 3
1276 3
1277 3
1278 3
1279 3
1280 3
1281 3
1282 3
1283 3
1284 3
1285 3
1286 3
1287 3
1288 3
1289 3
1290 3
1291 3
1292 3
1293 3...

output:

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

result:

ok 4589 lines

Subtask #2:

score: 13
Accepted

Test #11:

score: 13
Accepted
time: 324ms
memory: 25760kb

input:

1277351 1 2000000
2 2
5 1
7 3
8 4
10 1
12 1
15 2
16 1
18 1
22 1
25 1
28 3
29 1
32 1
35 1
36 1
38 2
40 1
41 2
42 1
43 2
44 2
45 1
48 1
49 1
50 2
54 2
55 2
56 1
58 2
59 2
60 2
62 1
66 1
68 3
69 1
70 3
72 2
76 1
78 1
79 2
81 2
82 3
84 2
85 1
86 2
89 1
90 2
91 2
92 1
93 1
96 3
98 3
99 2
100 3
101 1
102 ...

output:

1771

result:

ok single line: '1771'

Test #12:

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

input:

1276072 1 2000000
48 555
69 189
138 916
164 856
170 174
189 850
197 1043
211 907
218 121
237 183
238 2498
240 94
253 841
261 990
263 593
292 356
295 1018
324 576
328 1364
333 1133
344 16
350 1777
361 225
364 102
371 130
373 956
377 22
387 318
394 1020
395 78
398 445
402 1076
408 43
409 654
411 1143
...

output:

5128

result:

ok single line: '5128'

Test #13:

score: 0
Accepted
time: 302ms
memory: 26116kb

input:

1287842 1 2000000
2 1
4 1
5 1
12 2
15 1
16 2
17 1
18 1
20 1
21 1
24 3
25 1
27 3
32 1
33 3
36 3
38 1
39 1
40 1
42 2
43 1
44 2
47 1
49 2
50 1
51 1
53 1
54 2
55 1
56 1
57 1
58 1
59 1
61 3
66 1
71 1
72 1
73 1
77 2
79 1
80 1
81 2
82 1
83 1
84 1
86 2
87 2
88 2
93 1
94 1
96 2
97 1
98 2
99 2
100 1
102 1
103...

output:

1563

result:

ok single line: '1563'

Test #14:

score: 0
Accepted
time: 151ms
memory: 25992kb

input:

1287726 1 2000000
31 2304
38 1844
59 7080
66 935
69 790
91 2467
96 6595
100 187
113 2983
118 11250
119 2531
123 1634
129 3513
131 2806
132 9065
133 6537
139 8785
141 2432
144 185
162 2736
173 5683
176 710
181 3468
189 2900
191 5380
193 2120
194 1482
195 3129
202 189
203 1295
207 31
209 1308
211 3118...

output:

2527

result:

ok single line: '2527'

Test #15:

score: 0
Accepted
time: 107ms
memory: 25828kb

input:

1275261 1 2000000
261 1
282 1
289 1
315 2
322 1
323 1
325 1
329 2
330 1
333 3
334 1
336 1
339 1
354 1
363 2
382 2
384 3
385 2
408 1
409 2
412 1
437 1
438 1
449 2
457 1
469 1
471 1
473 1
487 4
505 2
517 1
520 1
525 1
526 1
528 1
531 1
533 1
541 1
548 1
549 1
552 1
557 3
565 1
566 1
582 1
587 1
593 2
...

output:

656

result:

ok single line: '656'

Test #16:

score: 0
Accepted
time: 169ms
memory: 26040kb

input:

1277958 1 2000000
41 45762
42 39827
47 7603
49 27415
51 34200
56 20936
67 22930
74 13714
78 8175
81 22953
88 19166
89 14746
90 759
92 6808
97 3985
103 9270
104 3971
105 9870
110 9753
111 4980
112 17645
113 17083
114 15474
115 3342
117 14040
118 13826
122 1633
125 12528
126 4024
128 8819
132 14262
13...

output:

40964

result:

ok single line: '40964'

Test #17:

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

input:

1285514 1 2000000
148 1
164 1
180 3
236 2
255 1
264 2
265 2
281 1
285 2
286 1
295 1
315 2
336 2
343 1
358 1
361 1
368 1
372 1
380 1
394 1
402 1
403 1
419 1
424 2
427 1
434 1
437 1
449 1
451 2
457 1
464 1
467 5
473 1
476 1
479 1
484 1
494 1
496 1
503 1
525 1
526 2
538 1
542 1
545 1
547 1
551 1
562 2
...

output:

1326

result:

ok single line: '1326'

Test #18:

score: 0
Accepted
time: 109ms
memory: 26064kb

input:

1285483 1 2000000
132 11882
175 10006
187 5406
193 2944
205 178
225 7158
245 7573
246 6539
270 5092
273 5858
279 2050
287 5157
293 5816
297 180
299 195
303 3886
309 4296
312 4111
314 2781
322 3666
324 741
335 1477
336 2217
337 1536
341 24
345 4958
346 719
347 1204
375 2312
377 1269
381 4655
388 892
...

output:

1

result:

ok single line: '1'

Test #19:

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

input:

166661 1 2000000
500003 3
500004 3
500005 3
500006 3
500007 3
500008 3
500009 3
500010 3
500011 3
500012 3
500013 3
500014 3
500015 3
500016 3
500017 3
500018 3
500019 3
500020 3
500021 3
500022 3
500023 3
500024 3
500025 3
500026 3
500027 3
500028 3
500029 3
500030 3
500031 3
500032 3
500033 3
5000...

output:

3

result:

ok single line: '3'

Test #20:

score: 0
Accepted
time: 8ms
memory: 11940kb

input:

66662 1 2000000
333336 4
333337 4
333338 5
333339 5
333340 5
333341 5
333342 4
333343 4
333344 5
333345 5
333346 5
333347 5
333348 5
333349 4
333350 4
333351 5
333352 4
333353 5
333354 5
333355 4
333356 5
333357 5
333358 4
333359 4
333360 4
333361 4
333362 5
333363 5
333364 5
333365 4
333366 4
33336...

output:

5

result:

ok single line: '5'

Subtask #3:

score: 15
Accepted

Test #21:

score: 15
Accepted
time: 260ms
memory: 11032kb

input:

5000 5000 2000000
1 1
2 1
3 1
4 1
6 1
7 1
8 1
9 1
10 1
11 1
14 1
15 3
17 2
18 2
21 1
22 1
24 1
25 3
27 1
28 2
29 1
30 1
31 1
32 1
33 1
34 1
35 1
37 1
38 1
39 1
40 2
41 2
43 1
45 1
47 1
49 1
50 1
51 1
54 1
55 1
56 1
61 1
62 2
64 1
65 1
67 2
68 2
70 2
72 2
74 1
76 3
79 2
82 4
83 2
84 1
88 1
91 1
92 1
...

output:

1778
591
934
692
980
1908
704
1449
1616
466
1670
1478
1322
1341
1033
1661
770
1305
1878
1816
819
949
1685
1624
1718
1311
1445
1365
812
1397
1524
1501
969
164
1891
1847
1393
1415
625
1517
972
1268
1887
892
936
391
1508
901
1257
1279
1083
1291
1337
1894
386
1613
461
568
1698
1716
1686
1060
1544
473
15...

result:

ok 2447 lines

Test #22:

score: 0
Accepted
time: 216ms
memory: 11216kb

input:

5000 5000 2000000
1 813802
2 134681
3 83044
4 315718
5 197248
6 119339
7 261285
8 156156
9 196051
10 173937
11 48028
12 116232
13 6597
14 105636
15 21987
16 108656
17 21158
18 30668
19 61562
20 79298
21 47690
22 23541
23 19543
24 45753
25 59750
26 24095
27 4249
28 69164
29 19751
30 8053
31 55434
32 ...

output:

1079713
1086432
218161
457276
540476
83324
10854
83045
208252
291139
7603
147552
120745
83690
95147
7154
168305
164019
137480
116156
142741
6717
126387
94326
89848
149896
11005
164660
150058
115697
139735
93890
147536
142988
143041
55759
87701
59518
10854
36364
28769
32607
7153
32726
21713
35936
434...

result:

ok 1017 lines

Test #23:

score: 0
Accepted
time: 53ms
memory: 11036kb

input:

5000 5000 2000000
4 1
16 1
41 1
60 1
86 1
93 1
125 1
126 1
184 1
249 1
260 1
308 1
311 1
322 1
424 1
427 1
451 1
477 1
523 1
629 1
660 1
680 1
694 1
724 1
731 1
741 1
742 1
743 1
744 1
768 1
798 1
822 1
872 1
874 1
897 1
904 1
950 1
971 1
973 1
982 1
1013 1
1024 1
1047 1
1063 1
1080 1
1121 1
1129 1
...

output:

389
1146
1376
1232
290
414
1302
622
85
158
932
352
462
605
787
136
310
402
275
1341
88
87
897
1259
497
1282
197
689
1369
299
525
808
1206
701
444
560
36
1393
393
791
459
923
1016
826
823
491
724
482
532
1246
296
1135
1222
890
763
979
75
8
686
734
923
93
210
979
727
759
1113
633
437
1368
48
1219
1161...

result:

ok 4022 lines

Test #24:

score: 0
Accepted
time: 238ms
memory: 11016kb

input:

5000 5000 2000000
1 1627103
2 716626
3 665364
4 497570
5 189147
6 82325
7 14868
8 137172
9 169535
10 141421
11 159956
12 63184
13 26342
14 6512
15 18048
16 101458
17 27905
18 12716
19 8580
20 12169
21 12097
22 55619
23 79732
24 18682
25 32267
26 4738
27 32772
28 29008
29 59773
30 19663
31 613
32 579...

output:

1651478
115856
717629
27591
109911
190188
717766
717764
104709
98950
104842
222065
26120
26121
272927
165070
1040
137173
219809
105155
178385
115243
34098
42137
138325
27585
234981
243886
1750
159494
124476
104333
34104
110222
249465
116231
245929
245630
249458
106389
226025
243562
226011
112287
339...

result:

ok 2513 lines

Test #25:

score: 0
Accepted
time: 184ms
memory: 11080kb

input:

5000 5000 2000000
3 1
5 1
6 1
7 1
8 1
11 2
14 1
15 1
16 1
22 1
25 1
27 2
28 1
31 1
32 1
33 1
34 2
35 1
36 1
38 1
42 1
43 2
45 1
46 1
50 1
51 1
52 1
53 1
55 1
64 1
65 1
68 1
70 1
71 1
72 1
73 1
76 1
77 1
78 1
85 1
89 1
91 1
92 1
93 1
94 2
96 1
97 1
109 1
110 1
111 2
120 1
126 2
129 1
132 2
134 1
140 ...

output:

641
522
1141
1372
922
1191
1490
638
1371
1534
841
117
1512
1392
943
375
1059
1044
393
711
1413
947
1143
436
893
1435
845
360
211
752
1428
529
1355
978
478
1348
1370
476
556
1537
1330
814
939
908
1155
1303
447
1047
896
379
692
457
460
182
402
845
1078
1247
400
489
977
1116
1494
139
1053
1303
1323
613...

result:

ok 988 lines

Test #26:

score: 0
Accepted
time: 234ms
memory: 11088kb

input:

5000 5000 2000000
1 364044
2 300803
3 218421
4 365847
5 63539
6 324669
7 31959
8 232865
9 32717
10 27341
11 29651
12 135000
13 27768
14 117739
15 77947
16 121183
17 50492
18 57533
19 25423
20 33988
21 67414
22 62686
23 85739
24 42313
25 78019
26 47515
27 19440
28 11992
29 29580
30 24818
31 24986
32 ...

output:

431373
431459
33615
459688
648833
647576
459684
459769
681755
647262
33269
431459
650357
615996
461254
647325
431929
649876
366874
364191
730022
647705
399069
431042
222732
283137
97208
283532
433688
33653
95629
1703
1655
63688
33614
283263
433696
433561
173
365936
285891
218555
219728
284791
251700...

result:

ok 4009 lines

Test #27:

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

input:

5000 5000 2000000
4 2
6 1
7 1
9 1
11 2
12 2
14 1
16 2
17 1
18 1
19 1
20 1
23 1
25 3
26 2
27 2
28 1
29 2
30 2
33 2
35 2
36 1
38 1
39 1
41 1
43 1
46 1
47 1
48 1
50 2
54 1
56 1
59 1
60 1
64 1
65 1
66 1
68 1
69 1
70 1
73 2
74 3
75 1
76 1
77 1
80 2
82 1
83 2
84 1
86 1
90 1
92 2
93 2
97 1
98 1
99 1
101 1
...

output:

1661
1428
964
1155
1224
876
1878
1277
384
379
1532
1772
211
983
1287
184
1757
1023
1121
1858
363
1184
886
1621
781
992
1456
1896
904
1818
888
1276
972
1170
1906
459
829
760
759
1603
1035
1131
1508
717
698
1638
859
773
883
1750
1690
1324
1801
1611
646
994
1570
629
1235
1883
598
520
881
838
748
846
14...

result:

ok 2475 lines

Test #28:

score: 0
Accepted
time: 221ms
memory: 11020kb

input:

5000 5000 2000000
1 12616
2 968067
3 471331
4 498123
5 174683
6 288045
7 123021
8 247009
9 20861
10 5184
11 167706
12 33538
13 107153
14 4583
15 81246
16 98517
17 42633
18 55345
19 80376
20 94003
21 73198
22 17908
23 36380
24 41210
25 44169
26 63612
27 53280
28 41724
29 57409
30 12451
31 387
32 2001...

output:

481105
39138
38751
26523
26608
26579
31299
86474
33933
27697
67544
87101
89858
61006
106221
80467
105911
7878
105849
29743
103834
66950
28521
106408
11570
25280
55470
17978
104814
100941
80269
671
25589
78737
20074
57375
3428
6296
60777
17819
8988
75335
61753
75200
2009
43220
49778
50991
62969
9843
...

result:

ok 978 lines

Test #29:

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

input:

5000 5000 2000000
500003 3
530259 2
661666 3
661667 3
661668 3
661669 3
661670 3
661671 3
661672 3
661673 3
661674 3
661675 3
661676 3
661677 3
661678 3
661679 3
661680 3
661681 3
661682 3
661683 3
661684 3
661685 3
661686 3
661687 3
661688 3
661689 3
661690 3
661691 3
661692 3
661693 3
661694 3
661...

output:

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

result:

ok 4036 lines

Test #30:

score: 0
Accepted
time: 40ms
memory: 11124kb

input:

5000 5000 2000000
333336 4
333337 5
356720 3
395001 5
395002 5
395003 4
395004 4
395005 5
395006 5
395007 4
395008 5
395009 5
395010 4
395011 5
395012 5
395013 5
395014 5
395015 4
395016 5
395017 5
395018 4
395019 4
395020 5
395021 4
395022 4
395023 5
395024 5
395025 5
395026 4
395027 5
395028 5
395...

output:

5
4
4
4
5
0
4
4
0
3
0
0
4
5
0
0
0
0
4
3
3
5
0
0
0
3
4
4
4
0
4
4
0
4
0
4
0
4
4
0
4
3
4
0
0
4
4
3
0
0
4
0
0
4
0
5
0
0
0
0
4
0
4
0
4
0
0
4
0
4
4
4
3
0
0
4
4
0
5
3
4
0
3
0
4
0
4
4
4
4
5
4
0
0
4
4
3
3
4
0
4
0
0
4
0
4
0
0
4
0
0
0
4
4
0
0
4
4
4
0
0
4
4
0
0
4
4
0
4
3
0
0
4
0
4
5
0
3
0
0
3
0
0
3
4
4
0
4
3
4
...

result:

ok 2480 lines

Subtask #4:

score: 21
Accepted

Test #31:

score: 21
Accepted
time: 53ms
memory: 6476kb

input:

191299 5000 300000
1 1
5 1
6 2
7 1
8 1
10 1
11 2
12 2
17 1
18 1
19 1
20 1
21 1
22 2
25 1
28 1
29 2
30 1
31 2
34 1
36 1
37 1
38 1
40 1
42 1
43 1
44 1
45 1
47 2
48 1
51 1
53 3
54 2
56 2
58 2
59 2
61 2
63 4
64 2
67 1
68 2
69 2
70 1
72 1
76 1
77 1
78 1
80 2
83 1
84 1
87 1
88 1
89 1
91 2
93 1
95 1
96 1
9...

output:

221
531
204
303
706
486
663
481
540
430
356
588
407
521
570
547
403
316
279
618
128
431
492
453
578
427
643
430
569
233
98
439
698
621
647
549
567
299
627
227
365
338
433
306
547
286
631
581
574
629
667
451
680
140
273
682
607
302
323
697
193
613
557
523
517
702
544
570
355
542
390
196
260
430
296
6...

result:

ok 2476 lines

Test #32:

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

input:

191816 5000 300000
1 74901
2 103360
3 89547
4 67750
5 40186
6 28389
7 24182
8 26076
9 5630
10 26706
11 12730
12 17632
13 7414
14 15422
15 8901
16 10990
17 1835
18 9986
19 10576
20 7349
21 9585
22 730
23 11619
24 955
25 9845
26 10221
27 4553
28 6352
29 543
30 6193
31 8335
32 8880
33 7372
34 2859
35 6...

output:

75673
84156
84079
75931
76804
88017
83643
5724
2566
82368
80605
7466
74
13141
772
25882
19136
28
15335
983
13151
1903
1027
15836
13179
9720
8449
8462
957
6586
41
8812
6679
9142
17162
8172
27
961
8398
6405
1778
93
8437
6931
16952
7357
97
17663
5778
16433
11220
13273
1001
5088
2947
7747
6358
7577
802
...

result:

ok 976 lines

Test #33:

score: 0
Accepted
time: 28ms
memory: 6728kb

input:

193270 5000 300000
22 1
29 1
33 1
40 1
43 1
62 1
63 1
64 1
78 1
80 1
94 1
105 1
106 1
108 1
110 2
120 1
128 1
149 1
203 1
207 1
212 1
234 1
255 2
263 1
266 1
286 1
298 1
300 1
302 1
304 1
313 1
314 2
317 1
327 1
353 1
380 1
384 2
403 1
408 1
426 1
428 1
434 1
442 1
472 1
473 1
476 1
477 1
479 1
490 ...

output:

174
412
199
206
181
217
467
139
18
435
483
412
569
114
317
494
256
149
235
292
371
311
293
565
65
390
528
499
502
338
430
532
36
276
276
123
406
466
151
566
294
498
433
423
228
426
225
474
311
340
91
407
16
59
114
557
56
153
78
415
445
168
531
219
228
395
540
401
212
485
88
549
547
527
146
454
300
1...

result:

ok 4004 lines

Test #34:

score: 0
Accepted
time: 46ms
memory: 6788kb

input:

193095 5000 300000
1 94614
2 123167
3 21362
4 23872
5 16365
6 35594
7 38193
8 7725
9 22330
10 19540
11 5255
12 13478
13 5510
14 6237
15 13251
16 14905
17 1701
18 6700
19 8176
20 10001
21 7572
22 8916
23 10170
24 8570
25 10033
26 7465
27 7099
28 6107
29 8603
30 3776
31 4112
32 4161
33 8181
34 7604
35...

output:

115981
21392
153
1922
2252
134582
94628
155
132469
116186
116104
134576
116221
123833
134594
134175
2358
94782
125418
35909
37321
235
24743
315
26345
35805
24310
16599
25819
24747
37300
125184
29515
21620
2369
18595
35825
123844
123194
24095
8250
1868
19545
10465
8379
13456
7948
15094
13988
15871
22...

result:

ok 2541 lines

Test #35:

score: 0
Accepted
time: 40ms
memory: 6456kb

input:

191758 5000 300000
1 1
2 1
10 1
11 1
14 1
15 1
19 1
23 1
26 3
27 1
31 2
33 1
35 1
38 1
43 1
48 1
49 1
59 1
60 1
62 1
63 1
70 3
73 2
74 1
85 1
91 1
92 1
94 1
97 1
107 1
110 1
114 2
119 1
122 1
124 2
129 1
131 1
137 1
138 1
140 1
145 2
148 1
151 1
153 2
155 1
156 1
160 1
164 1
166 1
167 5
170 1
172 1
...

output:

137
64
597
118
202
386
606
525
566
236
201
144
485
214
191
75
369
442
529
86
207
469
274
383
251
335
257
294
370
346
167
82
537
383
467
140
175
159
92
431
91
402
530
506
95
429
190
401
444
269
370
511
536
171
258
561
395
551
507
170
320
248
233
540
440
88
561
265
340
290
496
478
577
434
184
408
373
...

result:

ok 953 lines

Test #36:

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

input:

192547 5000 300000
1 259492
2 36730
3 19495
4 50645
5 14448
6 4834
7 27102
8 4737
9 31914
10 10057
11 10294
12 1471
13 9103
14 18481
15 18059
16 4633
17 3934
18 10299
19 4682
20 7800
21 1509
22 11812
23 852
24 2660
25 9322
26 3312
27 4782
28 7141
29 3014
30 7195
31 3522
32 3530
33 3921
34 6837
35 74...

output:

259504
6483
261002
5034
56411
264426
24452
4936
264348
52133
25833
25822
259614
21088
178
29187
30759
112
57062
259615
29593
29812
4838
21156
52333
31283
50684
211
29816
260963
29664
19617
29664
261815
34295
29564
29553
31272
19524
1657
35861
26656
200
25803
31202
259525
31146
1571
35799
31287
26596...

result:

ok 4052 lines

Test #37:

score: 0
Accepted
time: 45ms
memory: 6748kb

input:

193235 5000 300000
2 1
5 1
10 1
12 1
14 1
17 1
19 1
20 1
24 2
26 2
28 2
32 1
36 1
37 1
40 2
42 1
51 2
53 1
54 1
57 1
60 3
64 1
65 2
68 2
69 1
73 1
74 1
76 1
78 1
82 1
83 1
84 1
86 2
90 1
91 2
92 2
93 2
95 1
97 1
102 2
104 1
105 1
107 1
111 1
112 1
113 1
117 1
119 2
120 1
121 2
122 2
123 1
126 1
129 ...

output:

526
314
603
678
621
558
230
616
331
255
190
444
585
405
678
217
286
503
218
262
489
244
518
497
630
504
445
346
648
680
298
503
373
502
316
470
571
634
294
592
209
321
85
489
461
390
310
152
536
513
367
650
352
450
445
429
647
527
348
635
412
349
514
527
311
90
357
343
569
370
634
11
355
681
298
596...

result:

ok 2481 lines

Test #38:

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

input:

193127 5000 300000
1 118752
2 84001
3 9258
4 69673
5 35782
6 5615
7 14451
8 15585
9 19755
10 10853
11 3647
12 19328
13 8157
14 159
15 8439
16 4582
17 9117
18 14953
19 12846
20 320
21 1617
22 13279
23 10378
24 11925
25 9680
26 3611
27 7787
28 1585
29 5620
30 2865
31 935
32 8592
33 370
34 1099
35 162
...

output:

129021
133787
20757
20547
20225
21362
23875
161
32053
5776
6095
9590
5079
1417
13588
1747
4902
2072
15738
5069
4741
16512
14153
644
15461
9742
15900
159
15950
4903
5062
12906
9171
15740
16510
15014
9937
7653
9206
5878
10275
2275
642
9042
10259
7196
2277
1030
10100
2229
1744
6858
8883
14913
6965
960
...

result:

ok 1055 lines

Test #39:

score: 0
Accepted
time: 8ms
memory: 4636kb

input:

24995 5000 300000
75003 3
75004 3
75005 3
75006 3
75007 3
75008 3
75009 3
75010 3
75011 3
75012 3
75013 3
75014 3
75015 3
75016 3
75017 3
75018 3
75019 3
75020 3
75021 3
75022 3
75023 3
75024 3
75025 3
75026 3
75027 3
75028 3
75029 3
75030 3
75031 3
75032 3
75033 3
75034 3
75035 3
75036 3
75037 3
75...

output:

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

result:

ok 4043 lines

Test #40:

score: 0
Accepted
time: 8ms
memory: 4464kb

input:

9995 5000 300000
50003 4
50004 4
50005 5
50006 5
50007 4
50008 4
50009 5
50010 4
50011 5
50012 5
50013 5
50014 5
50015 5
50016 4
50017 4
50018 4
50019 4
50020 4
50021 5
50022 4
50023 4
50024 4
50025 4
50026 5
50027 4
50028 5
50029 5
50030 4
50031 5
50032 5
50033 5
50034 5
50035 4
50036 5
50037 5
500...

output:

5
4
0
5
0
4
0
0
0
0
0
0
0
5
4
0
4
0
4
0
4
0
0
5
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
5
5
0
0
0
4
4
0
0
0
5
4
5
4
0
4
0
4
3
4
0
3
0
0
4
0
0
3
5
0
0
0
0
0
4
0
4
4
0
0
4
5
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
5
0
0
4
5
0
0
5
5
5
4
0
5
4
0
0
3
5
3
0
0
0
0
0
0
4
0
3
0
0
0
5
0
4
4
0
0
4
5
4
0
5
0
0
3
3
0
0
0
0
5
0
...

result:

ok 2499 lines

Subtask #5:

score: 40
Accepted

Test #41:

score: 40
Accepted
time: 250ms
memory: 26256kb

input:

1278949 5000 2000000
4 1
9 1
12 1
13 1
15 2
20 1
21 2
26 1
36 1
39 2
43 1
46 2
59 1
64 1
66 1
71 1
73 1
75 1
78 2
83 1
87 1
89 1
92 1
97 1
103 1
104 1
108 1
111 1
113 1
114 1
117 2
118 1
130 1
137 1
140 1
151 1
152 1
155 1
158 2
163 1
164 1
165 1
168 1
172 1
173 1
183 1
185 1
186 1
192 1
208 1
210 2...

output:

272
361
1207
742
550
255
1305
781
1061
187
1354
262
448
426
1379
1246
1278
390
964
1243
1483
529
1150
545
1016
713
844
469
570
1353
426
995
1175
1390
1181
655
1294
538
906
572
415
1064
1276
1234
839
747
367
1135
621
363
1457
663
465
402
1146
1359
734
1093
527
1412
929
476
383
1463
344
1062
1456
452
...

result:

ok 2474 lines

Test #42:

score: 0
Accepted
time: 327ms
memory: 26184kb

input:

1278613 5000 2000000
1 1222462
2 456727
3 334990
4 330207
5 222769
6 52941
7 247811
8 131230
9 73420
10 187657
11 45883
12 121991
13 31509
14 94454
15 21739
16 118643
17 67978
18 22774
19 24405
20 4442
21 74797
22 10974
23 8219
24 11261
25 4112
26 39242
27 62294
28 71371
29 10931
30 53060
31 54203
3...

output:

12748
339473
103346
5489
66071
428436
423963
66210
64361
11415
339882
389422
74917
356757
21838
11384
417488
417362
414504
73489
86180
1493
69388
103532
11014
89566
72
66398
30369
5557
63335
84808
32743
66775
46224
4911
46588
1417
46777
4515
22110
30664
30373
51673
7466
23283
72609
27770
66637
76758...

result:

ok 1002 lines

Test #43:

score: 0
Accepted
time: 384ms
memory: 26292kb

input:

1288475 5000 2000000
2 2
3 1
5 1
6 2
7 1
9 1
12 1
13 1
18 2
19 3
20 1
23 3
25 2
29 1
30 1
31 2
34 1
35 1
36 1
37 1
39 2
41 3
43 2
45 2
46 1
48 2
49 1
51 1
54 2
57 3
58 2
60 3
62 3
63 1
65 3
67 1
68 1
69 1
71 1
72 1
74 1
75 1
76 1
77 2
78 1
79 1
81 1
82 1
83 1
87 1
88 1
89 1
91 1
94 1
95 1
96 2
98 1
...

output:

1531
1083
1804
2011
1978
1853
2031
1788
1414
1669
1580
1716
798
1415
1906
971
1261
893
207
1697
658
1221
1628
1702
1419
572
1144
1734
1521
1990
687
723
624
1028
1578
1603
1143
811
1118
1631
841
528
1474
1792
728
1267
1596
947
1691
1481
1881
591
1547
1407
1514
1670
1152
1210
596
727
1852
1476
1227
19...

result:

ok 3958 lines

Test #44:

score: 0
Accepted
time: 347ms
memory: 26512kb

input:

1289902 5000 2000000
1 790084
2 371044
3 436041
4 57717
5 287778
6 75840
7 174763
8 33883
9 132574
10 51288
11 125162
12 124874
13 102798
14 13655
15 123829
16 80061
17 12764
18 101698
19 97315
20 30037
21 28635
22 17819
23 11699
24 37423
25 53442
26 33138
27 45574
28 2138
29 51426
30 24398
31 21696...

output:

1232935
865933
371105
433547
518264
463201
87
539034
539004
506767
91687
429311
76302
371479
71806
465427
538919
95948
60466
96379
371072
520403
541057
94377
552572
442417
71431
373674
223075
14117
133624
181157
2658
245699
185345
93825
199108
245756
149350
200706
219248
60503
235158
4839
220894
147...

result:

ok 2512 lines

Test #45:

score: 0
Accepted
time: 322ms
memory: 26112kb

input:

1278678 5000 2000000
2 1
3 1
5 1
6 1
7 1
10 1
12 1
13 1
14 1
15 1
17 3
18 2
19 1
20 2
25 2
29 1
31 1
35 1
36 2
38 1
45 1
48 3
49 1
56 1
57 1
58 1
60 1
64 1
65 2
66 1
70 2
71 2
72 3
73 1
78 1
84 1
86 1
87 4
88 3
89 1
90 1
94 1
95 1
97 2
98 3
101 1
102 1
105 1
110 3
113 2
116 1
117 1
119 1
120 1
121 1...

output:

564
1227
1176
553
490
694
1534
776
926
1287
1399
883
1621
1542
1283
1299
1316
975
1233
1180
961
879
1748
716
905
660
814
987
244
1481
1025
1520
1304
1100
795
1365
1167
1381
1227
1494
1577
635
1078
887
1266
1279
1242
1344
744
765
1089
667
467
1452
932
1652
1303
1713
973
587
1268
888
1529
1544
1209
14...

result:

ok 967 lines

Test #46:

score: 0
Accepted
time: 340ms
memory: 26192kb

input:

1279740 5000 2000000
1 1579344
2 886454
3 136064
4 403417
5 362169
6 117644
7 212180
8 161458
9 65545
10 1462
11 26853
12 121916
13 50347
14 125723
15 63753
16 56726
17 100243
18 66131
19 70193
20 99419
21 70679
22 15929
23 33444
24 63664
25 894
26 72010
27 58953
28 41650
29 63931
30 65796
31 19201
...

output:

143876
204066
204053
1609861
282066
261475
1583934
1606243
282111
29641
203086
284240
30547
259272
142427
255216
141151
256152
144237
258299
141717
256569
142938
163005
261519
1581208
142425
165736
1582203
166624
171089
1715465
6861
259330
1582131
169293
1579401
204008
168570
285493
142104
140654
15...

result:

ok 4016 lines

Test #47:

score: 0
Accepted
time: 316ms
memory: 26324kb

input:

1290406 5000 2000000
1 1
8 1
10 1
11 1
15 1
17 2
19 1
20 1
21 1
23 1
24 1
25 2
26 1
28 2
33 1
34 2
35 1
36 1
37 2
38 2
39 1
41 1
42 2
44 1
47 3
48 1
49 1
53 2
55 1
56 1
59 1
60 2
63 1
64 2
68 2
69 1
70 1
71 1
73 3
74 1
75 1
78 1
79 1
80 1
82 1
84 2
86 2
87 1
88 1
90 2
91 2
92 2
95 1
97 1
98 1
99 1
1...

output:

179
1814
1039
1469
1047
705
882
339
1477
448
1223
399
1445
1854
920
1430
1732
1845
1537
649
1686
1698
1865
1910
1264
1713
1065
1452
148
242
111
809
1476
1635
1113
1489
327
645
1270
1664
1759
1255
981
1338
1163
1516
1035
829
1907
806
749
924
1575
1865
1670
1786
1585
774
994
967
1046
831
694
1793
737
...

result:

ok 2489 lines

Test #48:

score: 0
Accepted
time: 335ms
memory: 25980kb

input:

1289188 5000 2000000
1 582884
2 393185
3 116490
4 223231
5 338630
6 326741
7 20426
8 238814
9 113506
10 59893
11 94269
12 156479
13 122789
14 128054
15 55871
16 10709
17 24055
18 37791
19 58885
20 33538
21 43260
22 78338
23 44215
24 70524
25 28761
26 39758
27 44467
28 60823
29 960
30 20516
31 48830
...

output:

582992
583855
647556
532280
413630
616796
510589
117493
434026
415777
424429
414800
414422
31211
432115
21303
424320
906
432918
72
10783
272115
239699
224052
235127
273806
223505
224771
233954
223305
239685
11520
18535
114240
38003
37865
112916
10709
107848
132330
94346
113700
21199
132259
142775
96...

result:

ok 986 lines

Test #49:

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

input:

166661 5000 2000000
500003 3
500004 3
500005 3
500006 3
500007 3
500008 3
500009 3
500010 3
500011 3
500012 3
500013 3
500014 3
500015 3
500016 3
500017 3
500018 3
500019 3
500020 3
500021 3
500022 3
500023 3
500024 3
500025 3
500026 3
500027 3
500028 3
500029 3
500030 3
500031 3
500032 3
500033 3
5...

output:

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

result:

ok 4063 lines

Test #50:

score: 0
Accepted
time: 61ms
memory: 11984kb

input:

66662 5000 2000000
333336 5
333337 4
333338 5
333339 5
333340 5
333341 5
333342 4
333343 5
333344 4
333345 5
333346 4
333347 5
333348 4
333349 5
333350 5
333351 5
333352 4
333353 5
333354 4
333355 4
333356 4
333357 4
333358 4
333359 4
333360 4
333361 4
333362 4
333363 5
333364 5
333365 4
333366 4
33...

output:

5
0
5
5
5
0
0
5
0
5
3
5
0
5
3
0
5
0
5
0
4
5
3
0
3
3
0
4
5
0
3
3
0
0
5
5
0
0
0
5
5
5
0
0
0
0
5
3
0
0
5
3
4
0
3
5
4
0
4
0
0
5
0
4
4
5
3
3
3
5
3
0
4
0
0
0
5
5
0
3
0
5
0
5
4
0
5
0
0
3
5
3
0
5
4
3
3
0
5
0
0
0
3
0
5
0
0
3
4
0
3
4
0
0
0
0
4
3
4
0
3
0
5
5
0
3
4
5
4
5
0
3
3
0
4
3
3
0
0
0
4
0
4
5
0
0
0
0
4
0
...

result:

ok 2521 lines

Test #51:

score: 0
Accepted
time: 297ms
memory: 34628kb

input:

2000000 5000 2000000
1 1984758
2 951096
3 551230
4 284029
5 389855
6 46518
7 255156
8 100422
9 161609
10 177301
11 143577
12 28035
13 122474
14 1961
15 4167
16 91405
17 103710
18 32305
19 96136
20 87665
21 15071
22 44247
23 57539
24 32208
25 26245
26 55206
27 15522
28 54215
29 45644
30 63212
31 1370...

output:

553749
955265
953614
110183
6131
3
560435
108864
559077
290759
555397
78721
955265
338946
336676
337232
146942
102387
80685
148904
6133
288753
4724
104590
56325
104591
336677
104589
555399
80682
146945
48482
559671
9208
560229
8444
337273
6728
332511
81281
110224
77071
332509
953615
9805
1984759
560...

result:

ok 2525 lines