QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#945039#7443. vtizltAC ✓524ms179004kbC++146.7kb2025-03-20 18:46:142025-03-20 18:46:20

Judging History

This is the latest submission verdict.

  • [2025-03-20 18:46:20]
  • Judged
  • Verdict: AC
  • Time: 524ms
  • Memory: 179004kb
  • [2025-03-20 18:46:14]
  • Submitted

answer

// Problem: P8205 [Ynoi2005] vti
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8205
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
	const int maxn = 1 << 20;
	
    char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 2000100;
const int logn = 20;

int n, m, a[maxn], dfn[maxn], tim, st[logn][maxn / 20];
ll ans[maxn];

inline int get(int i, int j) {
	return dfn[i] < dfn[j] ? i : j;
}

inline int qlca(int x, int y) {
	if (x == y) {
		return x;
	}
	x = dfn[x];
	y = dfn[y];
	if (x > y) {
		swap(x, y);
	}
	++x;
	int k = __lg(y - x + 1);
	return get(st[k][x], st[k][y - (1 << k) + 1]);
}

struct graph {
	int hd[maxn], len, to[maxn], nxt[maxn];
	
	inline void add_edge(int u, int v) {
		to[++len] = v;
		nxt[len] = hd[u];
		hd[u] = len;
	}
} G;

int tot, in[maxn];
pii ord[maxn];

void dfs(int u, int t) {
	dfn[u] = ++tim;
	st[0][tim] = t;
	if (u > 1) {
		ord[++tot] = mkp(a[u], 1);
		in[u] = tot;
	}
	for (int i = G.hd[u]; i; i = G.nxt[i]) {
		int v = G.to[i];
		if (v == t) {
			continue;
		}
		dfs(v, u);
	}
	if (u > 1) {
		ord[++tot] = mkp(a[u], -1);
	}
}

int b[maxn], K, c[maxn], tq, bel[maxn], blo;

struct que {
	int l, r, o, i;
	ll ans;
	que(int a = 0, int b = 0, int c = 0, int d = 0, ll e = 0) : l(a), r(b), o(c), i(d), ans(e) {}
} qq[maxn];

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
}

ll f[maxn], g[maxn];

struct line {
	int l, r, o, i;
	line(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), o(c), i(d) {}
};

struct List {
	int hd[maxn], len, nxt[maxn];
	line to[maxn];
	
	inline void add(int x, line y) {
		to[++len] = y;
		nxt[len] = hd[x];
		hd[x] = len;
	}
} L1, L2;

namespace DS {
	int bel[maxn], blo, L[maxn], R[maxn], a[maxn], b[maxn];
	
	inline void init() {
		blo = sqrt(n);
		for (int i = 1; i <= n; ++i) {
			bel[i] = (i - 1) / blo + 1;
			if (!L[bel[i]]) {
				L[bel[i]] = i;
			}
			R[bel[i]] = i;
		}
	}
	
	inline void update(int x, int y) {
		for (int i = x; i <= R[bel[x]]; ++i) {
			a[i] += y;
		}
		for (int i = bel[x] + 1; i <= bel[n]; ++i) {
			b[i] += y;
		}
	}
	
	inline int query(int x) {
		return a[x] + b[bel[x]];
	}
}

void solve() {
	n = read();
	for (int i = 2; i <= n; ++i) {
		int p = read();
		a[i] = read();
		G.add_edge(p, i);
	}
	dfs(1, 0);
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	m = read();
	for (int i = 1; i <= m; ++i) {
		K = read();
		for (int j = 1; j <= K; ++j) {
			b[j] = read();
		}
		if (K == 1) {
			continue;
		}
		sort(b + 1, b + K + 1, [&](const int &x, const int &y) {
			return dfn[x] < dfn[y];
		});
		int t = K;
		for (int j = 1; j < t; ++j) {
			b[++K] = qlca(b[j], b[j + 1]);
		}
		sort(b + 1, b + K + 1, [&](const int &x, const int &y) {
			return dfn[x] < dfn[y];
		});
		K = unique(b + 1, b + K + 1) - b - 1;
		for (int j = 1; j <= K; ++j) {
			c[b[j]] = 0;
		}
		for (int j = 1; j < K; ++j) {
			int u = qlca(b[j], b[j + 1]);
			++c[u];
		}
		for (int j = 2; j <= K; ++j) {
			qq[++tq] = que(in[b[1]] + 1, in[b[j]], 1 - c[b[j]], i);
		}
	}
	blo = ceil(tot / sqrt(tq));
	for (int i = 1; i <= tot; ++i) {
		bel[i] = (i - 1) / blo + 1;
	}
	sort(qq + 1, qq + tq + 1, [&](const que &a, const que &b) {
		if (bel[a.l] != bel[b.l]) {
			return bel[a.l] < bel[b.l];
		} else if (bel[a.l] & 1) {
			return a.r < b.r; 
		} else {
			return a.r > b.r;
		}
	});
	int s = 0;
	for (int i = 1; i <= tot; ++i) {
		f[i] = f[i - 1] + BIT::query(ord[i].fst - 1) * ord[i].scd;
		g[i] = g[i - 1] + (s - BIT::query(ord[i].fst)) * ord[i].scd;
		BIT::update(ord[i].fst, ord[i].scd);
		s += ord[i].scd;
	}
	int l = 1, r = 0;
	for (int i = 1; i <= tq; ++i) {
		int ql = qq[i].l, qr = qq[i].r;
		if (l > ql) {
			qq[i].ans -= g[l - 1] - g[ql - 1];
			L2.add(r, line(ql, l - 1, 1, i));
			l = ql;
		}
		if (r < qr) {
			qq[i].ans += f[qr] - f[r];
			L1.add(l - 1, line(r + 1, qr, -1, i));
			r = qr;
		}
		if (l < ql) {
			qq[i].ans += g[ql - 1] - g[l - 1];
			L2.add(r, line(l, ql - 1, -1, i));
			l = ql;
		}
		if (r > qr) {
			qq[i].ans -= f[r] - f[qr];
			L1.add(l - 1, line(qr + 1, r, 1, i));
			r = qr;
		}
	}
	DS::init();
	s = 0;
	for (int i = 1; i <= tot; ++i) {
		DS::update(ord[i].fst, ord[i].scd);
		s += ord[i].scd;
		for (int _ = L1.hd[i]; _; _ = L1.nxt[_]) {
			line u = L1.to[_];
			for (int j = u.l; j <= u.r; ++j) {
				qq[u.i].ans += u.o * ord[j].scd * DS::query(ord[j].fst - 1);
			}
		}
		for (int _ = L2.hd[i]; _; _ = L2.nxt[_]) {
			line u = L2.to[_];
			for (int j = u.l; j <= u.r; ++j) {
				qq[u.i].ans += u.o * ord[j].scd * (s - DS::query(ord[j].fst));
			}
		}
	}
	for (int i = 1; i <= tq; ++i) {
		qq[i].ans += qq[i - 1].ans;
		ans[qq[i].i] += qq[i].ans * qq[i].o;
	}
	for (int i = 1; i <= m; ++i) {
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 64ms
memory: 159344kb

input:

100000
1 19270
2 16523
3 72807
3 48950
2 41661
2 74623
2 11727
6 13478
1 40534
1 20287
5 22016
7 56368
3 55726
7 38294
14 77270
16 34784
9 81185
8 47123
3 44430
17 27172
20 87246
13 65
10 17478
3 10313
25 28816
12 76911
25 52410
8 71803
1 57285
12 8264
3 92423
17 49511
9 5194
5 85403
6 43755
2 66620...

output:

23008
21632
15760
21770
23886
20526
18436
19302
24195
16780
16056
17013
20558
15483
25016
16175
20203
15728
17132
19926
21240
23774
16018
25231
24829
19085
16020
24923
17060
16607
18537
23509
14832
22176
25325
25419
15509
17850
23361
27148
19474
24186
21217
24400
22926
19315
19724
26624
19179
23353
...

result:

ok 100 numbers

Test #2:

score: 0
Accepted
time: 160ms
memory: 163232kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 666646 numbers

Test #3:

score: 0
Accepted
time: 281ms
memory: 163524kb

input:

100000
1 1
2 1
1 1
3 1
1 1
1 1
6 1
6 1
9 1
5 1
8 1
5 1
13 1
8 1
10 1
8 1
3 1
16 1
13 1
17 1
9 1
8 1
13 1
17 1
23 1
5 1
21 1
5 1
9 1
20 1
12 1
25 1
24 1
23 1
13 1
7 1
18 1
3 1
10 1
16 1
31 1
21 1
42 1
20 1
35 1
20 1
17 1
6 1
6 1
9 1
46 1
16 1
19 1
15 1
2 1
10 1
24 1
13 1
9 1
47 1
17 1
20 1
44 1
13 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 9980 numbers

Test #4:

score: 0
Accepted
time: 225ms
memory: 167296kb

input:

100000
1 3
2 13
2 9
1 2
5 15
3 4
7 8
2 2
4 9
7 2
4 5
2 9
8 12
2 9
7 16
1 4
1 3
15 14
6 18
17 15
11 4
21 11
14 1
3 4
25 11
20 19
8 9
7 7
27 7
3 17
18 19
32 2
22 7
3 4
6 1
36 14
8 5
22 3
16 11
23 15
8 19
37 10
37 14
32 3
32 7
20 6
1 12
41 18
44 13
29 11
12 17
19 10
41 13
6 8
9 10
54 19
54 15
58 2
54 1...

output:

52
105
35
95
100
47
77
111
144
151
74
51
58
143
112
113
161
89
88
110
244
67
97
125
68
43
97
78
29
152
158
34
92
103
101
121
154
87
102
117
124
28
141
101
105
93
63
170
40
43
149
102
117
75
109
94
45
199
122
45
81
40
49
155
145
154
89
60
39
37
71
45
103
114
83
83
156
46
53
85
116
165
130
18
139
104
...

result:

ok 333313 numbers

Test #5:

score: 0
Accepted
time: 255ms
memory: 162656kb

input:

100000
1 13
2 2
3 7
2 17
5 8
6 4
3 4
8 7
9 16
5 8
11 7
3 15
9 17
7 17
11 19
14 8
6 9
15 3
18 15
16 15
11 4
19 10
15 18
20 8
22 1
20 5
11 3
5 20
23 18
26 3
4 10
27 13
25 15
32 15
28 16
22 3
30 11
30 20
35 19
17 11
41 4
15 4
14 6
4 15
17 2
25 8
37 12
39 11
34 11
49 12
48 16
37 17
22 4
45 11
38 9
6 13
...

output:

433
388
436
221
338
487
183
512
479
288
418
271
262
346
219
346
195
394
333
272
327
378
256
231
251
388
405
329
231
254
316
260
388
379
379
239
256
206
390
266
214
373
290
251
344
294
495
263
325
458
218
423
250
420
312
330
456
347
370
370
313
462
209
448
216
509
340
391
302
373
543
373
293
271
250
...

result:

ok 99980 numbers

Test #6:

score: 0
Accepted
time: 287ms
memory: 161828kb

input:

100000
1 69991
1 48322
3 13632
2 1979
1 89732
3 56826
2 29944
6 36910
2 56723
7 6841
6 59234
4 37459
3 86631
2 6405
10 8149
16 92496
2 10486
1 59876
12 55941
12 23657
4 52020
11 24409
19 91944
1 21187
16 35800
23 50634
12 92785
27 41572
23 67861
24 7292
31 74903
7 17649
22 70432
7 83637
35 54926
12 ...

output:

19304
17321
12568
18139
19639
16916
15576
15425
19887
13415
13324
13611
16559
12331
20418
13337
16819
12899
14974
16545
18023
19463
12837
21021
19817
15891
12495
20174
13547
13607
15181
19128
12413
18031
20207
20809
12878
14524
18517
22017
15318
20558
16515
20259
18390
16518
16641
21820
14781
19134
...

result:

ok 980 numbers

Test #7:

score: 0
Accepted
time: 284ms
memory: 159208kb

input:

100000
1 19
2 20
3 6
2 4
5 5
5 9
2 12
8 3
6 15
9 14
3 3
4 13
11 16
3 4
8 5
16 14
17 5
4 16
2 18
5 12
18 5
21 11
15 12
12 8
12 3
17 18
3 10
9 10
11 18
19 15
24 15
18 4
12 17
8 1
12 4
15 18
12 6
29 15
20 13
11 6
35 10
3 16
2 3
41 16
41 9
21 15
1 7
30 14
26 18
28 3
4 15
25 9
11 8
33 7
6 15
5 1
15 17
15...

output:

1496
1907
2581
1620
1635
1893
2005
2281
2498
2796
2043
1796
1622
2173
2126
2250
2254
1814
2183
1730
2372
1652
2583
2716
2527
1810
2361
2834
1662
2099
1597
2145
2357
1737
1625
1464
2918
2353
2689
1678
1907
1860
1498
2750
1702
2825
1602
2507
1787
2791
2306
2707
1430
2247
1467
1924
2500
2102
1680
2276
...

result:

ok 9980 numbers

Test #8:

score: 0
Accepted
time: 306ms
memory: 157080kb

input:

100000
1 17
2 12
3 5
3 8
4 9
6 19
5 14
7 11
3 18
2 4
11 14
8 20
1 18
5 3
9 16
1 12
2 20
4 6
14 9
20 12
18 3
8 10
17 8
17 17
20 4
13 3
12 8
2 9
22 10
5 14
15 15
16 7
12 8
7 17
33 10
7 17
28 10
29 13
2 5
21 4
24 9
17 6
42 18
30 13
6 19
43 1
28 2
9 13
35 11
38 8
1 2
16 13
33 16
25 16
13 19
3 10
39 3
51...

output:

15553
18650
13721
16764
18775
13810
19901
15530
21370
13656
21946
19414
21346
22231
13450
21389
18715
20242
20544
13960
16664
13574
14690
19415
17130
19632
16047
20257
22731
16873
20956
20332
16698
19881
22550
18204
20979
12587
21192
22459
12789
18885
18286
13425
13902
20193
14191
18572
21901
19161
...

result:

ok 980 numbers

Test #9:

score: 0
Accepted
time: 231ms
memory: 168728kb

input:

100000
1 3
2 13
2 9
1 2
5 15
3 4
7 8
2 2
4 9
7 2
4 5
2 9
8 12
2 9
7 16
1 4
1 3
15 14
6 18
17 15
11 4
21 11
14 1
3 4
25 11
20 19
8 9
7 7
27 7
3 17
18 19
32 2
22 7
3 4
6 1
36 14
8 5
22 3
16 11
23 15
8 19
37 10
37 14
32 3
32 7
20 6
1 12
41 18
44 13
29 11
12 17
19 10
41 13
6 8
9 10
54 19
54 15
58 2
54 1...

output:

52
105
35
95
100
47
77
111
144
151
74
51
58
143
112
113
161
89
88
110
244
67
97
125
68
43
97
78
29
152
158
34
92
103
101
121
154
87
102
117
124
28
141
101
105
93
63
170
40
43
149
102
117
75
109
94
45
199
122
45
81
40
49
155
145
154
89
60
39
37
71
45
103
114
83
83
156
46
53
85
116
165
130
18
139
104
...

result:

ok 333313 numbers

Test #10:

score: 0
Accepted
time: 244ms
memory: 163780kb

input:

100000
1 244
2 394
3 280
2 484
4 320
2 22
7 491
1 79
4 16
9 486
11 87
12 195
2 421
10 499
2 403
4 343
4 103
7 21
18 41
2 386
12 48
10 2
9 255
15 12
11 376
7 199
13 116
24 274
1 117
20 461
11 375
25 166
15 72
22 97
12 283
9 452
18 316
19 255
37 58
35 377
19 285
11 109
27 146
37 10
20 166
28 484
16 26...

output:

308
304
339
432
394
284
298
352
409
395
299
257
259
277
449
339
217
343
368
440
292
287
307
124
498
414
300
169
187
465
235
448
327
340
321
304
459
393
424
253
199
179
277
157
206
249
237
374
316
399
180
220
297
381
288
229
381
262
176
391
336
437
225
503
390
192
303
309
508
262
481
293
270
323
404
...

result:

ok 99980 numbers

Test #11:

score: 0
Accepted
time: 122ms
memory: 163088kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 666646 numbers

Test #12:

score: 0
Accepted
time: 166ms
memory: 164664kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 199980 numbers

Test #13:

score: 0
Accepted
time: 135ms
memory: 164960kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499980 numbers

Test #14:

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

input:

100000
1 19270
2 16523
3 72807
3 48950
2 41661
2 74623
2 11727
6 13478
1 40534
1 20287
5 22016
7 56368
3 55726
7 38294
14 77270
16 34784
9 81185
8 47123
3 44430
17 27172
20 87246
13 65
10 17478
3 10313
25 28816
12 76911
25 52410
8 71803
1 57285
12 8264
3 92423
17 49511
9 5194
5 85403
6 43755
2 66620...

output:

23008
21632
15760
21770
23886
20526
18436
19302
24195
16780
16056
17013
20558
15483
25016
16175
20203
15728
17132
19926
21240
23774
16018
25231
24829
19085
16020
24923
17060
16607
18537
23509
14832
22176
25325
25419
15509
17850
23361
27148
19474
24186
21217
24400
22926
19315
19724
26624
19179
23353
...

result:

ok 100 numbers

Test #15:

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

input:

100000
1 238
1 192
2 239
2 161
3 224
4 367
7 297
8 76
6 198
2 239
6 118
12 214
7 359
3 142
11 168
15 450
14 90
1 372
15 324
7 443
4 59
7 483
6 83
9 296
15 119
4 287
7 141
21 175
10 459
19 430
1 451
12 493
32 105
6 387
17 288
20 351
27 420
21 422
35 499
34 362
14 59
19 37
39 149
14 206
36 218
18 231
...

output:

16804
18933
19714
21078
22498
21941
21801
18251
16701
17947
21291
18146
15613
15080
24105
14266
16735
20639
15809
21748
19354
15856
24650
19697
19126
15722
21657
14282
18228
16886
20127
22483
15362
16312
23323
13963
24327
16463
17137
17529
21773
20791
14277
20452
21832
14504
17829
24606
22043
20692
...

result:

ok 980 numbers

Test #16:

score: 0
Accepted
time: 248ms
memory: 162748kb

input:

100000
1 244
2 394
3 280
2 484
4 320
2 22
7 491
1 79
4 16
9 486
11 87
12 195
2 421
10 499
2 403
4 343
4 103
7 21
18 41
2 386
12 48
10 2
9 255
15 12
11 376
7 199
13 116
24 274
1 117
20 461
11 375
25 166
15 72
22 97
12 283
9 452
18 316
19 255
37 58
35 377
19 285
11 109
27 146
37 10
20 166
28 484
16 26...

output:

308
304
339
432
394
284
298
352
409
395
299
257
259
277
449
339
217
343
368
440
292
287
307
124
498
414
300
169
187
465
235
448
327
340
321
304
459
393
424
253
199
179
277
157
206
249
237
374
316
399
180
220
297
381
288
229
381
262
176
391
336
437
225
503
390
192
303
309
508
262
481
293
270
323
404
...

result:

ok 99980 numbers

Test #17:

score: 0
Accepted
time: 303ms
memory: 162348kb

input:

100000
1 356
1 441
1 196
1 245
1 842
4 616
7 867
1 318
7 861
1 626
9 198
5 433
4 491
4 284
4 842
9 450
10 425
7 395
14 860
19 478
18 867
19 204
3 9
23 154
3 998
20 507
7 166
23 900
4 328
5 335
21 241
3 704
8 766
24 491
3 621
12 20
16 245
26 925
24 736
36 772
31 96
33 722
34 376
24 653
36 423
40 614
...

output:

18312
19008
13321
16224
13801
16734
19718
22458
19099
13417
18155
21405
15404
18211
17973
20162
15971
18800
23316
20483
19229
15572
17874
18230
16296
16669
14703
19112
16584
14807
22443
19334
19674
17966
15415
20403
19874
19904
19054
21051
17005
22991
13710
20183
20780
17697
19120
14358
13023
17781
...

result:

ok 980 numbers

Test #18:

score: 0
Accepted
time: 233ms
memory: 161380kb

input:

100000
1 416
1 279
1 858
3 100
1 627
1 547
6 348
7 991
7 342
10 178
1 274
11 305
2 582
14 371
11 695
16 605
5 249
2 608
13 649
17 938
20 900
1 985
11 325
5 435
11 299
3 737
9 768
25 343
16 819
1 438
2 527
25 643
31 146
10 645
25 727
18 666
31 764
38 427
15 461
25 891
12 399
31 180
4 30
16 882
8 511
...

output:

413
401
305
269
194
136
250
430
398
271
299
217
347
365
288
118
230
423
368
285
308
150
270
254
243
294
358
435
338
382
229
288
208
285
156
277
436
228
450
151
246
350
363
309
303
285
164
277
279
351
217
237
210
295
319
267
377
252
231
277
283
222
277
176
343
287
254
359
339
185
375
206
162
224
266
...

result:

ok 99980 numbers

Test #19:

score: 0
Accepted
time: 303ms
memory: 162564kb

input:

100000
1 356
1 441
1 196
1 245
1 842
4 616
7 867
1 318
7 861
1 626
9 198
5 433
4 491
4 284
4 842
9 450
10 425
7 395
14 860
19 478
18 867
19 204
3 9
23 154
3 998
20 507
7 166
23 900
4 328
5 335
21 241
3 704
8 766
24 491
3 621
12 20
16 245
26 925
24 736
36 772
31 96
33 722
34 376
24 653
36 423
40 614
...

output:

18312
19008
13321
16224
13801
16734
19718
22458
19099
13417
18155
21405
15404
18211
17973
20162
15971
18800
23316
20483
19229
15572
17874
18230
16296
16669
14703
19112
16584
14807
22443
19334
19674
17966
15415
20403
19874
19904
19054
21051
17005
22991
13710
20183
20780
17697
19120
14358
13023
17781
...

result:

ok 980 numbers

Test #20:

score: 0
Accepted
time: 231ms
memory: 157960kb

input:

100000
1 1180
1 73336
1 3412
4 32887
2 69312
3 53909
5 63610
7 22310
7 54867
1 96949
1 77741
1 43903
11 11937
11 29558
8 44698
6 21055
17 4120
8 3765
12 34735
16 12548
18 52165
18 63950
23 10007
6 76202
16 42676
6 45376
27 28897
5 15086
13 94483
17 91622
25 64536
9 21293
30 91919
9 71838
4 87755
4 2...

output:

242
356
316
363
293
203
258
283
427
252
223
393
403
253
436
243
311
324
339
258
505
146
300
230
330
253
417
310
333
297
286
337
225
223
289
190
326
530
208
370
238
292
372
241
220
413
227
369
370
477
214
593
377
414
240
297
315
298
328
290
215
330
456
250
231
258
374
248
429
285
289
347
448
225
383
...

result:

ok 99980 numbers

Test #21:

score: 0
Accepted
time: 287ms
memory: 162376kb

input:

100000
1 69991
1 48322
3 13632
2 1979
1 89732
3 56826
2 29944
6 36910
2 56723
7 6841
6 59234
4 37459
3 86631
2 6405
10 8149
16 92496
2 10486
1 59876
12 55941
12 23657
4 52020
11 24409
19 91944
1 21187
16 35800
23 50634
12 92785
27 41572
23 67861
24 7292
31 74903
7 17649
22 70432
7 83637
35 54926
12 ...

output:

19304
17321
12568
18139
19639
16916
15576
15425
19887
13415
13324
13611
16559
12331
20418
13337
16819
12899
14974
16545
18023
19463
12837
21021
19817
15891
12495
20174
13547
13607
15181
19128
12413
18031
20207
20809
12878
14524
18517
22017
15318
20558
16515
20259
18390
16518
16641
21820
14781
19134
...

result:

ok 980 numbers

Test #22:

score: 0
Accepted
time: 406ms
memory: 174204kb

input:

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

output:

281863393
20353925
156462523
175783604
496581226
178442926
137540564
123514858
484835627
65624841
461983917
220986901
288938348
220465825
31842257
49212052
324683969
420709569
242476810
160055783
40580189
102777096
53770398
300389171
191963540
210550847
73257596
1830554
272757730
146003579
41488090
...

result:

ok 333313 numbers

Test #23:

score: 0
Accepted
time: 437ms
memory: 167788kb

input:

100000
1 71549
2 66826
3 92291
4 73386
5 55357
6 24538
7 3396
8 8318
9 74509
10 37031
11 83035
12 34537
13 56084
14 73354
15 81846
16 9565
17 32684
18 31374
19 83644
20 44991
21 964
22 48339
23 63685
24 50025
25 39902
26 46316
27 71325
28 96969
29 37074
30 95937
31 96261
32 64512
33 71626
34 84558
3...

output:

641578459
641824578
638040664
636240409
636682395
626987594
644273718
638028929
638607825
629719150
633272353
640899165
639954114
639886831
636524485
639813839
643945263
640815596
644545272
644735040
634716820
644656999
636721370
645709263
635583026
641783049
635496893
639852110
630449675
634072020
...

result:

ok 980 numbers

Test #24:

score: 0
Accepted
time: 445ms
memory: 169664kb

input:

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

output:

607439079
609064999
606893174
606945192
609673707
602034031
611913172
609769349
612660283
611471178
602985107
609887339
604375858
601284206
601737745
596360706
611752351
607710359
609996838
604247117
605828257
597700835
608650601
609582267
612129221
611571832
605710842
604014354
613124934
609103761
...

result:

ok 980 numbers

Test #25:

score: 0
Accepted
time: 490ms
memory: 174692kb

input:

100000
1 352
2 181
3 50
4 384
5 370
6 20
7 67
8 474
9 8
10 393
11 373
12 449
13 206
14 121
15 249
16 155
17 337
18 225
19 183
20 146
21 170
22 195
23 35
24 115
25 238
26 255
27 276
28 77
29 500
30 170
31 71
32 196
33 69
34 232
35 61
36 31
37 457
38 5
39 293
40 365
41 162
42 443
43 499
44 137
45 100
...

output:

145116418
175255542
153750228
145428279
64893786
204862368
189509514
86683959
111442153
100953630
186725668
162628570
180639258
96084960
191245622
144597583
145949043
199841958
175501960
144795050
196419012
147290511
107530224
197775336
162757034
181484990
183680064
89255627
128070355
134688437
2122...

result:

ok 99980 numbers

Test #26:

score: 0
Accepted
time: 444ms
memory: 175340kb

input:

100000
1 462
2 435
3 193
4 303
5 13
6 319
7 71
8 5
9 254
10 159
11 28
12 171
13 161
14 133
15 318
16 149
17 253
18 245
19 340
20 105
21 168
22 145
23 252
24 396
25 69
26 13
27 491
28 79
29 308
30 304
31 392
32 146
33 334
34 193
35 109
36 172
37 238
38 175
39 72
40 265
41 216
42 166
43 248
44 391
45 ...

output:

642391021
634613131
641937921
634836813
639464416
629870878
640554880
638499664
634387949
633616056
637756873
634700970
640522314
633637554
636126199
641718657
641135216
638514440
638912027
635907609
642417341
636890967
635262295
636875822
635971337
639323631
635258500
633227375
642655944
631435548
...

result:

ok 980 numbers

Test #27:

score: 0
Accepted
time: 478ms
memory: 176524kb

input:

100000
1 840
2 542
3 991
4 309
5 249
6 333
7 94
8 270
9 357
10 756
11 993
12 821
13 922
14 82
15 662
16 945
17 640
18 960
19 552
20 389
21 524
22 53
23 853
24 994
25 350
26 665
27 889
28 258
29 947
30 450
31 25
32 223
33 435
34 458
35 729
36 842
37 780
38 126
39 559
40 300
41 93
42 49
43 109
44 112
...

output:

416109740
350018933
336881168
512778815
316076629
496879820
535124420
556561515
530373558
590629324
287378959
280780347
299287180
180780282
470597948
553733708
496583738
477469485
435123554
374591071
517850175
283159104
264400279
495096226
533659569
281198421
468265984
320364410
166808147
404374135
...

result:

ok 99980 numbers

Test #28:

score: 0
Accepted
time: 444ms
memory: 171192kb

input:

100000
1 867
2 61
3 576
4 23
5 850
6 535
7 195
8 578
9 630
10 598
11 929
12 49
13 392
14 204
15 95
16 496
17 199
18 17
19 28
20 336
21 68
22 341
23 907
24 77
25 461
26 193
27 420
28 73
29 931
30 367
31 850
32 887
33 348
34 198
35 270
36 816
37 33
38 47
39 675
40 826
41 913
42 90
43 56
44 211
45 44
4...

output:

640520979
641671062
637990736
632732219
637221333
644135282
641903782
643663611
637370685
634000975
640503273
636923656
637686267
632888681
638973929
646113981
641009548
638171793
632662108
637931335
633696607
647667563
636092395
640095106
644946900
647470610
640351151
644749536
634216797
638213808
...

result:

ok 980 numbers

Test #29:

score: 0
Accepted
time: 504ms
memory: 179004kb

input:

100000
1 2379
2 370
3 3021
4 1530
5 8259
6 6848
7 7145
8 3627
9 5504
10 2008
11 7045
12 8073
13 8793
14 394
15 8636
16 8869
17 9596
18 7382
19 8318
20 7425
21 2698
22 5988
23 4189
24 4712
25 4089
26 4988
27 9072
28 9348
29 8465
30 2046
31 7714
32 7127
33 5568
34 1964
35 4691
36 3363
37 8870
38 683
3...

output:

209774480
140939673
112676353
122338831
127569896
207478098
157052461
164728690
177683026
94428486
202699439
157010321
131438796
145211247
107499063
133046900
99311226
162029654
118509324
98363928
158029652
167446547
212369622
142742280
97587039
112679863
167493650
189163305
89478984
128166122
20146...

result:

ok 99980 numbers

Test #30:

score: 0
Accepted
time: 454ms
memory: 171840kb

input:

100000
1 9650
2 302
3 4943
4 1896
5 6341
6 1897
7 6620
8 4308
9 9177
10 3343
11 9856
12 8462
13 4538
14 3520
15 3031
16 3704
17 6614
18 3472
19 9619
20 633
21 8769
22 5286
23 8041
24 7259
25 9506
26 3105
27 5250
28 4940
29 7172
30 7038
31 6027
32 8941
33 7670
34 8323
35 9941
36 3894
37 7211
38 1864
...

output:

635193342
643019144
642295997
640643321
647171986
635231545
634724913
646091501
635906697
646751684
647804446
644180073
635627346
639663453
638786794
637728742
633176049
643930379
643484651
643586120
646520708
646282780
638542512
646294439
647021648
641326338
636223776
642750479
647083128
632028580
...

result:

ok 980 numbers

Test #31:

score: 0
Accepted
time: 524ms
memory: 174832kb

input:

100000
1 24642
2 1224
3 56564
4 23728
5 70612
6 46544
7 68096
8 32960
9 13097
10 38444
11 43618
12 26822
13 28218
14 7774
15 93516
16 39696
17 94196
18 76253
19 95206
20 62814
21 49370
22 68437
23 64555
24 80772
25 68001
26 32003
27 53612
28 25164
29 10035
30 17081
31 71595
32 26930
33 94957
34 5673...

output:

309487127
366770129
317949501
275614891
560100211
383622832
541549916
396937212
458254824
371220303
391057604
499600045
565812391
311656577
588240237
381988744
532269037
403728156
322180428
493275230
586954763
420166295
542136317
580713941
365837925
359091945
433704369
470194682
480647294
601486598
...

result:

ok 99980 numbers

Test #32:

score: 0
Accepted
time: 444ms
memory: 171628kb

input:

100000
1 71549
2 66826
3 92291
4 73386
5 55357
6 24538
7 3396
8 8318
9 74509
10 37031
11 83035
12 34537
13 56084
14 73354
15 81846
16 9565
17 32684
18 31374
19 83644
20 44991
21 964
22 48339
23 63685
24 50025
25 39902
26 46316
27 71325
28 96969
29 37074
30 95937
31 96261
32 64512
33 71626
34 84558
3...

output:

641578459
641824578
638040664
636240409
636682395
626987594
644273718
638028929
638607825
629719150
633272353
640899165
639954114
639886831
636524485
639813839
643945263
640815596
644545272
644735040
634716820
644656999
636721370
645709263
635583026
641783049
635496893
639852110
630449675
634072020
...

result:

ok 980 numbers

Test #33:

score: 0
Accepted
time: 77ms
memory: 163716kb

input:

100000
1 3427
2 1422
3 3596
4 8021
5 2381
6 8497
7 6129
8 7085
9 5003
10 348
11 5299
12 7624
13 1978
14 8970
15 4404
16 4668
17 7783
18 6716
19 527
20 9379
21 5957
22 885
23 9584
24 9002
25 6747
26 5005
27 5896
28 9043
29 4723
30 8414
31 9259
32 7843
33 9405
34 9802
35 9889
36 7124
37 7210
38 2562
3...

output:

1698333488
30640636
1710905443
1690053967
779248918
422143659
599895834
988200032
402719588
1262808581
13203336
1537912493
70366
349186862
1717609735
352372213
1853461776
7752600
1760017524
778470845
373264585
1150399623
465621397
1249225289
97153700
33806653
85448913
46096980
109960676
540844621
10...

result:

ok 980 numbers

Test #34:

score: 0
Accepted
time: 228ms
memory: 164364kb

input:

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

output:

5816924
3362634
7766116
2159652
1585951
8507390
2554945
5524560
4411483
10437286
1470201
4078535
10327274
6588933
8987842
351744
10520375
3068463
4354136
1207758
6346412
4430016
3085543
11064143
3744027
7620405
542771
5716574
1848943
6497373
9647100
7904912
311792
9608529
5847052
1901421
4480466
735...

result:

ok 333313 numbers

Test #35:

score: 0
Accepted
time: 278ms
memory: 162348kb

input:

100000
1 18338
2 21450
3 36846
4 5182
5 1280
6 96121
7 92962
8 19343
9 73422
10 22561
11 85425
12 85467
13 31536
14 34301
15 4912
16 52029
17 56977
18 10283
19 63963
20 34838
21 69404
22 17101
23 82225
24 89801
25 51972
26 55657
27 74773
28 87198
29 23837
30 22217
31 32111
32 15907
33 41056
34 88828...

output:

5424879
5562120
5174857
5458558
5348215
5302263
5239253
5212901
5104264
5232531
5400421
4722628
4678353
5147930
5485747
5297932
5299984
5207358
5010992
5287324
5499969
5426811
5363346
4960553
4886986
5384652
4669099
4742328
5272151
5156031
5082988
5254901
4606209
5494669
5120826
5088065
4884233
5277...

result:

ok 980 numbers

Test #36:

score: 0
Accepted
time: 267ms
memory: 162320kb

input:

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

output:

210273
167913
190475
144110
123074
189294
171874
204416
179626
160710
166021
132859
197093
161356
161891
185740
152197
197414
176327
170980
199949
189210
162350
183404
178780
146654
148618
150678
145956
181020
166851
126770
123942
126163
166508
145123
145723
129364
194155
172935
166036
146511
180363...

result:

ok 980 numbers

Test #37:

score: 0
Accepted
time: 185ms
memory: 162388kb

input:

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

output:

37902
39521
108301
50535
60088
112317
81565
92346
39117
47111
54496
39505
57160
51979
77276
70775
90249
42309
117191
41008
56418
67255
89021
61077
38471
63928
44509
74745
72029
27509
27527
60929
29767
31586
84334
25063
50194
82763
32965
37062
72001
63028
103951
43203
68920
73134
70073
50295
31894
62...

result:

ok 99980 numbers

Test #38:

score: 0
Accepted
time: 273ms
memory: 162012kb

input:

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

output:

6333378
6536740
6208171
6521652
6633033
6258182
6237314
6048954
5792572
6565130
6124999
5921420
6558933
5585069
6406089
6783980
6762280
5838097
5980115
6066868
6455312
6791004
6293930
6402332
6464420
6428162
6697939
6516531
6759187
5662334
6812874
6472499
5622216
5840144
6856325
6217162
6437488
6369...

result:

ok 980 numbers

Test #39:

score: 0
Accepted
time: 181ms
memory: 164432kb

input:

100000
1 6313
2 2887
3 10643
4 93987
5 99654
6 95871
7 98179
8 59111
9 36823
10 10721
11 16136
12 55329
13 19627
14 84922
15 4536
16 26584
17 15328
18 90061
19 75358
20 3786
21 41548
22 33871
23 99384
24 68900
25 49655
26 84042
27 87801
28 30508
29 97278
30 68922
31 35112
32 25304
33 28594
34 24563
...

output:

278765
161743
129040
93456
380223
186107
180872
156033
130299
229602
299524
180644
264460
278380
192571
221690
161453
173396
297716
157027
211550
194076
205747
303239
117487
268003
190482
181856
307172
98393
193683
263045
171389
190815
215359
258939
243953
142115
168599
207545
315412
276530
188390
1...

result:

ok 99980 numbers

Test #40:

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

input:

100000
1 78717
2 82743
3 19754
4 14173
5 52660
6 23362
7 67737
8 70661
9 30474
10 78976
11 50531
12 51509
13 36604
14 95815
15 77759
16 21643
17 98297
18 32319
19 66197
20 3003
21 678
22 24166
23 11235
24 8362
25 24568
26 14954
27 59579
28 980
29 26589
30 17394
31 97730
32 63142
33 33812
34 64886
35...

output:

132469
135539
198567
152074
152586
143609
127347
144208
137637
189053
137745
197967
222005
146064
157473
142507
189082
191274
198849
166690
137122
158045
183725
183000
220714
226630
142399
228447
195086
144388
136941
222729
136649
213379
123205
200564
217035
164378
217470
157844
195849
135764
208882...

result:

ok 980 numbers

Test #41:

score: 0
Accepted
time: 178ms
memory: 159892kb

input:

100000
1 723
2 24855
3 91415
4 4921
5 68324
6 52595
7 91842
8 12203
9 88361
10 37378
11 35299
12 73397
13 7088
14 74430
15 56425
16 1152
17 52135
18 99876
19 91909
20 98238
21 35620
22 31540
23 29070
24 74816
25 2141
26 13268
27 93725
28 24254
29 39152
30 12237
1 27506
32 56404
33 85084
34 77964
35 ...

output:

658
898
510
1179
930
670
906
1435
582
630
949
316
982
589
1292
734
723
852
917
405
533
765
612
1286
491
754
382
167
278
575
586
444
741
798
395
745
610
953
400
426
680
1112
893
540
836
874
1096
855
467
561
684
501
667
647
732
997
509
692
936
343
788
705
723
469
1078
780
439
866
663
551
751
778
1744
...

result:

ok 99980 numbers

Test #42:

score: 0
Accepted
time: 280ms
memory: 160984kb

input:

100000
1 18338
2 21450
3 36846
4 5182
5 1280
6 96121
7 92962
8 19343
9 73422
10 22561
11 85425
12 85467
13 31536
14 34301
15 4912
16 52029
17 56977
18 10283
19 63963
20 34838
21 69404
22 17101
23 82225
24 89801
25 51972
26 55657
27 74773
28 87198
29 23837
30 22217
31 32111
32 15907
33 41056
34 88828...

output:

5424879
5562120
5174857
5458558
5348215
5302263
5239253
5212901
5104264
5232531
5400421
4722628
4678353
5147930
5485747
5297932
5299984
5207358
5010992
5287324
5499969
5426811
5363346
4960553
4886986
5384652
4669099
4742328
5272151
5156031
5082988
5254901
4606209
5494669
5120826
5088065
4884233
5277...

result:

ok 980 numbers

Test #43:

score: 0
Accepted
time: 233ms
memory: 162176kb

input:

100000
1 22358
2 29668
3 82802
4 50460
5 67858
6 84296
7 12824
8 12928
9 56646
10 17677
11 72627
12 68158
13 71740
14 70396
15 8440
16 69852
17 47152
18 74036
19 51981
20 91312
21 92434
22 15077
23 11500
24 8710
25 65640
26 63446
27 74116
28 127
29 46953
30 69057
31 77240
32 83468
33 33250
34 66577
...

output:

220565
56793
73188
112601
133177
164638
162586
266686
191182
98115
252158
173145
92534
188043
66694
163403
181284
150116
186227
125091
187739
212883
127996
126455
148268
98080
105236
219541
144634
167836
275548
255741
177388
190766
116512
136896
72152
243402
170213
155569
206978
231294
270843
107417...

result:

ok 99980 numbers

Test #44:

score: 0
Accepted
time: 206ms
memory: 163888kb

input:

100000
1 77666
2 84879
3 15087
4 83360
5 4450
6 56195
7 23749
8 90159
9 51654
10 96448
11 66606
12 29167
13 78161
14 70339
15 64455
16 91175
17 33339
18 32636
19 47394
20 22961
21 74734
22 15665
23 72324
24 30460
25 4428
26 66938
27 81447
28 87211
29 28454
30 18531
31 70329
32 5684
33 2054
34 82765
...

output:

521910
694697
561665
695133
785518
458288
907647
1008898
729015
562225
926900
683498
668604
658549
591131
748910
662181
774637
782323
694330
856009
808370
902056
648259
794620
811444
888150
699076
690525
598765
419920
866201
443209
776487
1013119
633896
891934
401470
406223
663717
711750
734873
7305...

result:

ok 9980 numbers

Test #45:

score: 0
Accepted
time: 201ms
memory: 162688kb

input:

100000
1 35593
2 62384
3 2002
4 70697
5 58497
1 26694
7 6037
8 58372
9 37246
10 81511
1 87647
12 11075
13 88917
14 84125
15 36216
1 49746
17 47072
18 8182
19 54506
20 54336
1 40380
22 22853
23 48581
24 26915
25 89065
1 15296
27 26140
28 18610
29 14157
30 3040
1 45446
32 40553
33 6993
34 73636
35 909...

output:

3753
2434
3105
3764
2877
3896
2541
2637
4053
3529
2436
4102
3221
2747
2713
2712
3295
2369
3881
3713
2372
2801
3513
3884
3913
3869
2288
3917
2906
3926
3778
2330
2879
3172
3568
3714
3156
2842
2581
2128
3405
3429
2902
2314
3538
4253
3662
3165
2740
2106
3173
3675
3186
2877
2630
2101
2168
3612
3329
4142
...

result:

ok 980 numbers

Test #46:

score: 0
Accepted
time: 258ms
memory: 164092kb

input:

100000
1 1135
2 1651
3 99494
4 17319
5 39336
6 44735
7 72567
8 13018
9 50376
10 88000
11 20545
12 40073
13 76194
14 1118
15 5385
16 33600
17 70738
18 81545
19 93660
20 37873
21 2642
22 42003
23 93257
24 66127
25 32806
26 82673
27 27491
28 42418
29 90385
30 3869
31 39136
32 50902
33 63325
34 86519
35...

output:

232200
360741
311650
412978
223804
280801
233514
182454
158775
330259
407994
239137
249867
315271
169256
288569
238506
396997
316052
351214
276096
291149
313525
267071
273049
297048
273797
262832
174718
283170
266952
153313
231491
317411
206717
293487
235388
316178
317642
200863
271294
224766
372478...

result:

ok 49980 numbers

Test #47:

score: 0
Accepted
time: 255ms
memory: 161836kb

input:

100000
1 57890
2 99148
3 18882
4 90797
5 89947
6 91293
7 18831
8 54821
9 59123
10 52850
11 9765
12 68302
13 83804
14 92878
15 73857
16 21800
17 9533
18 48361
19 30195
20 9988
21 29713
22 37613
23 4993
24 58311
25 93829
26 33852
27 89027
28 36556
29 62845
30 62727
31 84229
32 43423
33 57391
34 46232
...

output:

57722
60634
52314
76504
89040
75392
57957
65483
39854
103508
73753
57213
85464
101881
81675
42263
84674
77356
51463
89808
58104
67098
89808
90824
71970
71305
110167
95746
63671
81546
66427
66601
56060
38276
86185
109324
69787
68921
106969
91655
64835
83589
73777
59820
83976
81027
51924
69585
90493
7...

result:

ok 33313 numbers

Test #48:

score: 0
Accepted
time: 276ms
memory: 162840kb

input:

100000
1 28068
2 90875
3 38869
4 88850
5 50276
6 88559
7 18161
8 44832
9 1621
10 26471
11 28003
12 23100
13 79568
14 54386
15 10421
16 248
17 39027
18 11521
19 98103
20 36038
21 73279
22 24522
23 50748
24 36896
25 59640
26 91049
27 52282
28 70304
29 89033
30 28410
31 55342
32 76105
33 77149
34 24896...

output:

540548
559755
625397
695969
496265
697168
512476
574311
575406
612304
744562
733365
569074
740476
405633
863574
538990
528747
441360
537636
605349
818534
796563
728769
491613
600520
683525
781265
470109
808616
480562
736678
516744
718526
336573
578418
671922
402473
772740
647894
664033
730650
740522...

result:

ok 19980 numbers

Test #49:

score: 0
Accepted
time: 174ms
memory: 161840kb

input:

100000
1 783
2 621
3 159
4 521
5 588
6 722
7 943
8 951
9 102
10 728
11 404
12 498
13 801
14 74
15 667
16 446
17 587
18 617
19 964
20 966
21 920
22 480
23 716
24 31
25 918
26 950
27 131
28 972
29 702
30 239
31 23
32 24
33 673
34 227
35 56
36 151
37 545
38 46
39 186
40 693
41 915
42 798
43 454
44 445
...

output:

244011
238854
243831
307287
237886
244316
264516
274671
241536
245871
463882
246780
297418
327218
275133
241536
246780
245112
236478
329397
255539
396617
235210
248302
340821
223453
245784
241536
245784
270797
288117
270781
350688
245784
244451
248302
251077
232855
324294
295492
245113
244056
322390...

result:

ok 9980 numbers

Test #50:

score: 0
Accepted
time: 156ms
memory: 161280kb

input:

100000
1 32
2 370
3 121
4 544
5 720
6 145
7 19
8 908
9 940
10 960
11 965
12 748
13 517
14 439
15 723
16 834
17 435
18 475
19 72
20 443
21 858
22 155
23 457
24 491
25 376
26 12
27 341
28 712
29 265
30 223
31 820
32 739
33 419
34 550
35 237
36 794
37 578
38 930
39 821
40 913
41 797
42 792
43 599
44 65...

output:

5904913
5841827
2915837
7161860
5984346
5713945
4149452
5731624
8293640
3358113
5301421
11944039
6175304
11164780
5265299
10207029
6038392
9820745
3949747
4897037
4562774
4837771
6641140
6296415
5410378
9638553
7503458
5112990
9281689
4111255
4493666
6245184
11242238
3208282
4599802
9063307
5244413
...

result:

ok 99980 numbers

Test #51:

score: 0
Accepted
time: 177ms
memory: 161272kb

input:

100000
1 723
2 220
3 110
4 254
5 241
6 200
7 512
8 836
9 893
10 977
11 425
12 748
13 199
14 19
15 335
16 396
17 978
18 455
19 346
20 407
21 461
22 791
23 50
24 795
25 299
26 797
27 35
28 738
29 851
30 444
31 656
32 538
33 120
34 366
35 965
36 725
37 849
38 724
39 340
40 834
41 378
42 801
43 273
44 9...

output:

199259924
224282777
194673159
326260715
296849828
234657779
234905967
162208875
154862352
184993806
345337709
242589572
199184169
208032151
222368900
238002908
420362741
386449267
252089055
167995700
163000227
231105617
220614393
417526448
257071631
143833169
276350072
195617096
351832074
216382216
...

result:

ok 99980 numbers

Test #52:

score: 0
Accepted
time: 176ms
memory: 160816kb

input:

100000
1 933
2 242
3 754
4 567
5 685
6 221
7 758
8 862
9 81
10 366
11 729
12 282
13 460
14 958
15 48
16 743
17 941
18 63
19 378
20 808
21 229
22 131
23 622
24 562
25 811
26 690
27 386
28 726
29 283
30 889
31 605
32 914
33 322
34 126
35 94
36 201
37 204
38 53
39 122
40 598
41 423
42 462
43 610
44 981...

output:

60176
61341
67830
60180
59234
57529
58103
92516
79644
55650
69069
119538
66199
58444
60180
93721
60180
59762
56238
68192
60180
64947
66685
60180
58100
105780
59431
80048
59234
58570
60180
59051
60241
89712
60241
59762
60180
60241
119235
60241
122136
104766
59952
59564
60241
71526
118112
59762
60180
...

result:

ok 9980 numbers

Test #53:

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

input:

100000
1 900
2 154
3 80
4 103
5 734
6 363
7 639
8 695
9 948
10 779
11 80
12 580
13 651
14 817
15 2
16 306
17 924
18 91
19 910
20 224
21 90
22 394
23 531
24 657
25 861
26 315
27 19
28 229
29 977
30 295
31 676
32 205
33 632
34 563
35 489
36 882
37 116
38 305
39 959
40 710
41 918
42 326
43 512
44 1
45 ...

output:

642
589
589
1026
867
1048
589
589
589
589
686
589
589
714
589
589
843
627
986
589
666
1171
589
820
589
601
589
656
843
932
589
589
589
674
589
882
623
589
594
589
880
681
589
589
589
1159
638
589
589
589
589
928
589
589
664
589
589
589
589
640
589
946
589
589
589
589
677
705
719
589
598
652
775
739
...

result:

ok 980 numbers

Test #54:

score: 0
Accepted
time: 106ms
memory: 160888kb

input:

100000
1 900
2 154
3 80
4 103
5 734
6 363
7 639
8 695
9 948
10 779
11 80
12 580
13 651
14 817
15 2
16 306
17 924
18 91
19 910
20 224
21 90
22 394
23 531
24 657
25 861
26 315
27 19
28 229
29 977
30 295
31 676
32 205
33 632
34 563
35 489
36 882
37 116
38 305
39 959
40 710
41 918
42 326
43 512
44 1
45 ...

output:

642
589
589
1026
867
1048
589
589
589
589
686
589
589
714
589
589
843
627
986
589
666
1171
589
820
589
601
589
656
843
932
589
589
589
674
589
882
623
589
594
589
880
681
589
589
589
1159
638
589
589
589
589
928
589
589
664
589
589
589
589
640
589
946
589
589
589
589
677
705
719
589
598
652
775
739
...

result:

ok 980 numbers

Test #55:

score: 0
Accepted
time: 149ms
memory: 159656kb

input:

100000
1 34931
2 85062
3 4952
4 84761
5 81610
6 25908
7 89054
8 53010
9 35721
10 75257
11 33697
12 16315
13 11011
14 24409
15 39031
16 3240
17 97170
18 73623
19 43356
20 17040
21 57970
22 64445
23 71212
24 83246
25 68930
26 60025
27 78026
28 80833
29 67430
30 66106
31 41565
32 3212
33 17767
34 69207...

output:

60342
55267
41361
74325
67457
40114
23513
35583
67588
65514
112753
63733
61286
58085
110599
94170
58088
57095
41361
83628
65868
58088
55290
39405
56628
49857
51612
64174
44405
96862
41885
57095
58805
110594
59960
67587
59391
98800
57498
70027
67275
60458
41762
55095
69049
54727
55209
69052
58284
896...

result:

ok 99980 numbers

Test #56:

score: 0
Accepted
time: 137ms
memory: 165644kb

input:

100000
1 16795
2 38984
3 88626
4 71343
5 43373
6 3680
7 74601
8 16211
9 78157
10 31635
11 8678
12 51996
13 37267
14 4742
15 30370
16 51779
17 34107
18 47876
19 49821
20 59809
21 16774
22 11225
23 66967
24 31511
25 97719
26 68662
27 63895
28 90983
29 92439
30 5744
31 43368
32 3000
33 8434
34 35265
35...

output:

21320
33341
26004
31410
28721
20516
21630
36411
37461
15373
41064
29615
19009
26556
20447
39997
30073
17913
27342
29632
19060
25570
25978
21888
39830
30854
29365
22412
31844
26494
31473
20922
27794
13154
20258
15978
25643
20810
28335
26630
19596
40051
25053
32370
23652
27594
22976
39328
18416
14334
...

result:

ok 99980 numbers

Test #57:

score: 0
Accepted
time: 177ms
memory: 162236kb

input:

100000
1 67184
2 81486
3 69808
4 40596
5 60731
6 39874
7 71519
8 355
9 10321
10 67022
11 41360
12 32499
13 84713
14 83223
15 38620
16 33276
17 4160
18 74822
19 16035
20 99642
21 99508
22 46823
23 28933
24 59338
25 56363
26 25421
27 62249
28 26737
29 589
30 14412
31 18970
32 27989
33 22214
34 72062
3...

output:

118333
92182
69245
63441
73611
63541
94629
63671
70946
92380
66705
97303
120088
66414
63892
74020
76106
63671
125986
64769
124919
63893
93511
63892
63441
62777
98779
60902
75764
63359
94154
63671
58804
64336
60902
63441
64336
121923
63432
69978
101868
62812
71419
76466
64458
64325
63646
90928
62423
...

result:

ok 9980 numbers

Test #58:

score: 0
Accepted
time: 174ms
memory: 161368kb

input:

100000
1 32824
2 71979
3 75241
4 81704
5 27836
6 98788
7 34792
8 25444
9 50333
10 49512
11 67864
12 24480
13 7447
14 94815
15 3120
16 40781
17 75134
18 83617
19 63260
20 78479
21 85686
22 10719
23 34588
24 99647
25 32697
26 79674
27 17252
28 4169
29 88277
30 25034
31 25659
32 37999
33 51883
34 11480...

output:

85851
62386
62386
62386
116015
64904
66388
62386
62386
125611
63943
71518
67522
68567
82132
112390
62435
62543
83654
95252
62386
79715
82064
62885
68004
109331
69110
77195
62386
82122
72706
64075
93404
98982
114836
123981
114817
89554
70226
67436
62386
62659
93109
62386
77968
62446
107074
121739
626...

result:

ok 980 numbers

Test #59:

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

input:

100000
1 49497
2 28330
3 10598
4 31425
5 36898
6 2225
7 16783
8 29951
9 12469
10 38146
11 31602
12 29435
13 4382
14 17960
15 10578
16 31544
17 12426
18 9522
19 44394
20 5874
21 22430
22 44981
23 19220
24 7478
25 43214
26 37720
27 2595
28 46261
29 47046
30 28198
31 37259
32 44357
33 40421
34 49104
35...

output:

34300
38312
85985
36769
81128
43177
44636
90020
20778
101351
88850
104241
36667
70754
85358
24371
70147
26026
51271
37309
42541
59601
55723
19181
59127
31757
66698
23982
33571
49830
30060
30661
35585
81376
61640
2271
53507
80759
39419
31849
20526
2564
7503
59639
0
8360
99371
104489
14301
39152
6110
...

result:

ok 333313 numbers

Test #60:

score: 0
Accepted
time: 150ms
memory: 157656kb

input:

100000
1 19505
2 10791
3 10337
4 35153
5 17937
6 9122
7 18310
8 21837
9 14399
10 3275
11 33606
12 42073
13 20934
14 5535
15 8349
16 22005
17 13218
18 20546
19 1992
20 6950
21 14676
22 29833
23 46092
24 22419
25 17985
26 16734
27 44655
28 40186
29 24499
30 8400
31 27709
32 4473
33 6838
34 47039
35 57...

output:

85243
63545
48689
35924
58002
64077
60647
59032
60970
77505
78231
127027
97708
46234
53364
45562
66403
43713
60972
65893
29004
59655
67301
61001
44860
68784
74620
53952
92299
71582
58261
71218
70719
54980
77753
72414
101033
97473
70160
24342
87337
115265
82361
42051
63545
80468
65974
88174
62290
354...

result:

ok 99980 numbers

Test #61:

score: 0
Accepted
time: 171ms
memory: 163324kb

input:

100000
1 24783
2 33159
3 22350
4 20643
5 7030
6 5713
7 31874
8 29516
9 4253
10 48570
11 14875
12 36595
13 46681
14 26788
15 23714
16 495
17 15651
18 27110
19 12098
20 12264
21 33580
22 1291
23 12124
24 38780
25 4499
26 15444
27 24517
28 10252
29 38497
30 16290
31 9316
32 25884
33 49086
34 29917
35 2...

output:

27359
30088
40587
22534
22860
23856
31944
32674
25226
24116
28112
38399
43641
26282
34730
25731
27108
39381
26078
37369
22860
28226
24665
25441
31305
26611
40236
23762
28118
36346
28052
34905
27431
40553
22424
30060
22860
26828
22860
29412
37522
27348
24789
22860
33817
34531
30932
29824
23600
25760
...

result:

ok 9980 numbers

Test #62:

score: 0
Accepted
time: 105ms
memory: 161452kb

input:

100000
1 3917
2 8245
3 43624
4 49752
5 48615
6 2005
7 6271
8 24045
9 5732
10 46447
11 30379
12 2817
13 24513
14 25436
15 40475
16 19533
17 21886
18 8954
19 19361
20 41539
21 13935
22 29386
23 23266
24 884
25 33069
26 39104
27 1960
28 35096
29 16066
30 9991
31 20003
32 41386
33 23584
34 7034
35 39155...

output:

602
711
709
602
602
614
1177
1040
602
603
1199
966
602
626
602
1166
602
788
1267
978
633
939
631
602
1082
602
602
624
602
605
602
602
602
688
684
1212
602
604
1072
712
606
656
822
602
970
617
620
1099
700
602
602
998
606
921
688
936
719
602
1244
1162
604
631
735
602
1114
602
602
716
602
656
602
602
...

result:

ok 980 numbers

Test #63:

score: 0
Accepted
time: 161ms
memory: 164256kb

input:

100000
1 34240
2 40436
3 75340
4 43795
5 11351
6 13677
7 68663
8 37479
9 52315
10 20033
11 60066
12 62091
13 74857
14 33239
15 35814
16 52783
17 948
18 22601
19 12718
20 4473
21 24703
22 3430
23 71929
24 29184
25 77606
26 21809
27 412
28 54738
29 30997
30 40672
31 67646
32 56559
33 69839
34 67038
35...

output:

91705
75763
70941
59448
75572
39097
14914
61148
43655
89576
35105
2340
35893
54073
43610
85933
47616
27920
11009
53160
24388
38484
44664
44205
82910
41619
53277
54667
29354
57514
51990
13418
19676
55123
18687
60758
88094
58305
32971
48194
19042
17744
22762
1293
28177
12029
37788
25270
18132
50617
41...

result:

ok 333313 numbers

Test #64:

score: 0
Accepted
time: 134ms
memory: 164100kb

input:

100000
1 56461
2 59885
3 3443
4 27574
5 26306
6 73711
7 48428
8 13505
9 8212
10 42099
11 29812
12 74090
13 73345
14 50675
15 4876
16 78144
17 76458
18 77616
19 23
20 47443
21 45655
22 33965
23 10909
24 24120
25 56176
26 27695
27 57484
28 58121
29 70790
30 31939
1 70834
32 68066
33 16584
34 57784
35 ...

output:

188
239
164
99
210
163
231
178
189
263
180
221
289
370
213
324
268
227
246
238
316
263
289
412
247
179
336
192
225
203
226
390
179
226
297
132
347
151
188
291
267
191
160
199
138
299
264
199
374
179
225
244
275
406
138
264
192
146
165
322
117
265
222
235
484
189
403
179
151
175
210
227
284
233
147
2...

result:

ok 99980 numbers

Test #65:

score: 0
Accepted
time: 170ms
memory: 161240kb

input:

100000
1 8658
2 56566
3 47569
4 2367
5 8171
6 13138
7 17251
8 12672
9 67952
10 392
11 78860
12 34197
13 14730
14 66794
15 54254
16 35931
17 75128
18 27774
19 30978
20 69538
21 56843
22 68096
23 20626
24 35632
25 51112
26 48990
27 36800
28 11197
29 71881
30 63291
31 8702
32 67829
33 75900
34 72940
35...

output:

88264
68407
86332
97668
108293
59883
59576
79212
62779
78374
59027
60602
60602
60014
97851
60268
57348
60602
113518
64912
60602
81931
58536
56505
60268
60014
111985
60268
59096
60602
60268
60314
60602
58952
61783
74453
60786
71819
74154
74876
55350
60014
99440
60014
59576
60268
83141
60014
65442
606...

result:

ok 9980 numbers

Test #66:

score: 0
Accepted
time: 172ms
memory: 160692kb

input:

100000
1 13368
2 6182
3 19499
4 15868
5 42396
6 25411
7 11160
8 79194
9 25438
10 21266
11 37606
12 28620
13 47781
14 22752
15 7311
16 61760
17 74717
18 11101
19 33168
20 37576
21 21429
22 70428
23 64233
24 48028
25 50591
26 59415
27 54048
28 18836
29 35027
30 12842
31 27966
32 47406
33 60876
34 4123...

output:

120460
62844
62952
62844
115833
64268
69086
97528
66809
65563
79807
116402
62844
62844
70977
62704
88711
110472
62844
62844
62844
62704
62844
76660
62468
95904
111626
123472
100365
124931
70796
62844
93199
101980
117214
62844
105984
97616
62844
62844
62844
93710
62844
62704
62844
62844
62844
87423
7...

result:

ok 980 numbers

Test #67:

score: 0
Accepted
time: 157ms
memory: 164212kb

input:

100000
1 68841
2 96093
3 82436
4 80344
5 5762
6 88194
7 25435
8 65726
9 98089
10 75892
11 47041
12 42153
13 71042
14 30415
15 64433
16 66238
17 2245
18 60771
19 50623
20 97528
21 75357
22 42518
23 81230
24 82023
25 4169
26 46335
27 20122
28 86220
29 9566
30 72236
31 95952
32 65983
33 35203
34 46717
...

output:

30575
36647
88683
35188
30689
58814
19315
26135
37179
40809
48847
46923
93368
39021
69242
90762
47359
58480
64883
71748
28388
56398
41038
29892
40883
51062
19782
49136
80626
57966
78484
9639
53240
72444
33919
6495
55327
69407
31013
62128
35072
54937
48847
35306
66061
6426
58863
9186
9978
18376
26833...

result:

ok 333313 numbers

Test #68:

score: 0
Accepted
time: 141ms
memory: 163140kb

input:

100000
1 22358
2 29668
3 82802
4 50460
5 67858
6 84296
7 12824
8 12928
9 56646
10 17677
11 72627
12 68158
13 71740
14 70396
15 8440
16 69852
17 47152
18 74036
19 51981
20 91312
21 92434
22 15077
23 11500
24 8710
25 65640
26 63446
27 74116
28 127
29 46953
30 69057
31 77240
32 83468
33 33250
34 66577
...

output:

46422
58217
56320
31888
10450
52765
47783
52913
32248
58797
46789
59809
54775
32559
51540
47783
19163
43499
53310
36765
56751
51892
52903
52903
54446
27941
50834
52913
39444
53310
53896
51540
79046
45202
59809
55670
24448
49360
55384
58797
55673
60067
47003
52903
54138
36341
32264
58217
55384
47003
...

result:

ok 99980 numbers

Test #69:

score: 0
Accepted
time: 166ms
memory: 161448kb

input:

100000
1 77666
2 84879
3 15087
4 83360
5 4450
6 56195
7 23749
8 90159
9 51654
10 96448
11 66606
12 29167
13 78161
14 70339
15 64455
16 91175
17 33339
18 32636
19 47394
20 22961
21 74734
22 15665
23 72324
24 30460
25 4428
26 66938
27 81447
28 87211
29 28454
30 18531
31 70329
32 5684
33 2054
34 82765
...

output:

41574
35418
32209
29061
20855
28647
21009
42265
33928
34609
30803
22475
22291
44177
36095
23406
22152
22435
42335
40710
21367
20843
21247
29697
29628
38367
21324
25473
29559
37172
39600
23335
23788
21553
21119
30862
23361
25382
20700
21699
21472
35106
25940
24733
25587
28037
22009
40193
38256
21264
...

result:

ok 9980 numbers

Test #70:

score: 0
Accepted
time: 139ms
memory: 165640kb

input:

100000
1 6313
2 2887
3 10643
4 93987
5 99654
6 95871
7 98179
8 59111
9 36823
10 10721
11 16136
12 55329
13 19627
14 84922
15 4536
16 26584
17 15328
18 90061
19 75358
20 3786
21 41548
22 33871
23 99384
24 68900
25 49655
26 84042
27 87801
28 30508
29 97278
30 68922
31 35112
32 25304
33 28594
34 24563
...

output:

108540
49597
44450
76108
63778
60321
55866
51276
56140
46691
45867
59172
66840
67553
58206
62180
57377
62007
68585
108539
57714
111055
64524
41203
51388
62934
61663
86157
58227
6277
57029
59687
54606
94323
57377
62378
47660
60100
56650
73473
55320
60424
44064
54787
85998
119857
65773
40319
96945
551...

result:

ok 99980 numbers

Test #71:

score: 0
Accepted
time: 144ms
memory: 162416kb

input:

100000
1 22358
2 29668
3 82802
4 50460
5 67858
6 84296
7 12824
8 12928
9 56646
10 17677
11 72627
12 68158
13 71740
14 70396
15 8440
16 69852
17 47152
18 74036
19 51981
20 91312
21 92434
22 15077
23 11500
24 8710
25 65640
26 63446
27 74116
28 127
29 46953
30 69057
31 77240
32 83468
33 33250
34 66577
...

output:

46422
58217
56320
31888
10450
52765
47783
52913
32248
58797
46789
59809
54775
32559
51540
47783
19163
43499
53310
36765
56751
51892
52903
52903
54446
27941
50834
52913
39444
53310
53896
51540
79046
45202
59809
55670
24448
49360
55384
58797
55673
60067
47003
52903
54138
36341
32264
58217
55384
47003
...

result:

ok 99980 numbers

Test #72:

score: 0
Accepted
time: 154ms
memory: 156892kb

input:

100000
1 57890
2 99148
3 18882
4 90797
5 89947
6 91293
7 18831
8 54821
9 59123
10 52850
11 9765
12 68302
13 83804
14 92878
15 73857
16 21800
17 9533
18 48361
19 30195
20 9988
21 29713
22 37613
23 4993
24 58311
25 93829
26 33852
27 89027
28 36556
29 62845
30 62727
31 84229
32 43423
33 57391
34 46232
...

output:

8647
9687
8511
9267
8511
8828
8647
9554
8389
8511
9375
8988
10291
7564
9240
9240
9465
8252
7968
10593
9375
9554
8930
9465
9375
9375
9375
9554
9099
7968
9375
8194
9240
8252
9465
9465
9554
9687
9465
9240
9413
9267
9687
8647
9413
9413
9267
9267
9375
8511
9267
9687
9465
9687
9687
9465
9687
9521
9413
819...

result:

ok 33313 numbers

Test #73:

score: 0
Accepted
time: 162ms
memory: 161152kb

input:

100000
1 28068
2 90875
3 38869
4 88850
5 50276
6 88559
7 18161
8 44832
9 1621
10 26471
11 28003
12 23100
13 79568
14 54386
15 10421
16 248
17 39027
18 11521
19 98103
20 36038
21 73279
22 24522
23 50748
24 36896
25 59640
26 91049
27 52282
28 70304
29 89033
30 28410
31 55342
32 76105
33 77149
34 24896...

output:

59497
61065
62530
62530
62501
60923
54785
58224
61754
59053
59053
62178
61582
62501
61567
62501
53120
55118
61797
61623
61623
61582
58161
61567
61582
62530
90376
61797
62501
62178
62219
55118
59988
62219
62178
55710
61797
59988
61065
59868
61567
62219
60923
62501
58700
62501
60458
72641
62530
62501
...

result:

ok 19980 numbers

Test #74:

score: 0
Accepted
time: 166ms
memory: 161500kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 199980 numbers

Test #75:

score: 0
Accepted
time: 142ms
memory: 163152kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499980 numbers