QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#829225#6340. Tourismmaxrgby100 ✓1848ms49304kbC++204.0kb2024-12-24 07:51:032024-12-24 07:51:03

Judging History

This is the latest submission verdict.

  • [2024-12-24 07:51:03]
  • Judged
  • Verdict: 100
  • Time: 1848ms
  • Memory: 49304kb
  • [2024-12-24 07:51:03]
  • Submitted

answer

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int block = 450;

int n,m,q;
vector<int> adj[100005];
int loc[100005];
vector<array<int,3>> queries[100005];
int tin[100005];
int tout[100005];
int depth[100005];
int up[100005][20];
int bk[100005];
int fd[100005];
int on[100005];
int sparse[200005][20];
int sum;
vector<int> arr;
vector<int> tour;
int timer = 0;

void dfs(int u, int p){
	tour.push_back(u);
	tin[u] = timer++;
	up[u][0] = p;
	depth[u] = depth[p]+1;
	for(int i = 1;i < 20;i++){
		up[u][i] = up[up[u][i-1]][i-1];
	}
	for(auto v : adj[u]){
		if(v != p){
			dfs(v,u);
			tour.push_back(u);
		}
	}
	tout[u] = timer++;
}

bool ancestor(int a, int b){
	return tin[a] <= tin[b] and tout[a] >= tout[b];
}

int lca(int a, int b){
	if(ancestor(a,b)) return a;
	if(ancestor(b,a)) return b;
	for(int i = 19;i >= 0;i--){
		if(!ancestor(up[a][i],b) and up[a][i] != 0){
			a = up[a][i];
		}
	}
	return up[a][0];
}

int lg(int a){
	return 31-__builtin_clz(a);
}

int mindepth(int a, int b){
	if(depth[tour[a]] <= depth[tour[b]]){
		return a;
	}
	return b;
}

int lca2(int a, int b){
	a = tin[a];
	b = tin[b];
	if(a > b){
		swap(a,b);
	}
	int diff = lg(b-a+1);
	return mindepth(sparse[a][diff],sparse[b+1-(1<<diff)][diff]);
}

int dist(int a, int b){
	//cout << "a=" << a << "b=" << b << "lca=" << lca(a,b) << " " << tour[lca2(a,b)] << endl;
	//assert(lca(a,b) == tour[lca2(a,b)]);
	return depth[a]+depth[b]-2*depth[tour[lca2(a,b)]];
}

bool cmp(int a, int b){
	return tin[a] < tin[b];
}

bool cmp2(array<int,3> a, array<int,3> b){
	return a[1] > b[1];
}

void del(int u){
	int right = fd[u];
	int left = bk[u];
	if(left == 0){
		left = bk[n+1];
	}
	if(right == n+1){
		right = fd[0];
	}
	sum -= dist(arr[left],arr[u]);
	sum -= dist(arr[u],arr[right]);
	sum += dist(arr[left],arr[right]);
	fd[bk[u]] = fd[u];
	bk[fd[u]] = bk[u];
}

int main() {
	cin >> n >> m >> q;
	arr.resize(n+1);
	iota(arr.begin(),arr.end(),0);
	for(int i = 0;i < n-1;i++){
		int a,b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i = 1;i <= m;i++){
		cin >> loc[i];
	}
	for(int i = 0;i < q;i++){
		int l,r;
		cin >> l >> r;
		queries[l/block].push_back({l,r,i});
	}
	depth[1] = 1;
	dfs(1,0);
	for(int i = 0;i < tour.size();i++){
		sparse[i][0] = i;
	}
	for(int i = 1;i < 20;i++){
		for(int j = 0;(j+(1<<i)) < tour.size();j++){
			sparse[j][i] = mindepth(sparse[j][i-1],sparse[j+(1<<(i-1))][i-1]);
		}
	}
	// for(int j = 0;j < tour.size();j++){
	// 	for(int i = 0;i < 20;i++){
	// 		cout << sparse[j][i] << " ";
	// 	}
	// 	cout << endl;
	// }
	sort(arr.begin()+1,arr.end(),cmp);
	int mp[n+1];
	for(int i = 0;i <= n;i++){
		mp[arr[i]] = i;
	}
	int ans[q];
	for(int i = 0;i <= m/block;i++){
		int bl = i*block;
		if(bl == 0){
			bl++;
		}
		sort(queries[i].begin(),queries[i].end(),cmp2);
		memset(bk,0,sizeof(bk));
		memset(fd,0,sizeof(fd));
		memset(on,0,sizeof(on));
		for(int j = bl;j <= m;j++){
			on[mp[loc[j]]]++;
		}
		int last = 0;
		sum = 0;
		for(int j = 1;j <= n;j++){
			if(on[j]){
				bk[j] = last;
				fd[last] = j;
 				if(last != 0){
					sum += dist(arr[last],arr[j]);
					//cout << "sum=" << sum << endl;
				}
				last = j;
			}
		}
		sum += dist(arr[last],arr[fd[0]]);
		fd[last] = n+1;
		bk[n+1] = last;
		int cr = m;
		//cout << "sum=" << sum << endl;
		for(auto [l,r,q] : queries[i]){
			//cout << endl << "l=" << l << "r=" << r << "q=" << q << endl;
			while(cr > r){
				int u = mp[loc[cr--]];
				if(!--on[u]){
					del(u);
				}
			}
			//cout << "SUM=" << sum << endl;
			int tmp = sum;
			for(int j = bl;j < l;j++){
				int u = mp[loc[j]];
				if(!--on[u]){
					del(u);
				}
			}
			//cout << "SUM=" << sum << endl;
			ans[q] = sum/2+1;
			for(int j = l-1;j >= bl;j--){
				int u = mp[loc[j]];
				if(!on[u]++){
					fd[bk[u]] = u;
					bk[fd[u]] = u;
				}
			}
			sum = tmp;
		}
	}
	for(int i = 0;i < q;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 2ms
memory: 9904kb

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

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

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

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

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

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

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

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

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: 9888kb

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

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

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

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

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

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: 7852kb

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

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

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

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

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

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

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

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

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: 5
Accepted
time: 2ms
memory: 9944kb

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:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 #26:

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

input:

300 300 300
290 253
290 246
253 35
35 148
27 290
35 141
253 90
187 290
253 259
27 59
119 187
290 192
141 174
59 54
222 59
27 161
270 161
32 35
32 111
270 185
90 24
24 190
241 253
270 95
45 141
241 83
107 35
95 208
269 148
246 99
231 83
45 296
95 78
253 136
241 152
40 83
116 269
95 211
118 107
241 49...

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

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #27:

score: 5
Accepted
time: 8ms
memory: 10148kb

input:

1473 1453 1340
1202 996
996 681
720 996
720 1382
132 996
789 681
1024 1202
261 789
1133 1382
420 996
1133 603
1382 1461
1470 1202
1470 708
313 1461
788 720
132 710
1153 681
11 1133
710 221
681 88
925 1133
720 494
682 789
107 788
1164 261
1024 893
1133 163
868 11
1164 726
868 604
1212 88
420 1172
138...

output:

510 568 367 434 1106 1040 1083 1001 985 1164 305 982 29 115 1000 476 1014 326 1137 1054 914 604 761 796 982 827 585 950 655 760 613 396 450 432 907 366 865 505 871 206 1029 1004 1097 348 1006 608 509 230 269 951 771 607 685 665 1000 903 1146 783 61 810 1003 973 799 1078 785 949 393 258 957 726 1078 ...

result:

ok 1340 numbers

Test #28:

score: 5
Accepted
time: 9ms
memory: 8216kb

input:

1437 1592 1756
1289 660
454 1289
1289 847
660 1069
803 847
721 660
660 1043
1069 1337
1253 1337
454 462
1289 768
721 911
638 847
1043 54
261 638
153 721
54 1194
1289 637
1339 660
1043 216
54 1351
1312 721
1043 679
138 1253
880 1351
196 911
196 155
1395 54
153 1273
216 1136
637 732
1395 557
1046 462
...

output:

166 151 1085 943 240 811 615 386 645 536 689 445 623 320 743 633 438 902 600 735 210 531 415 707 41 555 558 417 858 773 200 863 626 666 943 461 970 805 504 151 589 574 53 571 1009 495 712 298 1006 489 100 540 582 329 1043 788 652 295 445 879 872 944 666 733 568 558 726 989 1004 832 660 611 846 720 4...

result:

ok 1756 numbers

Test #29:

score: 5
Accepted
time: 8ms
memory: 12204kb

input:

2000 2000 2000
1144 879
1144 841
1037 841
673 1144
641 879
673 142
1037 1494
673 1920
1094 1920
879 1093
1037 1796
1745 1093
1745 1455
497 1093
68 1094
1225 1745
317 641
1494 582
1920 605
1444 497
1008 1796
582 470
300 1225
1015 1745
737 497
879 1145
1494 608
219 1094
1035 300
1444 892
673 1932
1032...

output:

217 530 1155 704 187 1415 655 638 631 1311 659 631 671 876 278 774 970 830 1073 1096 992 1154 358 852 484 737 735 1118 176 705 1301 743 982 1018 865 1000 1415 1006 1357 696 980 84 332 711 942 627 1226 1182 1085 1378 1189 509 490 898 526 1207 29 1155 1354 1320 1344 996 424 637 145 464 928 1523 1498 3...

result:

ok 2000 numbers

Test #30:

score: 5
Accepted
time: 9ms
memory: 10272kb

input:

2000 2000 2000
722 1697
755 722
1697 290
300 755
1828 755
290 969
365 722
1394 755
969 1549
10 1697
1601 969
1108 1601
300 1398
300 1408
1108 1351
1697 1883
593 10
66 1108
1207 1697
110 1697
593 444
1983 66
36 1883
1351 1847
1540 1351
1398 289
1697 1214
871 1351
558 1883
256 300
1314 558
1547 1601
1...

output:

1432 1209 1290 314 1173 1188 1221 1342 940 545 1248 804 212 475 1402 707 1497 1200 1107 1076 1502 447 231 1423 1253 554 729 566 443 990 1163 1137 1252 788 1293 813 701 742 1139 1310 1093 1262 1019 378 619 1120 1357 1394 883 325 28 363 363 1040 1154 1151 1159 1016 1124 1034 1319 1119 565 816 1302 132...

result:

ok 2000 numbers

Test #31:

score: 5
Accepted
time: 8ms
memory: 10340kb

input:

2000 2000 2000
1414 105
1648 1414
105 1324
1324 1634
5 1648
1324 800
1878 5
1438 1324
1505 1634
1615 1438
1505 1495
1615 533
1414 726
1432 1505
1414 192
1648 1819
1648 1489
667 800
1505 1756
1796 800
481 1634
5 1223
245 105
1819 1427
1634 1962
1962 1603
760 1603
1615 157
327 1223
1819 1861
192 672
3...

output:

437 82 507 1415 1217 1106 823 328 1012 1426 1266 1458 723 1355 735 1370 415 868 419 1204 605 1039 75 894 1162 740 733 736 990 819 489 553 1358 70 1257 306 1230 284 853 268 199 759 988 1238 355 1490 1530 1127 1368 848 1488 1411 1368 740 1418 260 995 1555 556 1356 800 654 996 757 1568 101 834 311 1340...

result:

ok 2000 numbers

Test #32:

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

input:

2000 2000 2000
1381 1760
719 1381
719 199
1802 199
1381 709
1381 29
80 1802
199 1209
709 1221
1405 1760
1381 1954
1437 1209
1777 719
1190 709
29 1859
719 1862
1190 1206
880 199
199 1792
874 1760
56 80
1190 519
29 570
719 428
1867 1954
80 1876
668 1437
880 1814
760 80
1229 1760
1229 1884
1198 56
1862...

output:

1553 1555 1556 1546 1552 1548 1553 1555 1551 1553 1546 1556 1558 1549 1550 1548 1551 1553 1553 1558 1551 1557 1558 1545 1553 1552 1557 1547 1550 1556 1551 1560 1546 1556 1554 1548 1554 1555 1553 1555 1549 1547 1557 1554 1553 1555 1549 1554 1552 1551 1556 1558 1549 1550 1557 1556 1550 1555 1552 1556 ...

result:

ok 2000 numbers

Test #33:

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

input:

2000 2000 2000
1405 1156
1156 254
1107 1405
1107 1102
1156 1745
1107 1210
1431 1745
1102 978
357 1431
1405 1782
396 1431
357 1696
357 1013
1431 545
1259 357
1107 32
1009 545
1564 1210
32 481
1009 1930
325 254
483 1696
1629 254
1867 1782
1782 1702
189 32
1405 664
1696 1404
1013 1139
1210 1487
1702 19...

output:

1588 1584 1585 1583 1586 1580 1586 1586 1588 1585 1580 1582 1580 1585 1580 1594 1586 1580 1588 1580 1584 1585 1591 1588 1588 1580 1586 1588 1583 1591 1586 1583 1586 1587 1588 1594 1585 1589 1584 1583 1582 1590 1579 1583 1586 1584 1584 1580 1581 1583 1580 1587 1585 1588 1585 1589 1580 1593 1590 1586 ...

result:

ok 2000 numbers

Test #34:

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

input:

2000 2000 2000
722 1610
800 722
800 1902
1146 1610
722 263
1960 1610
1420 1902
1902 1634
1610 1181
479 1634
800 1203
291 1610
722 408
291 718
1420 94
408 821
1610 629
408 1051
94 1171
1420 207
479 1631
777 1610
408 191
408 838
800 1427
1865 1902
1493 1146
718 1549
727 191
1224 1631
207 1394
88 94
28...

output:

1554 1554 1551 1557 1555 1556 1558 1559 1558 1564 1554 1556 1552 1553 1554 1558 1558 1564 1556 1558 1557 1554 1553 1557 1559 1550 1550 1552 1558 1552 1551 1558 1566 1552 1564 1559 1558 1551 1558 1558 1557 1560 1555 1563 1564 1560 1555 1554 1563 1555 1564 1554 1557 1558 1557 1552 1550 1552 1560 1560 ...

result:

ok 2000 numbers

Test #35:

score: 5
Accepted
time: 7ms
memory: 8320kb

input:

2000 2000 2000
919 1147
1802 919
1802 199
199 1712
884 1712
884 935
935 1296
743 1296
1140 743
1140 1360
1360 230
230 70
70 1393
1393 885
885 1342
1342 1838
856 1838
856 1942
1942 1188
1188 851
1449 851
15 1449
15 1017
1017 185
185 1031
203 1031
203 100
354 100
354 545
545 1772
1772 1094
1094 1495
1...

output:

1978 1998 1998 1894 1996 1996 1997 1989 1997 1997 1997 1978 1997 1929 1996 1997 1996 1997 1928 1997 1997 1996 1997 1948 1971 1958 1997 1998 1942 1996 1998 1997 1997 1997 1994 1981 1973 1960 1951 1973 1996 1998 1998 1971 1996 1972 1997 1997 1995 1996 1989 1998 1914 1996 1997 1996 1996 1996 1997 1997 ...

result:

ok 2000 numbers

Test #36:

score: 5
Accepted
time: 11ms
memory: 10448kb

input:

2000 2000 2000
820 1043
820 1055
1055 1094
1094 905
905 550
550 1650
1312 1650
1312 1143
1143 1121
1121 1346
1346 734
45 734
45 1553
1262 1553
1871 1262
346 1871
346 278
249 278
795 249
427 795
519 427
973 519
973 1538
1538 1111
532 1111
532 1024
802 1024
802 1101
29 1101
29 1170
1170 1153
1153 1938...

output:

1993 1991 1994 1996 1993 1996 1993 1988 1996 1996 1996 1982 1984 1988 1992 1994 1982 1996 1996 1995 1995 1988 1996 1986 1996 1995 1985 1996 1996 1995 1994 1983 1996 1995 1996 1901 1973 1988 1996 1994 1996 1982 1995 1996 1996 1978 1996 1982 1993 1996 1996 1996 1739 1984 1996 1996 1995 1995 1992 1989 ...

result:

ok 2000 numbers

Test #37:

score: 5
Accepted
time: 2ms
memory: 10412kb

input:

2000 2000 2000
1987 1006
962 1006
1936 962
1936 1905
1905 134
134 1420
648 1420
460 648
460 1434
1434 783
1440 783
1198 1440
1198 1967
1967 216
1266 216
1266 825
1862 825
1862 264
1212 264
993 1212
993 408
966 408
966 1117
428 1117
428 1623
1824 1623
1970 1824
551 1970
1566 551
1566 1565
1054 1565
1...

output:

1991 1984 1987 1991 1925 1993 1991 1984 1991 1991 1857 1991 1979 1990 1991 1949 1993 1990 1990 1964 1990 1981 1991 1991 1990 1968 1987 1993 1990 1991 1990 1990 1991 1990 1991 1993 1980 1991 1981 1990 1993 1979 1979 1987 1991 1984 1991 1988 1991 1986 1991 1979 1990 1990 1968 1968 1991 1991 1987 1979 ...

result:

ok 2000 numbers

Test #38:

score: 5
Accepted
time: 4ms
memory: 10456kb

input:

2000 2000 2000
1791 1481
1347 1791
1347 1772
1875 1772
249 1875
249 144
144 1375
1375 293
1586 293
732 1586
732 996
996 1562
1915 1562
1915 729
729 1862
1862 330
830 330
599 830
340 599
1836 340
1836 386
113 386
1864 113
983 1864
983 1397
1397 200
200 15
516 15
1405 516
1405 875
875 73
513 73
1222 5...

output:

1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 1998 ...

result:

ok 2000 numbers

Test #39:

score: 5
Accepted
time: 5ms
memory: 12336kb

input:

2000 2000 2000
1080 1228
1228 329
1380 329
1569 1380
1814 1569
1814 1368
1368 1267
1267 1076
1253 1076
59 1253
47 59
47 811
811 871
871 805
494 805
105 494
518 105
518 1345
1345 1105
374 1105
1260 374
1260 96
606 96
727 606
1595 727
1305 1595
1305 1457
1457 1739
314 1739
1336 314
1336 1500
1206 1500...

output:

1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 ...

result:

ok 2000 numbers

Test #40:

score: 5
Accepted
time: 4ms
memory: 8368kb

input:

2000 2000 2000
543 17
543 1251
1182 1251
271 1182
271 1964
363 1964
363 1894
1894 1131
1383 1131
1383 1704
1704 1081
1081 875
875 909
909 610
36 610
381 36
381 1885
1885 301
301 1101
1101 865
1835 865
544 1835
544 702
1757 702
688 1757
688 1578
1578 1227
1227 1050
1050 585
585 1549
1127 1549
1127 70...

output:

1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 ...

result:

ok 2000 numbers

Test #41:

score: 5
Accepted
time: 7ms
memory: 8336kb

input:

2000 2000 2000
453 1834
453 1838
1081 1838
1081 1052
1052 45
45 1894
1631 1894
1631 91
1857 91
1857 294
899 294
372 899
1039 372
977 1039
1457 977
1898 1457
1898 988
1373 988
1413 1373
1227 1413
747 1227
1957 747
1945 1957
1339 1945
1339 249
249 1703
1703 1642
1642 985
6 985
988 1118
1118 403
403 18...

output:

1939 1976 1962 1294 1907 1983 1921 1987 1969 1897 1966 1967 1799 1912 1987 1974 1466 1965 1909 1796 1980 1835 1982 1666 1969 1864 1963 1967 1891 1470 1937 1942 1223 1987 1926 1974 1959 1918 1944 1864 1922 1945 1946 1987 1976 1822 1891 1969 1904 1951 1980 1687 1970 1572 1927 1159 1987 1925 1974 1197 ...

result:

ok 2000 numbers

Test #42:

score: 5
Accepted
time: 11ms
memory: 8300kb

input:

2000 2000 2000
1869 445
1365 1869
1206 1365
1206 384
1989 384
1989 1733
1733 1793
502 1793
967 502
569 967
569 649
937 649
564 937
564 743
95 743
1274 95
1594 1274
1594 126
1068 126
877 1068
877 488
1220 488
1220 236
989 236
989 1261
1261 862
1343 862
1343 1557
354 1557
1293 354
1012 1293
1012 1016
...

output:

1869 1975 1936 1900 1919 1957 1952 1774 1931 1972 1936 1864 1816 1975 492 1616 1913 1864 1795 1911 1186 1946 1916 1917 1941 1963 1974 1958 688 1973 1962 1949 1930 1964 1828 1890 1911 1974 1948 1970 1675 1741 1786 1494 1934 1946 1606 1941 1965 1963 1935 1878 1730 1940 1931 1751 1527 1961 1954 1933 15...

result:

ok 2000 numbers

Test #43:

score: 5
Accepted
time: 7ms
memory: 8300kb

input:

2000 2000 2000
1730 1659
1646 1730
1646 374
374 432
1579 432
1579 1327
1327 662
1287 662
613 1287
762 613
762 1166
521 1166
1945 521
1945 626
626 1390
1390 1261
577 1261
577 19
19 773
1958 773
1017 1958
1624 1017
1624 671
1218 671
1622 1218
1622 604
1220 604
1220 1396
1306 1396
1306 1746
1746 67
195...

output:

1468 1973 1014 1958 1987 1978 1843 1988 1947 1975 1924 1917 1941 1972 1100 1957 1979 1979 1966 1971 1978 1978 1899 1964 1981 1959 1957 1983 1975 1959 1956 1852 1909 1893 1931 1740 1967 1971 1913 1978 1924 1795 1965 1987 1890 1884 1985 1905 1943 1940 1977 1981 1959 1979 1986 1968 1942 1851 1986 1754 ...

result:

ok 2000 numbers

Test #44:

score: 5
Accepted
time: 4ms
memory: 8212kb

input:

2000 2000 2000
805 611
805 436
1789 436
126 1789
126 1758
1758 464
464 727
1163 727
1439 1163
1439 1115
1115 1621
1621 746
967 746
967 58
58 1258
1481 1258
1481 74
1302 74
1302 1999
1999 442
442 1418
1418 987
602 987
602 705
705 1109
1019 1109
434 1019
124 434
124 1365
811 1365
782 811
1381 782
505 ...

output:

1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 1988 ...

result:

ok 2000 numbers

Test #45:

score: 5
Accepted
time: 4ms
memory: 8280kb

input:

2000 2000 2000
741 677
677 96
1467 96
480 96
1118 480
988 1118
1197 988
514 1197
514 706
217 706
217 416
416 708
1134 708
244 1134
244 327
1668 327
7 1668
7 1424
1424 221
221 1280
1999 1280
1125 1999
1125 492
492 1371
1371 1748
1748 1715
437 1715
996 437
1289 996
417 1289
417 228
1753 228
1753 325
4...

output:

1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 1987 ...

result:

ok 2000 numbers

Test #46:

score: 5
Accepted
time: 4ms
memory: 10440kb

input:

2000 2000 2000
1187 524
1187 43
154 43
522 154
569 522
569 767
384 767
384 115
115 1948
1948 536
960 536
960 763
763 1237
243 1237
1725 243
1725 326
326 508
787 508
291 787
291 1674
242 1674
242 953
1074 953
1074 621
621 1739
1739 1257
1257 1655
1603 1655
1574 1603
1574 1621
1399 1621
1399 717
1191 ...

output:

1980 1980 1981 1980 1980 1981 1980 1980 1980 1980 1980 1981 1980 1980 1980 1980 1980 1980 1980 1981 1980 1980 1980 1981 1980 1980 1980 1980 1980 1980 1980 1980 1981 1981 1980 1980 1980 1980 1980 1980 1980 1980 1980 1980 1980 1980 1980 1981 1981 1980 1980 1981 1980 1980 1980 1980 1980 1980 1980 1981 ...

result:

ok 2000 numbers

Test #47:

score: 5
Accepted
time: 13ms
memory: 10280kb

input:

2000 2000 2000
152 1328
1135 1328
1335 1328
438 1328
1328 1123
1846 1328
1328 381
1328 760
1328 649
1355 1328
1328 712
1298 1328
107 1328
1328 191
7 1328
1328 9
1536 1328
1328 1664
1328 1456
1328 815
1229 1328
1328 915
1328 1946
1328 1825
1662 1328
1343 1328
1328 187
214 1328
399 1328
803 1328
1328 ...

output:

661 790 238 896 264 822 139 74 1206 240 852 71 368 500 21 129 572 1 177 471 209 1092 1228 435 726 435 221 635 115 339 724 158 1217 74 490 199 539 356 711 228 197 1080 893 313 690 897 159 324 63 1222 1077 1137 143 540 508 1111 1040 45 308 541 692 490 532 987 151 484 227 502 643 617 335 776 75 411 629...

result:

ok 2000 numbers

Test #48:

score: 5
Accepted
time: 11ms
memory: 10396kb

input:

2000 2000 2000
406 160
1111 160
160 1599
436 160
160 1169
1548 160
395 160
160 1434
11 160
160 1407
160 425
1990 160
1757 160
732 160
160 1078
160 66
160 162
160 1544
160 1940
993 160
160 606
160 98
1496 160
160 716
160 1092
160 1395
920 160
531 160
884 160
160 680
160 1747
1658 160
160 1705
40 160
...

output:

521 443 419 1003 320 344 752 519 729 458 639 808 133 84 926 1006 92 279 265 57 604 941 813 719 26 86 154 1108 277 762 206 922 353 977 345 298 35 749 804 1135 634 447 269 157 1163 650 209 458 799 294 560 211 1031 954 573 57 116 1157 696 528 156 192 496 671 98 920 762 163 634 882 554 930 978 323 883 8...

result:

ok 2000 numbers

Test #49:

score: 5
Accepted
time: 11ms
memory: 8328kb

input:

2000 2000 2000
1460 594
1854 594
1462 594
1973 594
1763 594
1125 594
594 1463
594 88
594 737
594 901
594 1837
594 236
1170 594
594 1738
594 1518
1129 594
779 594
594 714
594 1145
594 843
1665 594
269 594
594 1022
594 1959
594 1237
504 594
1851 594
1827 594
1132 594
594 1966
9 594
140 594
594 260
984...

output:

746 490 413 921 47 534 440 714 695 191 403 1005 108 122 1078 110 869 86 818 879 156 462 552 794 554 529 122 156 1063 1059 242 1108 715 451 178 56 813 486 218 36 420 558 529 1079 431 16 709 142 648 454 119 164 286 703 988 188 378 799 932 126 599 129 935 362 359 1020 176 523 410 153 553 1079 428 269 4...

result:

ok 2000 numbers

Test #50:

score: 5
Accepted
time: 11ms
memory: 12344kb

input:

2000 2000 2000
1856 387
1063 387
1932 387
295 387
96 387
387 1334
1651 387
1872 387
387 61
387 1639
387 1523
387 1292
948 387
387 1606
1875 387
1779 387
1670 387
667 387
699 387
387 309
387 1041
387 879
387 918
1285 387
387 539
1540 387
387 1050
387 16
671 387
1962 387
853 387
387 1745
387 768
409 3...

output:

174 998 656 545 59 429 333 802 144 1178 547 564 1019 299 141 961 1061 390 365 405 903 835 645 147 616 517 574 694 385 868 43 114 936 567 709 534 786 832 334 680 775 849 932 599 404 174 710 952 352 372 589 632 421 634 108 82 342 375 290 227 628 574 842 255 416 185 630 994 113 178 922 779 832 811 936 ...

result:

ok 2000 numbers

Test #51:

score: 5
Accepted
time: 7ms
memory: 8248kb

input:

2000 2000 2000
1743 425
425 1015
425 1426
599 425
1226 425
425 1448
425 1441
425 111
425 1833
49 425
425 1190
425 1285
1007 425
1949 425
1424 425
160 425
425 1941
425 82
357 425
974 425
425 52
1967 425
180 425
425 53
451 425
1942 425
425 89
1427 425
425 1804
1249 425
425 433
343 425
410 425
662 425
...

output:

343 821 759 477 372 51 468 825 695 412 583 65 317 299 389 1124 921 954 106 525 79 782 632 672 733 143 38 1253 693 866 1010 484 910 111 609 736 759 533 354 882 97 223 368 1198 630 488 666 207 101 514 774 182 163 349 1018 138 891 686 686 501 642 997 112 986 959 466 1206 133 407 246 890 233 566 370 103...

result:

ok 2000 numbers

Test #52:

score: 5
Accepted
time: 11ms
memory: 8260kb

input:

2000 2000 2000
1222 764
1236 764
764 905
764 161
764 245
764 1051
1375 764
764 580
764 506
340 764
1846 764
909 764
764 117
32 764
220 764
1704 764
764 1815
764 872
764 1981
1763 764
764 1032
944 764
628 764
764 1570
764 1784
764 1447
764 1808
1013 764
764 147
764 177
764 1397
1297 764
137 764
764 1...

output:

506 870 1095 748 880 627 274 1059 25 19 16 74 168 540 666 977 123 267 613 420 402 878 1007 1007 587 176 1003 544 245 950 310 426 1054 103 526 898 994 536 784 993 992 663 673 899 1000 234 592 305 101 654 432 851 739 335 488 925 504 614 200 709 264 31 326 605 696 631 794 788 344 596 640 1226 85 548 69...

result:

ok 2000 numbers

Test #53:

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

input:

1 2000 2000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 2000 numbers

Test #54:

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

input:

2000 1 2000
1831 109
303 1831
303 203
1531 303
883 1831
372 1831
1583 883
1757 109
429 1583
636 883
372 1365
303 1579
1531 1069
1831 139
1764 1757
1831 98
1177 1579
861 303
1757 1442
889 372
372 843
1757 873
873 1439
1764 1276
203 212
1276 1421
1069 1939
372 1192
1032 636
1569 139
590 1421
73 873
13...

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

Test #55:

score: 5
Accepted
time: 13ms
memory: 6252kb

input:

2000 2000 2000
380 12
380 842
380 1917
412 12
542 12
245 12
842 1941
1941 1987
1941 1458
378 542
245 1136
1987 704
289 1136
1833 542
704 865
865 1746
701 12
1652 12
412 702
922 1746
1440 702
420 542
1941 121
1652 876
245 1831
484 1917
1917 36
36 843
1652 1389
704 324
1097 1652
1178 412
344 1746
158 ...

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

Subtask #3:

score: 7
Accepted

Test #56:

score: 7
Accepted
time: 902ms
memory: 31344kb

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

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

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

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

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

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

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

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

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

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

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: 7
Accepted
time: 88ms
memory: 47328kb

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:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 #68:

score: 7
Accepted
time: 1670ms
memory: 47064kb

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:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 #4:

score: 18
Accepted

Test #69:

score: 18
Accepted
time: 306ms
memory: 23884kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 41
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #112:

score: 41
Accepted
time: 1462ms
memory: 38792kb

input:

99726 83659 98720
35409 46212
46212 13607
35409 76586
76586 14796
26092 46212
9570 14796
37237 46212
15640 35409
54094 46212
34233 46212
37237 31484
15640 98259
37663 98259
37237 18087
53260 26092
46212 68082
35158 37237
25012 31484
54094 1967
95905 76586
98975 76586
7844 46212
68082 36739
46212 555...

output:

71144 39055 45589 48195 49275 10699 68037 21400 51608 46453 45912 55624 18913 41238 26472 24232 66675 53912 31900 21482 45079 47828 64056 50093 27731 31279 57331 32134 16603 35777 46477 64234 65032 68658 32248 12636 45515 18268 3548 66019 57809 39262 7194 52845 53437 47233 53397 47271 51142 67050 25...

result:

ok 98720 numbers

Test #113:

score: 41
Accepted
time: 924ms
memory: 39288kb

input:

97247 63699 56063
17229 14270
17229 31696
69389 31696
32140 31696
17229 57391
57381 14270
32066 57391
32066 57281
32066 1132
44926 32140
57281 66370
57281 37016
54366 57391
30946 66370
17229 78978
31696 12992
57381 15583
15583 15933
5779 12992
27110 57391
69389 47751
78978 45124
57281 9767
3069 6637...

output:

15401 14743 17259 14445 5475 42002 29183 32293 33564 53616 37324 43906 34587 14374 20023 50532 47412 29916 22049 12709 21153 39943 14916 12194 9519 23490 42482 47294 18240 36403 24383 42564 29785 49183 29374 48809 47314 53028 19661 60918 36195 61323 43002 6287 37628 38090 8315 10437 15514 56122 2166...

result:

ok 56063 numbers

Test #114:

score: 41
Accepted
time: 1742ms
memory: 38808kb

input:

100000 100000 100000
77258 40515
40515 60247
60247 99703
95513 77258
60247 46357
77258 15031
46357 54586
45839 60247
61293 45839
68382 15031
46357 90329
68502 54586
54586 40128
55318 61293
15031 51135
51135 52053
21974 40128
40515 68073
21504 60247
46357 95427
45645 21504
90329 3479
55318 70055
9970...

output:

68680 47620 37782 53837 4447 18881 7506 28427 27932 32264 57799 58306 46508 31465 33295 67648 63458 58527 44360 60452 20114 9340 68963 37857 37408 40886 51595 69979 28647 74222 65230 45787 71744 35427 70058 62250 24412 56024 58324 53416 29671 55357 51581 42730 43045 41099 13339 33308 21475 64147 284...

result:

ok 100000 numbers

Test #115:

score: 41
Accepted
time: 1738ms
memory: 39048kb

input:

100000 100000 100000
84494 45784
45784 30291
30291 23587
30291 50535
39673 45784
39673 9651
55789 39673
27134 30291
54438 50535
23587 55463
40630 54438
17397 45784
39673 17930
17397 91353
98444 17397
43370 55789
98444 21734
3931 9651
45784 43872
82532 91353
11942 82532
40630 21553
96687 39673
2432 4...

output:

57009 72014 75712 14852 69411 62128 51684 48568 56566 33315 72558 76515 29994 68135 47558 75590 19551 57719 68975 42222 20533 64480 45276 65976 63993 11701 54716 6164 73289 78120 24321 61810 37066 51534 46918 21181 53856 12145 31759 29887 46592 27931 49782 58937 71429 32543 26149 60855 75517 5822 20...

result:

ok 100000 numbers

Test #116:

score: 41
Accepted
time: 1756ms
memory: 38852kb

input:

100000 100000 100000
69874 45124
69874 89131
9996 45124
69874 66316
89131 69301
66316 7997
9996 17755
7997 4272
32800 69874
17755 15731
56525 17755
45124 48949
89131 67689
7997 56769
89608 32800
90947 56769
66316 83215
20742 32800
65366 17755
20742 9083
37961 15731
86032 89131
44185 67689
94233 6930...

output:

9598 50938 32756 53960 21171 45940 55745 75158 50056 14751 52888 42531 48748 24617 55005 46652 29856 23727 11030 49423 38186 63964 76699 41821 44182 53045 45166 53633 12205 32955 16769 76229 70812 41349 44487 64388 64060 32835 49882 65795 44442 15682 11718 12707 68412 12221 48340 20923 34088 9974 15...

result:

ok 100000 numbers

Test #117:

score: 41
Accepted
time: 1693ms
memory: 38796kb

input:

100000 100000 100000
47614 15929
83612 47614
46763 47614
15929 18155
40165 47614
59488 47614
40165 45408
35403 46763
72603 45408
45408 13870
40165 58978
15597 47614
69540 47614
83612 42396
77532 46763
47614 17323
56182 13870
15597 34769
56182 63224
12530 15597
11247 46763
32646 18155
13870 10912
605...

output:

47299 60319 33937 54600 46029 47035 69202 62777 53477 15455 35912 27218 20041 49503 64977 42710 23800 59120 62205 57428 69103 23897 44578 45933 56538 51862 64070 55362 62847 53401 62016 67239 58164 47420 30576 58337 32888 45843 11849 34938 58991 65842 43781 36874 42236 52718 71117 33254 55026 27733 ...

result:

ok 100000 numbers

Test #118:

score: 41
Accepted
time: 1740ms
memory: 39036kb

input:

100000 100000 100000
60366 84436
81992 84436
84436 9094
14795 81992
9094 28704
21334 81992
21334 64412
9094 85943
81992 94163
94163 49815
93555 21334
69786 93555
53483 21334
85274 14795
9094 43631
42669 21334
85274 49974
10546 14795
28704 15674
88431 15674
88431 56983
98663 43631
21334 15451
43631 4...

output:

47183 42807 1856 65961 39556 50248 46528 24086 49057 44323 46969 68875 13262 16948 63239 57148 16152 37483 53692 32986 53039 40452 13505 45011 56730 43220 36314 44326 39656 30148 26529 45185 52134 45187 27553 57929 63586 46337 31429 39448 64463 925 44618 19933 69859 68390 58405 48123 53282 6441 2341...

result:

ok 100000 numbers

Test #119:

score: 41
Accepted
time: 1631ms
memory: 46000kb

input:

100000 100000 100000
18512 58863
41081 58863
41081 48239
23696 48239
23696 18980
34146 18980
78572 34146
99884 78572
15798 99884
59590 15798
59590 99335
99335 17167
28376 17167
73315 28376
86787 73315
86787 10893
66037 10893
50484 66037
63839 50484
15690 63839
15690 89895
94709 89895
32055 94709
320...

output:

99994 99996 99987 99989 99977 99994 99996 99968 99996 99993 99965 99977 99994 99995 99996 99959 99994 99996 99994 99993 99994 99996 99994 99996 99972 99993 99996 99989 99996 99994 99994 99972 99993 99991 99993 99967 99996 99994 99968 99995 99993 98822 99993 99977 99988 99996 99993 99994 99971 99935 ...

result:

ok 100000 numbers

Test #120:

score: 41
Accepted
time: 1684ms
memory: 47280kb

input:

100000 100000 100000
42632 61070
38720 42632
38720 95179
95179 25272
25272 89037
93245 89037
93245 93614
81848 93614
2475 81848
2475 7605
7605 18538
6251 18538
20169 6251
97426 20169
95796 97426
42615 95796
81515 42615
81515 78374
78374 8362
33024 8362
74741 33024
74741 97524
97524 35905
35905 85781...

output:

99998 99992 99977 99982 99977 99825 99988 99998 99937 99981 99972 99988 100000 100000 99988 99988 99995 99977 99988 100000 99998 99975 99977 99982 100000 99989 99988 99956 99982 100000 100000 99977 99656 99982 100000 99988 99988 99988 99988 100000 99988 99998 100000 99948 99982 99988 99976 99949 100...

result:

ok 100000 numbers

Test #121:

score: 41
Accepted
time: 1660ms
memory: 42680kb

input:

100000 100000 100000
55815 4911
55063 55815
72408 55063
72408 54311
54311 65433
65433 64345
69194 64345
69718 69194
81132 69718
61787 81132
61787 20369
20369 58117
58117 42320
42320 61406
37792 61406
52793 37792
52793 20906
20906 90565
90565 53972
8535 53972
33584 8535
10528 33584
10528 458
37649 45...

output:

99995 99932 99998 99995 99995 99994 99994 99991 99998 99998 99998 99998 99994 99998 99995 99998 99998 99996 99998 99995 99995 99995 99986 99998 99998 99995 99992 99984 99984 99954 99995 99994 99995 99985 99989 99945 99998 99998 99993 99990 99995 99995 99920 99995 99998 99961 99998 99995 99993 99998 ...

result:

ok 100000 numbers

Test #122:

score: 41
Accepted
time: 1638ms
memory: 38740kb

input:

100000 100000 100000
9625 63608
64015 63608
64015 12938
12938 24718
96658 24718
76774 96658
76774 34450
34450 31685
31685 23761
41553 23761
26410 41553
26410 71695
71695 78175
78175 19784
19784 52762
12619 52762
12619 11638
12294 11638
12294 26806
26806 4027
91018 4027
14590 91018
69059 14590
54345 ...

output:

92130 83115 98221 99192 94870 86070 95681 90014 98083 89128 98894 87811 92155 98414 70519 95720 96823 94485 82079 95398 98301 96801 85420 97858 80684 68644 97325 98514 93259 95752 90980 98284 95135 79038 96281 96504 97671 92804 99289 94472 99161 93549 97778 82449 97574 97850 75547 87901 97669 95587 ...

result:

ok 100000 numbers

Test #123:

score: 41
Accepted
time: 1691ms
memory: 38604kb

input:

100000 100000 100000
73184 20305
20305 2873
72885 2873
72885 51681
76782 51681
81175 76782
81175 77637
77637 76066
76066 75970
75970 75740
75740 72938
62254 72938
66437 62254
45519 66437
45519 72167
72167 25327
46581 25327
46581 75183
75183 12413
93023 12413
57852 93023
57852 24067
40194 24067
40194...

output:

98407 95555 98777 96384 89997 97157 98746 99170 98453 97729 99183 97464 95205 93306 96651 91568 98636 94435 97815 98378 99084 94795 98633 96646 91536 88755 97867 96308 96893 96267 87800 96744 98601 96894 98816 99336 96612 98457 93518 94789 98803 87652 99073 91841 98171 98844 94744 98152 99094 90995 ...

result:

ok 100000 numbers

Test #124:

score: 41
Accepted
time: 1687ms
memory: 38784kb

input:

100000 100000 100000
77541 26497
45507 77541
45507 51472
71984 51472
97049 71984
93846 97049
59870 93846
49079 59870
26790 49079
36702 26790
36702 37219
37219 13487
13487 63837
63837 39301
19985 39301
19985 24829
24829 7759
7759 78468
78468 29011
9959 29011
65744 9959
65744 41567
37535 41567
37535 1...

output:

94721 97228 53417 96838 98280 99261 99310 96888 97951 28608 98437 99050 98062 71314 99128 98744 98772 99179 99219 95108 91798 96150 91323 98593 96741 94513 98756 93219 98451 98369 97296 69330 78611 97827 95088 99142 92534 99116 99069 95549 93485 98874 93155 98745 95611 98171 97238 95897 93736 99244 ...

result:

ok 100000 numbers

Test #125:

score: 41
Accepted
time: 1648ms
memory: 39260kb

input:

100000 100000 100000
78136 92487
49022 92487
17525 92487
47606 92487
92487 50440
92487 84699
76972 92487
50805 92487
59387 92487
92487 90411
92487 2670
71648 92487
92487 27036
92487 76150
91300 92487
92487 60373
37411 92487
44242 92487
6965 92487
90892 92487
92487 24
60223 92487
92487 20373
92487 68...

output:

44195 32411 31158 12333 28307 34474 42616 32142 32917 33142 44985 17425 24438 15855 29000 10292 2021 15990 27269 25864 48750 28443 11829 40715 41074 39280 34735 46549 22077 32701 40152 18933 10744 49534 59630 43468 2155 27276 327 13956 38137 5446 2288 5217 40189 41834 25313 39418 50577 19891 29098 9...

result:

ok 100000 numbers

Test #126:

score: 41
Accepted
time: 1635ms
memory: 40992kb

input:

100000 100000 100000
67273 57476
67273 18451
57814 67273
67273 40302
67273 3567
67273 93287
61759 67273
62651 67273
67273 39565
67273 27342
64237 67273
6267 67273
67273 29593
41568 67273
8003 67273
67273 13982
12056 67273
53857 67273
67273 4481
40425 67273
67273 47794
3403 67273
67273 88266
66240 67...

output:

1451 11653 27954 22957 19990 46809 24800 8713 1420 44482 21227 48180 954 10743 18797 50365 12603 14041 7760 11871 21412 8456 5931 27943 32321 1469 55739 21109 11333 8474 53874 25501 28350 30971 13106 28694 9913 55367 13750 14751 25893 20862 22829 11931 53318 24805 17631 26442 6257 26087 32725 20955 ...

result:

ok 100000 numbers

Test #127:

score: 41
Accepted
time: 1682ms
memory: 39168kb

input:

100000 100000 100000
40907 78616
33670 78616
7204 78616
76543 78616
55686 78616
67221 78616
76775 78616
8761 78616
78616 85782
76899 78616
78616 14801
78616 66531
4246 78616
78616 62138
78616 97821
78616 99403
80479 78616
44881 78616
78616 36950
78616 93382
56264 78616
64556 78616
8534 78616
69507 7...

output:

18609 36759 4522 34859 36613 1830 33326 12029 8901 24335 18400 45779 42616 28497 60598 29199 13677 33533 10865 16337 49912 6047 61090 14371 19944 26404 52198 10925 10073 2729 50567 15635 55481 14569 30481 7881 33779 8364 4607 38307 1536 34094 51458 10871 2078 22599 19585 29760 39399 38238 5868 17116...

result:

ok 100000 numbers

Test #128:

score: 41
Accepted
time: 1647ms
memory: 41172kb

input:

100000 100000 100000
57745 67264
8994 67264
67264 15128
67264 30794
67264 5442
25002 67264
86359 67264
67264 10859
44377 67264
67264 2990
92161 67264
64850 67264
67264 1002
48978 67264
67264 5982
9794 67264
79703 67264
67264 66165
67264 74442
67264 84474
67264 58736
67264 37864
45787 67264
97968 672...

output:

48016 20375 12066 138 28555 4734 7659 13830 28241 38924 57353 276 11933 7331 33886 41337 30941 10315 14689 48548 13097 57214 29739 6728 38800 39989 4581 24323 21449 47772 17518 6273 8297 30852 25410 13254 2349 19361 56994 56450 25657 30960 42822 47416 30815 49292 38828 22545 6592 37609 15364 27369 3...

result:

ok 100000 numbers

Test #129:

score: 41
Accepted
time: 1630ms
memory: 39236kb

input:

100000 100000 100000
59246 93808
15498 59246
59246 51357
4512 59246
35330 59246
93808 84179
59246 82830
81717 59246
95378 59246
59246 64891
59246 17058
85384 59246
99993 59246
45465 59246
72341 59246
57279 59246
59246 50763
7018 59246
54615 59246
99937 59246
59246 33937
78836 59246
31890 59246
91473...

output:

27938 38929 29146 24021 8999 8356 4550 6614 32850 10669 26092 16342 4880 4540 48729 36114 35797 52592 32005 46213 10427 8213 52947 25158 25013 34926 39309 18466 11199 12078 12923 25613 46253 14373 46081 17384 44976 2828 35364 21497 20500 8942 45480 37199 30765 38919 17855 40021 25057 464 16745 38662...

result:

ok 100000 numbers

Test #130:

score: 41
Accepted
time: 1678ms
memory: 38976kb

input:

100000 100000 100000
13497 62722
13497 5161
13497 617
13497 25686
44939 13497
42238 13497
13497 63052
13497 84867
68543 13497
13497 93658
91378 13497
79735 13497
13497 69674
13497 16746
13497 65225
13497 58963
60841 13497
13497 69936
13497 90235
45836 13497
13497 51305
25797 13497
13497 59388
60317 ...

output:

22546 27882 34448 33894 44886 37018 17239 5747 30526 29016 46314 35501 12397 45772 30855 19123 32068 39251 40926 17309 22017 45222 6766 15638 33884 45760 4244 5466 22147 35348 40452 14717 32108 13170 24324 6263 39477 14822 43203 4441 22049 31308 44211 9016 55625 27807 5235 3545 6087 24699 15068 2794...

result:

ok 100000 numbers

Test #131:

score: 41
Accepted
time: 195ms
memory: 11672kb

input:

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

Test #132:

score: 41
Accepted
time: 89ms
memory: 38716kb

input:

100000 1 100000
68037 82621
68037 91945
42841 82621
42841 20630
52413 68037
91945 30472
69626 20630
31887 91945
21628 42841
42981 21628
68037 17150
42841 71467
20630 71837
20630 46285
20703 31887
84753 21628
33034 20630
71837 81435
20630 76919
94145 84753
94116 71837
30081 82621
84860 20703
52416 84...

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 #133:

score: 41
Accepted
time: 1848ms
memory: 40596kb

input:

100000 100000 100000
88171 78337
78337 79628
88171 69396
69396 49284
78337 77194
85739 77194
69735 77194
77194 19806
19806 69879
69396 35439
4518 69735
69396 5748
69735 89365
5748 60288
29612 88171
19806 94740
69879 9168
95817 79628
9168 54577
93361 4518
7162 49284
69879 9944
19247 35439
71686 85739...

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

Extra Test:

score: 0
Extra Test Passed