QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312232#7206. TriplezltAC ✓229ms24020kbC++143.8kb2024-01-23 16:50:282024-01-23 16:50:29

Judging History

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

  • [2024-01-23 16:50:29]
  • 评测
  • 测评结果:AC
  • 用时:229ms
  • 内存:24020kb
  • [2024-01-23 16:50:28]
  • 提交

answer

#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<ll, ll> pii;

const int maxn = 100100;

int n;
vector<int> gg[maxn];

int f[maxn], sz[maxn], rt;
bool vis[maxn];

void dfs2(int u, int fa, int t) {
	f[u] = 0;
	sz[u] = 1;
	for (int v : gg[u]) {
		if (v == fa || vis[v]) {
			continue;
		}
		dfs2(v, u, t);
		sz[u] += sz[v];
		f[u] = max(f[u], sz[v]);
	}
	f[u] = max(f[u], t - sz[u]);
	if (!rt || f[u] < f[rt]) {
		rt = u;
	}
}

int D, mxd[maxn], son[maxn], dep[maxn];
vector<int> g[maxn];
// F[d]: 深度 >= d 的点数
// G[d]: 深度 >= d 且在同一棵子树的点对,用于容斥
// H[d]:深度 = d 的点数(为了算前缀和)
ll F[maxn], G[maxn], H[maxn], ans;

void dfs3(int u, int fa, int rt) {
	D = max(D, dep[u]);
	if (dep[u] >= (int)g[rt].size()) {
		g[rt].pb(1);
	} else {
		++g[rt][dep[u]];
	}
	mxd[u] = dep[u];
	son[u] = 0;
	for (int v : gg[u]) {
		if (vis[v] || v == fa) {
			continue;
		}
		dep[v] = dep[u] + 1;
		dfs3(v, u, rt);
		if (mxd[v] > mxd[u]) {
			son[u] = v;
			mxd[u] = mxd[v];
		}
	}
}

int tim, h[maxn], id[maxn], p[maxn];

void dfs4(int u, int fa) {
	id[u] = ++tim;
	h[id[u]] = 1;
	p[u] = 1;
	if (son[u]) {
		dfs4(son[u], u);
		p[u] += p[son[u]];
	}
	for (int v : gg[u]) {
		if (v == fa || v == son[u] || vis[v]) {
			continue;
		}
		dfs4(v, u);
		ll s1 = p[u], s2 = 0, s = 0;
		for (int j = 0; j < mxd[v] - dep[u] * 2; ++j) {
			s += H[j];
		}
		for (int j = mxd[v] - dep[u]; ~j; --j) {
			s1 -= h[id[u] + j];
		}
		for (int j = mxd[v] - dep[u]; j; --j) {
			// A, C 同子树
			ans += F[max(0, j - dep[u] + 1)] * 2 * (s1 * h[id[v] + j - 1] + s2 * h[id[u] + j]);
			s1 += h[id[u] + j];
			// A, B 同子树
			if (j > dep[u]) {
				ans += s * 2 * (s1 * h[id[v] + j - 1] + s2 * h[id[u] + j]);
				s -= H[j - dep[u] - 1];
			}
			s2 += h[id[v] + j - 1];
			h[id[u] + j] += h[id[v] + j - 1];
		}
		p[u] += p[v];
	}
	// X = C = u
	ans += 2LL * (p[u] - 1) * F[0];
	// X = R, C = u, A, B 不同子树
	ans += F[dep[u] + 1] * (F[dep[u] + 1] - 1) - G[dep[u] + 1];
}

void dfs(int u) {
	D = 0;
	vis[u] = 1;
	for (int v : gg[u]) {
		if (vis[v]) {
			continue;
		}
		g[v].pb(0);
		dep[v] = 1;
		dfs3(v, u, v);
		for (int i = mxd[v], s = 0; ~i; --i) {
			s += g[v][i];
			F[i] += s;
			G[i] += 1LL * s * (s - 1);
			H[i] += g[v][i];
		}
	}
	// X = C = R 且 A, B 不同子树
	ans += F[1] * (F[1] - 1) - G[1];
	++F[0];
	H[0] = 1;
	for (int v : gg[u]) {
		if (vis[v]) {
			continue;
		}
		for (int i = mxd[v], s = 0; ~i; --i) {
			s += g[v][i];
			F[i] -= s;
			G[i] -= 1LL * s * (s - 1);
			H[i] -= g[v][i];
		}
		tim = 0;
		dfs4(v, u);
		for (int i = mxd[v], s = 0; ~i; --i) {
			s += g[v][i];
			F[i] += s;
			G[i] += 1LL * s * (s - 1);
			H[i] += g[v][i];
		}
	}
	for (int i = 0; i <= D; ++i) {
		F[i] = G[i] = H[i] = 0;
	}
	for (int v : gg[u]) {
		if (vis[v]) {
			continue;
		}
		vector<int>().swap(g[v]);
	}
	for (int v : gg[u]) {
		if (vis[v]) {
			continue;
		}
		rt = 0;
		dfs2(v, -1, sz[v]);
		dfs2(rt, -1, sz[v]);
		dfs(rt);
	}
}

void solve() {
	for (int i = 1; i <= n; ++i) {
		vector<int>().swap(gg[i]);
		vis[i] = 0;
	}
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		gg[u].pb(v);
		gg[v].pb(u);
	}
	for (int i = 1; i <= n; ++i) {
		reverse(gg[i].begin(), gg[i].end());
	}
	ans = 0;
	rt = 0;
	dfs2(1, -1, n);
	dfs2(rt, -1, n);
	dfs(rt);
	printf("%lld\n", 1LL * n * (n - 1) * (n - 2) - ans);
}

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

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12984kb

input:

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

output:

4
18

result:

ok 2 tokens

Test #2:

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

input:

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

output:

40
44
44
40
44
40
40
40
44
40
44
44
44
44
44
44
40
40
44
40
40
44
44
44
40
44
40
40
44
44
40
44
44
40
44
48
44
40
40
40
40
40
48
40
44
44
40
44
48
40
40
44
40
44
44
44
40
40
40
40
44
44
44
44
40
40
44
48
40
44
40
40
44
44
44
40
44
44
44
44
44
48
44
40
40
40
40
48
40
44
44
40
44
44
44
40
40
44
44
40
...

result:

ok 200 tokens

Test #3:

score: 0
Accepted
time: 6ms
memory: 13400kb

input:

6
3 5
2 5
6 1
6 3
4 6
6
1 2
4 1
6 2
2 3
5 6
6
3 4
6 3
1 2
1 5
4 1
6
1 2
6 3
1 3
1 4
4 5
6
2 1
6 2
5 2
3 5
4 2
6
4 6
2 3
6 1
3 5
1 5
6
5 4
6 2
6 1
1 5
3 4
6
2 1
6 4
1 4
2 5
3 6
6
1 6
1 3
5 3
6 2
2 4
6
5 3
5 4
1 3
6 4
2 3
6
4 5
1 3
2 4
3 2
6 4
6
1 4
3 6
6 1
1 2
1 5
6
6 4
1 4
4 5
3 4
3 2
6
6 3
2 3
4 6
...

output:

86
86
86
86
94
80
80
80
80
86
86
94
94
86
86
94
92
86
86
80
86
92
86
80
94
80
94
94
80
86
92
92
86
86
86
86
94
86
86
86
86
86
80
94
86
80
94
80
80
86
86
80
86
86
94
80
94
86
94
80
94
80
94
86
86
86
80
86
86
94
86
86
86
80
86
86
86
86
86
86
86
92
86
86
86
80
80
80
86
86
80
86
86
86
80
86
86
86
86
80
...

result:

ok 2000 tokens

Test #4:

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

input:

7
5 2
4 7
3 2
7 1
2 6
4 3
7
3 2
5 6
1 5
3 5
6 4
3 7
7
3 2
5 6
7 2
6 2
1 6
6 4
7
2 5
2 7
1 7
6 5
3 2
4 1
7
4 6
6 3
6 7
5 3
1 4
1 2
7
6 1
5 2
6 5
4 2
6 3
6 7
7
7 4
6 4
3 4
3 5
2 5
3 1
7
7 4
3 6
1 6
3 2
7 6
6 5
7
1 7
6 1
5 6
2 7
7 4
3 5
7
6 2
4 5
3 2
4 2
5 7
1 4
7
4 3
7 2
3 5
3 1
2 1
6 5
7
6 7
1 6
7 2
...

output:

148
156
168
148
148
160
156
160
148
156
148
160
148
148
140
168
148
148
160
160
156
150
160
148
148
140
148
148
148
148
148
148
150
148
148
148
150
148
156
140
148
148
148
156
160
148
148
148
148
140
150
148
148
148
156
148
156
156
140
156
148
140
148
148
160
148
160
148
148
156
156
148
148
168
160
...

result:

ok 5000 tokens

Test #5:

score: 0
Accepted
time: 23ms
memory: 12560kb

input:

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

output:

248
234
238
244
250
244
248
244
244
244
252
244
238
276
224
244
234
244
238
260
238
234
234
234
250
252
278
224
234
244
244
248
250
254
268
234
234
234
234
244
244
234
244
224
260
234
250
244
244
244
238
260
244
238
234
260
244
260
268
244
248
234
248
234
260
234
234
244
250
244
250
248
234
234
244
...

result:

ok 10000 tokens

Test #6:

score: 0
Accepted
time: 27ms
memory: 13860kb

input:

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

output:

372
380
360
348
384
380
368
394
366
372
336
354
372
348
368
372
380
380
348
380
348
380
366
360
372
360
348
360
348
404
360
392
372
348
348
348
368
348
380
372
360
380
368
360
360
348
360
368
348
368
372
360
348
354
348
380
360
386
372
366
366
354
354
360
372
360
368
394
348
386
380
348
368
348
372
...

result:

ok 10000 tokens

Test #7:

score: 0
Accepted
time: 32ms
memory: 13024kb

input:

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

output:

508
532
508
532
576
502
516
522
520
516
522
508
524
508
522
536
532
524
532
522
522
554
502
516
508
522
516
522
516
508
540
522
530
494
508
494
548
532
546
502
546
524
508
534
522
518
508
566
532
494
562
520
508
532
522
522
534
518
524
532
552
520
532
552
538
516
502
518
502
534
534
534
508
508
494
...

result:

ok 10000 tokens

Test #8:

score: 0
Accepted
time: 35ms
memory: 13264kb

input:

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

output:

516
532
522
546
508
502
562
532
522
546
508
570
540
502
556
532
520
532
508
494
502
516
524
522
508
532
520
546
556
532
508
576
494
532
538
518
534
508
534
552
516
508
494
540
554
532
494
508
548
522
518
508
516
516
518
532
508
522
534
524
520
522
508
508
518
582
532
546
508
502
508
516
494
530
532
...

result:

ok 10000 tokens

Test #9:

score: 0
Accepted
time: 21ms
memory: 12188kb

input:

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

output:

770
692
720
676
730
732
734
720
692
728
722
692
728
746
720
720
704
686
740
702
708
732
686
736
724
764
748
730
702
708
676
692
740
732
812
720
702
702
720
720
728
744
772
714
702
686
692
764
704
720
728
692
708
740
718
784
702
772
728
740
756
752
738
686
728
708
776
708
736
762
728
740
686
708
748
...

result:

ok 5000 tokens

Test #10:

score: 0
Accepted
time: 24ms
memory: 13592kb

input:

12
8 12
12 6
5 3
12 10
12 1
10 2
12 4
11 6
5 8
3 7
5 9
12
11 7
6 1
12 10
4 11
8 6
6 3
5 2
8 2
6 11
2 9
12 11
12
8 2
4 12
6 2
7 3
12 10
5 9
7 9
11 9
2 4
12 1
12 3
12
7 9
6 4
3 8
9 10
3 7
11 12
9 6
5 12
1 5
8 5
10 2
12
2 5
7 3
1 5
9 4
5 6
1 7
10 6
12 2
12 9
8 10
11 2
12
12 10
12 7
12 3
7 11
11 8
2 10
...

output:

998
998
966
928
936
966
960
966
978
998
970
934
956
966
916
948
928
948
948
972
954
952
966
948
948
968
1010
932
930
954
958
954
958
948
916
982
958
968
934
966
934
1006
930
966
980
946
962
948
1008
974
928
972
1026
964
954
984
980
1000
934
916
966
972
934
972
936
934
966
984
966
958
934
1000
966
97...

result:

ok 5000 tokens

Test #11:

score: 0
Accepted
time: 27ms
memory: 13420kb

input:

13
6 12
10 7
12 8
7 4
7 2
5 2
5 3
8 7
12 11
1 11
4 9
13 4
13
9 6
13 5
8 13
11 3
7 1
1 12
11 5
13 7
11 4
10 12
9 7
2 10
13
12 6
5 3
7 3
12 10
11 5
1 7
9 2
1 9
10 1
5 8
13 3
4 11
13
9 5
2 5
2 1
5 11
7 1
9 10
3 4
4 10
10 12
6 3
8 4
1 13
13
8 6
8 10
2 11
7 9
5 2
6 5
4 12
3 5
12 7
3 7
1 13
6 13
13
5 10
1...

output:

1260
1222
1218
1224
1238
1240
1248
1218
1368
1224
1268
1254
1244
1318
1240
1204
1340
1232
1254
1302
1238
1258
1184
1228
1238
1240
1238
1210
1276
1198
1280
1240
1312
1258
1260
1164
1204
1298
1208
1282
1224
1252
1246
1204
1262
1304
1314
1260
1288
1178
1242
1258
1288
1212
1240
1204
1288
1324
1204
1204
...

result:

ok 5000 tokens

Test #12:

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

input:

14
14 5
8 9
12 10
2 8
11 13
7 2
4 12
10 13
11 7
1 14
3 2
11 5
6 2
14
5 7
9 13
14 9
6 14
1 13
11 2
3 11
14 5
14 8
11 6
12 2
9 4
10 1
14
2 7
8 5
9 11
9 8
2 8
1 12
7 12
12 4
12 3
2 13
3 6
4 14
13 10
14
5 6
9 7
14 10
14 6
10 7
4 6
8 2
2 11
13 12
1 7
3 5
2 3
6 12
14
13 7
3 11
1 2
10 6
12 4
8 5
9 10
4 9
8...

output:

1570
1582
1602
1576
1494
1590
1600
1540
1584
1522
1632
1544
1586
1568
1616
1576
1554
1578
1632
1628
1554
1600
1652
1562
1640
1478
1556
1580
1582
1516
1550
1696
1556
1550
1532
1522
1668
1522
1550
1578
1616
1636
1598
1516
1610
1566
1554
1574
1602
1532
1636
1684
1594
1544
1522
1602
1562
1554
1522
1532
...

result:

ok 5000 tokens

Test #13:

score: 0
Accepted
time: 27ms
memory: 12488kb

input:

15
12 7
6 12
9 2
4 3
8 14
5 2
12 5
14 3
14 2
14 11
2 15
13 6
1 15
9 10
15
9 5
11 5
9 10
13 14
1 13
11 6
9 2
12 6
4 6
11 8
1 7
1 9
3 7
15 7
15
10 3
7 1
9 1
5 9
10 2
6 15
11 7
9 6
3 14
9 8
10 1
12 4
13 8
12 2
15
4 13
11 14
11 10
11 3
15 3
4 1
4 5
15 9
4 7
8 12
2 9
15 7
6 15
12 14
15
7 9
6 8
9 1
8 15
1...

output:

2048
2016
2010
1996
2014
1980
1868
1956
2040
2036
2018
1980
2144
1936
2004
1972
2016
2056
1952
2144
1948
2012
2076
2028
2024
1966
1964
2028
1960
1956
2014
1974
1972
2036
2046
2074
1936
2004
1960
2008
1972
1952
1916
1926
1936
2044
1926
2034
1960
2164
1954
1912
2038
2052
1958
1936
1942
1916
1916
1936
...

result:

ok 5000 tokens

Test #14:

score: 0
Accepted
time: 30ms
memory: 13340kb

input:

16
4 2
1 8
12 16
13 2
1 15
2 6
8 5
15 2
7 10
3 14
16 7
5 16
5 3
12 9
11 2
16
15 2
13 10
4 7
16 2
15 5
13 1
13 4
1 9
15 9
4 12
6 5
10 8
11 10
10 3
10 14
16
8 15
16 5
15 1
11 10
12 4
15 9
1 11
14 5
6 2
16 3
15 7
3 15
2 1
1 13
7 4
16
12 14
6 14
10 12
11 15
9 15
16 15
11 10
13 12
16 5
14 2
3 16
1 13
7 1...

output:

2484
2574
2508
2482
2480
2416
2492
2494
2426
2392
2662
2554
2366
2464
2422
2522
2398
2340
2398
2534
2406
2440
2464
2534
2416
2358
2432
2370
2390
2384
2392
2546
2578
2510
2414
2446
2416
2546
2352
2394
2390
2532
2416
2424
2364
2318
2470
2420
2440
2410
2504
2512
2374
2462
2368
2480
2430
2448
2414
2364
...

result:

ok 5000 tokens

Test #15:

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

input:

17
14 2
3 12
16 4
13 11
6 12
2 7
8 1
12 7
4 7
4 5
4 10
9 15
17 1
1 12
15 10
17 13
17
6 15
3 11
13 7
1 14
15 4
13 8
11 14
10 12
1 5
17 14
7 5
1 4
3 9
8 10
16 5
2 3
17
5 17
6 2
17 4
16 1
14 5
12 9
11 5
13 12
17 1
10 2
7 2
8 6
12 3
15 9
16 10
11 15
17
4 16
7 1
9 4
16 7
12 1
14 9
8 15
17 10
13 1
8 5
1 1...

output:

2990
2888
2832
2848
3000
3008
3058
2878
2986
2904
3018
2984
3100
3008
3000
3008
3032
3140
3086
3142
2956
2966
2898
2934
2956
2928
3016
2910
2920
2964
2940
2884
2996
3092
2912
2920
3056
2956
2856
3004
3200
2962
2956
2936
3044
2980
2968
2966
2906
2992
2966
2952
2854
3006
2936
3068
2900
2952
2860
3010
...

result:

ok 5000 tokens

Test #16:

score: 0
Accepted
time: 35ms
memory: 13036kb

input:

18
18 15
1 13
1 3
15 12
1 12
10 18
17 16
4 16
3 7
11 1
16 13
6 3
5 16
14 16
2 3
8 11
9 18
18
11 6
13 4
1 6
8 9
12 1
5 6
13 1
9 14
14 15
5 2
11 3
9 6
12 17
11 7
2 10
18 11
11 16
18
15 12
5 3
2 9
14 4
1 16
1 4
3 2
2 11
10 4
10 11
12 10
11 17
8 2
18 2
13 5
5 6
14 7
18
10 16
4 3
15 16
6 1
14 4
13 8
13 1...

output:

3748
3798
3616
3842
3754
3464
3554
3574
3632
3460
3608
3650
3626
3550
3662
3396
3632
3462
3554
3708
3684
3552
3588
3614
3478
3528
3466
3414
3442
3408
3564
3622
3578
3404
3458
3608
3712
3504
3556
3840
3500
3564
3536
3534
3526
3548
3604
3532
3626
3592
3618
3688
3514
3426
3600
3582
3522
3536
3586
3722
...

result:

ok 5000 tokens

Test #17:

score: 0
Accepted
time: 38ms
memory: 12908kb

input:

19
9 4
2 11
6 19
10 5
13 19
17 18
10 11
14 10
16 15
3 8
15 3
6 18
12 15
13 15
5 19
6 9
6 7
11 1
19
7 2
1 18
2 15
4 17
9 10
19 8
13 3
6 15
1 5
7 18
5 10
11 16
17 13
5 4
8 5
6 12
14 11
11 10
19
16 12
8 5
11 7
5 16
6 16
18 1
2 17
11 15
13 10
15 6
16 19
14 13
19 14
13 18
18 3
16 17
2 9
13 4
19
2 3
19 15...

output:

4294
4152
4252
4310
4396
4250
4266
4196
4118
4286
4168
4354
4142
4168
4354
4130
4216
4104
4236
4234
4272
4406
4402
4132
4488
4090
4242
4088
4270
4266
4174
4236
4286
4166
4088
4228
4198
4320
4178
4302
4102
4206
4200
4124
4392
4338
4368
4210
4238
4184
4224
4250
4476
4500
4384
4452
4252
4212
4180
4308
...

result:

ok 5000 tokens

Test #18:

score: 0
Accepted
time: 39ms
memory: 12116kb

input:

20
16 19
9 18
18 6
2 6
12 1
20 2
13 10
10 20
19 12
11 6
1 7
8 13
9 17
6 19
14 12
3 7
17 15
5 1
4 12
20
14 1
4 2
19 4
11 12
2 10
18 14
10 5
17 16
3 2
4 7
14 2
19 11
14 17
17 13
20 2
10 9
5 6
8 4
15 12
20
19 10
13 14
10 15
20 10
7 2
5 7
11 12
19 18
15 8
16 3
20 16
4 11
5 14
17 20
17 1
1 12
15 5
9 11
6...

output:

4900
5138
4912
5034
4974
5294
4898
5154
4930
5280
4786
5000
5086
4780
5212
5074
4986
4920
4896
4984
5018
4826
4776
5140
5036
4932
4976
4874
5046
4908
4730
4872
4916
5212
4956
5000
5196
5144
4940
4922
4758
4896
4930
4996
4794
4918
4858
4988
4904
4880
4928
5016
4906
5066
5194
5090
5058
5114
4910
4794
...

result:

ok 5000 tokens

Test #19:

score: 0
Accepted
time: 54ms
memory: 12352kb

input:

100
67 36
52 43
24 5
4 35
75 40
18 35
47 21
37 10
96 16
63 3
98 94
67 46
11 45
97 92
33 97
13 79
65 11
88 36
27 9
33 86
39 56
78 42
50 45
28 33
55 93
75 76
2 37
63 41
64 15
100 7
1 55
23 98
25 30
95 96
80 82
61 90
6 100
48 61
59 17
5 77
48 30
40 5
80 92
22 96
52 41
41 62
20 37
35 86
12 17
75 42
95 8...

output:

684472
684160
686940
691898
687648
683104
684422
695126
692778
690822
697448
676998
686388
698290
699268
694678
686726
684794
682138
686732
702140
692902
678436
690646
684552
685604
682708
681198
681978
679534
700508
699442
699746
688496
691660
686028
678772
681360
680922
693700
697238
680274
682314...

result:

ok 1000 tokens

Test #20:

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

input:

100
89 80
57 25
69 39
100 47
44 46
67 35
5 92
2 78
25 75
97 86
96 45
78 4
96 69
5 83
100 20
30 55
58 30
63 43
5 1
11 48
51 53
40 71
1 36
74 85
69 34
11 19
22 48
95 38
27 15
15 16
71 57
30 37
80 11
91 72
69 23
2 10
79 39
95 47
12 24
18 72
19 8
90 35
18 93
12 27
52 8
81 40
68 95
54 65
36 47
34 5
14 63...

output:

677592
679050
691422
678486
677090
687558
704776
686126
686082
681140
690424
689384
696380
706188
677484
691200
689586
697520
689492
677224
681056
690624
674660
684308
677576
690150
683250
679254
680180
680436
694134
679042
682032
687094
691560
681882
677486
683268
688512
704214
683218
679518
684494...

result:

ok 1000 tokens

Test #21:

score: 0
Accepted
time: 56ms
memory: 14124kb

input:

200
88 2
180 40
143 130
101 47
84 119
86 75
89 129
84 179
3 56
125 126
83 38
45 161
88 131
179 182
180 88
124 183
155 124
8 7
55 2
8 9
78 57
79 7
170 19
5 92
184 134
101 186
34 6
161 94
21 145
112 183
11 73
151 2
83 110
85 41
28 82
141 159
13 163
32 5
160 76
168 193
155 92
175 50
30 69
158 157
7 54
...

output:

5439070
5474370
5526810
5498838
5590220
5499442
5531662
5457316
5491428
5490756
5479394
5586032
5501850
5497722
5527908
5564148
5530414
5564320
5530196
5439706
5504816
5536340
5485100
5545576
5498008
5499710
5531946
5609290
5539656
5524424
5517760
5521518
5491250
5534982
5483072
5459988
5573136
5422...

result:

ok 500 tokens

Test #22:

score: 0
Accepted
time: 66ms
memory: 12836kb

input:

1000
604 979
559 660
734 3
340 529
495 604
585 895
38 195
790 271
588 36
103 821
431 581
778 378
984 306
436 451
749 279
765 776
848 753
567 382
517 286
379 318
696 759
196 851
141 405
897 728
110 770
223 848
553 492
942 804
191 189
279 481
63 349
940 639
608 118
232 35
434 415
419 869
238 91
143 14...

output:

684614502
686028670
681548598
681158212
678946054
679693540
684178782
684770184
686794848
679751858
681769862
676620020
679670694
679474144
681487960
681258688
679489670
688299170
678273082
680911080
689916116
680415064
681259328
686905758
684116908
679358034
682008768
684467596
681984316
683007912
...

result:

ok 100 tokens

Test #23:

score: 0
Accepted
time: 71ms
memory: 12592kb

input:

2000
19 1187
84 1323
1143 1379
840 580
1931 352
571 675
131 1144
1452 687
54 1628
91 642
1489 1760
543 683
1267 525
801 525
63 1120
1823 1790
748 1352
1978 1161
744 651
344 1388
1057 1713
1939 1179
1019 1656
1479 939
1245 287
200 360
899 331
570 1359
669 676
1159 1236
383 1977
1549 1182
79 1256
1021...

output:

5484503690
5424988368
5451277590
5461040958
5425633248
5446399920
5407014250
5422287448
5446998806
5448030558
5449229444
5461292494
5448063076
5432508748
5476508290
5458412972
5418733130
5405171660
5479449166
5428801246
5407395362
5456262362
5459681224
5444265966
5420082046
5430996272
5471252206
543...

result:

ok 50 tokens

Test #24:

score: 0
Accepted
time: 86ms
memory: 14052kb

input:

5000
3343 4811
2502 4695
2462 3073
2685 4790
2212 587
1034 805
4749 4287
2197 2716
2946 4470
4727 4575
4528 3359
4008 2301
1319 2025
1595 130
4796 4572
4173 1261
3079 625
377 3347
4686 1117
3622 1066
3952 1331
4855 1775
2843 1287
2074 1353
1991 459
2930 2131
1145 621
1862 4830
2193 2679
1343 3092
30...

output:

84688727530
84867134852
84589400146
84423365004
84582032952
84512931724
84359535098
84664133264
84831778978
84484653694
84604376572
84940833294
84744167102
84504676308
84473934064
84760926376
84489063878
84536572318
84573722174
84908909346

result:

ok 20 tokens

Test #25:

score: 0
Accepted
time: 86ms
memory: 12760kb

input:

5000
2443 4594
898 3244
3567 1310
667 99
3701 1448
2761 774
1607 3502
4072 885
783 1217
3486 3539
4247 2294
3813 7
434 797
3754 1588
2432 2085
3929 4136
102 830
3350 793
1220 4293
4093 1211
2829 659
4907 3427
4794 3039
1994 1856
895 1391
1545 4948
3533 3571
1834 135
2647 4691
4843 3932
1869 1931
300...

output:

84595306140
84236109832
84368594450
84353654018
84656502782
84606401972
84563318496
84538840012
84827745376
84493406248
84815969624
85046301234
84362229800
84479980290
84763419630
85012232422
84574032404
84782466460
84693829702
84656792252

result:

ok 20 tokens

Test #26:

score: 0
Accepted
time: 82ms
memory: 13620kb

input:

5000
3767 2505
2247 919
1905 264
4444 3677
3520 2422
2100 3528
1772 3099
3359 696
1968 2916
628 2230
2085 4728
4005 2948
1533 405
4238 4640
2680 3523
1106 1150
4122 3975
2798 3299
291 4146
1804 610
4229 1072
4114 283
2802 4242
680 3455
3108 3708
1598 3806
1995 1007
3227 3913
1011 2064
4895 704
3227 ...

output:

84678533164
84567568696
85002197688
84754591056
84728000354
84634520348
84521619194
84510988310
84400369384
84520036058
84670579590
84662067464
84538521586
84545245894
84501370662
84507734896
84838911858
84652926136
84863963396
84608649096

result:

ok 20 tokens

Test #27:

score: 0
Accepted
time: 90ms
memory: 13080kb

input:

5000
3113 144
144 1603
1603 3037
3037 2005
2005 3914
3914 3168
3168 2140
2140 382
382 2623
2623 1812
1812 2247
2247 392
392 4794
4794 4015
4015 356
356 2204
2204 1683
1683 42
42 3121
3121 4392
4392 4570
4570 2361
2361 3363
3363 2666
2666 3807
3807 1138
1138 4892
4892 4256
4256 97
97 1800
1800 3550
3...

output:

83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000
83283340000

result:

ok 20 tokens

Test #28:

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

input:

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

output:

480

result:

ok "480"

Test #29:

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

input:

100
11 86
86 27
27 90
90 69
69 3
3 76
76 15
15 19
19 75
75 5
5 61
61 1
1 50
50 88
88 25
25 42
42 72
72 59
59 87
87 14
14 22
22 100
100 21
21 80
80 6
6 24
24 94
94 46
46 78
78 18
18 98
98 70
70 45
45 91
91 30
30 40
40 67
67 64
64 81
81 74
74 79
79 83
83 23
23 16
16 34
34 52
52 68
68 65
65 2
2 95
95 4...

output:

646800

result:

ok "646800"

Test #30:

score: 0
Accepted
time: 3ms
memory: 12316kb

input:

1000
624 487
487 80
80 506
506 672
672 240
240 651
651 864
864 344
344 830
830 636
636 759
759 701
701 803
803 489
489 915
915 708
708 612
612 752
752 591
591 579
579 997
997 446
446 511
511 364
364 305
305 377
377 281
281 275
275 502
502 632
632 340
340 557
557 109
109 61
61 12
12 620
620 882
882 3...

output:

664668000

result:

ok "664668000"

Test #31:

score: 0
Accepted
time: 4ms
memory: 14660kb

input:

5000
4763 1341
1341 4951
4951 766
766 4202
4202 2004
2004 1743
1743 4734
4734 142
142 3556
3556 415
415 2231
2231 3768
3768 2881
2881 248
248 2295
2295 827
827 4832
4832 3311
3311 3966
3966 1233
1233 4497
4497 4226
4226 2134
2134 313
313 206
206 4704
4704 721
721 4337
4337 4445
4445 4230
4230 696
69...

output:

83283340000

result:

ok "83283340000"

Test #32:

score: 0
Accepted
time: 4ms
memory: 13504kb

input:

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

output:

81172
84364
83300
83300
83300
81172
85400
83300
85400
86272
86272
82240
86272
86272
84364
82240
86272
86272
86272
83300
81172
82240
81172
83300
81172
81172
86272
82240
82240
83300
82240
83300
84364
83300
81172
82240
83300
84364
86272
86272
84364
82240
83300
85400
84364
81172
86272
81172
83300
86272
...

result:

ok 100 tokens

Test #33:

score: 0
Accepted
time: 4ms
memory: 13144kb

input:

100
87 68
68 84
84 37
37 24
24 76
76 49
49 10
10 65
65 47
47 46
46 73
73 53
53 19
19 78
78 21
21 71
71 55
55 56
56 83
87 28
28 23
23 40
40 22
22 93
93 41
41 26
26 18
18 98
98 4
4 27
27 25
25 42
42 70
70 51
51 30
30 13
13 99
99 15
87 54
54 88
88 20
20 67
67 69
69 5
5 31
31 3
3 80
80 9
9 44
44 12
12 3...

output:

658352
658352
676368
671832
680712
662800
658352
680712
662800
680712
671832
658352
667310
671832
680712
671832
667310
680712
680712
667310
662800
676368
662800
671832
667310
667310
680712
671832
658352
658352
662800
671832
667310
671832
671832
671832
676368
658352
658352
680712
680712
680712
671832...

result:

ok 50 tokens

Test #34:

score: 0
Accepted
time: 3ms
memory: 12492kb

input:

100
91 35
35 83
83 62
62 70
70 30
30 24
24 5
5 93
93 12
91 44
44 39
39 87
87 58
58 100
100 46
46 18
18 71
71 66
91 42
42 32
32 55
55 50
50 51
51 69
69 21
21 13
13 86
91 2
2 64
64 14
14 74
74 34
34 98
98 88
88 31
31 77
91 22
22 61
61 27
27 75
75 96
96 3
3 29
29 99
99 63
91 72
72 4
4 8
8 94
94 40
40 1...

output:

680712
662800
658352
680712
662800
667310
680712
667310
662800
662800
680712
658352
671832
680712
667310
662800
680712
671832
662800
658352
680712
658352
680712
680712
676368
671832
658352
667310
676368
662800

result:

ok 30 tokens

Test #35:

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

input:

1000
91 529
529 538
538 189
189 815
815 122
122 756
756 635
635 65
65 469
469 905
905 602
602 410
410 379
379 353
353 188
188 268
268 501
501 701
701 435
435 43
43 168
168 977
977 327
327 775
775 936
936 729
729 579
579 2
2 823
823 409
409 74
74 523
523 45
45 675
675 697
697 358
358 703
703 157
157 ...

output:

668248632
666328000
665863592
667280680
666801550

result:

ok 5 tokens

Test #36:

score: 0
Accepted
time: 71ms
memory: 13216kb

input:

5000
279 2655
2655 499
499 2609
2609 1871
1871 527
527 1321
1321 674
674 3726
3726 2011
2011 3259
3259 2852
2852 1234
1234 2310
2310 3076
3076 2135
2135 2557
2557 4954
4954 32
32 3955
3955 93
93 3821
3821 608
608 3350
3350 728
728 4320
4320 2681
2681 798
798 3171
3171 825
825 2410
2410 722
722 4713
...

output:

83348903680
83373243832
83336865010
83336865010
83373243832
83336865010
83336865010
83373243832
83324973340
83336865010
83324973340
83373243832
83348903680
83336865010
83313317992
83324973340
83313317992
83324973340
83324973340
83373243832

result:

ok 20 tokens

Test #37:

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

input:

20
4 12
12 14
12 17
14 6
6 9
9 1
14 10
10 2
6 11
17 15
11 16
1 20
1 18
11 8
10 5
9 3
3 13
2 7
18 19
20
17 7
17 1
7 16
7 20
16 9
20 15
9 3
9 4
4 6
6 19
4 13
20 14
16 8
13 10
1 11
19 12
6 5
13 2
3 18
20
19 10
19 15
15 2
15 11
2 17
2 12
10 14
14 16
12 7
11 13
13 6
10 18
13 8
16 5
5 1
1 4
17 9
16 20
4 3...

output:

5058
5002
4870
4928
4898
4970
4906
4936
4964
4850
4816
4898
4980
4944
5028
4898
4952
4900
4904
4844
4892
4838
4842
4936
4948
4854
4882
4976
4910
4894
4898
4924
4878
4898
4964
4830
4876
4958
4824
4860
4888
4918
4952
4928
4928
4872
4866
4840
4808
4954
4920
4866
4970
4908
4982
5008
4932
4910
4944
4894
...

result:

ok 250 tokens

Test #38:

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

input:

100
10 65
65 93
10 54
54 78
54 81
81 74
81 27
78 32
32 99
32 15
15 98
27 82
98 18
15 47
65 55
98 9
74 76
47 91
27 20
91 35
99 29
35 6
6 80
47 33
9 13
33 62
93 83
20 26
91 57
78 79
99 89
13 25
76 63
18 41
13 30
57 75
89 12
76 44
41 8
74 14
83 43
6 58
26 31
31 92
62 51
89 77
18 7
33 85
8 4
7 70
12 53
...

output:

698540
695022
695544
693608
694546
696688
694526
697236
697800
686442
694472
699198
690618
690410
693386
692436
699556
695424
691452
691762
685694
690498
694852
697398
695928
693838
685014
697886
686990
691722
698960
687670
697300
698154
700262
691530
686624
697618
694044
704286
693212
698356
697758...

result:

ok 50 tokens

Test #39:

score: 0
Accepted
time: 6ms
memory: 13372kb

input:

1000
493 610
493 273
273 194
610 177
177 850
850 881
881 585
881 968
610 276
276 759
194 139
177 533
273 343
759 635
194 974
974 268
968 476
476 793
968 149
585 171
149 648
343 380
476 463
171 983
850 515
268 773
773 147
380 884
773 556
884 18
635 237
149 847
533 928
139 3
648 552
847 413
515 440
17...

output:

703048258
707147590
704036142
704436944
703599018

result:

ok 5 tokens

Test #40:

score: 0
Accepted
time: 70ms
memory: 12724kb

input:

5000
2463 4578
4578 2181
2463 4341
2181 277
4341 4963
277 4422
2181 4813
277 99
4813 1631
99 480
4341 977
99 636
977 1124
1124 3792
1631 4145
636 1260
3792 3188
3792 3606
977 4356
4145 1413
4422 809
636 446
480 1256
3606 3092
1256 3426
3092 2282
809 1823
4813 2723
446 1774
809 2017
1413 3065
4578 46...

output:

87833625464
87914794198
87785975306
87443880796
87765094428
87587319516
88165559454
88080472266
87675136510
87750913996
87601452870
87495979056
87773872772
87559695204
86939894764
87361016620
87385179258
87638797104
87354728328
87946063194

result:

ok 20 tokens

Test #41:

score: 0
Accepted
time: 73ms
memory: 14204kb

input:

5000
4244 3101
3101 239
239 1060
3101 4909
239 3997
4244 5
5 2683
3997 546
5 1774
1774 4438
3997 3561
4909 2507
1774 1699
1699 4931
4909 4840
3561 3752
2683 3570
4840 2881
546 1548
4438 899
546 1252
4840 2106
2106 4015
2507 2461
2881 444
4438 2456
1548 947
4931 1470
3752 3068
3561 1193
1699 2291
375...

output:

87783737650
88005609122
87892630316
87387103168
88167218266
87795408662
87914958024
87945220292
87894786034
88151415868
88183068898
88116992628
87720707770
87683438194
88466606050
87456851242
87701721288
87641325250
87995998210
87501567256

result:

ok 20 tokens

Test #42:

score: 0
Accepted
time: 42ms
memory: 13016kb

input:

5000
502 2694
613 2694
1789 2694
2753 2694
4650 502
3736 502
3388 502
582 502
1754 502
4226 613
495 613
749 613
1476 613
587 613
3889 1789
4045 1789
3165 1789
1311 1789
3661 1789
2200 2753
1736 2753
2378 2753
4089 2753
3933 2753
3175 4650
4166 4650
1617 4650
2456 4650
1349 4650
3227 3736
387 3736
39...

output:

108151028328
101991097124
104598483542
101991097124
101991097124
101991097124
101991097124
108151028328
108151028328
101991097124
108151028328
108151028328
101991097124
108151028328
104598483542
108151028328
95733951294
95733951294
95733951294
108151028328

result:

ok 20 tokens

Test #43:

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

input:

5000
3921 3134
2024 3134
3571 3921
4460 3921
1153 3921
4109 2024
1323 2024
3419 2024
2813 3571
2595 3571
1493 3571
3402 4460
3543 4460
4307 4460
598 1153
3566 1153
3918 1153
3636 4109
3702 4109
749 4109
2326 1323
3829 1323
3057 1323
604 3419
3995 3419
2855 3419
4050 2813
2302 2813
2413 2813
691 2595...

output:

101991097124
101991097124
95733951294
108151028328
108151028328
108151028328
95733951294
108151028328
108151028328
101991097124
104598483542
101991097124
95733951294
108151028328
104598483542
104598483542
108151028328
108151028328
101991097124
108151028328

result:

ok 20 tokens

Test #44:

score: 0
Accepted
time: 39ms
memory: 13140kb

input:

5000
4566 2541
2047 2541
1384 2541
3258 2541
199 4566
4215 4566
2695 4566
4585 4566
3464 4566
785 2047
4938 2047
114 2047
4976 2047
952 2047
2096 1384
3893 1384
2801 1384
3559 1384
2884 1384
187 3258
2212 3258
698 3258
2135 3258
2354 3258
2985 199
4913 199
4826 199
2603 199
4117 199
1761 4215
575 42...

output:

108151028328
104598483542
108151028328
104598483542
104598483542
108151028328
108151028328
104598483542
108151028328
95733951294
104598483542
101991097124
104598483542
104598483542
101991097124
101991097124
101991097124
108151028328
104598483542
101991097124

result:

ok 20 tokens

Test #45:

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

input:

100
39 17
86 17
24 17
56 39
70 39
8 39
52 39
55 86
67 86
82 86
98 86
43 24
9 24
14 24
19 24
5 56
73 56
63 56
76 56
41 70
21 70
29 70
75 70
72 8
2 8
26 8
71 8
80 52
27 52
48 52
90 52
87 55
100 55
16 55
11 55
35 67
12 67
54 67
7 67
25 82
6 82
10 82
97 82
94 98
81 98
49 98
23 98
59 43
58 43
57 43
61 43...

output:

812466
778546
812466
836478
778546
742674
812466
812466
778546
778546
836478
836478
778546
836478
742674
836478
812466
812466
742674
812466
836478
836478
778546
742674
812466
812466
778546
742674
742674
742674
742674
778546
778546
742674
778546
836478
742674
778546
836478
742674
778546
742674
778546...

result:

ok 50 tokens

Test #46:

score: 0
Accepted
time: 4ms
memory: 12448kb

input:

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

output:

98632
89616
98632
98632
95498
95498
103028
103028
95498
95498
95498
103028
89616
98632
95498
98632
103028
98632
95498
95498
98632
95498
95498
98632
95498
95498
95498
95498
95498
103028
89616
98632
103028
103028
98632
95498
103028
89616
98632
103028
89616
89616
95498
103028
103028
98632
98632
95498
9...

result:

ok 100 tokens

Test #47:

score: 0
Accepted
time: 16ms
memory: 13076kb

input:

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

output:

87420
87668
82636
85506
84928
85008
87038
86636
84708
87330
84826
83344
83242
83872
88228
85878
85526
85564
82370
85588
82378
82550
82808
88106
85318
86424
86128
83086
85514
84688
85728
83880
84208
87806
87948
86118
82628
83692
82812
83930
84728
88188
84920
84846
83856
83626
86268
86264
85120
86236
...

result:

ok 1000 tokens

Test #48:

score: 0
Accepted
time: 23ms
memory: 12888kb

input:

100
89 8
69 89
44 69
2 44
38 2
23 38
73 23
29 73
12 29
66 12
20 66
43 20
18 43
58 18
49 58
45 49
16 45
92 16
41 92
3 41
94 3
80 94
79 80
86 79
1 86
65 1
50 65
90 50
19 90
57 19
78 57
25 78
32 25
59 32
17 59
35 17
75 80
24 65
81 1
77 17
70 66
31 23
64 73
98 58
76 8
72 50
14 1
97 1
62 78
82 80
15 1
34...

output:

668798
675846
671798
667824
666874
672736
666550
667496
666352
672546
669562
673970
668608
672898
668006
666486
669562
671342
675166
669526
668984
670816
668992
669154
670036
670182
674964
673178
666938
671608
673274
673452
674786
673784
665414
669146
667310
665418
666344
675520
668936
668078
671470...

result:

ok 500 tokens

Test #49:

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

input:

1000
849 134
600 849
511 600
907 511
910 907
245 910
660 245
674 660
564 674
30 564
487 30
175 487
834 175
54 834
271 54
558 271
204 558
741 204
104 741
438 104
10 438
537 10
526 537
723 526
544 723
801 544
454 801
884 454
553 884
517 553
645 517
293 645
994 293
685 994
100 685
956 100
905 956
410 9...

output:

667289570
667214310
667194486
667267936
667192428
667307604
667194566
667414664
667291620
667230234
667319560
667299496
667364974
667251948
667214278
667186470
667307732
667277710
667230134
667250102
667218366
667297518
667249882
667361210
667210510
667232060
667186554
667248152
667235992
667176604
...

result:

ok 50 tokens

Test #50:

score: 0
Accepted
time: 83ms
memory: 14544kb

input:

5000
900 1606
1336 900
359 1336
4780 359
2571 4780
78 2571
1831 78
3611 1831
1079 3611
388 1079
3203 388
2650 3203
4595 2650
1512 4595
4388 1512
1771 4388
2354 1771
678 2354
4745 678
4011 4745
3312 4011
874 3312
3192 874
4411 3192
1795 4411
4704 1795
2268 4704
3604 2268
4997 3604
2139 4997
3928 2139...

output:

83326654690
83326125540
83325666056
83325695986
83325706208
83325795998
83326364808
83326145532
83325925700
83325895834
83325895762
83325805964
83325915710
83326255358
83325825760
83326644672
83325865772
83325286572
83325755914
83326075230

result:

ok 20 tokens

Test #51:

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

input:

5000
36 2446
373 36
11 373
1809 11
926 1809
3349 926
4687 3349
4497 4687
695 4497
4421 695
1129 4421
3326 1129
225 3326
1045 225
3852 1045
4425 3852
1578 4425
2207 1578
1631 2207
247 1631
2382 247
4060 2382
987 4060
4407 987
4761 4407
3093 4761
3299 3093
2340 3299
1817 2340
167 1817
529 167
3781 529...

output:

83378426350
83378646266
83378436728
83378875508
83379085078
83378985394
83379314652
83379285678
83380302194
83378676292
83378555892
83380781646
83377727870
83378956220
83380242738
83379594176
83378436572
83380022950
83379244898
83378925834

result:

ok 20 tokens

Test #52:

score: 0
Accepted
time: 86ms
memory: 14188kb

input:

10000
2119 1089
5715 9048
6676 8247
6238 3451
7174 7340
2776 1170
9259 9946
643 4442
5974 417
9138 3395
7853 4788
9181 3651
2633 2058
7120 4051
7689 4749
9003 6480
1919 4782
5459 1931
3617 8959
3776 5610
9737 5095
2829 1285
5526 1538
7564 7673
4137 9151
431 5288
9225 7248
1760 1079
9775 1805
6042 29...

output:

673959184764
674308431576
674791677754
674425165290
674657003072
676490758738
676322240104
676272022702
675268862378
678301798344

result:

ok 10 tokens

Test #53:

score: 0
Accepted
time: 93ms
memory: 13064kb

input:

10000
7579 4354
7837 2353
9716 9621
3249 5202
128 7759
9297 2273
6324 6504
7923 9353
8197 2685
5584 5768
319 61
549 2736
2225 5788
5891 2007
6127 3923
7072 5879
8543 4270
7092 3198
4204 6685
2205 9423
2759 7747
5995 7776
8144 1194
804 826
9825 2942
2721 2332
1268 8861
1504 6968
9160 2973
2832 2421
4...

output:

674473511776
675565326394
676192430620
673304375920
677381988144
676402628422
674673535188
675134379440
675171449746
677577222992

result:

ok 10 tokens

Test #54:

score: 0
Accepted
time: 143ms
memory: 15644kb

input:

50000
36134 46091
27888 9672
3168 25711
26881 34211
48456 22782
29692 5796
6904 7240
6464 6558
23697 44098
32781 312
18453 15267
37512 30491
47260 7289
1450 48885
10688 19938
2241 8280
44480 34467
12830 12363
23233 25189
27382 9064
28040 47490
7153 26797
4353 40445
6942 35099
11772 38919
27981 34538...

output:

83936633068782
84024739817202

result:

ok 2 tokens

Test #55:

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

input:

100000
72000 14481
17619 64613
92336 99792
28852 958
70321 70251
49849 43436
16059 26735
75277 6368
18380 28559
77376 63567
89540 84544
99941 74511
2921 85053
30707 74942
1445 91011
62757 34747
31043 58006
23514 83275
60085 95643
37013 45141
29809 53788
7357 94214
90959 80967
31007 97007
76685 20815...

output:

669406200606312

result:

ok "669406200606312"

Test #56:

score: 0
Accepted
time: 198ms
memory: 17380kb

input:

100000
72448 40984
99616 48762
18021 42239
60693 278
93498 61886
96265 56653
83175 30765
10439 10534
98743 76546
81340 26573
62043 56284
84923 58449
42503 88828
74969 25220
29716 91271
24304 5694
11869 38437
19296 75163
90626 35493
62538 21816
73415 74455
75796 92602
74582 1904
37383 13927
52345 396...

output:

670239562748750

result:

ok "670239562748750"

Test #57:

score: 0
Accepted
time: 226ms
memory: 24020kb

input:

100000
25401 80115
80115 8125
8125 51263
51263 16112
16112 52056
52056 8518
8518 16914
16914 13241
13241 58165
58165 82756
82756 39925
39925 51317
51317 84540
84540 34281
34281 48857
48857 66402
66402 96345
96345 30704
30704 72457
72457 20191
20191 77924
77924 8205
8205 71818
71818 72048
72048 17681...

output:

666646666800000

result:

ok "666646666800000"

Test #58:

score: 0
Accepted
time: 11ms
memory: 14560kb

input:

13123
3191 12915
12915 10126
10126 2540
2540 6133
6133 10160
10160 9399
9399 8686
8686 13121
13121 6840
6840 8322
8322 5867
5867 12058
12058 10163
10163 7410
7410 11829
11829 446
446 9197
9197 11061
11061 2359
2359 1968
1968 3846
3846 5469
5469 5834
5834 4505
4505 11609
11609 4788
4788 12991
12991 4...

output:

1506290852484

result:

ok "1506290852484"

Test #59:

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

input:

10000
2417 7202
7202 8447
8447 4337
4337 8072
8072 5845
5845 5892
5892 1904
1904 9456
9456 6480
6480 9345
9345 2810
2810 1989
1989 4121
4121 7002
7002 9674
9674 1286
1286 1349
1349 9214
9214 4981
4981 2027
2027 9282
9282 6206
6206 3149
3149 8031
8031 5094
5094 8299
8299 2047
2047 2437
2437 7950
7950...

output:

666729057430
666826487832
666826487832
666586635992
666586635992
666586635992
666633280000
666633280000
666633280000
666633280000

result:

ok 10 tokens

Test #60:

score: 0
Accepted
time: 83ms
memory: 14096kb

input:

10000
8514 264
264 481
481 6890
6890 1990
1990 9628
9628 6384
6384 5672
5672 5806
5806 6563
6563 8608
8608 537
537 480
480 4146
4146 3615
3615 5132
5132 8059
8059 7945
7945 2782
2782 6279
6279 704
704 3879
3879 6340
6340 1877
1877 3488
3488 8505
8505 6846
6846 1781
1781 2717
2717 6175
6175 4842
4842...

output:

666633280000
666729057430
666633280000
666680872860
666633280000
666586635992
666633280000
666729057430
666826487832
666729057430

result:

ok 10 tokens

Test #61:

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

input:

50000
49542 32423
32423 31108
31108 9883
9883 17304
17304 17599
17599 21383
21383 11512
11512 47213
47213 36204
36204 33095
33095 25697
25697 24476
24476 37282
37282 13101
13101 25045
25045 38820
38820 37875
37875 25139
25139 41118
41118 40822
40822 491
491 13772
13772 32566
32566 22703
22703 23534
...

output:

83333690078550
83332499733340

result:

ok 2 tokens

Test #62:

score: 0
Accepted
time: 190ms
memory: 20584kb

input:

100000
97536 6751
6751 17160
17160 45020
45020 30596
30596 45612
45612 63578
63578 63929
63929 88661
88661 70379
70379 90440
90440 39359
39359 93888
93888 46252
46252 18951
18951 97266
97266 69212
69212 73174
73174 40376
40376 57426
57426 57177
57177 48105
48105 8944
8944 98697
98697 74576
74576 778...

output:

666658666359992

result:

ok "666658666359992"

Test #63:

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

input:

100000
51153 73085
73085 12582
12582 7878
7878 461
461 1914
1914 98489
98489 80812
80812 83558
83558 93808
93808 51876
51876 23774
23774 1109
1109 61864
61864 51971
51971 23579
23579 13383
13383 42525
42525 21704
21704 36615
36615 12634
12634 92209
92209 12924
12924 25548
25548 18143
18143 31260
312...

output:

666663332800000

result:

ok "666663332800000"

Test #64:

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

input:

10000
6000 4261
6000 4359
4261 8722
4261 9518
8722 4380
8722 7322
9518 3683
4359 7561
4380 4180
4180 8941
7561 6830
7561 9619
3683 9513
8941 8822
9619 6218
7322 7610
8941 7912
9518 8735
9513 5016
6830 9473
7610 8791
7322 2437
4359 6154
4380 3781
7610 7971
5016 1408
8822 3539
8822 8421
9473 8605
7971...

output:

699662938988
704719861596
700211446486
700449499222
699007357796
702463734658
698871846288
697797400584
699694620558
700685359854

result:

ok 10 tokens

Test #65:

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

input:

10000
9564 4260
9564 8281
8281 5433
8281 3378
4260 2756
3378 1886
2756 7379
4260 7010
7010 5755
3378 218
2756 7407
5433 2221
2221 6689
7010 9043
218 9603
9043 9969
9603 3269
9043 2505
7379 8800
9969 6819
7379 1136
9969 3202
9603 81
218 901
7407 7819
81 33
5755 7972
901 6558
7819 7041
2505 860
860 62...

output:

698937805658
699961616694
699510813792
700946996722
701372111738
698580860132
704939184204
703402095880
701629140064
700122191326

result:

ok 10 tokens

Test #66:

score: 0
Accepted
time: 136ms
memory: 15680kb

input:

50000
31605 40646
40646 19475
40646 2422
31605 37534
19475 36999
36999 2219
19475 43170
37534 13047
36999 41741
2422 42808
2219 11548
2219 40064
13047 41426
13047 8605
41741 17828
40064 10141
40064 20312
10141 26479
20312 29237
37534 16771
16771 3161
42808 45126
42808 31040
41741 47688
47688 20480
4...

output:

87231741627382
87071830074104

result:

ok 2 tokens

Test #67:

score: 0
Accepted
time: 190ms
memory: 17120kb

input:

100000
7069 53014
7069 35644
35644 57955
57955 80855
57955 81215
80855 72107
80855 68568
72107 41484
68568 4757
53014 44456
35644 71125
41484 92749
41484 85048
44456 48982
53014 74888
48982 71157
71125 11774
48982 85265
85048 62458
72107 54166
4757 43495
92749 40806
43495 40116
74888 41338
81215 181...

output:

697673363098932

result:

ok "697673363098932"

Test #68:

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

input:

10000
4261 6000
4359 6000
8722 4261
9518 4261
4380 4261
7322 4359
3683 4359
7561 4359
4180 8722
8941 8722
6830 8722
9619 9518
9513 9518
8822 9518
6218 4380
7610 4380
7912 4380
8735 7322
5016 7322
9473 7322
8791 3683
2437 3683
6154 3683
3781 7561
7971 7561
1408 7561
3539 4180
8421 4180
8605 4180
7700...

output:

808681756150
838255723262
766166959862
838255723262
838255723262
766166959862
838255723262
808681756150
808681756150
766166959862

result:

ok 10 tokens

Test #69:

score: 0
Accepted
time: 90ms
memory: 16948kb

input:

100000
73953 19330
32615 19330
84431 19330
11781 19330
53886 73953
31309 73953
2321 73953
62000 73953
60014 73953
31402 32615
45046 32615
92313 32615
31036 32615
38396 32615
96568 84431
59350 84431
76504 84431
73420 84431
97470 84431
45530 11781
45572 11781
17211 11781
50917 11781
99222 11781
73945 ...

output:

857251078358328

result:

ok "857251078358328"

Test #70:

score: 0
Accepted
time: 86ms
memory: 13312kb

input:

10000
7621 6255
1033 7621
5481 1033
2488 5481
3279 2488
3597 3279
689 3597
4896 689
5545 4896
3296 5545
4178 3296
4001 4178
8159 4001
6629 8159
6176 6629
8568 6176
3543 8568
5139 3543
7224 5139
3359 7224
4932 3359
8933 4932
6130 8933
6171 6130
6697 6171
3807 6697
4929 3807
4745 4929
4560 4745
2912 4...

output:

666653862454
666654641872
666654861634
666654362368
666653762460
666655820934
666653642588
666650625014
666652803184
666656020766

result:

ok 10 tokens

Test #71:

score: 0
Accepted
time: 86ms
memory: 14400kb

input:

10000
9104 3617
8975 9104
5950 8975
2703 5950
2011 2703
2816 2011
1287 2816
796 1287
6026 796
2551 6026
9295 2551
8875 9295
9287 8875
9852 9287
5957 9852
1591 5957
764 1591
6153 764
8452 6153
4251 8452
9832 4251
8213 9832
5535 8213
839 5535
9817 839
8320 9817
900 8320
5976 900
2250 5976
9717 2250
24...

output:

666655161900
666654881840
666652223734
666654642172
666655821326
666654302262
666653043012
666651684200
666655721208
666654342134

result:

ok 10 tokens

Test #72:

score: 0
Accepted
time: 118ms
memory: 15720kb

input:

50000
16813 41324
8574 16813
35700 8574
2290 35700
15754 2290
10088 15754
7870 10088
22360 7870
11259 22360
12344 11259
36913 12344
6279 36913
31263 6279
7547 31263
14369 7547
15488 14369
14296 15488
29110 14296
19509 29110
32484 19509
49585 32484
1095 49585
25647 1095
24942 25647
41957 24942
35073 ...

output:

83339927807884
83339927908962

result:

ok 2 tokens

Test #73:

score: 0
Accepted
time: 121ms
memory: 16336kb

input:

50000
9755 36575
33095 9755
9749 33095
7755 9749
43898 7755
35345 43898
17016 35345
21764 17016
6161 21764
43450 6161
32172 43450
19065 32172
9017 19065
45278 9017
1908 45278
38853 1908
10111 38853
2489 10111
40638 2489
9568 40638
43983 9568
27552 43983
3072 27552
28985 3072
18445 28985
32666 18445
...

output:

83339914909490
83339912712942

result:

ok 2 tokens

Test #74:

score: 0
Accepted
time: 229ms
memory: 21088kb

input:

100000
61228 42073
10958 61228
69996 10958
22976 69996
84141 22976
32021 84141
28595 32021
21133 28595
71566 21133
2677 71566
9986 2677
27413 9986
91866 27413
47252 91866
21638 47252
2480 21638
3210 2480
44232 3210
44767 44232
34274 44767
26605 34274
58506 26605
6809 58506
46614 6809
71228 46614
759...

output:

666661500424746

result:

ok "666661500424746"

Test #75:

score: 0
Accepted
time: 207ms
memory: 20044kb

input:

100000
5993 32592
77609 5993
69890 77609
36847 69890
21272 36847
30568 21272
79690 30568
66580 79690
25194 66580
52309 25194
60206 52309
20849 60206
59074 20849
4519 59074
20017 4519
94058 20017
66932 94058
40223 66932
70593 40223
88054 70593
17340 88054
31723 17340
60477 31723
88096 60477
6728 8809...

output:

666667499907792

result:

ok "666667499907792"

Extra Test:

score: 0
Extra Test Passed