QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#525956#6340. TourismQwerty123242 1870ms42624kbC++235.8kb2024-08-21 05:22:512024-08-21 05:22:53

Judging History

你现在查看的是最新测评结果

  • [2024-08-21 05:22:53]
  • 评测
  • 测评结果:42
  • 用时:1870ms
  • 内存:42624kb
  • [2024-08-21 05:22:51]
  • 提交

answer

#include <bits/stdc++.h>

struct ST {
    std::vector<std::vector<int>> data;

    ST(const std::vector<int>& vec) {
        int lg = std::bit_width(vec.size());
        data.resize(lg);
        data[0] = vec;
        for (int k = 1; k < lg; k++) {
            data[k].resize(vec.size() - (1 << k) + 1);
            for (int i = 0; i < data[k].size(); i++) {
                data[k][i] = std::min(data[k - 1][i], data[k - 1][i + (1 << k - 1)]);
            }
        }
    }

    int get_min(int l, int r) {
        int k = std::bit_width<uint32_t>(r - l) - 1;
        return std::min(data[k][l], data[k][r - (1 << k)]);
    }
};

using u64 = uint64_t;

struct TreeBitset {
    using T = uint8_t;
    static constexpr int K = sizeof(T) * 8;
    std::vector<size_t> sz;
    std::vector<std::vector<T>> data;
    int lg;

    TreeBitset(int n) {
        for (int n2 = n; n2 > 1;) {
            n2 = (n2 - 1) / K + 1;
            sz.push_back(n2);
        }
        std::reverse(sz.begin(), sz.end());
        lg = sz.size();
        data.resize(lg);
        for (int i = 0; i < lg; i++) {
            data[i].assign(sz[i], 0);
        }
    }

    void update(int i, int val) {
        for (int k = lg - 1; k >= 0; k--) {
            auto [pos, ind] = div(i, K);
            val = bool(data[k][pos] = (data[k][pos] & (~(T(1) << ind))) | T(val) << ind);
            i /= K;
        }
    }

    int find_next(int i) {
        int k = lg - 1;
        while (k >= 0) {
            auto [pos, ind] = div(i, K);
            int ind2 = std::countr_zero<T>(data[k][pos] >> ind + 1 << ind + 1);
            if (ind2 != K) {
                i = pos * K + ind2;
                for (k++; k < lg; k++) {
                    i = i * K + std::countr_zero<T>(data[k][i]);
                }
                return i;
            }
            k--, i /= K;
        }
        if (data[lg - 1][0] & 1) {
            return 0;
        }
        return find_next(0);
    }

    int find_prev(int i) {
        int k = lg - 1;
        while (k >= 0) {
            auto [pos, ind] = div(i, K);
            int ind2 = (K - 1) - std::countl_zero<T>(T(data[k][pos] << (K - ind)) >> (K - ind));
            if (ind2 != -1) {
                i = pos * K + ind2;
                for (k++; k < lg; k++) {
                    i = i * K + ((K - 1) - std::countl_zero<T>(data[k][i]));
                }
                return i;
            }
            k--, i /= K;
        }
        if (data[lg - 1][sz[lg - 1] - 1] & T(1) << K - 1) {
            return sz[lg - 1] * K - 1;
        }
        return find_prev(sz[lg - 1] * K - 1);
    }
};

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> gr(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    std::vector<int> input(m);
    for (auto& i : input) {
        std::cin >> i;
        i--;
    }

    std::vector<std::array<int, 3>> quer(q);
    for (int i = 0; i < q; i++) {
        auto& [l, r, id] = quer[i];
        std::cin >> l >> r;
        l--;
        id = i;
    }

    std::vector<int> eul_dp, tin(n), tout(n), depth(n);
    auto dfs = [&](auto dfs, int v, int f) -> void {
        tin[v] = eul_dp.size();
        eul_dp.push_back(depth[v]);
        for (int t : gr[v]) {
            if (t != f) {
                depth[t] = depth[v] + 1;
                dfs(dfs, t, v);
                eul_dp.push_back(depth[v]);
            }
        }
        tout[v] = eul_dp.size();
    };
    dfs(dfs, 0, -1);

    ST st(eul_dp);

    auto get_lca_depth = [&](int u, int v) {
        return st.get_min(std::min(tin[u], tin[v]), std::max(tin[u], tin[v]) + 1);
    };
    auto get_dist = [&](int u, int v) {
        return depth[u] + depth[v] - 2 * get_lca_depth(u, v);
    };
    auto get_dist_tin = [&](int u, int v) {
        return eul_dp[u] + eul_dp[v] - 2 * st.get_min(std::min(u, v), std::max(u, v) + 1);
    };

    constexpr int K = 330;
    std::sort(quer.begin(), quer.end(), [&](auto a, auto b) {
        auto [l1, r1, id1] = a;
        auto [l2, r2, id2] = b;
        if (l1 / K != l2 / K) {
            return l1 / K < l2 / K;
        }
        return (r1 < r2) != bool(l1 / K % 2);
    });

    std::vector<int> ord(m);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int a, int b) { return tin[input[a]] < tin[input[b]]; });
    std::vector<int> pos(m);
    std::vector<int> ord_tin(m);
    for (int i = 0; i < m; i++) {
        pos[ord[i]] = i;
        ord_tin[i] = tin[input[ord[i]]];
    }

    TreeBitset tb(m);

    int64_t total_dlt = 0;
    int sum_dist = 0;
    auto add = [&](int t, int f) {
        total_dlt++;

        // auto it = set.insert(t);
        if (f == 1) {
            tb.update(t, 1);
        }
        int t1 = tb.find_prev(t);
        int t2 = tb.find_next(t);
        if (f == -1) {
            tb.update(t, 0);
        }
        sum_dist -= get_dist_tin(ord_tin[t1], ord_tin[t2]) * f;
        sum_dist += get_dist_tin(ord_tin[t1], ord_tin[t]) * f;
        sum_dist += get_dist_tin(ord_tin[t], ord_tin[t2]) * f;
    };
    int L = 0, R = 0;
    std::vector<int> ans(q);
    for (auto [l, r, id] : quer) {
        while (R < r) {
            add(pos[R++], 1);
        }
        while (l < L) {
            add(pos[--L], 1);
        }
        while (r < R) {
            add(pos[--R], -1);
        }
        while (L < l) {
            add(pos[L++], -1);
        }

        assert(total_dlt <= 1e8);
        ans[id] = sum_dist / 2 + 1;
    }

    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 5
Accepted
time: 1ms
memory: 3660kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

67
97
110
93
110
139
84
24
126
121
70
97
83
96
25
113
86
60
79
49
107
131
66
33
4
41
86
110
59
123
46
130
73
63
93
75
113
85
25
95
127
69
85
121
77
127
123
83
34
62
99
121
63
56
99
106
28
69
127
48
74
134
68
94
22
120
105
116
36
83
124
112
130
19
34
112
138
37
98
64
122
109
1
105
137
73
105
109
89
9...

result:

ok 224 numbers

Test #2:

score: 5
Accepted
time: 1ms
memory: 3540kb

input:

225 173 232
88 46
74 88
88 60
86 46
202 86
175 86
165 74
60 61
13 88
78 46
61 163
61 123
13 15
211 60
78 75
123 188
165 146
88 93
93 214
16 202
137 146
75 133
202 1
213 202
30 214
203 165
146 222
91 146
203 106
23 75
104 202
30 47
165 174
144 133
137 58
20 1
75 183
133 26
21 30
80 93
106 36
207 188
...

output:

96
88
75
71
122
133
102
121
19
89
121
25
78
20
19
123
91
71
104
102
48
51
38
101
126
107
55
29
30
121
20
72
98
57
37
50
14
84
129
78
63
43
68
51
40
62
69
83
101
29
17
121
35
52
39
139
79
92
115
138
141
79
18
143
115
108
55
116
54
130
113
105
66
76
54
108
50
54
56
49
42
116
55
52
146
102
60
120
98
86...

result:

ok 232 numbers

Test #3:

score: 5
Accepted
time: 1ms
memory: 3820kb

input:

161 196 214
46 122
64 46
156 46
146 122
46 105
16 122
119 156
121 119
156 58
46 40
99 105
119 113
91 16
13 113
13 39
40 49
147 105
11 40
99 148
7 156
113 53
32 64
132 7
32 108
32 54
40 111
119 137
127 32
91 34
136 147
148 71
26 46
64 68
9 34
78 9
40 110
153 78
5 13
78 70
96 153
55 64
131 121
21 108
...

output:

112
79
121
66
73
68
101
82
66
59
132
92
77
23
75
111
97
95
85
127
128
122
100
33
114
107
103
40
33
111
13
63
131
37
45
10
59
126
84
58
90
17
70
15
33
109
110
57
103
97
119
70
14
121
76
72
57
105
121
66
106
79
132
83
47
105
61
121
79
86
97
117
132
73
126
117
128
39
80
90
126
53
124
107
127
128
47
118...

result:

ok 214 numbers

Test #4:

score: 5
Accepted
time: 1ms
memory: 3664kb

input:

191 176 283
154 157
154 109
157 113
122 109
78 109
78 133
109 132
31 157
77 109
154 24
132 35
132 74
78 26
86 35
157 117
59 133
29 77
117 186
37 186
70 157
76 186
44 77
42 154
170 24
74 99
132 30
99 156
133 67
35 20
51 31
71 44
121 109
84 154
26 119
38 30
67 166
102 121
77 32
20 167
170 123
123 61
1...

output:

89
17
108
71
101
50
79
66
96
123
92
54
91
84
50
74
134
94
73
36
61
43
114
61
114
106
120
41
113
17
116
128
66
1
118
62
115
86
55
111
20
140
107
62
133
75
104
95
64
61
61
109
34
84
133
21
143
54
103
94
101
122
98
11
86
123
48
77
77
37
30
59
29
94
53
122
85
120
80
62
100
117
101
73
80
53
91
90
44
85
6...

result:

ok 283 numbers

Test #5:

score: 5
Accepted
time: 1ms
memory: 3660kb

input:

280 195 170
153 16
153 152
249 153
152 87
210 152
111 210
11 152
75 111
247 249
155 16
142 111
152 125
155 241
210 23
93 241
142 108
11 15
249 183
183 131
38 23
142 271
34 183
75 225
80 93
247 85
153 136
41 249
38 91
15 43
158 153
144 271
96 93
131 232
11 116
131 68
75 188
179 225
99 75
87 250
41 14...

output:

106
180
88
144
120
162
118
105
35
61
97
145
53
134
75
164
105
159
174
121
140
71
69
53
170
124
168
83
42
115
95
113
135
166
98
126
61
193
146
26
185
34
124
1
101
143
18
146
161
119
69
83
117
105
130
23
181
112
160
38
47
178
95
129
103
80
127
85
118
49
18
180
105
119
180
134
83
26
142
190
89
186
57
1...

result:

ok 170 numbers

Test #6:

score: 5
Accepted
time: 1ms
memory: 3684kb

input:

300 300 300
9 290
290 177
9 57
258 290
115 57
177 116
57 48
177 113
177 151
290 105
285 57
154 48
154 300
251 57
300 217
154 267
127 115
48 275
154 287
38 177
9 253
285 86
34 275
199 300
115 183
178 115
57 70
251 110
127 43
26 9
165 86
257 105
59 127
115 66
252 183
86 92
281 285
7 127
59 179
245 183...

output:

223
92
71
132
176
68
209
44
177
132
194
155
142
111
157
43
182
157
50
216
168
29
59
103
156
101
36
127
120
133
179
91
173
178
175
218
209
210
159
82
64
121
184
227
189
52
36
158
125
157
152
178
109
87
158
225
86
50
147
52
160
98
226
216
133
178
222
78
195
163
17
71
51
114
118
84
192
188
149
167
158
...

result:

ok 300 numbers

Test #7:

score: 5
Accepted
time: 1ms
memory: 3612kb

input:

300 300 300
69 94
5 94
287 5
94 289
13 5
5 159
226 159
148 94
69 191
116 148
94 57
57 24
98 69
115 24
226 271
77 57
67 271
158 69
252 69
158 37
69 121
244 287
139 77
91 139
238 287
91 154
77 9
278 115
139 221
203 158
37 127
159 292
177 148
69 174
279 244
40 221
98 260
268 69
158 12
144 40
244 213
27...

output:

222
145
178
25
169
190
224
135
90
222
200
200
135
52
154
157
47
117
93
43
121
211
16
188
129
212
182
150
77
174
208
131
73
178
126
104
145
214
141
81
199
161
137
1
158
94
196
87
81
131
169
22
197
155
42
192
143
137
180
140
136
44
32
78
110
186
104
135
213
159
41
79
195
83
122
97
190
157
135
202
176
...

result:

ok 300 numbers

Test #8:

score: 5
Accepted
time: 1ms
memory: 3600kb

input:

300 300 300
230 57
57 140
227 230
227 164
57 199
49 57
49 131
57 208
98 57
281 98
131 76
103 227
49 46
279 140
279 83
295 49
24 131
78 279
127 24
281 9
199 104
230 256
122 103
111 49
176 256
57 119
83 135
131 273
279 206
176 278
83 211
256 193
211 259
21 199
257 9
194 127
269 295
257 298
131 129
206...

output:

109
80
212
185
207
223
159
47
103
44
120
161
162
84
119
173
192
189
9
140
191
189
10
182
91
201
181
88
16
54
60
31
213
170
97
167
80
194
203
190
197
140
204
218
167
216
73
97
205
153
91
186
40
11
228
167
131
199
97
196
181
163
111
65
84
122
178
32
166
153
156
200
86
99
130
186
116
223
38
202
164
186...

result:

ok 300 numbers

Test #9:

score: 5
Accepted
time: 1ms
memory: 3612kb

input:

300 300 300
275 44
19 44
184 275
8 184
8 68
274 44
184 257
19 154
227 154
44 84
23 227
256 84
154 31
160 8
100 160
273 100
154 77
100 150
121 8
273 50
218 121
201 150
77 266
202 201
31 131
23 261
65 8
47 160
123 218
164 100
202 15
50 259
274 182
196 31
98 150
202 113
164 59
83 68
261 177
116 275
261...

output:

245
245
247
246
246
245
246
246
245
246
246
245
245
243
247
246
246
245
246
246
245
246
246
247
246
246
247
245
245
244
244
246
247
247
244
247
245
246
247
243
246
246
247
243
246
246
247
245
247
246
247
247
247
245
247
246
245
247
246
246
247
246
245
245
247
246
247
245
246
245
246
246
245
246
247
...

result:

ok 300 numbers

Test #10:

score: 5
Accepted
time: 0ms
memory: 3824kb

input:

300 300 300
151 108
151 217
71 217
64 71
108 86
151 285
86 12
71 101
281 151
134 71
148 86
217 179
131 86
229 148
12 190
274 101
89 12
286 190
12 232
43 232
172 148
229 140
108 208
64 249
151 169
84 86
134 115
131 82
58 229
71 98
86 163
169 248
115 127
274 70
163 51
172 287
153 287
44 208
281 291
93...

output:

220
220
220
219
218
218
218
220
218
222
220
220
219
220
215
219
218
218
222
222
218
220
223
218
218
221
218
219
220
223
220
218
218
219
218
220
221
219
218
220
218
220
220
218
218
220
219
220
220
220
221
219
218
222
220
216
222
220
222
218
219
220
218
220
220
219
220
218
218
218
220
218
221
218
220
...

result:

ok 300 numbers

Test #11:

score: 5
Accepted
time: 1ms
memory: 3612kb

input:

300 300 300
210 194
210 179
46 210
46 186
256 179
56 256
46 44
194 192
106 179
56 146
17 194
179 197
23 17
106 121
257 194
23 160
23 124
257 48
179 71
187 160
179 35
186 252
197 195
43 35
35 278
248 278
13 35
15 13
278 272
199 257
252 244
195 9
164 13
17 147
214 257
155 278
82 56
263 43
172 48
28 24...

output:

225
222
225
224
225
222
224
225
224
226
226
224
225
226
224
224
224
222
225
223
227
225
224
223
225
222
222
224
224
226
224
225
225
224
223
222
224
224
225
223
224
224
222
225
224
225
223
226
223
224
224
225
224
224
223
222
225
225
225
225
224
226
223
222
225
227
223
225
223
224
223
227
226
225
224
...

result:

ok 300 numbers

Test #12:

score: 5
Accepted
time: 1ms
memory: 3708kb

input:

300 300 300
96 198
70 96
167 70
273 167
273 52
52 204
63 204
143 63
296 143
296 92
292 92
17 292
17 166
166 290
290 66
66 105
80 105
80 51
277 51
277 168
223 168
223 152
152 54
116 54
177 116
177 186
190 186
190 68
101 68
101 182
300 182
300 213
110 213
110 179
179 205
205 119
33 119
33 65
147 65
25...

output:

297
179
294
297
293
193
292
296
294
294
293
290
293
284
294
219
217
289
299
293
299
214
278
1
293
268
293
299
297
293
294
241
287
297
294
299
294
289
297
296
296
294
297
297
293
281
299
289
184
297
283
264
287
293
297
293
299
299
82
293
296
299
297
297
283
293
299
299
293
296
300
299
299
290
293
294...

result:

ok 300 numbers

Test #13:

score: 5
Accepted
time: 1ms
memory: 3584kb

input:

300 300 300
15 60
15 287
26 287
3 26
3 145
177 145
177 122
29 122
29 75
198 75
31 198
31 172
219 172
126 219
126 84
56 84
56 203
203 225
227 225
227 195
200 195
217 200
47 217
47 73
251 73
118 251
118 14
42 14
263 42
7 263
32 7
102 32
102 205
205 64
253 64
253 120
120 166
166 164
185 164
185 254
254...

output:

300
297
293
300
216
298
297
299
297
297
293
299
294
261
300
288
243
299
299
297
293
294
300
156
300
297
1
293
300
291
299
300
300
300
297
294
300
300
232
300
298
297
299
298
282
297
283
293
278
283
299
280
296
299
298
294
57
164
300
300
1
297
297
299
300
297
283
300
289
290
293
297
300
156
295
283
2...

result:

ok 300 numbers

Test #14:

score: 5
Accepted
time: 1ms
memory: 3664kb

input:

300 300 300
145 236
290 145
290 3
136 3
135 136
135 284
284 45
45 62
12 62
265 12
265 154
154 226
273 226
256 273
256 30
30 137
259 137
251 259
251 72
218 72
218 73
188 73
168 188
168 158
158 214
214 152
152 37
37 268
227 268
227 206
206 95
53 95
53 127
90 127
213 90
213 74
74 164
149 164
94 149
94 ...

output:

292
1
299
299
299
292
284
289
223
299
290
299
289
299
265
298
276
299
273
299
281
292
258
292
299
292
299
299
192
299
294
299
298
299
299
289
299
284
273
290
299
298
299
299
299
299
294
299
299
271
97
290
299
299
299
299
284
290
289
292
223
299
292
299
292
287
289
299
299
292
292
275
299
299
299
299...

result:

ok 300 numbers

Test #15:

score: 5
Accepted
time: 1ms
memory: 3684kb

input:

300 300 300
124 163
292 163
292 197
208 197
271 208
271 261
261 144
144 153
153 139
139 213
279 213
279 50
15 50
297 15
143 297
143 45
146 45
232 146
169 232
169 265
221 265
221 136
225 136
6 225
164 6
296 164
11 296
11 95
27 95
61 27
114 61
295 114
295 184
41 184
143 78
78 43
42 43
42 244
21 244
74...

output:

127
290
294
236
288
294
293
277
267
140
295
267
276
298
286
269
294
286
286
294
251
267
225
265
285
243
297
165
264
246
284
201
248
234
227
211
296
293
90
225
287
246
294
175
297
254
294
269
71
293
287
144
169
263
288
221
284
295
283
263
293
237
294
215
284
284
287
288
263
275
290
294
220
163
288
27...

result:

ok 300 numbers

Test #16:

score: 5
Accepted
time: 0ms
memory: 3624kb

input:

300 300 300
164 241
156 164
156 37
37 173
173 29
29 291
291 129
275 129
118 275
254 118
254 217
217 210
210 271
271 139
160 139
181 160
211 181
211 99
74 99
208 74
208 123
123 202
214 202
80 214
121 80
121 263
263 8
8 22
6 22
149 6
149 295
285 295
94 285
140 94
140 104
104 230
183 230
183 87
62 87
4...

output:

269
287
267
276
214
275
237
282
257
296
296
203
280
238
256
296
296
205
296
282
277
283
11
245
296
296
275
256
288
269
259
291
296
265
158
296
292
262
296
285
294
296
213
274
296
292
269
296
282
224
237
268
294
276
216
282
51
107
263
263
251
1
168
296
282
280
282
271
256
296
279
282
252
211
280
293
...

result:

ok 300 numbers

Test #17:

score: 5
Accepted
time: 1ms
memory: 3904kb

input:

300 300 300
152 232
247 232
247 75
75 56
56 50
256 75
160 256
260 160
28 260
28 40
40 269
146 269
146 35
35 117
117 235
230 235
126 230
126 201
43 201
43 93
282 93
171 282
171 194
194 270
270 89
76 89
76 224
224 181
288 181
291 288
291 95
293 95
105 293
105 298
298 262
262 217
217 13
13 139
139 73
7...

output:

295
295
296
296
294
294
294
294
286
294
291
294
294
291
272
294
296
274
287
292
294
294
295
296
291
287
276
284
294
280
285
269
294
251
281
286
296
281
291
296
285
287
294
295
284
291
296
292
266
294
295
294
284
296
295
285
276
292
294
298
295
278
295
284
280
67
257
277
295
269
284
1
281
286
276
276...

result:

ok 300 numbers

Test #18:

score: 5
Accepted
time: 1ms
memory: 3608kb

input:

300 300 300
31 202
254 31
227 31
31 247
31 5
2 31
272 31
68 31
31 151
98 31
31 183
207 31
31 193
189 31
31 173
31 89
248 31
31 156
258 31
157 31
31 106
31 234
31 139
127 31
31 50
31 256
162 31
199 31
31 67
31 62
31 165
31 138
132 31
31 46
120 31
229 31
31 171
241 31
192 31
42 31
31 48
198 31
31 94
7...

output:

146
102
63
85
26
31
78
142
57
50
148
20
143
149
19
6
146
74
107
16
5
106
28
91
27
25
97
60
189
131
48
152
26
3
111
62
126
28
18
102
146
117
3
50
166
74
39
76
49
27
101
69
100
12
120
115
66
74
8
115
120
123
92
56
71
69
127
160
48
19
122
177
91
56
132
70
57
130
75
84
83
177
178
118
182
24
29
142
4
7
3...

result:

ok 300 numbers

Test #19:

score: 5
Accepted
time: 1ms
memory: 3820kb

input:

300 300 300
116 172
100 172
172 251
172 266
172 173
64 172
276 172
172 60
172 204
293 172
27 172
153 172
172 82
172 244
220 172
297 172
172 189
97 172
172 168
125 172
172 179
172 232
172 227
28 172
288 172
172 195
172 48
25 172
172 119
172 226
172 250
172 46
172 182
172 165
172 93
280 172
172 258
17...

output:

177
164
151
168
40
35
111
90
7
160
137
103
69
46
112
84
77
127
18
71
71
60
123
53
69
93
98
155
54
8
52
79
101
25
118
83
31
165
76
6
139
37
95
80
121
67
64
69
98
9
60
41
12
112
156
84
76
6
19
53
62
17
23
13
4
6
24
80
110
65
57
81
32
109
119
123
162
14
129
86
45
10
77
129
56
24
133
48
113
129
45
122
8...

result:

ok 300 numbers

Test #20:

score: 5
Accepted
time: 1ms
memory: 3852kb

input:

300 300 300
98 64
98 292
98 105
98 32
98 196
276 98
4 98
12 98
150 98
27 98
73 98
256 98
124 98
98 237
98 202
98 133
98 239
98 3
98 190
273 98
98 20
295 98
182 98
98 226
98 177
253 98
98 266
51 98
98 63
238 98
19 98
98 218
156 98
103 98
98 146
274 98
112 98
98 251
98 86
50 98
184 98
186 98
92 98
98 ...

output:

97
56
155
33
72
66
130
122
57
115
42
139
106
119
88
126
89
6
4
32
121
109
159
155
161
94
116
145
114
114
93
175
75
34
115
79
37
168
60
151
95
183
111
145
127
67
68
61
52
82
69
57
27
135
3
78
23
110
30
171
128
83
148
23
27
16
79
105
78
109
152
3
34
57
8
34
92
93
77
121
7
60
63
1
128
38
61
167
51
114
...

result:

ok 300 numbers

Test #21:

score: 5
Accepted
time: 1ms
memory: 3816kb

input:

300 300 300
109 116
116 230
116 158
96 116
116 272
116 218
158 160
116 234
116 32
185 116
116 266
210 116
65 116
47 116
56 116
116 55
78 116
286 116
197 116
116 83
116 25
116 44
116 231
139 116
205 116
12 116
116 4
277 116
116 247
116 104
204 116
215 116
269 116
118 116
90 116
116 292
116 51
116 98
...

output:

106
107
97
147
66
174
36
35
17
121
136
7
180
6
71
34
85
40
49
159
8
23
9
37
7
117
151
5
98
102
129
39
112
167
92
76
107
8
16
15
61
14
133
89
31
94
62
45
118
97
144
3
124
64
157
146
14
146
138
25
186
17
140
46
48
47
6
140
67
6
61
179
93
52
110
88
150
56
140
50
79
100
165
10
142
77
175
1
73
143
131
77...

result:

ok 300 numbers

Test #22:

score: 5
Accepted
time: 1ms
memory: 3684kb

input:

300 300 300
203 253
245 203
4 203
203 38
197 203
203 144
202 203
243 203
291 203
10 203
281 203
203 123
88 203
203 90
203 225
238 203
115 203
221 203
203 289
195 203
203 91
25 203
203 294
191 203
203 116
92 203
122 203
203 138
203 149
32 203
203 74
203 135
137 203
203 22
76 203
203 177
100 203
203 1...

output:

115
80
144
102
49
140
68
84
79
25
59
158
84
118
8
4
98
58
7
113
69
91
92
161
51
98
77
15
167
5
84
12
114
61
121
61
165
170
78
80
38
139
65
176
42
26
18
47
157
87
116
81
128
30
30
50
24
47
71
35
83
8
174
44
86
161
121
145
90
156
50
78
16
30
161
121
97
18
23
101
96
20
110
155
44
25
161
25
75
158
116
3...

result:

ok 300 numbers

Test #23:

score: 5
Accepted
time: 1ms
memory: 3884kb

input:

300 300 300
122 269
269 21
171 269
269 221
132 269
269 161
232 269
126 269
269 237
269 157
269 190
79 269
269 43
289 269
269 234
80 269
127 269
269 163
269 68
269 188
269 274
269 175
269 49
269 252
269 143
269 147
269 230
269 138
300 269
269 98
105 269
116 269
165 269
258 269
269 113
269 131
269 201...

output:

123
46
104
129
67
71
17
176
129
18
138
135
116
72
146
5
40
115
97
20
56
125
139
162
82
20
63
114
6
17
127
49
8
87
28
73
14
89
15
84
121
116
79
146
44
31
127
7
151
6
140
35
95
145
141
43
70
103
113
126
65
39
100
83
6
8
22
11
4
110
74
70
89
12
17
152
41
142
146
63
26
47
95
148
135
110
44
138
77
167
11...

result:

ok 300 numbers

Test #24:

score: 5
Accepted
time: 1ms
memory: 3560kb

input:

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

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

Test #25:

score: 0
Runtime Error

input:

300 1 300
105 102
102 218
105 245
218 212
218 242
32 105
190 245
150 32
135 218
150 214
245 258
90 190
90 262
105 236
190 226
22 90
116 226
135 298
53 298
234 150
126 90
83 150
174 226
41 90
110 22
294 116
150 267
82 236
82 261
110 56
169 258
80 262
155 262
78 41
51 262
71 82
100 83
241 226
58 51
25...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #56:

score: 7
Accepted
time: 1310ms
memory: 25500kb

input:

55321 88650 75523
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

55319
55319
55313
55306
55319
53676
55320
55301
55319
55319
55268
55319
55318
55320
55311
55311
55319
55275
55301
55319
55319
55317
55320
55319
55319
55318
55295
55318
55319
55319
55319
55248
55319
55320
55319
55319
55319
55319
55319
55319
55320
55301
55319
55186
55204
55320
55319
55319
55297
55318
...

result:

ok 75523 numbers

Test #57:

score: 7
Accepted
time: 758ms
memory: 33932kb

input:

80807 56552 65576
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

80782
80805
80805
80769
80805
80805
80805
80791
80805
80782
80805
80805
80783
80805
80802
80805
80334
80791
80777
80805
80805
80802
80805
80805
80805
80805
80805
80758
80805
80789
80805
80790
80805
80805
80805
80805
80781
80777
80805
80805
80805
80805
80802
80805
80805
80805
80805
80777
80777
80805
...

result:

ok 65576 numbers

Test #58:

score: 7
Accepted
time: 1093ms
memory: 38536kb

input:

91904 82063 54619
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

91904
91883
91878
91896
91897
91902
91902
91901
91748
91902
91904
91904
91901
91904
91896
91904
91896
91901
91901
91904
91900
91886
91902
91904
91894
91902
91853
91885
91893
91893
91902
91900
91902
91886
91902
91904
91416
91904
91901
91904
91904
91902
91904
91904
91902
91904
91828
91809
91904
91875
...

result:

ok 54619 numbers

Test #59:

score: 7
Accepted
time: 1776ms
memory: 42484kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99999
99954
99991
99993
99986
99942
99993
99986
99994
99993
99993
99993
99989
99986
99999
99991
99994
99956
99999
99989
99991
99999
99991
99981
99973
99993
99999
99983
99986
99991
99986
99999
99988
99954
99983
99999
99983
99993
99999
99993
99986
99991
99999
99999
99999
99991
99993
99993
99837
99990
...

result:

ok 100000 numbers

Test #60:

score: 7
Accepted
time: 1773ms
memory: 42544kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

100000
99997
99998
99992
99992
99970
99996
99981
99981
99997
99982
99981
99990
99973
99963
99997
99997
99537
99997
99990
99997
99997
99990
100000
99997
99987
99943
100000
99981
99981
99996
99960
99998
99997
100000
99991
99754
99961
99960
99990
99990
100000
99997
99963
99981
99935
99991
100000
99997
...

result:

ok 100000 numbers

Test #61:

score: 7
Accepted
time: 1790ms
memory: 42620kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99996
99998
99998
99998
99994
99915
99996
99972
99996
99998
99998
99837
99996
99998
99996
99994
99989
99942
99998
99603
99998
99972
99981
99915
99463
99994
99994
99994
99996
99969
99972
99989
99998
99989
99998
99603
99843
99959
99998
99998
99998
99996
99998
99998
99996
99998
99996
99998
99994
99998
...

result:

ok 100000 numbers

Test #62:

score: 7
Accepted
time: 1762ms
memory: 42620kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99997
99994
99951
99998
99994
99998
99990
100000
100000
100000
99996
100000
99994
99980
99998
99990
99967
99994
100000
100000
99998
99997
99994
99991
100000
100000
100000
99970
100000
99997
99998
100000
99998
99994
99997
99981
99994
99982
99997
100000
100000
99997
99998
99997
100000
100000
99997
100...

result:

ok 100000 numbers

Test #63:

score: 7
Accepted
time: 1774ms
memory: 42472kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99995
99990
99997
99999
99999
99999
99999
99999
99997
99971
99969
99999
99999
99997
99999
99999
99999
99990
99999
99999
99990
99999
99997
99999
99999
99999
99999
99999
99999
99894
99999
99913
99999
99999
99973
99999
99986
99999
99999
99999
99997
99999
99990
99989
99990
99999
99999
99999
99997
99990
...

result:

ok 100000 numbers

Test #64:

score: 7
Accepted
time: 422ms
memory: 42624kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99720
99788
99790
99720
99916
99714
99738
99834
99815
99707
99944
99584
99856
99930
99916
99856
99982
99796
99627
99754
99782
99790
99788
99848
99627
99982
99834
99834
99751
99944
99728
99751
99817
99944
99796
99720
99831
99916
99831
99728
99707
99627
99859
99668
99848
99771
99710
99710
99728
99838
...

result:

ok 100000 numbers

Test #65:

score: 7
Accepted
time: 425ms
memory: 42604kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99649
99852
99852
99852
99632
99758
99761
99820
99730
99750
99887
99783
99721
99865
99802
99867
99798
99811
99553
99691
99852
99750
99787
99774
99948
99774
99695
99811
99649
99811
99908
99975
99806
99761
99760
99820
99862
99806
99903
99798
99783
99691
99811
99903
99908
99865
99811
99632
99750
99948
...

result:

ok 100000 numbers

Test #66:

score: 7
Accepted
time: 428ms
memory: 42532kb

input:

100000 100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

99753
99961
99806
99756
99720
99900
99749
99823
99720
99846
99756
99602
99950
99749
99841
99818
99558
99792
99762
99900
99719
99750
99756
99856
99756
99950
99728
99934
99884
99660
99706
99762
99884
99977
99793
99860
99756
99602
99770
99833
99764
99841
99558
99937
99756
99950
99950
99756
99910
99729
...

result:

ok 100000 numbers

Test #67:

score: 0
Runtime Error

input:

100000 1 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:


result:


Subtask #4:

score: 18
Accepted

Test #69:

score: 18
Accepted
time: 34ms
memory: 14960kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

276
238
198
214
294
240
233
266
184
241
207
241
256
225
215
222
190
269
221
242
287
225
215
252
273
203
281
186
259
195
152
183
206
241
218
205
241
233
194
239
258
244
267
339
224
205
242
202
260
275
173
243
178
228
251
242
239
231
203
249
277
215
202
169
243
258
208
306
232
231
211
224
249
256
203
...

result:

ok 1797 numbers

Test #70:

score: 18
Accepted
time: 54ms
memory: 16444kb

input:

59284 89368 1930
4029 716
1741 4029
14542 4029
48937 4029
716 24494
29506 1741
4029 3097
2898 716
3097 8627
2898 46025
29506 15319
716 12015
1741 5566
8627 58178
2898 14837
7742 1741
21507 24494
20151 24494
48937 9926
55162 7742
32033 14837
2898 27435
12292 8627
24972 58178
55074 48937
45787 21507
1...

output:

369
311
313
353
339
335
284
364
434
382
298
243
268
306
282
383
400
371
343
357
399
329
285
264
350
350
372
391
378
398
281
257
419
308
307
462
379
357
327
356
323
427
360
368
312
394
268
310
310
324
275
312
279
347
298
281
314
291
447
257
320
269
343
311
397
279
332
319
238
268
369
334
301
321
390
...

result:

ok 1930 numbers

Test #71:

score: 18
Accepted
time: 47ms
memory: 17692kb

input:

67606 66951 1824
37697 58269
58269 20521
53476 37697
51085 20521
20521 3727
3727 59823
38837 53476
38837 40963
20521 28388
43757 51085
14394 58269
43757 1117
53476 60607
58269 57399
31600 57399
52004 3727
53476 44312
44312 49253
58269 2843
16982 43757
16982 60419
14394 5307
21031 20521
16982 13147
5...

output:

369
309
338
203
348
299
298
331
273
247
281
248
318
311
268
293
276
247
300
285
354
257
219
227
325
271
286
376
305
294
230
276
261
268
292
217
345
240
296
258
300
296
328
284
284
265
300
278
331
292
278
300
286
231
222
261
425
274
259
226
391
286
207
267
366
231
275
249
287
252
209
273
278
279
267
...

result:

ok 1824 numbers

Test #72:

score: 18
Accepted
time: 45ms
memory: 25316kb

input:

100000 100000 1
26451 75404
81327 75404
26451 29978
26451 40155
89550 29978
26451 16783
40584 40155
45697 16783
45697 46663
23828 46663
29978 77426
76408 26451
46663 8400
70202 29978
49633 40584
70202 77511
89375 76408
15804 29978
49633 38747
89550 42375
89550 81055
75404 88488
41733 89550
70202 137...

output:

78872

result:

ok 1 number(s): "78872"

Test #73:

score: 18
Accepted
time: 51ms
memory: 25340kb

input:

100000 100000 3
82208 40540
80548 82208
51536 80548
80548 84376
93726 82208
16865 84376
40540 39439
35540 93726
94810 16865
58036 35540
41837 80548
41837 5186
48275 41837
81090 93726
13718 35540
16865 77
39439 33192
58036 56787
40540 21934
13718 41327
46616 16865
77 88013
98749 40540
33949 16865
460...

output:

50026
49745
49971

result:

ok 3 number(s): "50026 49745 49971"

Test #74:

score: 18
Accepted
time: 47ms
memory: 25264kb

input:

100000 100000 10
34595 88812
53602 88812
51012 88812
34595 25192
96336 34595
25192 61224
21676 25192
34595 84305
25192 87097
87097 78572
78572 56128
76900 56128
47761 88812
99770 61224
47761 12554
56128 58321
63156 58321
58321 9825
12554 15673
99770 81857
63156 29843
81905 88812
38032 34595
96336 36...

output:

24893
24697
24858
24512
24636
24838
24613
24786
24626
24729

result:

ok 10 numbers

Test #75:

score: 18
Accepted
time: 48ms
memory: 25344kb

input:

100000 100000 30
42863 76067
63251 42863
76067 48333
42863 53221
29390 42863
85971 42863
3185 42863
63251 42450
3185 19834
19834 44010
48470 42450
19834 22824
54068 85971
63251 65339
97059 44010
42450 66115
98472 97059
33557 42863
74927 54068
69415 42450
69415 3326
63251 41552
85971 67253
93346 5406...

output:

11576
11233
11667
11966
11490
11509
11586
11307
11704
11674
11520
11361
11595
11324
11586
11570
11668
11588
11448
11759
11601
11651
11455
11452
11714
11746
11560
11602
11567
11750

result:

ok 30 numbers

Test #76:

score: 18
Accepted
time: 48ms
memory: 25260kb

input:

100000 100000 100
22634 75465
19501 75465
25894 19501
14338 19501
5523 25894
52399 14338
52399 42507
67866 75465
25894 61608
25894 93402
87416 22634
45236 52399
36472 75465
61608 41436
92396 93402
85899 25894
41436 21440
14228 14338
85899 56625
83318 41436
21440 51711
6339 56625
51711 80000
36472 53...

output:

4811
4631
4591
4481
4686
4687
4512
4917
4559
4688
4809
4515
4695
4519
4834
4446
4875
4768
4769
4793
4894
4685
4708
4629
4672
4594
4624
4547
4715
4922
4780
4686
4616
4464
4474
4537
4486
4697
4616
4643
4786
4509
4533
4510
4691
4667
4409
4687
4535
4578
4560
4699
4732
4490
4671
4722
4894
4658
4648
4568
...

result:

ok 100 numbers

Test #77:

score: 18
Accepted
time: 52ms
memory: 25416kb

input:

100000 100000 300
90578 89684
89684 3831
90578 66618
77524 66618
90578 48241
57189 3831
64968 57189
69650 3831
25557 77524
86156 66618
90578 34093
16791 89684
85977 34093
8297 85977
57189 60674
89684 75021
75021 49529
14470 34093
75021 13628
64968 23217
49529 13292
13292 9531
86156 64479
95832 89684...

output:

1913
1972
1803
1934
1795
1923
1896
1786
2012
1767
1870
1846
1898
2015
1895
1950
1959
1977
1824
1970
1758
1816
1996
1894
1828
1983
1948
1908
1801
1901
1964
1941
1860
1954
1856
2028
1833
1940
1754
1920
1791
2053
2068
1837
1889
1949
1714
1951
1879
1913
1925
1932
1856
1855
1951
1834
1843
1981
1938
1816
...

result:

ok 300 numbers

Test #78:

score: 18
Accepted
time: 69ms
memory: 25424kb

input:

100000 100000 1000
39153 45943
94392 39153
79053 39153
94392 33885
2756 79053
51903 33885
38859 51903
79053 36974
2767 36974
2756 15571
36974 72001
15933 79053
15933 74976
51127 45943
19196 38859
12936 2756
25536 38859
79053 97016
39585 15571
56150 12936
44998 39153
80397 79053
2767 37989
32196 7905...

output:

707
671
798
647
770
720
746
616
654
695
702
663
590
666
621
653
672
668
761
680
567
697
701
844
723
581
773
668
816
746
727
777
602
763
798
605
647
644
709
633
523
742
605
805
613
640
654
673
605
765
707
697
674
694
676
665
596
791
588
664
711
726
675
582
696
698
574
687
652
733
741
616
674
604
728
...

result:

ok 1000 numbers

Test #79:

score: 18
Accepted
time: 72ms
memory: 25452kb

input:

100000 100000 3000
24460 92288
92288 78218
92288 90483
92288 23779
23145 78218
23145 86709
78006 86709
19093 92288
23145 15895
78006 10663
15895 19595
24460 29358
51460 19093
19093 96262
24460 64190
15895 91390
15895 22891
56695 78006
78218 81580
99267 91390
47670 19093
96262 46523
81580 62720
55665...

output:

278
219
186
361
306
260
294
267
260
289
326
149
236
389
265
311
250
268
300
264
277
311
325
220
364
303
241
173
251
274
236
242
157
293
242
265
275
231
294
245
303
254
285
199
279
311
245
293
290
238
329
309
242
258
275
407
322
276
272
297
329
295
310
230
227
288
316
276
357
310
201
268
296
264
315
...

result:

ok 3000 numbers

Test #80:

score: 18
Accepted
time: 79ms
memory: 25460kb

input:

100000 100000 10000
60471 67901
60471 79481
67901 70274
43259 60471
40484 60471
70274 91612
70274 95567
30745 70274
25482 40484
67901 68399
68978 79481
57690 79481
61927 95567
31670 67901
99069 30745
58593 99069
29956 79481
106 67901
43259 74994
40484 4306
40484 59011
62413 4306
59011 81345
31670 52...

output:

135
58
123
95
36
97
39
143
132
98
114
104
103
45
85
73
88
44
93
85
63
102
71
128
61
61
39
66
101
89
63
124
156
118
123
68
92
59
72
42
55
119
105
114
127
84
124
87
81
69
124
104
98
85
70
96
128
96
96
91
148
106
120
141
85
72
58
51
52
68
58
72
44
109
96
91
113
89
72
114
108
88
76
69
99
110
100
126
115...

result:

ok 10000 numbers

Test #81:

score: 18
Accepted
time: 89ms
memory: 25836kb

input:

100000 100000 30000
16121 88102
71932 16121
88102 80368
80368 5806
88102 81591
80368 40177
45878 80368
16121 31693
81591 12812
21604 40177
60700 80368
32826 31693
8722 16121
40177 32445
13848 80368
20181 13848
20117 71932
32445 29712
80368 52542
80368 67199
88102 39197
36959 20181
86947 21604
60700 ...

output:

22
25
23
27
48
32
31
51
29
19
58
52
35
17
29
20
70
15
29
22
33
24
18
35
30
49
31
73
32
26
21
42
1
10
23
15
17
24
1
16
41
47
30
36
48
38
22
27
65
23
27
30
60
30
33
44
27
33
22
14
16
1
1
17
43
19
57
45
59
48
36
28
44
37
39
32
19
20
37
24
35
53
20
43
19
46
31
40
47
38
38
31
51
18
1
38
50
65
28
24
29
1
...

result:

ok 30000 numbers

Test #82:

score: 18
Accepted
time: 96ms
memory: 26976kb

input:

100000 100000 100000
25295 36699
36699 80196
25295 91969
86535 91969
94878 25295
80196 83806
94878 47722
36699 90327
8122 25295
90327 30030
91969 69857
17424 25295
99511 36699
86535 42411
91914 99511
43550 8122
13876 43550
47722 90714
90714 29235
90327 94216
16261 29235
86535 2183
13876 36794
33029 ...

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

Test #83:

score: 18
Accepted
time: 72ms
memory: 25360kb

input:

100000 100000 10000
38222 15170
15170 75637
99084 15170
80452 38222
15170 541
5526 80452
23574 80452
16220 15170
37892 5526
38222 27074
75637 97632
99084 76474
31858 5526
76474 91316
15170 4855
35230 541
99084 90246
35230 82033
37892 83347
25670 31858
80452 5212
81318 16220
27074 48624
56864 37892
4...

output:

58130
31
36
80
13
45
88
65
58
55
34
54
36
21
63
53
25
54
48
68
87
44
84
58
55
83
67
45
77
27
69
42
54
22
55
20
54
67
17
39
73
30
37
1
64
34
36
62
57
47
44
111
51
49
74
44
107
67
68
34
21
71
55
35
66
43
47
45
51
80
41
87
36
25
37
25
66
40
48
37
19
55
46
47
38
58
72
46
55
79
50
54
71
71
23
62
57
28
61...

result:

ok 10000 numbers

Test #84:

score: 18
Accepted
time: 70ms
memory: 25392kb

input:

100000 100000 10000
10087 59488
52461 59488
10087 45159
35663 52461
27244 10087
6802 10087
22085 45159
66718 52461
90682 59488
24586 22085
10087 47842
66718 32472
52461 19963
66718 48379
16667 35663
55150 59488
59488 71116
43492 55150
59488 50117
35663 44933
90682 58523
39987 32472
43492 53557
53557...

output:

57905
17
61
75
45
21
69
21
59
61
58
65
107
31
77
57
76
45
24
38
82
54
66
82
65
76
44
26
25
35
47
49
65
38
73
74
38
49
56
59
88
72
70
59
89
76
63
28
42
59
60
47
33
29
49
59
61
60
79
39
40
84
69
63
54
31
70
70
80
60
38
58
31
68
82
28
67
34
59
1
76
64
72
51
36
82
42
74
48
58
52
51
43
37
55
53
36
53
68
...

result:

ok 10000 numbers

Test #85:

score: 18
Accepted
time: 77ms
memory: 25424kb

input:

100000 100000 10000
50249 81030
81030 77615
37533 50249
77615 71106
50249 66355
68757 77615
23692 77615
59517 71106
71106 43631
69947 43631
59081 71106
43631 99849
68757 87248
80348 81030
86928 71106
37533 49237
72424 77615
69925 69947
77615 94960
52230 99849
81030 97500
94960 40587
69925 90591
5223...

output:

57638
25
42
52
40
45
68
44
58
71
36
61
59
22
32
55
25
53
35
51
52
68
85
58
61
29
29
79
73
55
70
53
76
14
36
39
29
32
34
48
44
81
57
66
44
51
79
60
62
77
33
39
45
86
82
49
59
64
1
98
72
31
30
91
49
81
23
46
82
28
39
62
30
69
55
67
65
31
84
58
64
80
32
38
53
31
31
54
33
73
40
42
66
40
26
64
53
66
55
4...

result:

ok 10000 numbers

Test #86:

score: 18
Accepted
time: 46ms
memory: 25536kb

input:

100000 100000 1
17336 24713
8334 24713
3279 8334
3279 25340
99746 25340
27914 99746
27914 14041
14041 78218
15946 78218
70589 15946
70589 94215
80626 94215
77426 80626
77426 4928
42781 4928
42781 38468
764 38468
764 40711
78246 40711
61110 78246
89319 61110
29300 89319
20450 29300
60532 20450
60532 ...

output:

99429

result:

ok 1 number(s): "99429"

Test #87:

score: 18
Accepted
time: 58ms
memory: 25452kb

input:

100000 100000 2
30969 34798
34798 58343
58343 81155
49294 81155
49294 33410
97390 33410
97390 81957
81957 3357
3357 40951
40951 31951
31951 96562
23439 96562
23439 88382
38083 88382
38083 26581
26581 55969
55969 16351
78107 16351
4882 78107
58029 4882
58029 9913
91908 9913
91908 11742
11742 69178
97...

output:

98472
98448

result:

ok 2 number(s): "98472 98448"

Test #88:

score: 18
Accepted
time: 48ms
memory: 25372kb

input:

100000 100000 5
75776 27
75776 83410
75192 83410
32454 75192
86642 32454
75192 23868
5657 23868
89968 5657
39947 89968
39947 89884
24021 89884
90531 24021
41514 90531
41514 86252
86252 33736
33736 97107
99170 97107
99170 25340
58761 25340
58761 84492
71696 83410
71696 15721
56118 15721
56118 88270
8...

output:

95964
95972
95915
95902
95937

result:

ok 5 number(s): "95964 95972 95915 95902 95937"

Test #89:

score: 18
Accepted
time: 49ms
memory: 25508kb

input:

100000 100000 10
49590 51200
51200 92734
92734 62448
61295 62448
47940 61295
62140 47940
62140 19454
19454 56398
55020 56398
46127 55020
75883 46127
75883 90396
90396 36081
88892 36081
88892 80541
80541 74268
74268 60884
42690 60884
8388 42690
8388 69797
39651 69797
14311 39651
14311 92970
68505 929...

output:

91720
91726
91847
91170
91665
91058
91235
91794
91569
91284

result:

ok 10 numbers

Test #90:

score: 18
Accepted
time: 47ms
memory: 25524kb

input:

100000 100000 20
42939 95341
95341 80137
74305 80137
74305 62030
84320 62030
84320 36495
56723 36495
56723 10023
94707 10023
94707 24180
24180 79603
66069 79603
66069 47082
78855 47082
78855 1708
82047 1708
72746 82047
8294 72746
8294 63927
63927 47149
47149 8544
35907 8544
35907 90099
21705 90099
2...

output:

86054
86116
86145
86177
85644
86454
85948
85428
85547
86545
85972
86244
85972
85011
85361
86615
85454
86075
85552
86514

result:

ok 20 numbers

Test #91:

score: 18
Accepted
time: 51ms
memory: 25476kb

input:

100000 100000 50
91063 56666
56666 84770
33256 84770
92203 33256
92203 26547
50455 26547
50455 12214
12214 20646
61777 20646
61777 25527
44271 25527
44271 31371
31371 40062
52303 40062
52303 34909
34909 88370
88370 25548
86001 25548
86001 27929
27929 13692
13692 2234
24128 2234
24128 11987
54953 119...

output:

73412
72484
71901
72628
72374
71424
72194
71611
72321
72316
71666
72187
71897
72173
72029
71404
72672
72070
72345
71076
71479
71166
72099
74024
72687
72974
73154
72686
72571
73091
71305
73593
71427
71958
73301
73156
72084
72667
71653
72902
72531
71870
71579
72697
72703
73512
72918
71693
72467
72823

result:

ok 50 numbers

Test #92:

score: 18
Accepted
time: 43ms
memory: 25420kb

input:

100000 100000 100
79835 65625
79835 46101
46101 35569
52654 35569
18865 52654
23449 18865
23449 70124
86965 70124
5155 86965
64712 5155
15402 64712
15402 36922
55872 36922
55872 68526
88352 68526
6022 79835
6022 29039
23909 29039
23909 32123
65487 32123
88233 65487
88233 50674
74916 50674
74916 1363...

output:

59588
59646
57664
60014
58229
60620
59351
60462
61001
61463
60148
60200
60390
60351
61431
60322
58379
60579
60667
60901
59951
60833
60302
58485
61060
60303
60177
60041
60912
58407
59989
59531
60042
61654
59219
59626
59836
59548
60175
59769
58725
61111
59208
61247
59809
58534
58707
59656
59249
57950
...

result:

ok 100 numbers

Test #93:

score: 18
Accepted
time: 60ms
memory: 25516kb

input:

100000 100000 200
70876 43754
70876 97121
96062 97121
96062 37487
90682 37487
41579 90682
48324 41579
21247 48324
92500 21247
21515 92500
19971 21515
82600 19971
2954 82600
60677 2954
60677 32698
32698 13984
58449 13984
58449 87913
87913 38704
15021 38704
15021 51322
51322 56139
75697 56139
75697 47...

output:

46551
46302
47347
47559
47639
45621
45957
45270
45497
48017
47708
46868
47113
42945
47095
47797
47868
46386
47151
46000
47671
44786
48792
46178
47928
47498
47380
46928
46906
44536
47231
47188
46296
44868
45548
45912
46201
47181
49064
46076
48941
49602
48392
44711
47946
44902
45822
47261
48501
44939
...

result:

ok 200 numbers

Test #94:

score: 18
Accepted
time: 61ms
memory: 25488kb

input:

100000 100000 500
57360 64763
64763 75381
18461 75381
18461 17287
38722 17287
38722 29937
29937 31954
31954 78127
78127 17425
95713 17425
82315 95713
82315 49051
83397 49051
83397 23902
37020 23902
37020 93584
93584 29528
29528 84863
84863 93022
93022 96825
96825 25162
25162 85333
5118 85333
90315 5...

output:

27934
29538
30878
24981
29462
28229
29629
29798
28435
26482
28191
31900
29370
29173
28467
29707
27684
32533
30918
29167
32438
30041
29973
33562
28763
28387
30458
31898
29838
30533
27020
28963
29943
25939
31565
29810
28016
29013
27914
30307
26889
28670
30933
30832
31319
32869
30086
29457
30381
30917
...

result:

ok 500 numbers

Test #95:

score: 18
Accepted
time: 68ms
memory: 25444kb

input:

100000 100000 1000
99530 945
945 72420
82768 72420
82768 871
24906 871
64900 24906
64900 32592
32592 54200
54200 10811
35490 10811
35490 51493
4208 51493
15730 4208
75969 15730
75969 91410
91410 3670
59481 3670
32947 59481
32947 31713
31713 33014
33014 43209
89362 43209
41577 89362
75434 41577
75434...

output:

20179
18493
20048
18108
18293
21310
19320
19512
19736
16480
19388
17574
18331
22048
21172
19805
19786
17489
14997
19153
18009
16072
17644
18920
21501
19482
16908
19407
16489
20715
17321
20989
19012
20777
17647
19907
20579
16752
19082
17944
19558
17804
18499
20672
18859
20060
20797
18422
19555
17976
...

result:

ok 1000 numbers

Test #96:

score: 18
Accepted
time: 77ms
memory: 25468kb

input:

100000 100000 2000
46795 88145
34353 88145
34353 28718
28718 72605
99247 72605
99247 19291
6696 19291
3855 6696
3855 40768
40768 11480
11480 35942
91717 35942
91717 56952
56952 88713
88713 57883
5092 57883
29831 5092
29831 52946
91272 52946
91272 11901
91202 11901
91202 78475
29162 78475
29162 76471...

output:

9806
12013
13128
10162
13263
13823
10991
15391
12722
15002
14228
13178
12705
13744
11494
13943
10556
12324
10929
15445
11458
9064
13295
15465
10351
12587
12444
12310
12366
13362
11404
11888
9750
13490
11531
12721
13068
13695
13691
12637
11934
12666
13690
13402
14495
9899
13352
15480
12877
11605
1354...

result:

ok 2000 numbers

Test #97:

score: 18
Accepted
time: 76ms
memory: 25692kb

input:

100000 100000 5000
77273 56100
56100 91660
50227 91660
50227 15926
15926 92373
42060 92373
42060 74980
74980 32644
43156 32644
43156 13121
13121 72421
85187 72421
85187 59467
17511 59467
17511 13574
92386 13574
20667 92386
12338 20667
66556 12338
27196 66556
27196 58247
58247 87471
87471 46775
59404...

output:

7295
6453
6322
3874
6610
5375
7551
7292
6786
4254
6606
5971
5195
5481
6387
7425
5114
5370
5086
6789
4536
7406
7479
5657
5689
6627
6983
8039
4469
4980
6774
8140
5590
7117
5002
4318
10313
9616
5938
7124
7246
6107
7529
7279
8779
6057
8540
6179
7164
7840
7874
7758
7321
3427
7779
7603
5827
7021
7302
6776...

result:

ok 5000 numbers

Test #98:

score: 18
Accepted
time: 82ms
memory: 25628kb

input:

100000 100000 10000
99625 10262
33273 10262
33273 87688
87688 28262
28262 21378
44930 21378
44930 73035
74047 73035
60258 74047
36678 60258
15988 36678
15988 96940
48407 96940
90871 48407
15765 90871
41212 15765
41212 13281
46311 13281
46311 30281
30281 91223
91223 57416
57416 30624
65673 30624
7656...

output:

3580
3574
6771
8071
2997
4013
2677
2818
6640
3815
2609
4162
6620
3715
4255
3332
3917
4570
3640
4018
5708
3418
5269
5639
5638
4182
5809
5242
6168
3160
4653
3648
2522
3344
5626
3677
3586
2601
4461
4130
4782
2806
4754
3610
5817
5210
1457
4697
4988
3914
3152
5511
4627
1170
4649
4005
4858
2654
3673
4361
...

result:

ok 10000 numbers

Test #99:

score: 18
Accepted
time: 77ms
memory: 25816kb

input:

100000 100000 20000
46502 14399
27374 14399
11920 27374
37881 11920
37881 83015
2129 83015
2129 85014
85014 74249
74249 85926
71766 85926
69125 71766
34215 69125
34215 13662
13662 51316
47210 51316
35931 47210
64658 35931
15298 64658
23374 15298
23374 26063
26063 96279
96279 67981
45324 67981
45324 ...

output:

2414
618
1227
4819
3524
1510
4737
2664
1358
3562
978
2043
4618
1982
1
2557
608
2838
1701
2247
2264
2540
2035
2308
1368
1642
4086
1771
1672
2438
1904
3460
2901
1646
1
2396
2594
1921
2885
1627
2408
5089
2796
503
1830
594
2101
2295
1355
2903
1786
1920
1936
2498
2496
3353
1510
844
1892
2463
2225
5494
18...

result:

ok 20000 numbers

Test #100:

score: 18
Accepted
time: 89ms
memory: 26212kb

input:

100000 100000 50000
45769 24178
24178 20604
15039 20604
2050 15039
88588 2050
88588 41436
7833 41436
88477 7833
88477 6437
6437 90266
90266 98586
58347 98586
58347 25467
66701 25467
66701 79702
62348 79702
18322 62348
57153 18322
57153 60621
90360 60621
90360 99224
97984 99224
97984 30507
69662 3050...

output:

1378
622
791
446
1
1
796
1
1131
812
1006
1
811
1
614
193
1
854
1
667
1446
1
824
1
1
1
1
1751
650
1
1598
1412
599
1087
559
539
1
1
1754
660
1757
1
625
513
1
591
1
839
1
556
1
1
1315
1808
1
1
651
1033
1046
732
1
1550
1142
387
1
1
1
634
1
2246
1
651
1138
1144
1
1
1298
994
1
1085
752
567
1
1863
330
1
17...

result:

ok 50000 numbers

Test #101:

score: 18
Accepted
time: 90ms
memory: 27372kb

input:

100000 100000 100000
33223 71503
48111 33223
48111 54357
54357 85597
48710 85597
87401 48710
87401 99833
52408 99833
52408 9973
21639 9973
10032 21639
53594 10032
53594 89729
56572 89729
87704 56572
93536 87704
93536 88191
34283 88191
34283 25104
43699 25104
43699 8756
8756 5017
5017 31474
31474 217...

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

Subtask #5:

score: 24
Accepted

Test #102:

score: 24
Accepted
time: 1526ms
memory: 17228kb

input:

55965 89652 95687
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

42788
7820
39914
18090
47411
43990
2171
29300
18235
16451
44208
47526
32163
44460
32385
30155
45741
45708
47396
43518
30989
19208
13902
35077
49210
21200
43577
32110
19690
35461
45079
11601
42233
16862
23259
44558
41924
39465
34626
41081
32139
34482
41166
24623
11638
18786
29659
38064
42423
42321
30...

result:

ok 95687 numbers

Test #103:

score: 24
Accepted
time: 1559ms
memory: 17672kb

input:

58162 92590 89370
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

26124
11696
34672
19906
37517
39745
12092
11803
38936
29481
39777
42062
22087
43080
42468
22618
42584
42512
36052
48395
44563
29063
20611
42203
40753
37002
24991
38717
37467
43935
36308
37416
43842
39169
44996
35657
38159
30030
41535
34488
37655
50046
46898
42657
45573
4308
15509
41852
28225
32898
3...

result:

ok 89370 numbers

Test #104:

score: 24
Accepted
time: 1790ms
memory: 23488kb

input:

84839 99146 96158
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

54950
43189
36772
1311
65352
65239
39742
60625
5657
51176
12141
22845
42904
46862
12604
38455
45384
26962
63267
28904
9995
50936
39499
48890
47780
7253
6239
49271
59029
46282
27940
57496
64917
52909
58560
27947
46253
21818
59417
63544
21645
37364
26764
23249
66794
50332
51190
44172
68809
62291
46510...

result:

ok 96158 numbers

Test #105:

score: 24
Accepted
time: 1842ms
memory: 26936kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

74296
48517
45111
49478
42663
30316
66980
14003
52373
69355
26205
22241
70123
62132
25494
49459
17717
51008
30285
38307
61890
49679
39923
21693
19328
73265
26327
77090
54503
74185
49855
27162
51570
35838
65915
75805
44534
68679
45700
9883
73608
21808
60186
5320
43240
42021
55300
38369
51151
63595
73...

result:

ok 100000 numbers

Test #106:

score: 24
Accepted
time: 1845ms
memory: 26848kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

55661
72881
55021
58078
53349
21715
54142
73477
55470
56603
40428
59731
54626
8400
56046
17766
66014
48806
76195
61741
49472
66302
55213
40434
58123
46091
46564
60096
73852
67311
77958
38297
54985
40428
23638
29758
15211
31168
52671
58116
56280
67887
68408
37271
74504
52906
24333
39868
15906
62095
1...

result:

ok 100000 numbers

Test #107:

score: 24
Accepted
time: 1870ms
memory: 26996kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

49384
72701
65618
43104
29539
20835
59080
59167
56906
20578
46819
13802
50034
47888
68226
69683
53386
58689
3005
68357
70057
42532
29448
63486
59387
75767
1484
50118
7531
59768
64142
33124
58482
70372
21619
5524
37882
49407
57595
67194
8814
23826
74496
45761
8423
63268
52487
63160
58909
53162
65003
...

result:

ok 100000 numbers

Test #108:

score: 24
Accepted
time: 1853ms
memory: 26920kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

38465
43388
71697
56061
6291
40224
57457
67627
68790
34583
73389
43063
39974
73144
52951
58669
70864
15981
45044
23527
30202
26791
60615
60846
50771
69093
32598
52346
53692
33355
42582
70057
12128
52963
31023
36955
48359
39535
6049
31335
74831
64311
32046
45695
67030
59949
69438
71994
5359
26311
621...

result:

ok 100000 numbers

Test #109:

score: 24
Accepted
time: 1851ms
memory: 26904kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

26184
13746
53879
74756
18323
28970
47470
57972
34286
25245
61319
34479
13814
60595
62463
63360
27912
61408
23127
50981
54756
35666
63071
72127
20254
65490
57530
51176
67262
78884
27346
72671
5421
33642
76750
43390
53948
52980
39795
70102
15985
66308
51198
49738
33588
18825
62592
47119
57733
65814
5...

result:

ok 100000 numbers

Test #110:

score: 24
Accepted
time: 1859ms
memory: 26864kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

26479
23046
36774
24865
44391
78375
49346
7754
74043
72476
37596
8906
60787
36825
21658
8554
931
49288
50894
46211
36664
3786
41495
47245
37349
28584
60715
26725
77691
56564
70960
62827
50819
57064
61332
43428
62586
63789
53495
59866
32477
44190
33551
48908
8890
73163
59870
77730
42497
75153
46755
4...

result:

ok 100000 numbers

Test #111:

score: 24
Accepted
time: 1844ms
memory: 26924kb

input:

100000 100000 100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

18616
52534
54018
54103
39251
67225
40344
75167
69598
74411
62698
47426
70535
30737
33020
70772
51000
70396
75726
12926
38592
43706
33934
55736
68545
65599
17447
68380
34831
60273
77781
52341
42480
69806
71029
69797
38672
68520
67630
47153
67495
58497
61878
54799
43576
68697
31787
22247
26277
37491
...

result:

ok 100000 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

0%