QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#752374#9539. Disrupting Communicationsucup-team5069AC ✓87ms25732kbC++144.2kb2024-11-16 01:24:522024-11-16 01:24:52

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

6
5
14
13
15

result:

ok 5 lines

Test #2:

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

input:

3000
98 100
1 2 1 3 5 3 2 5 5 4 3 7 12 10 12 8 10 4 4 3 10 14 11 11 22 23 14 20 29 1 18 7 12 29 20 29 12 21 6 20 3 25 7 21 16 44 38 44 7 11 5 24 34 24 41 48 56 58 56 3 26 55 62 33 9 38 63 39 3 67 14 24 60 35 1 22 74 36 57 61 55 46 44 12 16 60 44 50 22 58 78 15 57 57 75 88 15
43 28
67 66
3 39
6 19
84...

output:

964062690
949799024
949777463
964050185
119859605
949794873
949799267
964064991
836980963
964045750
964065023
959849545
536098301
964045791
964064966
964046253
964052677
949782329
964050627
949794848
188617843
964065041
2617316
949782330
964046253
536098346
949777935
964052584
949777939
964046254
94...

result:

ok 300000 lines

Test #3:

score: 0
Accepted
time: 51ms
memory: 8940kb

input:

300
998 1000
1 2 1 3 3 2 2 8 5 2 8 8 12 3 13 3 7 8 16 14 10 22 10 1 24 17 16 1 16 21 2 23 2 1 20 11 1 1 22 19 5 15 10 37 15 39 13 16 33 37 37 36 37 16 3 45 10 28 14 4 16 17 55 6 6 5 31 67 51 35 47 48 10 16 75 21 45 71 28 64 39 9 37 5 65 79 28 84 29 79 21 50 21 16 93 72 58 35 30 14 86 90 60 65 33 47 ...

output:

327306708
121504060
970333956
71256467
492200713
164920447
56359491
54857868
62271655
175858304
373532115
138628785
54854112
616763633
41337286
837501264
861536431
572242958
417784906
22152900
460075855
89587278
985881197
291627546
96610921
437457168
101307362
180803897
373532108
80109336
837492247
...

result:

ok 300000 lines

Test #4:

score: 0
Accepted
time: 85ms
memory: 24132kb

input:

3
100000 100000
1 1 2 4 2 4 6 5 1 8 9 7 12 10 7 12 10 4 9 7 6 22 10 5 18 3 8 18 5 20 12 26 10 11 14 5 28 29 33 12 5 10 30 21 36 24 1 26 39 29 2 42 40 33 41 39 23 2 50 11 47 61 61 52 3 27 65 4 24 1 15 41 68 5 62 1 44 60 44 79 68 6 53 72 21 58 66 24 54 78 29 39 75 74 13 52 71 35 40 85 47 19 60 44 101 ...

output:

174648911
988966670
586060443
352691812
610467698
718056854
353397034
944134980
945506609
743772159
17398768
898225958
509929535
581516662
124983919
679181027
890516256
792976265
81256963
846568565
990778256
394490295
307247131
281874314
78565559
438162317
218440246
677940950
608561943
237178689
748...

result:

ok 300000 lines

Test #5:

score: 0
Accepted
time: 78ms
memory: 24340kb

input:

3
100000 100000
1 2 3 2 2 3 4 3 7 6 10 8 6 4 3 6 5 8 3 17 2 7 1 1 17 3 4 11 25 26 5 7 2 20 2 32 35 11 9 39 16 42 26 43 29 22 35 18 3 34 45 19 27 3 41 27 10 14 4 4 45 53 35 49 57 37 24 43 68 6 44 5 15 12 62 22 11 26 37 41 8 73 56 76 78 9 46 14 81 67 49 12 74 15 16 69 86 48 47 77 58 77 87 54 79 80 99 ...

output:

761112418
717651384
861477152
134730845
623546487
488508714
852403783
522543884
880846196
809656417
876270841
575462796
111884802
845956357
990889899
222833220
7564761
917539269
355409810
261089607
166264493
612109684
526575279
410009284
848925228
885468503
90907188
969960703
663719627
309794696
503...

result:

ok 300000 lines

Test #6:

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

input:

3
100000 100000
1 2 1 2 3 5 1 4 2 6 10 3 10 6 13 14 4 18 13 4 21 19 9 16 14 5 13 15 10 29 11 4 33 31 25 15 19 32 12 17 22 24 35 38 3 1 46 28 16 8 13 5 46 44 25 49 37 30 47 37 10 56 32 29 36 7 13 47 11 2 24 6 51 65 36 52 15 74 62 65 25 34 35 61 12 4 20 81 64 39 21 79 90 29 68 30 7 34 60 1 1 1 1 1 1 1...

output:

47613014
867989885
314355471
515168737
161160818
552527
328577529
705173752
262933227
431743363
481168259
545043565
319743713
655278418
20733052
900938971
104104163
575553196
635937653
545910595
298966873
864807486
817091004
10697715
66840685
327639210
80580410
489368876
303238352
545043565
26533356...

result:

ok 300000 lines

Test #7:

score: 0
Accepted
time: 87ms
memory: 13200kb

input:

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

output:

89
106
100
108
90
91
89
45
89
106
71
58
60
50
68
63
66
60
59
71
72
55
50
68
73
57
46
55
63
110
90
113
113
114
99
115
118
118
113
83
83
73
77
82
57
82
57
83
90
91
92
92
91
59
91
93
88
66
79
69
80
72
66
66
63
33
171
169
169
170
106
160
159
157
168
169
56
91
23
95
86
80
87
91
92
89
40
34
41
37
31
37
33...

result:

ok 290206 lines

Test #8:

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

input:

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

output:

62
57
68
44
57
70
70
57
70
133
134
83
123
133
132
42
133
80
42
96
94
97
92
83
86
84
98
87
57
152
171
172
172
172
170
154
180
179
154
63
65
60
30
46
49
42
63
62
54
97
110
98
114
114
115
98
110
112
112
170
171
170
158
160
170
171
79
169
160
74
74
77
73
75
76
26
76
112
110
112
100
112
91
99
99
58
99
36...

result:

ok 290080 lines

Test #9:

score: 0
Accepted
time: 67ms
memory: 13268kb

input:

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

output:

65
90
70
35
68
88
85
84
85
39
82
86
96
82
87
41
86
93
88
101
98
75
102
104
102
103
100
97
52
52
42
52
51
56
52
41
61
57
64
38
66
23
23
60
23
87
116
86
115
118
136
87
135
129
115
123
130
82
120
82
119
120
133
132
129
85
89
87
90
41
85
86
45
63
53
48
23
46
35
45
47
41
36
58
64
62
62
61
67
20
69
56
56
...

result:

ok 289972 lines

Test #10:

score: 0
Accepted
time: 55ms
memory: 19200kb

input:

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

output:

74
74
111
117
119
104
117
118
120
10
34
40
39
31
23
34
19
121
125
122
121
125
123
121
123
125
66
69
33
65
63
33
62
79
80
24
17
38
38
39
29
17
21
38
66
74
70
50
68
69
45
70
45
81
95
103
96
100
75
75
75
61
100
91
87
92
92
86
43
55
86
82
80
95
100
102
49
25
108
71
94
104
89
92
98
91
94
93
96
63
63
98
6...

result:

ok 289954 lines

Test #11:

score: 0
Accepted
time: 64ms
memory: 25248kb

input:

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

output:

44
68
70
73
72
71
74
68
68
37
46
40
50
45
37
44
38
29
20
39
27
39
41
35
37
42
61
121
42
122
121
126
51
123
55
55
60
55
44
56
56
55
101
127
51
83
127
125
127
131
123
127
44
132
135
118
79
136
128
137
137
128
112
92
99
92
111
108
106
106
114
112
55
56
51
60
55
54
55
56
52
22
42
53
31
44
45
45
50
45
40...

result:

ok 289847 lines

Test #12:

score: 0
Accepted
time: 76ms
memory: 13048kb

input:

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

output:

51
48
51
53
54
43
50
30
30
20
20
20
14
26
33
30
94
92
91
91
92
55
85
86
91
53
67
68
69
34
66
66
68
67
32
42
39
35
40
39
39
37
42
58
54
50
49
42
61
51
53
18
88
68
78
85
36
81
63
24
84
28
40
31
39
38
24
38
30
84
73
75
57
82
78
57
65
84
68
70
53
70
53
67
68
50
71
74
72
23
31
45
66
73
65
22
108
101
102
...

result:

ok 290127 lines

Test #13:

score: 0
Accepted
time: 75ms
memory: 19024kb

input:

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

output:

118
105
112
117
106
117
74
55
75
24
29
38
27
35
24
42
42
36
114
119
71
121
105
119
122
57
103
56
56
60
59
55
55
55
55
90
87
92
87
94
81
96
28
88
38
38
21
37
21
44
35
21
37
42
48
33
46
42
48
14
39
32
95
97
39
78
94
63
96
106
86
34
100
104
97
85
99
113
106
71
47
65
70
67
39
60
63
64
60
74
53
60
52
60
...

result:

ok 289926 lines

Test #14:

score: 0
Accepted
time: 57ms
memory: 25732kb

input:

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

output:

54
54
52
39
34
55
51
28
104
96
104
49
90
69
103
94
103
103
64
20
58
29
58
58
58
54
49
49
74
71
74
49
61
65
74
40
33
38
36
40
37
27
36
93
87
94
79
90
28
93
88
93
52
43
49
45
45
43
31
54
48
52
31
22
53
52
50
46
104
107
100
94
102
96
108
105
104
96
112
92
115
94
93
62
111
92
107
62
32
44
44
33
42
23
44...

result:

ok 289769 lines

Test #15:

score: 0
Accepted
time: 59ms
memory: 25168kb

input:

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

output:

35
41
12
40
36
33
34
35
59
57
42
59
58
42
50
54
51
67
31
67
62
53
68
61
63
59
90
78
86
94
94
93
94
82
137
133
136
129
136
135
129
133
87
130
78
78
71
64
80
65
64
71
65
164
168
165
164
164
167
167
167
166
163
36
40
36
37
37
37
39
38
95
92
92
86
94
57
92
87
90
80
29
57
55
60
59
57
51
57
54
64
39
59
64...

result:

ok 290030 lines

Test #16:

score: 0
Accepted
time: 58ms
memory: 20004kb

input:

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

output:

8
25
30
20
30
27
32
20
38
42
41
42
44
27
26
44
59
57
60
58
60
59
60
57
43
87
87
55
59
92
93
86
85
103
103
45
104
99
99
96
77
78
44
40
46
42
43
48
33
49
62
66
45
45
31
70
62
64
67
34
80
86
78
75
48
86
80
84
82
71
64
70
69
68
63
58
68
62
138
145
154
156
151
114
157
151
113
158
51
31
51
22
49
51
50
44
...

result:

ok 289869 lines

Test #17:

score: 0
Accepted
time: 87ms
memory: 13668kb

input:

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

output:

43
36
37
34
31
38
42
38
57
59
59
58
41
41
58
50
54
53
52
52
52
49
53
57
39
11
30
36
37
43
41
42
50
48
46
46
36
45
47
50
56
65
51
34
51
57
56
55
48
23
65
66
74
74
69
74
23
63
116
113
119
66
112
116
99
105
116
113
59
53
25
59
41
41
49
59
116
110
125
110
83
110
123
109
111
122
79
74
79
79
75
51
51
51
5...

result:

ok 289830 lines

Test #18:

score: 0
Accepted
time: 67ms
memory: 25196kb

input:

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

output:

59
23
56
59
59
45
55
55
50
149
147
98
147
150
150
147
153
148
56
64
57
63
64
58
57
66
60
56
55
56
45
54
54
59
75
76
78
76
51
74
72
50
22
38
39
44
43
39
22
27
41
21
41
40
41
49
51
47
126
109
135
122
135
129
126
133
51
135
135
135
101
140
135
135
140
134
137
134
45
59
45
56
60
60
56
45
220
219
74
218
...

result:

ok 290002 lines

Test #19:

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

input:

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

output:

102
95
60
86
101
102
31
87
96
62
137
128
133
129
132
138
101
101
135
132
122
182
187
188
184
187
186
185
184
184
30
30
40
32
27
39
34
25
26
49
46
39
40
27
43
14
57
66
64
54
62
38
59
67
59
110
113
75
75
111
112
75
111
113
83
97
23
93
95
94
83
86
86
84
156
144
159
69
156
159
143
156
145
73
168
165
168...

result:

ok 289994 lines

Test #20:

score: 0
Accepted
time: 60ms
memory: 19692kb

input:

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

output:

67
43
63
67
68
70
72
65
71
63
65
65
64
54
63
64
58
86
81
79
87
87
93
79
84
93
99
78
89
102
104
104
89
99
100
26
38
44
33
42
23
39
45
90
94
97
97
87
47
96
96
69
90
114
118
110
110
119
121
120
114
119
82
43
51
31
44
46
16
52
52
68
33
66
70
71
70
37
71
57
51
51
52
34
18
18
49
73
64
74
66
61
70
49
65
75...

result:

ok 289988 lines

Test #21:

score: 0
Accepted
time: 84ms
memory: 25188kb

input:

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

output:

41
86
70
82
82
69
81
68
70
91
82
82
68
51
77
74
76
91
147
145
44
130
153
151
145
129
145
145
66
71
66
70
65
19
65
68
51
48
44
31
51
48
45
50
60
59
59
51
54
59
55
45
74
73
77
77
75
75
75
75
160
171
160
160
157
170
168
158
159
171
90
90
117
114
118
117
107
114
37
113
47
37
45
37
19
45
50
48
121
116
11...

result:

ok 290036 lines

Test #22:

score: 0
Accepted
time: 65ms
memory: 13804kb

input:

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

output:

113
111
109
55
110
112
111
38
113
62
64
61
56
68
70
45
63
62
51
28
57
41
48
29
41
49
96
59
55
69
66
95
46
97
69
46
86
86
57
85
86
83
87
86
84
48
68
63
54
20
68
17
61
65
69
49
49
25
70
69
66
60
66
105
112
68
117
117
116
69
113
113
115
49
45
47
48
45
48
39
40
160
169
172
159
169
170
171
171
169
160
79...

result:

ok 289982 lines

Test #23:

score: 0
Accepted
time: 76ms
memory: 19032kb

input:

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

output:

42
43
42
38
23
23
36
42
80
82
76
83
82
80
80
75
81
90
96
89
103
99
99
103
100
104
62
62
76
69
47
77
71
80
76
27
67
66
63
65
63
68
42
154
154
172
171
111
171
154
153
154
173
112
113
112
112
114
113
114
108
109
105
122
123
125
131
132
55
122
123
123
65
62
53
63
61
53
64
67
166
81
165
166
166
133
161
1...

result:

ok 289985 lines

Test #24:

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

input:

2
2 1
1
2 1
2 4
1
1 1
1 2
2 1
2 2

output:

3
2
3
3
2

result:

ok 5 lines

Test #25:

score: 0
Accepted
time: 63ms
memory: 25340kb

input:

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

output:

63
62
34
58
65
58
58
64
58
67
98
98
98
97
103
100
100
104
114
102
68
86
69
100
113
101
115
116
57
65
66
58
65
65
28
58
39
39
21
42
43
36
43
41
50
59
59
59
50
49
58
49
45
49
54
52
52
54
45
16
14
15
25
23
27
26
26
23
85
94
94
92
93
88
94
91
54
154
177
176
85
177
177
177
103
171
175
92
94
94
92
92
59
9...

result:

ok 290047 lines

Test #26:

score: 0
Accepted
time: 60ms
memory: 25180kb

input:

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

output:

126
135
130
126
120
125
90
126
135
45
134
127
129
129
127
137
135
116
58
131
91
92
88
87
85
92
91
94
88
100
114
113
105
114
117
114
118
67
116
26
69
90
45
75
87
65
78
62
78
83
29
73
84
29
37
73
83
70
74
75
77
74
73
26
76
74
33
38
35
40
40
26
49
48
86
78
102
101
96
30
87
75
84
100
62
64
23
57
46
73
6...

result:

ok 290027 lines

Test #27:

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

input:

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

output:

111
111
167
111
111
168
164
111
168
168
64
62
31
22
66
43
43
64
41
44
42
23
41
36
41
42
169
171
150
152
176
85
153
178
178
171
93
32
98
95
93
95
95
95
39
146
145
148
147
148
146
147
146
147
49
51
50
53
42
51
51
43
35
99
100
100
102
97
100
99
101
99
33
71
65
51
70
71
67
66
136
131
129
135
118
115
129...

result:

ok 290108 lines

Extra Test:

score: 0
Extra Test Passed