QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733499#4889. 愚蠢的在线法官NineSuns100 ✓851ms135152kbC++143.2kb2024-11-10 19:26:192024-11-10 19:26:20

Judging History

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

  • [2024-11-10 19:26:20]
  • 评测
  • 测评结果:100
  • 用时:851ms
  • 内存:135152kb
  • [2024-11-10 19:26:19]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
#define lowbit(x) x&-x

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5+5, mod = 998244353; 
int n, v[N], vis[N], dfn[N], sz[N], a[N], dt, ld[N], rd[N], k; 
vector <int> e[N];

ll qpow (ll x, ll y = mod-2) {
	ll res = 1;
	while (y) {
		if (y&1) res = res*x%mod;
		x = x*x%mod; y >>= 1;
	}
	return res; 
}
void dfs (int p, int fa) {
	sz[p] = vis[p]; 
	for (int i : e[p]) {
		if (i == fa) continue; 
		dfs(i, p); sz[p] += sz[i]; 
	}
}
void tdfs (int p, int fa) {
	ld[p] = dt+1;
	if (vis[p]) dfn[p] = ++dt; 
	for (int i : e[p]) {	
		if (i == fa) continue; 
		tdfs(i, p); 
	} 
	rd[p] = dt; 
}
int s[N*4], ml[N*4]; 
inline void push_up (int p) { s[p] = (s[p<<1]+s[p<<1|1])%mod; }
inline void upd (int p, int k) { s[p] = s[p]*k%mod; ml[p] = ml[p]*k%mod; }
inline void push_down (int p) {
	upd(p<<1, ml[p]); upd(p<<1|1, ml[p]); 
	ml[p] = 1; 
}
void build (int p, int l, int r) {
	ml[p] = 1; 
	if (l == r) return s[p] = 1, void(); 
	int mid = l+r>>1; 
	build(p<<1, l, mid); build(p<<1|1, mid+1, r); 
	push_up(p); 
}
void cmul (int p, int l, int r, int tl, int tr, int k) {
	if (tl > tr) return; 
	if (tl <= l && r <= tr) return upd(p, k); 
	int mid = l+r>>1; push_down(p); 
	if (tl <= mid) cmul(p<<1, l, mid, tl, tr, k); 
	if (tr > mid) cmul(p<<1|1, mid+1, r, tl, tr, k); 
	push_up(p); 
}
ll qsum (int p, int l, int r, int tl, int tr) {
	if (tl <= l && r <= tr) return s[p]; 
	int mid = l+r>>1, res = 0; push_down(p); 
	if (tl <= mid) res += qsum(p<<1, l, mid, tl, tr); 
	if (tr > mid) res += qsum(p<<1|1, mid+1, r, tl, tr); 
	return res; 
}
	
ll ans = 1; 
ll f[N], g[N], tmp[N], td[N]; 
void dfs2 (int p, int fa, int w) {
	if (vis[p]) {
		g[dfn[p]] = (v[p]+w)%mod;
		ans = ans*(v[p]+w)%mod; 
		cmul(1, 1, k, dfn[p], dfn[p], qpow(g[dfn[p]])); 
		for (int j : e[p]) {
			if (j == fa || !sz[j]) continue; 
			dfs2(j, p, -v[p]);  
		}
		cmul(1, 1, k, ld[p]+1, rd[p], 0); 
		return; 
	}
	ll s = 0; 
	for (int i : e[p]) {
		if (i == fa || !sz[i]) continue;
		dfs2(i, p, w);  
		tmp[i] = (1-s)%mod; 
		td[i] = (v[p]+w)%mod; 
		ll sv = qsum(1, 1, k, ld[i], rd[i])*td[i]%mod;
		(w -= (v[p]+w)%mod*sv) %= mod; (s += sv*tmp[i]) %= mod; 
	}
	ll st = 0; 
	for (int I = 1l*e[p].size()-1; ~I; I--) {
		int i = e[p][I]; 
		if (i == fa || !sz[i]) continue; 
		cmul(1, 1, k, ld[i], rd[i], (tmp[i]-st*td[i])%mod); 
		(st += qsum(1, 1, k, ld[i], rd[i])) %= mod; 
//		for (int j = ld[i];j <= rd[i];j++) (st += qpow(g[j])*sk[j]) %= mod; 
	}
}

void solve () {
	cin >> n >> k; 
	for (int i = 1;i <= n;i++) cin >> v[i]; 
	for (int i = 1;i <= k;i++) {
		cin >> a[i]; 
		if (vis[a[i]]) {
			cout << "0"; return; 
		}
		vis[a[i]] = 1; 
	}
	build(1, 1, k); 
	for (int i = 1;i < n;i++) {
		int x, y; cin >> x >> y; 
		e[x].pb(y); e[y].pb(x); 
	}
	dfs(1, 0); tdfs(1, 0); 
	dfs2(1, 0, 0);  
	if (ans < 0) ans += mod; 
	cout << ans;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1;
	while (T--) solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 55ms
memory: 31792kb

input:

499999 500000
879485015 176694934 629415436 677018935 33186863 696674214 19586946 878479076 318116264 823399347 140314195 715329843 996129441 446979068 600062488 847953138 978347569 865596472 147980317 199880680 187953368 989585254 457868128 466175307 381871948 369138343 826894839 963935318 36550896...

output:

0

result:

ok 1 number(s): "0"

Subtask #2:

score: 6
Accepted

Test #2:

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

input:

10 1
663730929 273617752 74933376 562874267 346105266 779139305 198742356 291012786 227170675 127136999
2
10 8
5 10
1 5
9 8
6 10
4 6
3 1
2 4
7 3

output:

273617752

result:

ok 1 number(s): "273617752"

Test #3:

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

input:

10 10
144077216 482507381 588297929 801675226 21569141 816295251 425507414 150613951 822735519 802838587
7 10 9 2 1 6 8 3 5 4
10 9
6 10
5 6
2 5
8 5
3 5
1 10
4 2
7 1

output:

816324383

result:

ok 1 number(s): "816324383"

Test #4:

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

input:

10 2
136932305 774891472 782708047 361400653 241613404 206577781 241535900 917672952 105332067 165467540
2 5
2 4
5 4
1 4
7 2
3 5
10 5
8 3
6 10
9 10

output:

830180673

result:

ok 1 number(s): "830180673"

Test #5:

score: 6
Accepted
time: 5ms
memory: 34288kb

input:

10 3
106669121 934163752 505411505 487296100 135689018 776930268 130240777 167200291 726820445 449323201
10 5 2
9 5
3 5
2 9
1 3
7 1
8 7
6 2
4 9
10 6

output:

516982188

result:

ok 1 number(s): "516982188"

Test #6:

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

input:

10 4
554115046 86946870 492346089 759285688 597393634 534292327 742418751 40866289 456853511 777192624
6 10 1 4
3 4
5 4
7 4
2 7
9 4
10 2
8 7
1 7
6 10

output:

525980396

result:

ok 1 number(s): "525980396"

Test #7:

score: 6
Accepted
time: 3ms
memory: 36368kb

input:

10 5
156072097 743398614 639218862 297252114 250194624 291963313 870909501 644015194 402352389 623034872
7 2 6 5 8
3 7
10 7
5 7
4 3
6 4
9 4
1 10
2 6
8 10

output:

971134438

result:

ok 1 number(s): "971134438"

Test #8:

score: 6
Accepted
time: 2ms
memory: 36428kb

input:

10 6
58754522 928459597 174632208 377936445 469281312 236879760 214372862 700076292 513613148 778426835
2 9 6 8 7 10
1 3
9 3
10 9
7 9
8 7
5 7
4 9
6 4
2 10

output:

383720205

result:

ok 1 number(s): "383720205"

Test #9:

score: 6
Accepted
time: 4ms
memory: 34320kb

input:

10 7
168762354 271736588 761917216 86643499 677986829 885713846 696532784 435399905 113862203 798130316
10 6 8 5 2 1 4
6 1
7 1
3 7
8 6
9 3
5 9
2 9
10 8
4 5

output:

336844044

result:

ok 1 number(s): "336844044"

Test #10:

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

input:

10 8
727643452 96661577 109323043 94391368 943841820 772388814 620778403 424167899 950821917 236642846
6 2 8 1 7 3 10 4
4 6
1 4
10 6
3 4
7 3
2 6
9 10
5 1
8 2

output:

180649465

result:

ok 1 number(s): "180649465"

Test #11:

score: 6
Accepted
time: 4ms
memory: 32340kb

input:

10 9
117163394 156945447 136708770 224773742 105988662 323714230 608540583 786406145 376690056 848998167
5 3 1 8 9 4 2 10 7
2 5
3 5
10 2
7 2
4 3
6 3
1 4
9 5
8 7

output:

199480877

result:

ok 1 number(s): "199480877"

Test #12:

score: 6
Accepted
time: 4ms
memory: 36492kb

input:

10 1
310390327 26621492 98419973 106234069 846950161 118046850 174859624 961989377 51668388 989751256
10
7 1
9 1
2 7
5 7
10 9
6 9
8 2
4 2
3 5

output:

989751256

result:

ok 1 number(s): "989751256"

Test #13:

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

input:

10 10
455951699 832766533 368655882 274544983 630176565 149197662 125666866 811780187 718334218 758563081
6 4 8 5 7 1 2 10 9 3
7 1
10 1
4 7
9 7
6 10
8 10
5 4
2 4
3 9

output:

859352350

result:

ok 1 number(s): "859352350"

Test #14:

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

input:

10 2
987594303 113921174 60526162 363948313 953235693 442146116 239088362 970808700 672708631 266329194
1 7
3 1
5 1
7 3
4 3
9 5
6 5
10 7
2 7
8 4

output:

670634365

result:

ok 1 number(s): "670634365"

Test #15:

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

input:

10 3
816651453 62348752 681535935 116805607 955973251 476700964 874368097 579852140 368797919 88107985
3 8 9
2 1
4 1
10 2
3 2
7 4
5 4
9 10
8 10
6 3

output:

384680534

result:

ok 1 number(s): "384680534"

Test #16:

score: 6
Accepted
time: 5ms
memory: 36368kb

input:

10 4
58528783 12671113 11126837 192243188 969173998 711355158 552139230 134986041 320297780 856214300
4 10 2 5
6 1
9 1
2 6
4 6
5 9
8 9
3 2
10 2
7 4

output:

935582164

result:

ok 1 number(s): "935582164"

Test #17:

score: 6
Accepted
time: 2ms
memory: 36304kb

input:

10 5
918601200 505156312 418368340 295664939 184721209 379115481 848903082 880171694 194423672 240200865
3 4 10 1 9
5 1
6 1
9 5
10 5
2 6
4 6
7 9
3 9
8 10

output:

939502688

result:

ok 1 number(s): "939502688"

Test #18:

score: 6
Accepted
time: 3ms
memory: 34372kb

input:

10 6
533004017 920499852 255505289 485140854 915061638 943663314 522785302 422180206 691568926 180303165
4 8 6 7 2 9
10 1
4 1
9 10
8 10
3 4
5 4
7 9
6 9
2 8

output:

245402078

result:

ok 1 number(s): "245402078"

Test #19:

score: 6
Accepted
time: 2ms
memory: 36424kb

input:

10 7
352055946 828848449 193657266 250426731 531119954 123361593 818336280 448454352 385509919 877884505
4 8 1 2 3 7 5
6 1
8 1
9 6
4 6
7 8
5 8
3 9
10 9
2 4

output:

437134755

result:

ok 1 number(s): "437134755"

Test #20:

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

input:

10 8
222505897 729863884 642300093 102527485 464137817 473460079 845548391 73579791 864520933 350567502
3 8 6 5 1 4 7 2
9 1
6 1
5 9
3 9
10 6
8 6
2 5
4 5
7 3

output:

362729610

result:

ok 1 number(s): "362729610"

Test #21:

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

input:

10 9
310531917 121040796 201720207 819345654 577591809 36619321 65407253 957660104 168632846 972191988
3 2 4 10 1 8 5 7 6
8 1
3 1
9 8
4 8
2 3
5 3
6 9
10 9
7 4

output:

7616320

result:

ok 1 number(s): "7616320"

Test #22:

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

input:

10 1
176826797 993104097 437228475 200083350 883358996 226269431 774694002 958882177 761126249 319383560
1
5 10
4 5
9 4
6 9
8 6
2 8
1 2
3 1
7 3

output:

176826797

result:

ok 1 number(s): "176826797"

Test #23:

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

input:

10 10
30079784 360490012 614575707 114958413 538017501 766980081 227243229 64074734 143317951 384396094
2 6 7 8 5 1 4 10 3 9
4 6
1 4
10 1
2 10
9 2
3 9
7 3
8 7
5 8

output:

392261918

result:

ok 1 number(s): "392261918"

Test #24:

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

input:

10 2
15319105 320956351 16097549 796607736 925606797 701963523 564229119 389994811 268587770 568257143
6 5
9 3
6 9
4 6
1 4
5 1
7 5
8 7
2 8
10 2

output:

603533874

result:

ok 1 number(s): "603533874"

Test #25:

score: 6
Accepted
time: 8ms
memory: 36452kb

input:

10 3
44467062 848254409 944037739 214010122 199987320 42351578 71741265 869158293 181319317 473381037
5 2 6
8 2
10 8
9 10
1 9
3 1
4 3
6 4
5 6
7 5

output:

545061818

result:

ok 1 number(s): "545061818"

Test #26:

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

input:

10 4
190443107 301626916 303642985 164619167 499088700 93817253 975100330 262829154 978166486 288412971
10 8 2 4
8 3
6 8
2 6
10 2
5 10
9 5
7 9
4 7
1 4

output:

594401130

result:

ok 1 number(s): "594401130"

Test #27:

score: 6
Accepted
time: 4ms
memory: 36436kb

input:

10 5
110793878 310328709 227166902 980758502 554847856 359024344 463071742 292118656 631555660 980587509
9 3 6 1 7
4 9
7 4
10 7
3 10
5 3
6 5
8 6
2 8
1 2

output:

753066803

result:

ok 1 number(s): "753066803"

Test #28:

score: 6
Accepted
time: 3ms
memory: 34280kb

input:

10 6
408680647 280087657 455789909 955735280 548605911 478765573 226976310 231047820 377968528 425761364
4 10 2 5 7 8
3 9
8 3
10 8
4 10
1 4
2 1
5 2
6 5
7 6

output:

308535888

result:

ok 1 number(s): "308535888"

Test #29:

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

input:

10 7
153452208 742977622 213209346 805345546 844591057 833352142 885290602 332667906 121009427 370665044
6 4 1 5 8 9 2
5 4
3 5
8 3
9 8
2 9
1 2
7 1
6 7
10 6

output:

308496735

result:

ok 1 number(s): "308496735"

Test #30:

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

input:

10 8
935213254 97676917 940161417 449680462 488762117 149428956 53538771 149098863 224101629 296182299
3 9 7 2 4 10 5 8
9 1
3 9
6 3
7 6
5 7
2 5
4 2
10 4
8 10

output:

652166784

result:

ok 1 number(s): "652166784"

Test #31:

score: 6
Accepted
time: 4ms
memory: 34344kb

input:

10 9
456742144 553041375 5867236 530066976 785298902 317844948 748554302 641854054 754601526 830217622
3 7 6 8 5 4 1 2 10
6 4
2 6
5 2
9 5
1 9
3 1
8 3
7 8
10 7

output:

287008023

result:

ok 1 number(s): "287008023"

Test #32:

score: 6
Accepted
time: 4ms
memory: 36400kb

input:

10 1
654029472 298153105 209351017 117803612 39983728 918790970 82428460 281708618 597736551 939830393
8
3 8
4 8
2 8
5 8
10 8
9 8
1 8
7 8
6 8

output:

281708618

result:

ok 1 number(s): "281708618"

Test #33:

score: 6
Accepted
time: 4ms
memory: 32240kb

input:

10 10
815031204 504027511 420973193 443230724 60015324 629020761 198129478 973455912 667696713 81705176
4 10 1 2 6 8 9 3 5 7
1 2
5 2
10 2
8 2
6 2
7 2
9 2
3 2
4 2

output:

965712618

result:

ok 1 number(s): "965712618"

Test #34:

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

input:

10 2
810912843 321442222 167408147 150459017 319505790 205482194 434032701 915771345 32570479 46068323
4 10
6 4
1 4
5 4
10 4
9 4
8 4
3 4
2 4
7 4

output:

192345387

result:

ok 1 number(s): "192345387"

Test #35:

score: 6
Accepted
time: 3ms
memory: 36384kb

input:

10 3
28606805 992656838 409799793 284693896 665536294 735549707 385528702 709032715 127474148 628237946
1 3 10
2 8
3 8
5 8
7 8
9 8
6 8
1 8
10 8
4 8

output:

5032130

result:

ok 1 number(s): "5032130"

Test #36:

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

input:

10 4
838731516 902989484 984968609 231223629 691996501 634243912 628250615 2314503 251145300 660804486
8 2 4 1
3 7
1 7
8 7
10 7
4 7
9 7
6 7
5 7
2 7

output:

393189683

result:

ok 1 number(s): "393189683"

Test #37:

score: 6
Accepted
time: 2ms
memory: 36368kb

input:

10 5
103358211 987438369 172995049 181914491 650269872 961462921 148532141 506079325 420012385 411301164
9 7 5 1 8
1 2
6 2
7 2
4 2
8 2
5 2
10 2
9 2
3 2

output:

243389542

result:

ok 1 number(s): "243389542"

Test #38:

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

input:

10 6
738939095 462022763 568173107 500905679 321356488 753819583 159648909 619473204 606464394 19394894
5 10 6 1 3 9
9 4
1 4
2 4
6 4
5 4
3 4
7 4
8 4
10 4

output:

123685535

result:

ok 1 number(s): "123685535"

Test #39:

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

input:

10 7
202547886 646401736 93164326 422174119 436766865 666557482 142214475 72224229 969751790 188142466
4 8 3 10 6 7 2
7 1
8 1
5 1
2 1
10 1
4 1
9 1
6 1
3 1

output:

171412495

result:

ok 1 number(s): "171412495"

Test #40:

score: 6
Accepted
time: 3ms
memory: 34404kb

input:

10 8
342750163 757047550 6702148 786150699 919530550 866064379 196212597 270399055 646964848 71988965
4 9 1 2 5 6 7 8
5 10
6 10
1 10
9 10
8 10
4 10
7 10
3 10
2 10

output:

410117969

result:

ok 1 number(s): "410117969"

Test #41:

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

input:

10 9
708468107 852623868 230491853 68750332 475802506 803976211 334452286 841322432 721667182 67588114
2 1 3 4 7 9 10 6 5
3 5
7 5
1 5
6 5
2 5
4 5
10 5
8 5
9 5

output:

391675231

result:

ok 1 number(s): "391675231"

Test #42:

score: 6
Accepted
time: 2ms
memory: 21928kb

input:

10 5
323063351 730481512 370548177 802215316 911918467 914669598 543857289 821891818 548953740 960792658
10 6 7 3 3
3 4
10 4
9 10
7 3
5 4
1 9
8 7
2 10
6 2

output:

0

result:

ok 1 number(s): "0"

Subtask #3:

score: 11
Accepted

Test #43:

score: 11
Accepted
time: 231ms
memory: 73192kb

input:

500000 600
375999961 486674339 753591626 263678997 153496902 843204506 294273913 59353025 80121537 938426018 309354784 359915003 480316315 880954496 544396164 478808641 583197144 202111021 277512785 193266475 511298159 750302398 30978705 278891583 701736665 516664158 47658598 456194527 517690925 870...

output:

739558267

result:

ok 1 number(s): "739558267"

Test #44:

score: 11
Accepted
time: 209ms
memory: 69036kb

input:

500000 600
144424234 822427316 300192847 7262228 210896294 454472658 15628508 599308527 39208834 748087468 100403532 861554271 440434658 207763150 960826231 405540153 513306322 903562629 19659973 24682032 339889038 859238787 933505007 113096874 144805990 391745221 750054096 992392845 976030209 54069...

output:

144059750

result:

ok 1 number(s): "144059750"

Test #45:

score: 11
Accepted
time: 221ms
memory: 71104kb

input:

500000 600
331840935 487267543 141846510 959026554 23406702 924114236 382412574 498288136 278551271 468110673 889355705 280620460 293234713 915880082 112280963 634256130 769027328 297590919 844224351 761851954 220242868 91163991 403705643 47533012 401410594 110156291 810282175 26989897 18481764 8392...

output:

483838047

result:

ok 1 number(s): "483838047"

Test #46:

score: 11
Accepted
time: 180ms
memory: 72100kb

input:

500000 600
53862718 259806630 150158643 181217331 113064043 454111950 428452164 976639831 608516063 26785656 323722935 479978164 897653034 385776962 891522660 805681141 668633845 682173127 425775925 152860757 661118323 78766810 557465765 279838691 263662634 788444774 35025549 657163252 525195519 667...

output:

571994801

result:

ok 1 number(s): "571994801"

Test #47:

score: 11
Accepted
time: 550ms
memory: 115356kb

input:

500000 600
503473613 365243138 600037485 794034899 794552034 774168344 213632833 222607873 840997672 209089919 507182333 932583841 952032419 58613852 251087250 669879021 47148034 550524618 392246249 639068987 776360220 40611378 480234261 470879368 887158649 370114946 968903569 166932590 98362078 781...

output:

113780969

result:

ok 1 number(s): "113780969"

Test #48:

score: 11
Accepted
time: 139ms
memory: 70388kb

input:

500000 600
607381480 855257322 86837613 746292682 784437716 57828253 965602864 73366173 773343611 613090636 974259882 306344413 101762602 561276318 273649470 372936825 332131006 195006635 706694602 206926288 569775417 575506863 69587689 306273511 861134280 539359231 514955013 395790534 233435991 109...

output:

706488870

result:

ok 1 number(s): "706488870"

Test #49:

score: 11
Accepted
time: 29ms
memory: 26760kb

input:

500000 600
47276203 913060613 450816229 609126980 959139016 643131397 323632377 809345946 695036059 311699768 499433533 464837625 20916653 253473039 272974046 144202520 759240782 322252624 597886217 304390498 467405890 162800240 73662318 67080226 221733451 123656796 186936776 424886406 794288225 915...

output:

0

result:

ok 1 number(s): "0"

Subtask #4:

score: 29
Accepted

Dependency #2:

100%
Accepted

Test #50:

score: 29
Accepted
time: 0ms
memory: 34548kb

input:

3000 1500
42883564 80574283 273833934 166057637 337879912 877080836 107149196 39638806 454969404 374763652 551323106 166695380 602768449 131716757 93613885 683355340 354969975 271162786 859687815 486896647 564174656 565933300 181982453 662453794 472529628 519108624 263406891 422398508 149982516 2879...

output:

585147791

result:

ok 1 number(s): "585147791"

Test #51:

score: 29
Accepted
time: 0ms
memory: 36492kb

input:

3000 100
406481723 737771418 389556572 897703654 86847332 28379824 186208305 700232412 799869874 551278992 2314371 398829981 881278199 30789925 106812709 589775614 587779670 712118576 17675095 577277291 880965849 785287517 553644697 852741576 268770346 476867584 389294691 57923005 103117096 28888297...

output:

631712859

result:

ok 1 number(s): "631712859"

Test #52:

score: 29
Accepted
time: 5ms
memory: 34476kb

input:

3000 2999
496778258 78347774 65717662 241566493 263636829 607742551 326237834 826635844 415444681 464676451 81457464 400152693 673900135 577777267 494402263 679016148 398084693 594146900 683604271 18559177 876807587 776878405 669934875 480800040 130156446 405001532 219553217 507424998 58509036 86188...

output:

6809706

result:

ok 1 number(s): "6809706"

Test #53:

score: 29
Accepted
time: 3ms
memory: 38660kb

input:

3000 2000
81926901 577404940 595738842 997580474 601316741 702969700 292210507 79447327 315199288 607496655 356829447 715741109 231885409 718091006 186345206 469133857 470871384 538323490 112657809 485696737 901486276 417660110 86421995 210306791 202031936 480791012 18009896 276458319 724521600 8412...

output:

577865481

result:

ok 1 number(s): "577865481"

Test #54:

score: 29
Accepted
time: 4ms
memory: 36600kb

input:

3000 1500
329906058 830350650 760729564 406865460 392429561 51121442 604853716 79727392 175756022 925836158 78146965 188663709 184716001 264646438 989190525 545621486 842771253 582016935 636065352 470253822 472219891 137307703 472674375 111237845 178492739 14046898 761748125 735321992 325813701 8097...

output:

432621237

result:

ok 1 number(s): "432621237"

Test #55:

score: 29
Accepted
time: 4ms
memory: 36560kb

input:

3000 100
928499233 225959659 86893719 96153598 814679220 444061720 764300592 996717680 584781375 79790321 627507654 208888613 715916780 823266852 281918285 946519653 791504479 206084252 123808495 714756142 108308002 275542582 748238962 558326597 459473217 259710926 390759040 504341237 752801332 7613...

output:

724230792

result:

ok 1 number(s): "724230792"

Test #56:

score: 29
Accepted
time: 0ms
memory: 32384kb

input:

3000 2999
85463697 771370838 942869660 24361575 679604883 802074588 9212949 356105299 780377648 818715205 895668514 868762968 828432606 482676035 245001957 851720485 970298719 525652919 511657 419196957 155644704 328926619 981507883 402503163 755661168 663718004 671015306 399636511 937968294 2081504...

output:

989972013

result:

ok 1 number(s): "989972013"

Test #57:

score: 29
Accepted
time: 4ms
memory: 36544kb

input:

3000 2000
468712625 776623564 962985205 81345933 650902827 807699925 285672027 79964867 877939192 990322346 188506716 203603879 292292306 840410960 849619751 223120405 28927084 644341328 861354589 183128106 199188486 324710283 672439640 450405179 66509370 876136323 367858765 884344570 522428067 6055...

output:

840153604

result:

ok 1 number(s): "840153604"

Test #58:

score: 29
Accepted
time: 3ms
memory: 36860kb

input:

3000 1500
397284276 973512698 726328051 185111766 190756326 134872324 121829360 842204258 152467813 913261943 927390002 589534815 539104011 203239616 621873000 294693262 413715921 858172340 665169082 116291294 695156770 898154865 74887307 524036840 711411619 520371755 592561146 805530590 941088479 1...

output:

470737370

result:

ok 1 number(s): "470737370"

Test #59:

score: 29
Accepted
time: 6ms
memory: 36736kb

input:

3000 100
872426571 176711449 170040374 682404894 521403864 357549062 514231690 841793182 703306296 203438876 158469499 551987976 492655833 119721601 725873231 590743343 559905798 679009075 397692272 356580932 638007195 201681101 700155142 144536274 551250774 81742787 881699915 404838924 527004639 73...

output:

748023974

result:

ok 1 number(s): "748023974"

Test #60:

score: 29
Accepted
time: 5ms
memory: 36672kb

input:

3000 2999
182687894 213985577 239947187 166007369 103682596 583162905 183288483 730806228 609394025 631805125 891797575 942327511 379980210 385585830 785962410 105234763 141296468 351130466 46939033 448929723 519906692 19003448 5974421 407159751 549218524 527084101 25109390 461561490 766641179 45906...

output:

666840804

result:

ok 1 number(s): "666840804"

Test #61:

score: 29
Accepted
time: 4ms
memory: 34724kb

input:

3000 2000
324855847 391675781 948238058 940850830 905223162 244202019 112615496 402363187 735392206 936107579 103711008 178578450 357339094 902283223 103434377 755059657 297253425 53614850 575084051 687541586 481607194 366548476 915357783 91512150 901593902 408131309 878870032 616792326 738512900 80...

output:

718064190

result:

ok 1 number(s): "718064190"

Test #62:

score: 29
Accepted
time: 4ms
memory: 36612kb

input:

3000 2778
861328063 227661828 986730560 592966646 492723707 714518080 365790883 774032879 455727872 170409099 941291352 69250972 227548550 110021382 947470313 297854855 362783484 28367664 227354293 171492376 682912069 828628996 732717677 797660867 712263671 207709917 534174081 618710887 668036028 85...

output:

595387225

result:

ok 1 number(s): "595387225"

Test #63:

score: 29
Accepted
time: 3ms
memory: 36612kb

input:

3000 2137
423935941 546297660 810369541 906415562 84904067 695556892 317838629 753964929 133153304 8812501 208777724 673220731 581228598 236465455 151620062 614120245 961384388 657453079 26713136 58128481 804103577 508654256 804530966 944092201 303655362 765356548 865544598 779562479 930090188 50736...

output:

940998569

result:

ok 1 number(s): "940998569"

Test #64:

score: 29
Accepted
time: 0ms
memory: 36544kb

input:

3000 2525
717190635 631092218 604248732 552421497 165614079 656959486 493899014 308505691 269248491 534601785 278747247 826120661 505378752 409485406 837032885 636942342 795166012 400998481 353236352 895254300 224875909 511670541 986794699 925225059 430873962 282149801 949448497 759136473 201699913 ...

output:

287088202

result:

ok 1 number(s): "287088202"

Test #65:

score: 29
Accepted
time: 0ms
memory: 36492kb

input:

3000 2693
336882287 300608817 797879015 12795806 816112083 814856416 253613782 902808816 64817357 585772948 430993799 483081645 755574375 797728836 243170944 356949481 877031858 455478430 46761483 62679400 742033898 49451734 67363689 966156171 98477983 663936318 105868817 897173457 321140249 8765775...

output:

414460985

result:

ok 1 number(s): "414460985"

Test #66:

score: 29
Accepted
time: 4ms
memory: 34548kb

input:

3000 1209
163283284 673092992 263687678 773903965 529999499 805613065 229039816 361889699 582092852 864836189 203932058 863821740 362552003 109588069 515608530 671919358 755439987 132806822 108683122 877224298 155721088 125877 754727320 300524311 770003567 137701837 54661462 299973612 821666081 1969...

output:

110883990

result:

ok 1 number(s): "110883990"

Test #67:

score: 29
Accepted
time: 3ms
memory: 38644kb

input:

3000 1460
746646704 833243297 21111249 83417077 544667549 192161597 87551064 239524022 732231008 73360415 492286017 334285333 827815095 419667352 727721061 325121587 261901239 295270417 128248965 537277825 576573378 842023190 776732153 360166342 828828961 163815688 142691647 36045734 800344143 98203...

output:

988301414

result:

ok 1 number(s): "988301414"

Test #68:

score: 29
Accepted
time: 4ms
memory: 36624kb

input:

3000 1459
303982108 356522996 309693055 345392315 652532441 612720073 638908827 500904183 352496137 437016038 185982530 864212153 951418669 126919332 383594652 83915146 272633311 993033879 341464146 498705657 178425026 450742138 907192399 602748957 802963704 182085096 503731040 990745993 380454544 9...

output:

467649547

result:

ok 1 number(s): "467649547"

Test #69:

score: 29
Accepted
time: 0ms
memory: 34488kb

input:

3000 319
461074884 317270297 765735982 30930764 440140521 773111556 865349002 771878793 239657248 386711905 995558015 672680458 442252235 398252805 126122832 898281685 179921591 885004139 461548320 726810422 548704954 362998876 761010262 601717401 585451729 400599217 838125434 759736804 265575975 25...

output:

729860568

result:

ok 1 number(s): "729860568"

Test #70:

score: 29
Accepted
time: 0ms
memory: 38584kb

input:

3000 1316
878511081 937338967 358818349 905935415 725945250 346945292 898402798 130058465 136976405 347771034 310388130 614990543 904524137 447348923 535193834 28552743 761823855 706066105 627834284 430365049 561640998 378661913 334088312 213185670 302305953 342289934 482512477 220115165 870144747 5...

output:

915697525

result:

ok 1 number(s): "915697525"

Test #71:

score: 29
Accepted
time: 0ms
memory: 34544kb

input:

3000 1992
435504093 169275140 720301815 961097462 722511562 200270589 748616471 851237173 933735217 778644099 877426631 554733395 384575200 518483587 51729673 374587352 652127901 639019337 761720159 551202875 335955435 119563139 652898749 732886962 918859366 36180303 630799088 563255160 254976151 83...

output:

831697430

result:

ok 1 number(s): "831697430"

Test #72:

score: 29
Accepted
time: 4ms
memory: 36548kb

input:

3000 1500
4642201 624638397 653848565 857166971 934423790 530916935 78522369 968902313 974440508 490531830 355191683 267730046 502520149 210367680 527925773 977080746 943888335 118201932 59234058 389935214 833345035 293432674 998242488 306048673 15698433 961594729 182944752 850849228 829124243 75781...

output:

513343504

result:

ok 1 number(s): "513343504"

Test #73:

score: 29
Accepted
time: 0ms
memory: 36484kb

input:

3000 100
836874254 206784635 253297366 910419080 846426068 485126432 505483795 37792327 226315271 345520467 765757832 258698167 245620729 202100267 754987968 660711324 38782581 496090844 352674511 541736139 121458750 934345159 363805754 451408507 649257234 78835432 866988377 870113481 941455201 9495...

output:

263480544

result:

ok 1 number(s): "263480544"

Test #74:

score: 29
Accepted
time: 0ms
memory: 34428kb

input:

3000 2999
757694387 68290630 764368450 138576926 989817480 712797143 261130312 726517444 907272541 559818054 101788452 507398530 169208082 674770945 968454260 866159731 638085205 246570300 74740715 375274926 44450814 995347336 138764159 545482819 459776410 287208600 155858495 220391785 354264010 409...

output:

210375149

result:

ok 1 number(s): "210375149"

Test #75:

score: 29
Accepted
time: 0ms
memory: 32488kb

input:

3000 2000
604896907 744155454 345238763 196339752 694494171 135437217 436773828 842799114 122471430 165033160 775058671 766145281 661566365 87557316 452335822 783241594 718784182 321904411 537242178 647731621 504743709 604882810 152059486 987065956 583530983 519195941 165831374 545597519 533902653 6...

output:

96056543

result:

ok 1 number(s): "96056543"

Test #76:

score: 29
Accepted
time: 0ms
memory: 22084kb

input:

3000 600
910859265 509355593 656323749 678871204 334930578 771068780 56356418 491361170 137710041 636396915 672236379 679534243 671011986 971317015 553547686 154011827 812031257 207141131 924490715 384785717 446516934 518899052 339384806 87210703 15268276 476263912 654451138 299308690 810308691 3473...

output:

0

result:

ok 1 number(s): "0"

Subtask #5:

score: 16
Accepted

Test #77:

score: 16
Accepted
time: 611ms
memory: 88920kb

input:

500000 500000
200910665 704700912 664276 824905098 512233060 623259142 478040808 509760810 756074623 387351466 261683363 140331101 135736712 184881987 425557684 61914673 951508934 787260914 386285199 40458274 175322609 429002885 606957721 742057849 342942076 104844271 656874266 826513447 76400873 55...

output:

771496320

result:

ok 1 number(s): "771496320"

Test #78:

score: 16
Accepted
time: 655ms
memory: 88584kb

input:

500000 500000
393325784 423307620 769839934 488701594 34980277 797798611 971252417 460892286 567253464 767364025 93413829 75786578 256363071 217722512 645295877 510711584 480877049 428293642 214340569 818013745 26677511 669553845 89063601 534123295 248791524 138950624 251295359 636455647 417371091 7...

output:

439789184

result:

ok 1 number(s): "439789184"

Test #79:

score: 16
Accepted
time: 669ms
memory: 90528kb

input:

500000 500000
304834659 23334136 281137008 195895112 196794218 9096321 550195738 251406926 794310053 392944702 896889429 377202988 383812779 855411433 996638204 176946965 14610588 31326580 287865536 285356776 15181214 721975103 7479393 923265076 700703478 244253830 13595300 191060192 506315015 82731...

output:

386763205

result:

ok 1 number(s): "386763205"

Test #80:

score: 16
Accepted
time: 851ms
memory: 114608kb

input:

500000 500000
963769621 792032953 548743692 812303224 806859822 107106153 670071669 457532666 516564922 867509289 563112863 620766458 971804950 533739313 126272905 817695615 569475276 227580608 323342974 375310982 265196242 579298928 82855065 820284887 873105018 906167288 489289717 472219706 8127735...

output:

490477004

result:

ok 1 number(s): "490477004"

Test #81:

score: 16
Accepted
time: 509ms
memory: 89792kb

input:

500000 500000
934825416 221317375 979103615 273478171 355638257 208592783 254723141 463073783 405970022 680755268 266037075 931070258 928975898 442231376 471302244 364395206 266480387 284288074 707928785 957518641 526274338 899411209 442421594 13370142 383410592 249354068 255747031 99288455 18754772...

output:

809226100

result:

ok 1 number(s): "809226100"

Subtask #6:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #82:

score: 35
Accepted
time: 238ms
memory: 72000kb

input:

500000 1000
292277236 238577278 136014715 118409268 431366200 416212021 826010725 594798761 392307591 722643781 747229247 982293551 413081113 779651179 517624118 570994191 741068717 510679203 39371111 625990426 90936949 351765808 326779156 232694008 184751304 40257549 808704006 810769625 65573051 97...

output:

871348275

result:

ok 1 number(s): "871348275"

Test #83:

score: 35
Accepted
time: 630ms
memory: 83644kb

input:

500000 200000
2362365 248521990 554378695 948006277 743306081 895088490 95085339 572721464 336244288 494382610 167887956 332392134 584390396 42484353 68683872 846215204 838316126 185820051 672223916 206971305 271963348 504703037 716956333 279024606 418771740 8516005 731348707 897387669 733690756 121...

output:

481303146

result:

ok 1 number(s): "481303146"

Test #84:

score: 35
Accepted
time: 270ms
memory: 72768kb

input:

500000 1000
516345906 424650485 624687412 615928420 682024306 351614558 773791375 467776523 540237412 369520222 399211094 633155481 59987371 187448869 442608203 200305553 502184180 443014937 265462382 802268390 213950197 235129172 302822850 102565815 684500951 280645321 194036175 267038465 326454797...

output:

705870347

result:

ok 1 number(s): "705870347"

Test #85:

score: 35
Accepted
time: 520ms
memory: 84552kb

input:

500000 200000
266938343 511593146 717203114 80864939 132674177 38733700 321148684 243430282 955539002 909361259 146967443 704106047 122128369 719408401 565902011 303254233 326687510 288182056 367736831 12733978 482444013 983906703 510473714 550585655 43931175 530855350 292039211 699128928 222511712 ...

output:

401859828

result:

ok 1 number(s): "401859828"

Test #86:

score: 35
Accepted
time: 587ms
memory: 116848kb

input:

500000 1000
395026269 877144043 897629156 33012620 390380932 38995109 602693238 103368964 811076081 303805096 498224191 160503510 806017609 881421302 248039437 525474824 519414550 767090927 273684450 128479650 809343409 264208498 76778023 212069157 179689333 283586568 179964723 133530069 342495436 5...

output:

75496538

result:

ok 1 number(s): "75496538"

Test #87:

score: 35
Accepted
time: 783ms
memory: 135152kb

input:

500000 200000
387212727 372381957 571898900 316704350 84308620 700977324 941738552 884696873 493028907 455642315 891071173 531681789 975140740 439028173 38187166 96065980 476335138 749306218 250554723 221752632 564836652 334560418 226112305 301355719 227539937 535598514 304912951 923066576 665810158...

output:

94352274

result:

ok 1 number(s): "94352274"

Test #88:

score: 35
Accepted
time: 541ms
memory: 83596kb

input:

500000 182169
281782310 825385984 497975797 402470799 483210204 601221738 444728163 771387537 61791690 669944551 911553399 868801538 315918030 956538385 343309237 110048412 564925910 479817993 658011318 685379177 273572855 537001011 419648596 652939939 889833775 175217251 331940356 756147462 3147812...

output:

380503798

result:

ok 1 number(s): "380503798"

Test #89:

score: 35
Accepted
time: 330ms
memory: 75500kb

input:

500000 58990
397615696 203456312 265694321 850759065 973964750 825791068 754476405 929297497 623619339 362938767 229523572 171239204 67800652 722445389 496831686 754285503 630480702 776246231 455339785 989460582 890116966 426466076 246363470 898057751 885824604 165187108 634777678 177998272 41621932...

output:

336371539

result:

ok 1 number(s): "336371539"

Test #90:

score: 35
Accepted
time: 605ms
memory: 95972kb

input:

500000 425928
102861572 941370277 640358362 403421011 126295605 406111069 364564869 162821088 320258254 836914437 609652357 955174265 342788762 581952196 169656525 583728122 376571786 856869356 118422149 318682586 106040151 652994400 613218869 271717161 565586481 713362843 44255537 353606834 8171094...

output:

325171498

result:

ok 1 number(s): "325171498"

Test #91:

score: 35
Accepted
time: 547ms
memory: 93892kb

input:

500000 290695
558057768 489805064 361230023 590580709 406449512 894545041 884939630 560272848 199383527 362688075 911362989 616639427 903439027 639994217 946708565 117393287 29618698 454052769 6760359 373803642 174812397 558589176 834814878 495060447 753954148 407091667 501648661 860547660 724981453...

output:

285384108

result:

ok 1 number(s): "285384108"

Test #92:

score: 35
Accepted
time: 136ms
memory: 71752kb

input:

500000 1000
983615298 136866929 749332328 822693130 566390884 953359269 879947919 54609942 893325059 438211840 500092879 769712440 881143810 120395120 148621275 229638689 4543245 598472790 850134316 355441517 44045330 784592004 20199166 183301798 1837168 177574127 538003106 916171808 243416410 73869...

output:

801876776

result:

ok 1 number(s): "801876776"

Test #93:

score: 35
Accepted
time: 249ms
memory: 79548kb

input:

500000 200000
422449221 833205672 379303886 879348175 872993811 791666686 564642727 291018070 461083664 423530366 340994334 755533549 511866905 6988939 156078558 876191974 818005939 527141434 840709275 420648223 97599519 701112200 572289883 237005710 76263002 9190701 684366145 199232978 820607996 33...

output:

94198829

result:

ok 1 number(s): "94198829"

Test #94:

score: 35
Accepted
time: 49ms
memory: 29788kb

input:

500000 250000
621664539 717101365 376985909 709515423 325017936 660135072 349368774 978673975 202396422 790032885 645120448 921601616 738206883 794495787 524987800 815583101 865635560 697177439 530113560 494748975 106614188 527565705 328384039 481482246 269392014 212511535 372801202 218883500 185542...

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed