QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334964#6111. Two PathsTeracAC ✓847ms172028kbC++149.2kb2024-02-22 15:38:392024-02-22 15:38:39

Judging History

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

  • [2024-02-22 15:38:39]
  • 评测
  • 测评结果:AC
  • 用时:847ms
  • 内存:172028kb
  • [2024-02-22 15:38:39]
  • 提交

answer

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

namespace IO {
	#if ONLINE_JUDGE
	#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
	#else
	#define getc() getchar()
	#endif
	const int IL = 1 << 21, OL = 1 << 21;
	int olen = 0;
	char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
	inline int read() {
		register char ch = getc(); register int x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		return x * f;
	}
	inline double readdb() {
		register char ch = getc(); register double x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		if(ch == '.') {
			register double b = 0.1;
			ch = getc();
			while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
		}
		return x * f;
	}
	inline int readstr(char *s) {
		register char ch = getc(); register int len = 0;
		while(!isalpha(ch)) ch = getc();
		while(isalpha(ch)) s[++len] = ch, ch = getc();
		return len;
	}
	inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
	inline void putc(register char ch) { obuf[olen++] = ch; }
	template<class T>
	inline void write(register T x) {
		if(x < 0) obuf[olen++] = '-', x = -x;
		if(x > 9) write(x / 10);
		obuf[olen++] = x % 10 + 48;
	}
} using namespace IO;
const int N = 2e5 + 10;
const ll inf = 1e15;
int n, q, m, p[N];
ll a[N], b[N];
struct edge {
	int to, w, nxt;
} e[N << 1];
vector<int> E[N];
int head[N], ecnt;
void addedge(int u, int v, int w) {
	e[++ecnt] = {v, w, head[u]};
	head[u] = ecnt;
}
int S, T, fa[N], dfn[N], dep[N], tim;
ll dis[N], mx[N], sec[N], mxid[N], dis2[N];
bool vis[N];
void dfs0(int u, int f) {
	if(dis[u] > dis[S]) S = u;
	for(int i = head[u], v; i; i = e[i].nxt) {
		v = e[i].to;
		if(v == f) continue;
		E[u].push_back(v);
		dis[v] = dis[u] + e[i].w;
		dfs0(v, u);
	} 
}
int top[N];
void dfs(int u, int f) {
	dep[u] = dep[f] + 1, fa[u] = f, dfn[u] = ++tim;
	for(int i = head[u], v; i; i = e[i].nxt) {
		v = e[i].to;
		if(v == f) continue;
		dfs(v, u);
	}
}
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
int L[N], R[N];
namespace st_table {
	int st[20][N];
	inline int Min(int u, int v) { return dep[u] < dep[v] ? u : v; } 
	void init() {
		for(int i = 1; i <= n; i++)
			st[0][dfn[i]] = i;
		for(int i = 1; (1 << i) <= n; i++)
			for(int j = 1; j + (1 << i) - 1 <= n; j++)
				st[i][j] = Min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	}
	inline int query(int l, int r) {
		int L = 31 ^ __builtin_clz(r - l + 1);
		return Min(st[L][l], st[L][r - (1 << L) + 1]);
	}
} using namespace st_table;
inline int LCA(int u, int v) {
	if(u == v) return u;
	if(dfn[u] > dfn[v]) swap(u, v);
	return fa[query(dfn[u] + 1, dfn[v])];
}
inline ll Dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[LCA(u, v)]; }
void dfs2(int u, int id) {
	top[u] = id;
	L[u] = u, R[u] = u;
	for(int i = head[u], v; i; i = e[i].nxt) {
		v = e[i].to;
		if(vis[v] || v == fa[u]) continue;
		dfs2(v, id);
		int tmp[4] = {L[u], R[u], L[v], R[v]};
		for(int i = 0; i < 4; i++)
			for(int j = i + 1; j < 4; j++)
				if(Dis(tmp[i], tmp[j]) > Dis(L[u], R[u])) L[u] = tmp[i], R[u] = tmp[j];
		if(mx[v] + e[i].w > mx[u]) sec[u] = mx[u], mx[u] = mx[v] + e[i].w, mxid[u] = v;
		else sec[u] = mx[v] + e[i].w;
	}
}
struct ST_table {
	ll st[20][N];
	void init(ll *a, int n) {
		for(int i = 1; i <= n; i++)
			st[0][i] = a[i];
		for(int i = 1; (1 << i) <= n; i++)
			for(int j = 1; j + (1 << i) - 1 <= n; j++)
				st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	}
	inline ll query(int l, int r) {
		int L = 31 ^ __builtin_clz(r - l + 1);
		return max(st[L][l], st[L][r - (1 << L) + 1]);
	}
} s1, s2;
inline int get(int u, int v) { return *--upper_bound(E[u].begin(), E[u].end(), v, cmp); }
vector<pair<ll, ll>> t[N << 2];
#define ls x << 1
#define rs x << 1 | 1
inline bool check(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
	return (b.second - c.second) * (a.first - c.first) <= (a.second - c.second) * (b.first - c.first);
}
void build(int x, int l, int r) {
	t[x].push_back({0ll, 0ll});
	if(l == r) return;
	ll res = -1e9;
	for(int i = l; i <= r; i++) {
//		assert(b[i] >= 0);
		if(i != l) {
			while(t[x].size() > 1 && check(make_pair(res, b[i]), t[x].back(), t[x][t[x].size() - 2])) t[x].pop_back();
			t[x].push_back(make_pair(res, b[i]));
		}
		res = max(res, a[i]); 
	}
	int mid = l + r >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}
ll query(int x, int l, int r, int L, int R, ll A, ll B) {
	if(L <= l && r <= R) {
		ll res = -1e14;
		if(L < l) res = max(res, A * s1.query(L, l - 1) + B * s2.query(l, r));
		if(t[x].size() < 2) return res;
		int curl = 1, curr = t[x].size() - 1, mid, ans;
		while(curl <= curr) {
//			cerr << curl << " "<< curr <<endl;
			mid = curl + curr >> 1;
			assert(mid >= 1 && mid <= t[x].size() - 1);
//			cerr << A << " " << t[x][mid].first <<" " << B <<" " << t[x][mid].second << endl;
			if(A * t[x][mid].first + B * t[x][mid].second > A * t[x][mid - 1].first + B * t[x][mid - 1].second)
				ans = mid, curl = mid + 1;
			else curr = mid - 1;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
		}
		return max(res, A * t[x][ans].first + B * t[x][ans].second);
//		return res; 
	}
	ll res = -1e14;
	int mid = l + r >> 1;
	if(mid >= L) res = max(res, query(ls, l, mid, L, R, A, B));
	if(mid < R) res = max(res, query(rs, mid + 1, r, L, R, A, B));
	return res;
}
int main() {
//	if(system("fc my.out path1.out")) return 0;
//	freopen("path1.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	n = read(), q = read();
	for(int i = 1, u, v, w; i < n; i++) {
		u = read(), v = read(), w = read();
		addedge(u, v, w);
		addedge(v, u, w);
	}
	dfs0(1, 0);
	T = S, S = 0;
	memset(dis, 0, sizeof(dis));
	dfs0(T, 0);
	swap(S, T);
	dfs(S, 0);
	init();
	int t = T;
	while(t) { p[++m] = t; vis[t] = 1; t = fa[t]; }
	reverse(p + 1, p + 1 + m);
	for(int i = 1; i <= m; i++)
		dfs2(p[i], i);
	for(int i = 1; i <= m; i++)
		a[i] = dis[p[i]] + mx[p[i]];
	s1.init(a, m);
	for(int i = m - 1; i; i--)
		dis2[p[i]] = dis2[p[i + 1]] + dis[p[i + 1]] - dis[p[i]];
	for(int i = 1; i <= m; i++)
		b[i] = dis2[p[i]] + mx[p[i]];
	s2.init(b, m);
	build(1, 1, m);
//	return 0;
	while(q--) {
		ll ans = 0;
		int u = read(), v = read();
		ll A = read(), B = read();
		if(top[u] == top[v]) {
			int f = LCA(u, v);
			if(u == f) {
				ll a = max(Dis(u, S), Dis(u, T));
				int t = get(u, v);
				ll b = max(Dis(v, L[t]), Dis(v, R[t]));
				ans = max(ans, a * A + b * B);
			}
			else if(v == f) {
				ll a = max(Dis(v, S), Dis(v, T));
				int t = get(v, u);
				ll b = max(Dis(u, L[t]), Dis(u, R[t]));
				ans = max(ans, b * A + a * B);
			}
			else {
				int lca = LCA(u, v);
				ll a1 = max(Dis(u, S), Dis(u, T));
				ll a2 = max(Dis(v, S), Dis(v, T));
				ll b1 = 0, b2 = 0;
				int t1 = get(lca, u), t2 = get(lca, v);
				b1 = max(Dis(u, L[t1]), Dis(u, R[t1]));
				b2 = max(Dis(v, L[t2]), Dis(v, R[t2]));
				ans = max({ans, a1 * A + b2 * B, b1 * A + a2 * B});
			}
		}
		else {
			int f1 = top[u], f2 = top[v];
			if(f1 > f2) swap(f1, f2), swap(u, v), swap(A, B);
			int fa1 = p[f1], fa2 = p[f2];
			int t1, t2;
			if(fa1 != u) t1 = get(fa1, u);
			else t1 = u;
			if(fa2 != v) t2 = get(fa2, v);
			else t2 = v;
			ll b1 = max(Dis(u, L[t1]), Dis(u, R[t1]));
			ll b2 = max(Dis(v, L[t2]), Dis(v, R[t2]));
			ans = A * b1 + B * b2;
			if(u != fa1) ans = max(ans, A * b1 + B * max(Dis(v, S), Dis(v, T)));
			if(v != fa2) ans = max(ans, A * max(Dis(u, S), Dis(u, T)) + B * b2);
			ll c1 = dis[u] - dis[fa1], c2 = dis[v] - dis[fa2];
			if(mxid[fa1] == t1) c1 += sec[fa1];
			else c1 += mx[fa1];
			if(mxid[fa2] == t2) c2 += sec[fa2];
			else c2 += mx[fa2];
			c1 = max(c1, Dis(u, S)), c2 = max(c2, Dis(v, T));
			ans = max(ans, A * c1 + B * c2);
			if(f1 + 1 <= f2 - 1) ans = max(ans, A * c1 + B * (s2.query(f1 + 1, f2 - 1) - dis2[fa2] + dis[v] - dis[fa2]));
			if(f1 + 1 <= f2 - 1) ans = max(ans, A * (s1.query(f1 + 1, f2 - 1) - dis[fa1] + dis[u] - dis[fa1]) + B * c2);
//			ll X = -1e9;
			if(f1 + 1 <= f2 - 1) ans = max(ans, query(1, 1, m, f1 + 1, f2 - 1, A, B) + A * dis[u] - 2 * A * dis[fa1] + B * dis[v] - B * dis2[fa2] - B * dis[fa2]);
//			for(int i = f1 + 1; i <= f2 - 1; i++) {
//				if(i != f1 + 1) ans = max(ans, A * (X - dis[fa1] + dis[u] - dis[fa1]) + B * (dis2[p[i]] + mx[p[i]] - dis2[fa2] + dis[v] - dis[fa2]));
//				X = max(X, dis[p[i]] + mx[p[i]]);
//			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

详细

Test #1:

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

input:

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

output:

18
32
18
160

result:

ok 4 number(s): "18 32 18 160"

Test #2:

score: 0
Accepted
time: 7ms
memory: 51260kb

input:

2 1
1 2 1
1 2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

2 10
1 2 2
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 3 1
1 2 3 2
1 2 3 3
1 2 2 3
1 2 1 3

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

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

input:

10 500000
4 5 576
5 8 218
1 10 678
1 9 2540
7 8 2023
2 7 5510
2 9 8454
4 6 22
3 9 5248
2 5 35782 82142
1 2 95412 85188
4 5 82466 22193
3 6 22169 67901
4 10 67229 30987
1 10 68282 17858
1 8 53726 3246
5 8 13913 74110
2 8 30052 7204
1 4 95255 48216
2 5 41392 98997
3 8 8435 5947
1 5 22067 21610
7 9 343...

output:

674365186
1454303268
477920681
1359445921
1501996827
1320778726
889342640
1582045824
426346196
1792561801
789005461
166905972
478560756
71705653
343648830
901237204
420263788
1710700661
309792440
335240094
1852278021
1679904905
1055408048
1644275016
563316675
602184744
873340490
815015664
1356022267...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 108ms
memory: 72892kb

input:

100 500000
4 63 6394
57 91 2108
5 52 9292
6 63 3151
52 62 1006
13 19 8138
42 59 6102
3 95 275
36 80 8426
20 84 7879
32 100 4423
71 89 9590
55 98 240
46 100 7470
70 92 7417
43 54 6092
24 41 230
93 94 6591
8 92 2558
34 63 7534
4 36 5620
17 93 987
35 96 1288
42 68 6280
72 89 9818
43 57 8266
26 62 2431
...

output:

30730511688
35868047826
94569561805
103860674856
108734641138
103921529851
151172279864
108994447520
79859941598
90637244010
113651189677
26614889256
54138181416
163935808262
43257729984
101945300646
27547811269
67543514171
84292164869
59484837480
117300068794
77146438694
27400485192
55424042658
628...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 326ms
memory: 109684kb

input:

200000 500000
83239 106513 1257
142726 196994 1263
95614 142588 7488
88575 193932 8123
31396 180633 1564
37559 131657 927
143893 157390 740
117889 182920 7831
103309 142289 6864
15478 36228 2717
5896 6815 5902
42275 184396 2646
21903 63571 8966
23873 42450 2721
36540 46154 9467
155293 161123 8588
54...

output:

5966882576104305
7271792958583645
8570461339781342
9614114352538144
6712681170527500
9409581586879995
6304678086998919
6559831613756394
4016495625693024
4381351843519688
4971908463803118
8759545709797016
11418325924391126
8912046248703475
10780907424911508
3112723787504739
9395431732704804
851233289...

result:

ok 500000 numbers

Test #7:

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

input:

10 500000
7 8 6474
3 4 6652
4 5 5193
6 9 457
5 9 3937
1 7 7261
2 5 6472
6 8 6967
3 10 8997
2 9 77462 28703
3 7 31026 16732
2 6 39340 36431
6 9 95641 333
4 8 17377 97247
2 4 20769 98147
4 6 425 42124
4 8 53119 54974
2 4 49307 3731
1 7 13417 95608
7 8 36330 40656
6 10 16594 36336
1 6 47819 1121
1 3 93...

output:

2723123845
841480408
1828727322
1988211389
2006138424
2972774483
878701873
1811610573
1614909795
3697830616
1573037298
1336010492
685083521
3657916506
2557058802
3370810317
3011684921
862077669
2124928512
3326043566
1360831395
1603107540
3131147303
1037179764
1973141216
1587191713
747094784
36277104...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 95ms
memory: 72812kb

input:

100 500000
40 72 2893
46 57 7594
13 90 4014
32 59 8870
4 81 4432
59 94 8856
59 96 4895
96 100 9950
32 80 8362
5 89 1777
36 69 2134
24 62 9978
21 65 3506
49 61 6056
33 48 5740
1 30 4143
30 60 8914
60 70 4900
66 93 6395
10 68 1687
10 95 2472
4 20 3135
2 17 9637
56 78 4429
20 27 2053
52 89 6906
27 39 9...

output:

106913710770
4495733708
102758976134
80160799892
76732267750
47039029473
72520507589
73042063332
73155659164
70949908024
18019999665
55814535350
72254712051
121025392740
66270956091
135577152247
39206666175
97754289402
83622700164
89895046420
147890155522
62926235281
108657350392
100238158900
814086...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 343ms
memory: 107656kb

input:

200000 500000
72622 96340 7225
16757 66347 2999
101297 187932 6437
49037 154632 460
124025 196592 9940
153072 170123 1421
34394 199313 4817
32364 32518 5106
88700 199062 8686
31819 36499 9765
52871 159318 6576
1498 113000 6088
87532 137708 9913
18424 42545 9372
10501 33545 5958
23767 170025 2704
187...

output:

14850031235173232
6999821359673356
13994322220418811
15658897860429808
5566180270698198
7768919631255131
7795054483438192
7419776394069074
12641505965465227
7472188388977804
15268455327661860
10901394489199617
8199280990426768
12441824458056512
5059765147523162
8301785128173369
6921399963160754
9272...

result:

ok 500000 numbers

Test #10:

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

input:

10 500000
7 8 6564
4 8 6189
3 9 5516
2 4 8374
2 9 4364
7 10 7523
6 8 9898
5 8 7016
1 5 2345
5 8 51845 42560
4 5 55887 98340
3 8 49610 54530
9 10 22945 35062
3 8 3458 95253
3 6 23153 11481
1 8 34851 37986
5 9 87362 27198
1 7 55997 43106
1 7 75611 27271
7 8 71599 78148
6 7 34117 75458
2 4 79390 55048
...

output:

1161870605
3095430318
1673745050
1133235480
1802853531
892085090
1010217393
2190048410
2217209026
2761113977
2448810841
2339726206
1900526448
2923869030
1282299167
2882083522
2590862660
2125646342
2738520864
1608180381
1666730547
2125172192
2345809770
1603963890
3685256440
2391830675
183542487
93557...

result:

ok 500000 numbers

Test #11:

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

input:

100 500000
64 80 6288
35 50 3079
47 52 1840
5 69 4588
3 14 5154
76 80 5382
35 60 9496
19 61 9625
71 73 9786
7 46 9867
5 15 9846
14 57 7663
39 52 9476
21 38 3153
44 63 1358
60 67 4899
56 59 302
8 52 104
50 56 2937
28 72 8543
85 91 7835
16 87 5283
29 77 3795
11 84 6769
49 65 1585
45 51 1354
2 89 9853
...

output:

72202925787
97514852513
56756195638
37288713475
35676803180
90017144414
38927158215
28601206274
14400684154
45932515989
77207561276
59432631660
70376380240
78182150824
76907451131
97790656742
61036431338
66756945882
44962902462
95491099215
84137846038
57887416052
58421189377
45768814245
47300757994
...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 368ms
memory: 109820kb

input:

200000 500000
84618 98845 7176
107087 196559 4404
173709 192096 4717
122383 132949 1263
13177 34882 5439
139807 160157 1421
45167 91345 9766
107962 187717 2148
66125 151170 6686
63358 86085 5420
92294 134701 5058
113293 149067 2818
52824 164065 9708
44586 64319 6527
52176 147205 1116
36120 153708 18...

output:

10077660798661166
6673502274389958
12939177208895010
9047200007665110
6573554974664500
5242597508990838
13676616292679150
9704815634833183
11561184450694770
12472403863791083
13122447381660824
13320490331795583
8658969745868196
8796014087160251
13063721599988841
12566284718749275
7973072528332602
11...

result:

ok 500000 numbers

Test #13:

score: 0
Accepted
time: 68ms
memory: 60540kb

input:

10 500000
5 10 9359
6 8 2622
3 4 32
1 5 6291
2 5 4790
6 7 9273
5 7 7916
2 3 1256
7 9 6094
1 4 93524 56417
1 4 72235 21165
1 8 59881 96821
3 7 60649 69792
3 7 40702 86345
2 7 89678 55741
3 7 83505 90656
9 10 91223 25352
6 10 12287 11104
5 8 94433 78823
4 6 19397 21614
2 6 56138 89726
3 7 87392 7152
2...

output:

2513828544
1912738490
2824268570
1764473685
1654088085
1931893217
2364747645
2037769347
362591929
2301745394
631573827
2454351592
1431346800
1917618468
112297763
185018940
1653764936
1250254372
1568465383
1292309244
236168002
506864435
425491147
2028002330
476710384
1808277470
2247989250
1318111291
...

result:

ok 500000 numbers

Test #14:

score: 0
Accepted
time: 114ms
memory: 73740kb

input:

100 500000
8 10 4275
5 60 2756
55 71 6562
46 53 306
40 85 8980
24 97 1909
59 90 8289
58 77 9299
38 74 9722
5 95 9173
34 42 7558
35 92 8051
78 86 5446
29 63 4443
72 78 3872
26 100 246
35 50 203
73 74 2605
53 74 6774
66 81 6888
39 66 4686
31 62 4727
3 92 9440
71 88 4918
18 90 9628
22 46 9995
28 49 991...

output:

65913039086
86901503285
145182328228
51391603893
107334514650
33026739520
141561395797
94885846572
85557851805
95450858526
43327973728
76933550118
105576354578
116690159952
127214406241
57156892577
92243211803
2929303556
60914681674
87520089774
88616664175
89811058923
60767857476
39044073040
6597593...

result:

ok 500000 numbers

Test #15:

score: 0
Accepted
time: 369ms
memory: 109872kb

input:

200000 500000
48263 193405 8782
39826 138335 6086
43411 47049 42
32460 100163 6561
110839 195838 6052
5325 169299 7212
2594 89322 851
46973 138509 8277
45626 176835 6893
94589 172557 9834
46014 69648 1541
10815 31117 7070
123771 141531 2871
72939 179823 4185
68124 69369 7576
127353 144997 9295
96779...

output:

4813047735928155
13563121456000208
10623977740697384
12368325537868986
9906634169705396
15509065513494903
5103499979323596
12246478270010336
14933318539416384
8682385540396731
6020406730020679
14413092183185878
12398399473755534
14259938583507292
11726545588336542
12617036028393990
11053303327631314...

result:

ok 500000 numbers

Test #16:

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

input:

10 500000
3 7 9449
3 5 2159
5 8 355
1 3 1104
6 9 6705
9 10 9535
4 7 5934
4 6 8201
2 4 9843
1 9 92099 2978
2 10 29800 2773
3 9 45959 6408
8 10 55249 4522
1 8 98109 69741
1 7 56836 13930
1 4 7749 81274
3 6 67170 72637
3 4 39522 19991
3 8 28045 8334
1 3 73971 33646
3 8 24965 37029
2 7 24474 60167
3 4 8...

output:

2453361900
871685520
1220462014
1812332947
4040163207
628756398
2068193031
2874055300
862043409
1119822650
1339918304
1007351455
1827572625
1163734879
2383959500
1900098890
2455446271
1823237724
2457600854
2669165980
2242954420
2886332020
2097531384
666029210
2068152260
875855713
3015757786
17857956...

result:

ok 500000 numbers

Test #17:

score: 0
Accepted
time: 117ms
memory: 73152kb

input:

100 500000
14 76 774
6 50 8242
20 77 1284
54 69 3321
7 46 2405
56 64 8435
29 67 7083
19 81 2078
14 95 1146
21 91 7263
17 83 6757
5 43 8439
51 88 8712
15 85 5732
34 89 2194
4 26 1001
50 91 8887
3 37 5105
48 81 1827
42 58 1040
61 79 4242
6 82 6875
44 62 3598
59 91 9962
25 91 4568
59 73 8635
76 100 997...

output:

116400494286
104580113985
68880117122
131948244233
35343773131
100666540698
75158851568
89717230196
104502389946
48973081722
100478141976
91980290003
137115094714
93668643240
107190886884
99570436976
109341640400
113119225372
64886734716
49555552176
103942689145
79245699399
96260733612
93079934826
1...

result:

ok 500000 numbers

Test #18:

score: 0
Accepted
time: 332ms
memory: 109764kb

input:

200000 500000
131798 169313 5103
10660 167741 8275
71369 177082 7071
94023 175057 6285
5236 62128 4118
45145 49844 5960
5469 27531 1940
91347 139404 2938
81422 163356 909
143033 192772 3189
79340 148691 8720
80447 94182 3029
156490 164075 3647
67391 99673 841
19307 109516 858
52393 130048 5572
11053...

output:

10800964533361095
13397792616011778
2840433935282426
4089862708527832
5612515473124553
11282891088637211
14247727524719144
10608965275092284
6469991183666541
14868049842352340
6737187884943531
8881942760307495
6038742155446525
4524630271319190
6043319166641563
5691043644442530
6839751030234923
14050...

result:

ok 500000 numbers

Test #19:

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

input:

10 500000
4 10 9539
2 7 8593
3 10 7974
6 9 9021
2 8 4427
1 7 7094
3 7 6656
5 9 8250
3 6 7783
6 10 66482 73731
2 3 78853 92894
7 9 56229 24507
2 7 25657 39252
3 9 88219 10034
6 10 91291 72118
6 9 68635 77327
2 5 92335 48990
2 6 28564 34863
3 7 64020 60300
1 3 81195 77522
5 10 13705 14899
2 5 74356 64...

output:

3186872772
3564333287
1580076348
1358264459
1826313758
3570749561
2522596215
3871185560
1537932641
2389063080
3575392418
755146211
3924253368
2118317205
2671630920
2305723692
3392396114
2653834329
2323642550
2126838922
2819453713
2894045195
2848017800
2236762853
4134443688
1576405524
3747787953
1784...

result:

ok 500000 numbers

Test #20:

score: 0
Accepted
time: 115ms
memory: 71048kb

input:

100 500000
21 87 4169
33 37 3727
75 84 9110
54 63 1743
48 91 8935
5 22 4961
1 90 1684
23 60 1753
89 93 1083
42 88 1162
50 56 4469
49 70 6123
30 82 4683
23 77 7021
12 24 517
16 33 6349
78 92 275
53 74 7606
22 53 5665
69 72 2089
48 82 6901
6 13 6319
12 97 9243
4 15 8111
7 64 9908
21 34 7276
45 71 3146...

output:

110748389784
38264562297
43359546636
101911021064
30699213294
36015252942
66923406949
122805090233
79042845551
85174670294
76465411077
111600779360
56770476856
124648390450
55383052877
89724504242
104478388504
75640827746
155849821685
132186971658
99149089195
96175712205
92808752603
51408413125
1531...

result:

ok 500000 numbers

Test #21:

score: 0
Accepted
time: 371ms
memory: 109840kb

input:

200000 500000
85651 116999 6112
158097 171696 7424
81082 114242 60
37965 54899 6
125494 187147 2082
49480 63274 3900
35086 198565 7888
20283 122198 9709
784 61133 2439
71605 185908 7979
95753 169217 3965
62954 133637 9554
3981 167663 7799
33102 34663 8954
130446 146696 4934
8205 166566 7149
58213 58...

output:

6629318792107142
10044113522610660
2330988015274776
12278123707454910
12875452078148204
11884913875794177
13377361131534638
4162637141844698
10395433513479830
1656706940234251
9416321342660328
4009752871445568
8946741333314748
10764269715844342
5609227805988978
14947691905102305
15036214604008772
10...

result:

ok 500000 numbers

Test #22:

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

input:

10 500000
1 4 2333
5 9 8130
5 7 5193
1 2 6938
3 6 6342
4 8 8844
8 9 4674
3 4 5195
5 10 4236
6 10 8162 87588
3 10 36418 7206
8 10 42308 34094
9 10 69914 24030
4 7 25745 6115
7 10 90829 5614
2 5 5274 43016
1 2 93991 3173
5 10 76358 24253
1 9 81231 90412
7 10 64509 90419
4 5 39855 74709
4 10 85353 1435...

output:

3130919544
1166687048
1283885752
1978274140
666383580
3485835362
1464076972
2742093434
2533940230
2828853338
3383569399
1416381171
2290959873
720247712
1788311442
888393556
671638500
1346955142
943494291
3047948234
2223756945
1642791852
2448163256
1258738266
1540328357
1707714964
2506707831
12724457...

result:

ok 500000 numbers

Test #23:

score: 0
Accepted
time: 110ms
memory: 76932kb

input:

100 500000
30 89 2155
48 65 1916
32 81 3833
2 79 4757
22 60 6953
19 34 1487
16 25 3181
54 82 8724
50 73 2507
72 90 9252
8 77 2181
35 45 6511
21 72 7949
41 79 5607
34 65 8839
21 31 7104
14 49 176
40 80 5914
30 40 2206
40 93 6241
50 57 6456
46 49 5763
50 91 3400
6 78 6259
52 67 2143
33 35 5916
39 63 5...

output:

32912262307
139343527824
44901405068
118159532620
88397372490
110052683328
119328576491
9277212971
123574233705
27991577125
143889082627
173111063353
98995218279
143744963340
102148798266
108724227526
172617870186
66324246022
143879313167
89526963368
118357400256
113714636722
91983601092
16096044184...

result:

ok 500000 numbers

Test #24:

score: 0
Accepted
time: 352ms
memory: 107856kb

input:

200000 500000
70716 167838 2768
12842 140231 3468
95053 173664 1745
114564 160388 1549
169509 189258 5106
89692 155019 4514
115225 171897 6091
87097 110604 1176
89940 117417 2300
86549 197732 4537
12343 133030 5206
88716 197689 6413
85288 157124 4246
46005 124694 719
119999 176784 4897
57160 90184 7...

output:

12732832828062653
9211037791337106
5237768669844932
9023251773903405
8858519509171100
13939771675148235
2699313248449214
7720785879667220
13976414809780410
11491808564740729
8274430160134475
10647944661154060
10637105504452602
9992561160987843
12646401358321221
9426845067847364
13918444902412404
117...

result:

ok 500000 numbers

Test #25:

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

input:

10 500000
4 5 8232
2 8 4563
5 8 2812
2 7 4856
1 5 6768
3 10 6402
2 6 5397
2 3 9435
2 9 7984
3 4 82545 1445
1 4 28575 97326
4 7 19874 43682
1 10 57962 32903
7 8 78841 99132
2 5 17095 64304
7 9 15073 63528
4 10 48518 23005
4 8 53929 12059
5 6 9970 10660
3 10 68509 2443
4 6 33337 29210
2 9 9641 27724
3...

output:

1946246010
3060318744
1202021626
1653212363
2726270621
800084043
1513300488
1291866148
1054938600
308427480
1715602378
1120300140
152684517
1331850486
1080470856
992378094
2285506415
1421551796
613398904
593742225
303233578
3116125396
1252975929
1144870791
2793236600
2612217360
868606320
1956713836
...

result:

ok 500000 numbers

Test #26:

score: 0
Accepted
time: 109ms
memory: 74516kb

input:

100 500000
46 80 2846
6 32 8889
13 40 1659
5 70 475
20 39 7675
26 68 718
25 85 9270
33 44 4206
33 91 2443
17 27 3150
52 54 9892
36 44 4195
2 96 6623
4 22 2704
4 47 8649
23 100 2451
30 37 8860
18 22 8415
29 77 1851
49 55 4586
36 78 9115
23 53 3719
41 85 1750
24 37 8600
48 96 4379
38 63 4557
40 90 568...

output:

113751532017
80123268206
87262423810
137924584380
12800009202
92234031684
58589655165
78344066172
58556856157
48696946584
104850617405
108932596632
17183906241
121368553624
90729404336
43840759604
85075307140
85184463782
24672530760
43602676780
84931463370
61920440394
54949716012
77486651814
5884819...

result:

ok 500000 numbers

Test #27:

score: 0
Accepted
time: 350ms
memory: 107776kb

input:

200000 500000
89413 191901 8274
41004 66726 2629
67729 182199 5599
31500 34542 4398
117299 150081 8774
60011 67816 294
10880 67932 9348
33260 101496 5210
151825 190505 8648
20718 137357 1552
42327 104476 6705
112606 130339 9915
83218 187258 9013
40136 186203 5580
166737 188199 2516
59847 196235 8764...

output:

13470360035139118
15627984620842116
6909370776351859
8565758903929875
1737990841654072
11391139854962264
9886630099101457
16257953272665298
15030575954097100
10134173407874800
7075652323089936
3671195129356384
6042485688632407
8079271696016708
11979823162045712
13114450214675068
8098647102818376
130...

result:

ok 500000 numbers

Test #28:

score: 0
Accepted
time: 69ms
memory: 62568kb

input:

10 500000
1 10 5618
2 9 6804
6 9 31
3 9 2773
7 9 1386
1 7 856
2 5 6119
3 4 2188
1 8 5925
2 6 24224 48006
5 9 77628 11639
4 10 38657 94485
7 9 61074 337
5 6 36247 15232
1 8 51550 22492
3 6 78227 25180
4 8 31900 94974
1 10 25323 26620
1 8 27360 88306
6 10 19483 27773
5 6 80003 18945
8 9 6083 78310
5 7...

output:

541779844
570061445
2048263271
418497845
764449230
781755750
1227850992
2072798860
384023295
414914400
577206259
1687263270
1082216199
437861970
819779180
1478754268
721540744
1337824010
1097899253
1253298460
597971682
1022829994
1449053412
1266804248
2132569267
1903570104
762936815
1006646790
19210...

result:

ok 500000 numbers

Test #29:

score: 0
Accepted
time: 96ms
memory: 69572kb

input:

100 500000
47 48 2049
47 85 4375
47 95 6381
13 77 6194
13 42 6909
2 24 4540
36 94 8063
20 98 6585
3 78 9275
50 54 1240
65 76 4900
59 67 4584
40 56 9889
72 100 3993
32 59 9675
71 99 3207
3 21 248
39 85 915
15 77 5688
37 75 1443
22 51 8671
8 14 5868
36 81 3203
57 87 6748
62 83 2422
17 21 9005
2 43 631...

output:

63285961413
32106790163
81034137362
69774212050
64874364310
33037534269
49801134488
92236309048
103461371576
76807213638
77792057236
34377887914
54575715818
81091323147
130289449044
38859798515
114768107713
86100072195
98284969254
12855923119
119608031566
114788843552
99483748842
28454936947
1039703...

result:

ok 500000 numbers

Test #30:

score: 0
Accepted
time: 331ms
memory: 109820kb

input:

200000 500000
161614 170796 8711
31541 145252 6019
6581 43902 9393
65492 173813 1977
26737 144071 1295
46596 128588 5887
40024 125184 1059
49850 128105 579
145860 156981 8189
23649 39758 2523
92545 186880 5844
99460 181884 2413
40458 176879 1094
101450 111492 4881
15628 29165 7724
70212 94427 7220
3...

output:

15587358611644622
2753354696419528
13032234556657804
11569437841817306
15678266754380351
4774770209393394
7144555280515641
3511975770131904
3216537433659968
14225446872275521
3886046886644282
13600935004052392
614316794520190
8441719504412288
6126977015402654
19225850274049522
13556443075825916
1108...

result:

ok 500000 numbers

Test #31:

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

input:

10 500000
5 7 5364
6 9 195
2 10 2865
1 6 3430
4 7 4892
8 10 96
4 6 2918
1 8 1545
3 5 9282
4 6 92225 34265
4 6 16542 38006
4 8 78850 44308
4 10 12518 8835
1 6 65906 5386
3 6 12511 1337
3 10 2744 76630
2 7 45597 3705
5 8 72929 80974
4 10 95885 74294
5 7 57915 75877
6 10 62811 46853
6 8 64977 88114
8 1...

output:

2073819090
624813212
1769643660
291101794
417920452
255050350
1398114350
549173268
1712179568
2264633334
1732326272
1544717661
1720029066
28366112
1258071772
2415655634
1097710670
863915598
2167180404
2551945589
2255950620
1845962130
1480663976
1109666250
651536563
2393766210
1428725183
1477365478
1...

result:

ok 500000 numbers

Test #32:

score: 0
Accepted
time: 110ms
memory: 73676kb

input:

100 500000
53 58 2341
50 59 8029
29 96 9922
2 42 2537
4 64 8252
45 61 3776
73 87 2728
69 92 8022
5 52 8549
32 38 2100
68 91 5373
31 80 7016
21 62 9706
3 62 1913
5 12 8508
60 79 8014
1 99 3417
17 58 4927
45 59 388
41 92 9324
9 19 5665
71 72 5374
49 98 6745
4 74 3035
45 66 3977
49 76 5262
67 84 6544
3...

output:

113275578588
94811155533
70088383860
67083851893
119017361930
39943371460
162674241147
176183288228
163113256519
118061681904
110402458110
64049779318
107480590890
68976875498
115686471588
136602354006
132493869051
127020415149
55996927769
53377746996
78970027154
67917663935
93618128016
98842580082
...

result:

ok 500000 numbers

Test #33:

score: 0
Accepted
time: 346ms
memory: 109736kb

input:

200000 500000
145185 175065 2436
53356 84599 1290
105557 175136 4540
60977 151141 4942
163917 172758 9403
53860 183870 9961
5112 25159 1855
114711 164151 9716
17733 53577 7274
89123 165488 3664
136 141988 2825
63446 85508 2584
17629 90534 261
81969 158653 41
26512 164537 8184
44294 147894 3009
13794...

output:

10426893441188036
7224297544847883
10657174227740772
8791298429141878
14963476699472786
16464564376772758
8531890388037306
4578989017907610
6346680972886632
5000181689913762
10990458809557436
10119262457473258
4099435763483130
1627314993616369
8861368912679331
8495422887539577
14065742283508675
9404...

result:

ok 500000 numbers

Test #34:

score: 0
Accepted
time: 796ms
memory: 171324kb

input:

200000 500000
8859 166855 9818
78272 175133 9324
47078 159150 5282
68538 136326 9077
18774 36664 5397
52385 94763 4224
168615 199168 2148
40707 106627 6316
96426 182772 1146
59413 85149 4069
105781 182866 1305
7355 83740 4350
167219 170628 6499
29748 162314 3984
28988 52392 3067
70130 188852 5090
11...

output:

1000462170
2000922314000000000
2000909554000000000
2000924340000000000
730725289641976287
447730651113676684
900095965917182352
1293909919305497253
656823784440904824
898798865792751556
1385145503906622931
591341527537817883
306540705538620312
731545685482956223
1150668143506257090
17964789002923917...

result:

ok 500000 numbers

Test #35:

score: 0
Accepted
time: 824ms
memory: 170552kb

input:

200000 500000
57015 149285 9879
28544 152998 3713
25802 110059 4795
86853 107388 8494
176076 191815 2808
165752 169376 8008
24017 30541 1844
129796 188853 5103
1621 124316 7435
12073 24070 7934
103916 136440 6319
112433 120519 5416
8111 99401 3395
125150 162346 1698
78140 144632 5049
48323 81048 576...

output:

1002626517
2005233370000000000
2005245938000000000
2005253034000000000
739346057543654683
920744266636160962
452498520092735287
1530300605349377829
1116099106255822467
683735009718297838
711589829297811835
1577214235179306567
1658979091839100176
1412184796341697246
533924772459843599
236895297048860...

result:

ok 500000 numbers

Test #36:

score: 0
Accepted
time: 837ms
memory: 172028kb

input:

200000 500000
115815 123648 6156
79253 111480 6977
84185 128329 1475
79473 163105 9760
61239 186905 1357
149721 191564 891
64587 78969 3684
14597 182366 1231
10025 90751 5090
20216 36500 2874
131576 169512 4488
50373 80542 5730
11827 91891 2494
174330 184277 2104
1652 94882 3339
28264 32408 525
6928...

output:

999975234
1999932062000000000
1999948824000000000
1999950468000000000
661591716089270848
915680199624585766
1434167854370962636
1779749366161518808
287115300068686987
905487213139243304
1212623617364534034
551794304484333294
1277825556854361570
988320702201908892
658021069472979274
35707211466928469...

result:

ok 500000 numbers

Test #37:

score: 0
Accepted
time: 828ms
memory: 168812kb

input:

200000 500000
131562 178676 2632
46354 150847 1815
92095 93512 1758
62830 146374 3230
89760 174186 7084
2532 18290 5205
6197 113403 5352
99747 165295 1910
90134 150784 2035
29848 186120 535
61174 85283 9598
128455 177567 9391
114655 122068 1372
184161 199568 8699
141462 189507 2329
76272 118780 4386...

output:

1000726846
2001448888000000000
2001435860000000000
2001453692000000000
904479579881274072
954395157655097898
815516157008918489
1024173332541872537
1369663762863014380
408134896988859408
374588771267388033
899578310674017693
996295518644283749
584709334940985982
1642736140830176786
11746452443321951...

result:

ok 500000 numbers

Test #38:

score: 0
Accepted
time: 818ms
memory: 170708kb

input:

200000 500000
14959 117058 9733
11185 151871 8292
30899 166428 8575
20184 138441 4931
147251 159450 7236
94070 171081 6943
146591 191476 5050
39370 190243 2644
170789 176248 9176
40408 45918 2048
121599 178547 8136
83319 152223 1589
53811 80803 4138
40375 127717 7296
102970 195093 1628
120443 173722...

output:

1001262207
2002523934000000000
2002519634000000000
2002524414000000000
1337893225166326277
996791973320113816
617565038561160030
464515405428083409
778505173092407457
1471927642382407140
1508479931599231610
554439415324587232
1222403590045493116
264963640459200637
85932016709412804
16299507434853534...

result:

ok 500000 numbers

Test #39:

score: 0
Accepted
time: 687ms
memory: 168888kb

input:

200000 500000
58135 125858 1
114725 126732 1
23205 57286 1
14057 21691 1
22648 66157 1
142596 192969 1
38724 118161 1
56649 150881 1
93568 144640 1
109964 122400 1
2426 3133 1
46327 109711 1
24759 125146 1
12369 54466 1
181501 194617 1
12182 106913 1
53200 72899 1
108457 177795 1
157064 157836 1
294...

output:

199998
399996000000000
399996000000000
399996000000000
65058057698608
251631442905875
148179521041673
50828396157631
55032060850336
95065279717206
295797388272588
157214174484965
294474833602594
234063224777035
221269976164186
284117217588189
126028337534274
94561379255032
272114672536140
3602520274...

result:

ok 500000 numbers

Test #40:

score: 0
Accepted
time: 669ms
memory: 167764kb

input:

200000 500000
54737 121996 10000
116805 159884 10000
14824 108446 10000
125782 138095 10000
134214 198690 10000
49064 100641 10000
14918 94337 10000
41946 198028 10000
59686 186633 10000
23800 53431 10000
61859 196561 10000
63408 106000 10000
44826 162357 10000
139872 174148 10000
73340 129012 10000...

output:

1999980000
3999960000000000000
3999960000000000000
3999960000000000000
2112939366422610000
1652588792680600000
3534944192185520000
2138523765864690000
1920653337754830000
2371081801553730000
1674852843724050000
3689778263812170000
1761900838750970000
2628927029796920000
1071933251689020000
180237521...

result:

ok 500000 numbers

Test #41:

score: 0
Accepted
time: 705ms
memory: 167768kb

input:

200000 500000
18280 146267 1
53153 53814 1
40752 86560 1
152092 173596 1
36755 144659 1
23045 62588 1
111028 194440 1
91938 122143 1
141402 170123 1
38669 154348 1
128719 173132 1
10873 101529 1
1501 188904 1
71638 181803 1
2944 197056 1
142913 174843 1
25120 70013 1
34836 41517 1
59326 147528 1
732...

output:

199998
399996000000000
399996000000000
399996000000000
342854506131046
269405581975706
58744792707530
299222967022625
150965427026454
269817943665195
143406572495313
177366207171208
99649175313741
248797580465156
238923214616007
147684064592059
221983786700072
102177339750258
150928744519870
1088691...

result:

ok 500000 numbers

Test #42:

score: 0
Accepted
time: 712ms
memory: 167552kb

input:

200000 500000
87775 116743 10000
120737 141840 10000
58322 148456 10000
12756 142058 10000
108617 117902 10000
7265 173904 10000
63833 68382 10000
77267 160237 10000
38900 68259 10000
33888 166138 10000
14435 145218 10000
5592 82242 10000
103098 112490 10000
42053 103885 10000
67942 180352 10000
114...

output:

1999980000
3999960000000000000
3999960000000000000
3999960000000000000
2832053943134980000
578101600135680000
1625586053880290000
2201418046890190000
2513634609619770000
275856912403430000
2339656623176070000
3856070775043110000
3234974266323690000
642938928362350000
1661703339491790000
316828535182...

result:

ok 500000 numbers

Test #43:

score: 0
Accepted
time: 801ms
memory: 160688kb

input:

199999 500000
177639 187054 10000
53633 58838 10000
156394 174041 10000
63775 97370 2104
73163 193678 5823
53573 141187 8296
61961 75498 7709
103044 107827 7712
1426 120114 6650
56610 191872 10000
135673 140552 10000
57968 137914 10000
72661 94425 10000
7833 93730 10000
39678 94555 10000
59304 68766...

output:

6154260174064
9802363109918
1886160921750
10385842550840
9141495445947
17276485166694
8979852635025
1503083743564
859109166973
1848113477653
12176991099885
13328353929048
2277048140304
906773562549
2607468499258
1592776164772
11074948869980
2192234739187
1789772831430
12541878653411
11758993185796
9...

result:

ok 500000 numbers

Test #44:

score: 0
Accepted
time: 819ms
memory: 160628kb

input:

199999 500000
6035 197909 10000
31501 51143 8859
57845 88388 1421
45009 78895 10000
16152 172707 10000
69263 178748 1894
79822 164403 3843
8684 16020 993
5088 144742 9726
97598 154393 10000
59598 101962 10000
137754 150035 9603
126803 133637 9961
125803 133265 2766
84357 176033 10000
72627 89689 504...

output:

139947406389
5891473599866
14129740182318
134563048125
5337509412672
11927036858913
14665421541730
10689272275724
7118330595063
5799028598007
9368118773750
14514056337724
6517790592887
14785213111254
3330280902198
4012804398587
8519243407321
10972807360957
8016634890364
8044438238929
3533646052128
1...

result:

ok 500000 numbers

Test #45:

score: 0
Accepted
time: 687ms
memory: 154932kb

input:

199999 500000
37086 96937 3878
8854 123271 10000
97720 151315 10000
117078 174984 10000
41065 156400 10000
41008 54529 10000
5637 58551 1608
24943 105226 10000
85352 124448 10000
80107 190498 4195
40647 110809 10000
9853 120720 10000
53452 116676 10000
7414 124839 1448
38914 97935 10000
118746 15317...

output:

880489084944
1564955634622
4625556426455
1837465431805
6715848417678
5147613692434
392484178917
5441314046262
3218755015930
4105699034233
4852148150847
9753180893784
9511753693828
6096146372693
7418534841240
8808393073543
1436654136899
4419285430176
7740953215478
2197521607860
2597450179116
24944584...

result:

ok 500000 numbers

Test #46:

score: 0
Accepted
time: 785ms
memory: 159552kb

input:

199997 500000
58336 78659 10000
155915 162205 10000
18740 81958 10000
183617 195225 10000
42900 104488 10000
92366 124938 1068
58152 74131 1924
75947 127093 3040
47409 76491 10000
140741 196054 8696
32892 168884 10000
20255 197006 10000
121339 180373 9460
73239 105444 10000
51257 159528 10000
107853...

output:

18983503917876
6191307941016
29485438589132
7748110302160
3493742050476
28548777468324
20022881315580
9130183760728
98735154236
10212893972452
5622767047000
16902277986112
5615816223872
9280090611488
10105451736288
16390204096344
6527242330732
5040452687020
30106777184320
7386959092584
1906486323076...

result:

ok 500000 numbers

Test #47:

score: 0
Accepted
time: 658ms
memory: 153496kb

input:

199997 500000
95130 126673 10000
23194 113538 10000
20400 177565 10000
17309 197072 3754
104197 199869 10000
42847 73581 10000
60747 192806 10000
70211 97307 1838
10434 39403 10000
72581 97798 10000
48535 60551 10000
162580 191244 10000
193160 193666 5010
95399 117565 10000
57551 127181 4964
66080 1...

output:

18000635747955
40873165756962
38836000955909
4109576635643
7740534771903
12292681255583
30742508887536
26783417703210
17785170421344
17143079971779
8397978001407
1609713803698
1593075569163
20358263008434
16049544196671
42576091411573
20019742470630
11026945717341
3971844510660
21537404514680
477331...

result:

ok 500000 numbers

Test #48:

score: 0
Accepted
time: 636ms
memory: 143292kb

input:

199999 500000
9377 100040 5658
43987 53942 10000
44653 95734 10000
40082 43909 3846
75294 94733 9871
136720 151476 10000
35431 160481 10000
21663 157861 10000
69456 175492 6421
132213 137870 10000
98664 173600 8510
99175 167461 10000
40269 75816 10000
57882 145247 10000
86708 163753 10000
89488 1909...

output:

1923307476548
4629429353282
449636274258
2042923036477
248740344047
3097165863343
4458251893963
5148839103400
358259464634
6528493015867
5155429852738
587813729689
6261659040121
2684182818305
3688100894521
3619144346496
3624700575816
1791484288371
1677481696899
1893696697639
1467412936168
6077048581...

result:

ok 500000 numbers

Test #49:

score: 0
Accepted
time: 722ms
memory: 153396kb

input:

199999 500000
61356 195745 10000
37207 64305 10000
104123 185276 10000
11544 38521 5396
31494 69204 10000
70439 121675 10000
73162 128463 10000
36926 61221 10000
53084 141043 6835
96744 151690 1356
48996 154807 8721
31010 193117 10000
15782 47886 10000
36812 153556 7224
86399 146538 10000
154636 172...

output:

12274022386229
12079249691431
16827965643855
2823531420113
18511485486974
20323485132402
3490682672358
11799881034641
2785231722259
360586142523
5277509347609
9054173014819
6167495103936
10545831703538
10570710371223
8418604622239
1774963709809
17519192338756
9439860745380
13954542976863
19499477859...

result:

ok 500000 numbers

Test #50:

score: 0
Accepted
time: 640ms
memory: 141812kb

input:

199995 500000
12878 43249 10000
30272 197071 10000
20740 178838 10000
21518 48105 9733
144837 157876 10000
55550 147981 10000
14819 146293 10000
44396 133267 10000
63687 185314 3312
78127 126130 10000
157449 157777 696
164379 168306 1334
76866 198964 10000
3530 133177 1656
35576 96915 10000
60206 66...

output:

593746504160
82991834992
1931351112739
4783928456366
2786409296799
1757476810145
83701165348
3901539338372
2381351047770
2713183269835
2843742359216
1795329679240
3991174790394
1822034549534
1574125021711
4129639547957
3830352036248
1218716189524
68446457129
4216730991896
1575981894826
914269813066
...

result:

ok 500000 numbers

Test #51:

score: 0
Accepted
time: 698ms
memory: 148824kb

input:

200000 500000
46676 113849 6740
101206 126909 10000
19529 80553 8940
68426 146456 10000
18205 35579 10000
39475 187507 3090
124166 147338 10000
68921 161366 2360
128983 174966 10000
45835 53618 10000
113138 183819 10000
65360 197473 10000
22612 152918 10000
91325 109086 6048
17794 38027 1304
34812 8...

output:

9944891454424
15949051268688
3617483933544
2282613690420
619452010068
12428314409592
13936664159460
10962944594956
12467078293196
6780449470940
3315805023160
16900122707688
10512303629184
9153271869972
7925999354940
10479965266560
4800408506964
7143314327008
9187351798256
11299529851596
563439058645...

result:

ok 500000 numbers

Test #52:

score: 0
Accepted
time: 716ms
memory: 153084kb

input:

199999 500000
155223 168937 10000
118162 178165 10000
80438 191072 5062
23772 147846 7213
87055 99749 9065
72798 174774 4632
29522 133851 10000
49223 97059 10000
176384 195077 10000
153416 185126 10000
72786 76808 9119
3031 141247 10000
72093 83183 10000
43082 69281 10000
12637 61286 10000
79522 126...

output:

1453826037145
1383674338329
12746221563571
15322265205661
29340338682109
1506774828050
1780797959671
31101495294067
1454124702148
25279385970354
13350358395878
27150159297607
18564627534280
23488115321805
19723673513446
3836076823917
9806200137934
12468193355418
15143567278618
17404082189908
2519328...

result:

ok 500000 numbers

Test #53:

score: 0
Accepted
time: 847ms
memory: 141024kb

input:

200000 500000
189505 195026 5261
102020 186607 10000
53680 110202 10000
62732 102799 4768
52784 132897 4172
52784 147876 4252
84933 150689 2827
52784 178069 6961
15704 94742 9584
121463 125974 10000
25914 79909 6687
52784 177265 8836
64161 138281 8181
9690 94405 5589
143629 189505 2419
52784 143950 ...

output:

5051019581659
908949291118
183477881123
3081953986095
4564048522496
2157783044887
4695100210301
2456194528051
4271433982439
2085348990633
4670659220354
4878236042866
756269217332
245770016036
4712320387035
56389223519
498045939678
1464734062316
4323611232809
5131117472566
5107659335238
587222729445
...

result:

ok 500000 numbers

Test #54:

score: 0
Accepted
time: 803ms
memory: 141056kb

input:

200000 500000
133872 139325 3596
29904 48660 5952
142727 146550 3997
101923 103275 10000
29904 65269 5639
75294 161927 6407
93737 137890 10000
19551 139325 3747
98693 139325 4277
50523 139325 7371
139325 163701 6182
28281 29904 2855
83198 132703 10000
136565 174419 1775
139325 164389 4150
29904 1389...

output:

939148732265
2680048941941
4420402804290
4846662110815
274142543739
2176562314122
1852829117888
1878277366172
2387933426578
1538584743245
4697862507970
3645664203340
2066956170559
1936945764254
440637053613
2732551051938
481589548122
2755853785947
2757256281895
2879588077359
1405299494284
1237171686...

result:

ok 500000 numbers

Test #55:

score: 0
Accepted
time: 803ms
memory: 139100kb

input:

200000 500000
43387 154874 3422
65640 93811 5022
93811 154048 8592
43387 183783 2219
93811 130903 4365
26287 93811 4816
93811 119205 8694
44796 89552 9138
85974 90127 2376
23641 93811 9701
93811 189035 5514
16270 43387 9405
167089 169098 6246
43387 71973 8020
43387 176218 131
56832 197102 10000
9982...

output:

786064597703
4986983439657
4109613343675
1435665772265
349316658358
924421160874
4312537368758
3160481898147
2860266913963
3763704907695
4966950706033
589951634610
5277006120548
2183079055509
4151866015185
3507468409634
4886392641421
2810282922977
1523707654762
1754976014459
93983928396
876028983136...

result:

ok 500000 numbers

Test #56:

score: 0
Accepted
time: 717ms
memory: 137292kb

input:

200000 500000
67936 71453 6067
31640 44028 4813
135929 171669 10000
123902 147440 4726
147440 186229 3604
11059 31640 9840
180150 184339 10000
31640 101877 2462
2198 31640 1822
116358 190869 9434
105076 106716 10000
55687 141117 1288
38355 137359 10000
147440 183134 8627
16502 147440 8837
147440 174...

output:

747893835297
873114660110
1860455089930
418472745006
2491480242268
1175537418690
1695006046660
803981627580
1211513175406
455845721423
1454831147203
3198269914820
1338055547825
3281115569601
3364100974984
213809197100
2458537932114
89888415570
639437510094
2331646442161
62118075340
2111630245477
241...

result:

ok 500000 numbers

Test #57:

score: 0
Accepted
time: 785ms
memory: 140000kb

input:

200000 500000
44570 57642 10000
32817 152059 7949
81799 91476 9660
91476 191584 5664
15976 92566 10000
32817 191789 7973
41644 91476 8691
56453 91476 4998
45028 86089 4914
3979 56945 2514
39830 68149 10000
77728 107638 10000
32817 151688 6336
78961 135706 5120
49878 69100 10000
74739 134700 7172
914...

output:

3548059022172
6030626139092
8568965843732
8887820160380
3566737295988
5586198541348
5583732560264
8522076300802
4703332706984
3445753738472
8607976190514
4120375167232
7684776862434
7048069429924
5442122197840
5455461764880
8426917686132
6279208346908
951404105796
5318691502134
953266487828
62045694...

result:

ok 500000 numbers

Test #58:

score: 0
Accepted
time: 659ms
memory: 136916kb

input:

200000 500000
9253 76614 10000
106773 142647 10000
8978 38819 5520
81329 109796 8812
84201 139836 10000
142701 159787 10000
42231 199856 10000
82062 189589 7104
70924 99991 10000
33518 133908 6813
33518 194499 4250
8978 188421 6599
33518 160278 4881
33518 142393 482
33518 135293 7819
83232 126802 10...

output:

9768810446864
9962627320672
2456140051183
8292679198678
664143235679
13637542221996
12485898727188
8349771431262
6747382607710
15954671628180
15893105958568
7917108069689
3467627617261
2207919431760
5956102633798
13717268823495
14746401598176
10319574274691
10561227876010
12388820515135
986695154850...

result:

ok 500000 numbers

Test #59:

score: 0
Accepted
time: 702ms
memory: 135404kb

input:

200000 500000
182388 199500 10000
63081 191483 10000
29226 76792 10000
13717 167193 9483
70270 172602 10000
6276 13717 4594
28965 109050 1344
119217 164626 6114
13717 198125 8252
107613 148449 10000
13717 172538 237
37676 54022 6481
50284 117096 4352
23043 123924 5706
54022 197235 1930
47420 195642 ...

output:

1847381225419
1264842360115
834224481232
2226697032138
2332552009280
1403526992478
868388956661
557094342734
67236368562
190852373454
807734684597
2120061064228
2198999258492
292296224910
1166372324066
581466867437
1998526492515
1868794058326
1456472868383
626808054797
2305465416726
11814652589
6293...

result:

ok 500000 numbers

Test #60:

score: 0
Accepted
time: 734ms
memory: 136020kb

input:

200000 500000
5691 34034 10000
132381 197524 10000
148409 181471 6018
59782 183412 9778
24502 108517 10000
81726 155124 9990
18162 148409 7145
23970 148409 2251
49865 181610 3860
148409 185273 4070
35703 148409 3502
49865 196662 3404
148409 184412 8790
51865 194469 10000
49865 157909 3146
49865 1671...

output:

1132120479367
1792129233802
1277637108246
6525526526162
4895590429693
5397018206364
5151504234445
1796246024114
4170426416229
2194506397316
5389171523192
2858866952498
1944312203086
4572210114145
4428253424967
4324471885157
5421858624141
6447149501744
5742140892245
5880411034415
6808218386419
659891...

result:

ok 500000 numbers

Test #61:

score: 0
Accepted
time: 674ms
memory: 130032kb

input:

200000 500000
120752 195946 1313
15233 195946 9397
4633 79724 3744
62274 127681 10000
3487 71392 2996
108670 193270 10000
13491 58499 10000
3254 75019 1504
3254 157444 1422
3254 45367 5800
3254 192144 3365
78085 195946 8765
14885 195946 7242
6533 124374 8324
87848 178054 1199
61847 177846 10000
1090...

output:

746796865016
691040829251
994155264768
1729766005545
912782528535
1076703641416
193011406551
299253313673
520569166820
1362016771281
1052466673298
570691024850
676538501463
737831006514
1499713171930
1718869679352
1357772822392
1739094047986
72511911595
1790681356364
1281436308519
521686891456
61057...

result:

ok 500000 numbers

Test #62:

score: 0
Accepted
time: 752ms
memory: 137008kb

input:

200000 500000
15287 68501 10000
7075 172606 5380
534 2898 3116
97818 168218 750
36251 143414 10000
534 94155 2553
534 82550 538
154936 168218 3796
51356 110480 10000
162635 180725 10000
74682 98059 10000
54968 182694 4150
103074 168218 9460
99035 168218 226
114360 168218 1151
103040 103563 3624
1295...

output:

2295167140352
1806569915892
3555319080190
847573656096
2247193623502
657880069078
3028599412644
4219700644246
2817620839724
4872694694984
3766841436740
288161586422
3035390124228
736880341426
4401421431264
80524519862
456305846968
4795583113986
811001201632
1741688812084
3624072066696
5519662462186
...

result:

ok 500000 numbers

Test #63:

score: 0
Accepted
time: 710ms
memory: 135328kb

input:

200000 500000
40883 167547 4224
46018 90251 10000
112479 189078 10000
67705 86647 7674
86647 144486 7642
114893 120878 10000
40883 58874 2194
20695 40965 1400
52544 86647 5740
35700 102805 6832
7858 86647 5324
9418 171083 10000
18064 166593 10000
21439 41606 10000
40883 92280 3550
84110 166514 10000...

output:

6108011148519
9502918170252
6721065349061
6497419327042
9760028616926
2961183808921
3642326902880
6292848964558
2255299336701
6468504888538
3752592287186
10414094502065
2218770098187
605602518641
6036791932052
10535361462701
7354246522159
9812111254888
4473865134591
6023895639540
7566028630282
51520...

result:

ok 500000 numbers

Test #64:

score: 0
Accepted
time: 295ms
memory: 76228kb

input:

200000 500000
73429 170969 4821
7545 73429 8574
19132 73429 578
73429 98049 628
15167 73429 4167
73429 178762 9210
73429 194425 277
73429 138260 8355
73429 101342 4105
73429 148078 3848
27870 73429 3665
73429 171295 444
73429 103562 2622
14664 73429 7250
73429 171516 9082
73429 169316 2379
73429 986...

output:

150746475
156345936
170646480
95029488
54869598
140872896
132059802
110519994
39065184
150770700
70522506
101252500
68692708
112654011
90661350
123056700
110668129
53520652
62314980
158260126
184049110
96595707
96410525
144711038
110043010
116074078
99622916
170267250
50754571
109560987
138947154
14...

result:

ok 500000 numbers

Test #65:

score: 0
Accepted
time: 312ms
memory: 73272kb

input:

200000 500000
56681 174064 574
133322 174064 6319
16923 174064 704
59974 174064 5700
60921 174064 440
3167 174064 1560
44477 174064 5613
7421 174064 5241
7764 174064 3988
76949 174064 1633
128239 174064 9326
27166 174064 8218
137315 174064 5472
105439 174064 6355
28814 174064 7523
107669 174064 4116...

output:

96275298
67372772
94915925
62469265
108522828
106509143
122088956
99607794
88209745
123574110
71151528
120223740
52723011
46030765
47121620
125960037
86013252
63422646
63086240
143151465
81200000
121522477
76180536
170042400
85281336
112964958
51397980
81378570
98824475
106094030
68137914
180699435
...

result:

ok 500000 numbers

Test #66:

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

input:

200000 500000
136018 176757 889
101799 176757 2941
3298 176757 3723
89681 176757 1731
120663 176757 5607
25701 176757 8060
72743 176757 8707
101340 176757 923
176757 199200 9325
87816 176757 8942
157709 176757 5744
153462 176757 3779
157907 176757 3416
152468 176757 5322
176757 181575 6968
167697 17...

output:

141756450
100421493
69219048
101662113
168816018
45102008
124533216
24640668
81405165
172964862
181218940
45252892
61702904
144071340
94727160
92649252
89851950
80335872
171994020
141939462
47638934
155596532
105638370
72613320
41763876
140876253
99105220
65620800
83966872
78871380
131312094
6318540...

result:

ok 500000 numbers

Test #67:

score: 0
Accepted
time: 194ms
memory: 89564kb

input:

200000 500000
170969 182851 4821
7545 45628 8574
19132 37369 578
98049 178987 628
15167 70970 4167
171446 178762 9210
64877 194425 277
107273 138260 8355
69392 101342 4105
146278 148078 3848
27870 48002 3665
165399 171295 444
103562 128121 2622
14664 139225 7250
63548 171516 9082
40915 169316 2379
9...

output:

96520757113
68950916352
52372297037
99607184960
114043071087
83003001127
68493985746
123451862191
69936594032
125263946125
55948375724
32893941354
46988591451
47746774749
31579539334
55072518240
43924352709
98225327537
45396042090
6154103451
54180387387
92163290736
47143691968
18441572786
6916227922...

result:

ok 500000 numbers

Test #68:

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

input:

200000 500000
42226 56681 574
40311 133322 6319
16923 35337 704
59974 71071 5700
8346 60921 440
3167 141903 1560
44477 51424 5613
7421 107081 5241
7764 93501 3988
14211 76949 1633
74172 128239 9326
27166 65805 8218
82728 137315 5472
105439 193490 6355
28814 67043 7523
107669 164560 4116
91468 139442...

output:

57480012300
54062661733
55666531568
62832803934
83644293972
98644747846
30739318889
100523059149
133890725797
113985154757
123869023998
89650671147
71843371656
44549480290
124221609162
59377536101
19561257784
117432897019
86713958292
63159473731
129045253550
46622027490
26887410321
97071340407
12531...

result:

ok 500000 numbers

Test #69:

score: 0
Accepted
time: 179ms
memory: 91680kb

input:

200000 500000
3898 136018 889
101799 184657 2941
3298 77311 3723
38082 89681 1731
36003 120663 5607
25701 64751 8060
69470 72743 8707
101340 193195 923
42288 199200 9325
49175 87816 8942
33964 157709 5744
153462 199569 3779
102828 157907 3416
37704 152468 5322
44608 181575 6968
73861 167697 5611
229...

output:

111258489343
115735237926
70536038445
86078282470
71490950430
71701712600
62066560779
44908623364
116125170205
63675003059
132166682907
41715103340
85515152628
96006858669
105916985333
69023525476
102975973459
109512860907
124734990461
69521311759
73031223018
42562362359
104267684272
122953330600
54...

result:

ok 500000 numbers

Test #70:

score: 0
Accepted
time: 191ms
memory: 89632kb

input:

200000 500000
147434 162944 4821
113271 154872 8574
63837 70988 578
47627 82859 628
64917 87647 4167
58277 151709 9210
21265 60956 277
82178 182277 8355
37110 71343 4105
43543 96028 3848
56566 68268 3665
118191 142291 444
15348 171644 2622
5183 121311 7250
83179 157871 9082
18923 49677 2379
68295 11...

output:

93271465652
70128842816
57330666576
110412740518
111782034111
86653411411
62884991266
119933132370
72775786618
112922076511
62058101236
34466747362
48954100282
48533516322
30924147268
57166372080
41975296756
96120550358
49316537025
7099704770
50967342813
91474967355
47031950297
19368814088
668482510...

result:

ok 500000 numbers

Test #71:

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

input:

200000 500000
17241 22395 574
62134 96773 6319
44389 102997 704
11285 194146 5700
179837 197562 440
7405 175969 1560
52064 55276 5613
147504 184990 5241
15151 94017 3988
126048 151852 1633
122155 141346 9326
18529 107129 8218
66561 77845 5472
27253 137607 6355
82265 101518 7523
3079 151558 4116
1316...

output:

54094298336
62960610697
55891705900
65927309485
90206831628
94552389811
30735381789
100823530108
135201441225
126449968802
121913998986
86936404712
64502359583
46562117000
119114404868
61390814569
18302391568
111238777198
86093106279
61139409990
115461073530
47876543229
26643607200
95918719107
11462...

result:

ok 500000 numbers

Test #72:

score: 0
Accepted
time: 203ms
memory: 91668kb

input:

200000 500000
128269 150094 889
74092 137159 2941
15984 121961 3723
48370 121604 1731
7727 97285 5607
16574 75978 8060
70783 198649 8707
34883 37898 923
11046 142855 9325
48714 127630 8942
118439 144545 5744
58830 195044 3779
134888 174356 3416
107178 178954 5322
80456 166946 6968
40637 146134 5611
...

output:

112298530134
117625138281
79051804146
90689451716
79177422876
80279680565
70416171144
47230389712
128582056801
69241472569
132083367850
40452042332
85116368304
99160684418
105944322164
79445333700
107000272339
105352879563
115953370542
74866938621
66134361878
42243220488
111946985256
133553952324
60...

result:

ok 500000 numbers

Test #73:

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

input:

100000 10
11144 99817 9379
46222 80615 4748
48124 80167 9522
24254 39453 7959
27125 44714 1303
47339 63723 6194
27606 37044 2334
3247 27044 8602
17154 46539 1405
11466 36233 6738
9221 90634 6381
27828 70637 7127
56232 56358 6441
45235 71901 7651
10673 28017 3797
7093 80868 5206
15814 97465 8609
6554...

output:

3029676008066994
2308586298538575
848703709157613
2502830434971719
3873934927729468
4298115894022313
2739180653224424
3704496181494105
3676518979478792
4599240524788351

result:

ok 10 numbers

Test #74:

score: 0
Accepted
time: 787ms
memory: 139068kb

input:

200000 500000
92080 195520 8523
32057 190571 124
131851 183457 1648
166355 180972 5732
45870 133085 1909
66227 92069 1689
37418 155321 2968
68089 73599 10000
32057 164036 7084
36963 142993 10000
32057 57847 7749
97684 195375 8001
119875 184087 10000
32057 114886 3870
135068 145200 10000
140779 16662...

output:

4643813748762
659124066090
2791960658242
4449028983407
4694959521344
2339951105126
4908578461776
1732193849948
2375297367714
3599326344612
4555246556927
2609942367744
4659467801025
379197447085
3601811443473
3772596855100
3455044725502
3459844448658
2560098098443
2226823433482
2204250526513
45009045...

result:

ok 500000 numbers

Test #75:

score: 0
Accepted
time: 750ms
memory: 138984kb

input:

200000 500000
11332 155323 4642
17192 98867 7871
86494 180211 2172
115221 122791 10000
21006 89059 2850
63047 83175 10000
63269 145451 9739
44407 63269 1787
45599 108184 808
74901 100674 10000
19506 125338 10000
11292 45438 10000
62950 63269 4880
98867 123028 6206
71375 98867 6786
61009 191595 3728
...

output:

860859257723
1996869088746
3404780909991
695148218388
5122168949032
3709757645145
1988616540519
256247240106
2530157537503
4443914604645
4861567262407
1835601601352
3749802024226
609214470643
5336730177563
1143775584513
2298568157350
1897537192534
4620880445100
1222435517411
179091786101
35449635280...

result:

ok 500000 numbers

Test #76:

score: 0
Accepted
time: 764ms
memory: 139144kb

input:

200000 500000
126568 196936 9430
10915 35169 4802
158358 178385 6972
64394 195785 6516
25461 26599 4038
8053 139220 3544
56433 102992 10000
108418 160973 9148
19311 33007 10000
28585 149000 9409
79166 115331 9260
90520 149000 3196
115331 157352 999
123567 149000 6488
149000 172863 5282
30759 118996 ...

output:

4744411891211
5012680904894
1880454352016
106574956676
4448367361727
5115072109791
731839373300
4816597185649
422449205245
3407982925073
2242409016374
2242403017560
2982840925171
3307244980099
1177265318709
45894923678
1099429971393
3479343390442
103800362802
2003388858219
3142414351229
203090740387...

result:

ok 500000 numbers

Test #77:

score: 0
Accepted
time: 756ms
memory: 142280kb

input:

200000 500000
21455 192801 5941
145517 192801 5116
168363 192801 1460
34116 192801 7573
157046 198857 904
11006 107185 10000
23919 116612 8499
107441 192801 9761
116612 177368 5246
90719 116612 5872
26501 121790 10000
92183 193016 503
28988 192801 7265
138166 170541 2285
52274 167486 2755
64755 9292...

output:

352421514321
5688989047022
305687333436
6431068693441
2317259176716
4259592171561
3263650928500
6107707492824
4408608859908
3614989575024
5047633318413
518388905870
5208683356281
1829181665024
1493035890769
2821513371556
5058595446273
679937728688
3999776762320
2018164114826
393734169787
47149331386...

result:

ok 500000 numbers