QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56487#4240. Tree CirclesKING_UT#AC ✓265ms92228kbC++204.4kb2022-10-19 19:05:492022-10-19 19:05:51

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-19 19:05:51]
  • Judged
  • Verdict: AC
  • Time: 265ms
  • Memory: 92228kb
  • [2022-10-19 19:05:49]
  • Submitted

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

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

using ll=long long;
using uint=unsigned;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;

using vi=vc<int>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){a=b;return true;}
	else return false;
}

#define mp make_pair
#define a first
#define b second
using pi=pair<int,int>;

const int inf=INT_MAX/2-100;

const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint&s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint&operator+=(mint r){return s(v+r.v);}
	mint&operator-=(mint r){return s(v+mod-r.v);}
	mint&operator*=(mint r){v=(unsigned ll)v*r.v%mod;return *this;}
	mint&operator/=(mint r){return *this*=r.inv();}
	mint operator+(mint r)const{return mint(*this)+=r;}
	mint operator-(mint r)const{return mint(*this)-=r;}
	mint operator*(mint r)const{return mint(*this)*=r;}
	mint operator/(mint r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};

struct unionfind{
	vi p,s;
	unionfind(int n):p(n,-1),s(n,1){}
	int find(int i){
		return p[i]==-1?i:p[i]=find(p[i]);
	}
	void unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return;
		p[b]=a;
		s[a]+=s[b];
	}
};

template<class E>
struct HLD{
	vvc<E> g;
	int n,rt,cnt;
	vi sub,in,out,par,head,dep,hei,ni;
	vc<E> pe;
	int dfs1(int v,int p,int d){
		par[v]=p;
		dep[v]=d;
		
		for(auto&e:g[v]){
			pe[e]=e;
			sub[v]+=dfs1(e,v,d+1);
			if(sub[g[v][0]]<sub[e])
				swap(g[v][0],e);
		}
		return sub[v];
	}
	void dfs2(int v,int h){
		in[v]=cnt++;
		head[v]=h;
		for(int to:g[v])
			dfs2(to,to==g[v][0]?h:to);
		out[v]=cnt;
		if(si(g[v]))hei[v]=hei[g[v][0]]+1;
	}
	HLD(const vvc<E>&gg,int rr):g(gg),n(si(g)),rt(rr),cnt(0),
	sub(n,1),in(n),out(n),par(n,-1),head(n),dep(n),hei(n,1),ni(n),pe(n){
		dfs1(rt,-1,0);
		dfs2(rt,rt);
		rep(i,n)ni[in[i]]=i;
	}
	int lca(int a,int b){
		while(head[a]!=head[b]){
			if(dep[head[a]]>dep[head[b]])
				swap(a,b);
			b=par[head[b]];
		}
		if(dep[a]>dep[b])swap(a,b);
		return a;
	}
	vi index;
	pair<vi,vc<pi>> tree_compress(vi vs){
		if(si(index)==0)index.resize(n);
		assert(si(index));
		auto comp=[&](int x,int y){
			return in[x]<in[y];
		};
		sort(all(vs),comp);
		vs.erase(unique(all(vs)),vs.ed);
		int k=si(vs);
		rep(i,k-1)vs.pb(lca(vs[i],vs[i+1]));
		sort(all(vs),comp);
		vs.erase(unique(all(vs)),vs.ed);
		k=si(vs);
		rep(i,k)index[vs[i]]=i;
		vc<pi> es;
		rng(i,1,k){
			int p=lca(vs[i-1],vs[i]);
			es.eb(i,index[p]);
		}
		return mp(vs,es);
	}
};

void slv(){
	int n;cin>>n;
	vvc<int> t(2*n-1);
	unionfind uf(2*n-1);
	rng(i,n,2*n-1){
		int a,b;cin>>a>>b;
		a--;b--;
		a=uf.find(a);
		b=uf.find(b);
		t[i].pb(a);
		t[i].pb(b);
		uf.unite(i,a);
		uf.unite(i,b);
	}
	HLD<int> h(t,2*n-2);
	
	vvc<int> g;
	
	int q;cin>>q;
	rep(_,q){
		int k;cin>>k;
		vi vs(k);rep(i,k){cin>>vs[i];vs[i]--;}
		/*vc<pi>es;
		tie(vs,es)=h.tree_compress(vs);
		
		int s=si(vs);
		g.resize(s);
		rep(i,s)g[i].clear();
		//cerr<<_+1<<endl;
		//rep(i,s)cerr<<vs[i]<<" ";
		//cerr<<endl;
		rep(i,s-1){
			//cerr<<es[i].a<<" "<<es[i].b<<endl;
			g[es[i].b].pb(es[i].a);
		}
		using P=pair<mint,mint>;
		
		auto dfs=[&](auto self,int v,int p)->P{
			P res;
			if(g[v].empty()){
				res=P(0,1);
			}else{
				assert(si(g[v])==2);
				P a=self(self,g[v][0],v);
				P b=self(self,g[v][1],v);
				res.a=a.a*b.a;
				res.b=a.a*b.b+a.b*b.a;
			}
			if(p!=-1){
				int w=vs[p]-max(vs[v],n-1);
				res.a+=res.b*w;
			}
			return res;
		};
		P ans=dfs(dfs,0,-1);
		cout<<ans.b.v<<"\n";*/
		
		sort(all(vs),[&](int x,int y){return h.in[x]<h.in[y];});
		vi mn(k,2*n-1);
		rep(i,k-1){
			int v=h.lca(vs[i],vs[i+1]);
			chmin(mn[i],v);
			chmin(mn[i+1],v);
		}
		mint ans=1;
		rep(i,k)ans*=mn[i]-(n-1);
		cout<<ans.v<<'\n';
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	//int t;cin>>t;rep(_,t)
	slv();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3648kb

input:

3
1 2
2 3
2
3 1 2 3
2 1 3

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: 0
Accepted
time: 37ms
memory: 3868kb

input:

1000
251 1
610 251
1 621
610 534
617 1
27 617
54 534
251 435
610 984
1 850
291 610
251 461
51 27
376 617
461 310
36 850
36 351
456 461
461 171
456 294
949 294
688 1
833 610
174 534
435 841
841 60
556 251
251 423
655 376
688 188
610 448
456 549
894 841
65 688
65 522
421 435
382 65
894 613
617 789
880...

output:

275623202
374067774
494473471
420011499
643061355
554361044
755532440
289845686
45368764
527834219
925520205
659238238
433870012
469990636
657873561
852213216
966862980
542663190
982471669
458857532
478701698
947460452
451178245
603042191
422792889
685952031
417241570
548357718
223143158
101179924
9...

result:

ok 1000 numbers

Test #3:

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

input:

2000
1 1229
1229 743
7 1229
7 1684
293 1
1652 293
1458 743
293 1912
1912 1726
359 1458
372 743
772 293
756 1
409 1726
1652 921
433 1912
359 1515
1458 1897
1458 1439
409 952
1439 1877
1298 756
743 1055
1665 1897
1313 743
743 978
1515 1099
627 409
1665 1318
921 1859
293 39
627 1954
1665 646
1055 1584
...

output:

985661081
289663642
426379198
961782139
145012705
45028730
513933554
853668549
529541313
702845230

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 246ms
memory: 89900kb

input:

300000
1 265092
1 46487
265092 220364
124925 1
1 288590
265092 156898
280571 46487
184789 220364
280571 151321
280571 66880
86168 151321
151321 273555
46487 112431
124925 45049
1 66769
112431 36492
86168 137565
251083 66880
143467 66880
284087 1
280571 112916
112431 254872
238475 280571
180865 36492...

output:

425265333
650921663
28695301
191498362
567238295
582516091
948253770
242063171
597569966
190082202
300000
521207503
300000
570927982
122195019
889056495
982165169
300000
70088500
224396729
443558073
770844475
992420728
129019298
66932621
140351691
402404024
748029355
324810833
847382658
975494158
23...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 265ms
memory: 90044kb

input:

300000
79564 1
47775 1
1 55662
1 95099
46649 1
132646 1
105499 1
79564 290851
1 9253
281426 1
1 110805
1 216082
117289 55662
294531 79564
1 53982
107060 1
1 176946
79564 110870
229429 79564
246870 55662
115502 55662
129935 47775
174291 1
147090 47775
1 226095
241060 79564
32290 9253
55662 236528
795...

output:

300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000...

result:

ok 300000 numbers

Test #6:

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

input:

300000
116934 1
1 182470
152180 1
93537 1
241528 1
1 240053
109127 1
180738 1
280053 1
93887 116934
29885 1
1 86207
1 228297
193775 116934
1 175284
1 151285
182470 85967
116934 187438
221233 1
50563 1
166403 240053
1 227052
152180 9889
23189 1
182470 113585
256036 241528
287678 109127
104179 182470
...

output:

714000148
300000
174066807
300000
47525612
760523799
506417577
543570745
426849467
234698179
181019066
293681713
85952591
861174021
335750354
275816026
300000
789961803
524888729
828570588
537371431
566627474
891911870
300000
839889510
206649204
351689600
752698283
879503419
735693514
479114908
3023...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 230ms
memory: 90036kb

input:

300000
210587 1
1 104556
19707 1
1 211524
41604 1
1 90342
101151 1
1 72463
104556 129396
1 19676
1 290787
117637 210587
50372 210587
121945 1
1 98314
265433 1
168223 1
124102 210587
237576 210587
1 178683
144542 104556
19707 209307
1 203353
24946 211524
173967 19707
1 187376
82934 210587
13215 1
210...

output:

185583551
821280343
258654503
839901552
627857271
452006338
846340886
598211011
108466210
420855740
298766579
25109357
177286059
818396912
789709981
632551495
869991650
865368372
47875087
297776219
681259147
527786931
851185890
166047110
853559859
435549961
422481660
441219611
777076356
782913251
84...

result:

ok 30000 numbers

Test #8:

score: 0
Accepted
time: 236ms
memory: 90064kb

input:

300000
3595 1
1 201293
26120 1
1 246277
195374 1
216294 1
204662 1
23675 3595
32865 3595
204271 3595
3595 239870
3595 270001
255649 201293
195693 3595
1 228826
1 107858
1 248831
253806 1
122498 1
26120 58309
246277 121452
81219 1
195374 89784
246277 237757
216294 190889
26120 148293
26120 246942
221...

output:

180707128
691081541
119348846
844365810
47017673
63585014
752113560
522149235
573217320
94296030
549628937
493008829
304886615
688197776
937351562
378683021
992918562
83275890
17356353
628070191
301989238
165043209
508761379
124112700
227845632
613580595
240995229
554234612
774007467
895006949
30005...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 242ms
memory: 90032kb

input:

300000
61105 1
61105 154295
193577 154295
60755 1
154295 85469
1 286658
193577 81084
45864 61105
286658 248457
193577 148069
61105 128974
154295 291326
35405 60755
46532 61105
286658 294578
202151 154295
201363 291326
252027 35405
217884 286658
78620 35405
81084 296367
187588 128974
143335 294578
19...

output:

300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000...

result:

ok 300000 numbers

Test #10:

score: 0
Accepted
time: 257ms
memory: 89980kb

input:

300000
1 122693
1 266822
270744 122693
122693 211140
102058 1
122693 24434
231158 1
105829 270744
158127 102058
118361 158127
1 195824
266822 147530
158127 137954
102058 298976
137954 296794
118361 148402
1 55640
231158 202204
211140 176377
122693 78171
211140 198703
266822 25208
164354 270744
10205...

output:

972478860
727500590
966350803
941578681
300000
888955874
540340352
224972571
116926389
289878431
300000
490829762
267344703
114071170
620963259
20804661
663549826
938826349
276691252
288298971
664481708
484260055
300000
219405489
628463999
300000
39521744
195623654
516772446
406616563
679216515
5290...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 232ms
memory: 89976kb

input:

300000
1 152493
22345 1
152493 189747
1 270064
81374 152493
81374 162573
111000 152493
1 111284
152493 102640
276263 152493
189747 257123
3977 162573
115989 1
1 121537
67540 115989
111000 284566
248956 111000
162573 33283
162573 255858
618 1
3977 270011
276263 283051
147237 270064
1 190852
618 25654...

output:

155769907
11405955
271799289
239307105
809008662
480410252
963584842
194180529
651855397
415368463
932963668
472009522
11315308
148221753
106953936
932019422
84917756
173959130
618714409
351834943
113722239
321265061
651364014
946440714
547989690
41360505
179574252
719608678
718006665
449145748
4845...

result:

ok 3000 numbers

Test #12:

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

input:

300000
1 243295
219700 1
34505 243295
37545 1
243295 69980
37545 125560
131391 34505
97894 219700
125560 128926
23878 219700
68334 243295
35726 243295
81358 1
34505 59254
194150 131391
243072 243295
34505 157888
69980 254018
246638 194150
1 142576
44767 243295
131391 23053
1 239294
219700 273609
716...

output:

495424543
869207668
467721751
167205281
47486735
909958732
422095282
437463788
834045177
7928083
853941333
138243238
789533472
80714156
683673692
571098239
924887916
800052283
925990667
783491724
519715379
429909508
344627967
63548768
756381242
46873202
290519271
131376666
591797346
371166185
870952...

result:

ok 100 numbers

Test #13:

score: 0
Accepted
time: 257ms
memory: 90048kb

input:

300000
1 223459
59958 223459
223459 29314
223459 72580
1 88677
88677 139113
88677 289178
223459 201292
139113 133429
133429 254493
15249 139113
201701 223459
108764 201701
281569 108764
109259 201292
729 254493
130174 281569
15249 133724
197668 133429
82047 15249
57796 15249
166504 130174
166504 151...

output:

490061879
313666461
653680485
487114206
686066685
543622500
883299848
455612299
300000
293637494
59749722
427234941
499127440
300000
587082005
300000
747045815
486374224
651252524
124042265
300000
801776315
836494533
61662403
300000
956112952
530991145
795077403
752488266
315247788
419087525
2398034...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 237ms
memory: 90032kb

input:

300000
197211 1
133892 197211
197211 249299
149903 133892
249299 296864
249299 298152
298152 262736
228502 149903
175208 298152
209138 228502
124065 262736
209990 298152
209138 160219
162853 175208
249299 91300
59964 209990
11085 124065
124065 194419
194419 233467
237298 160219
176972 296864
296864 ...

output:

500027185
445609471
709141003
135134684
818936122
741056750
748683507
922194969
754124593
411927787
350994738
76770950
529138197
249359845
85499831
740542688
175638366
789149520
882210414
974410837
675796222
43905951
807491654
945169046
273887557
228504587
792080791
557379422
403659650
603069765
454...

result:

ok 5000 numbers

Test #15:

score: 0
Accepted
time: 237ms
memory: 90040kb

input:

300000
1 148728
171078 1
272162 148728
1384 272162
171078 91100
94396 171078
269763 91100
1384 206477
206477 20642
208374 269763
91100 26288
96012 206477
26288 265128
24845 26288
263264 206477
147261 272162
24845 199563
162864 265128
199563 240385
285336 148728
265128 39725
20692 240385
147261 92253...

output:

945584069
540546362
112486467
393383339
892286897
818680525
905980576
698207977
175564674
471817947
57132060
699327835
550741047
651694235
364440406
330059022
585628021
367833935
941932461
199737426
585623660
59746769
863081426
563142908
664285475
311592487
71223836
984934261
948613967
321065209
909...

result:

ok 10000 numbers

Test #16:

score: 0
Accepted
time: 247ms
memory: 90032kb

input:

300000
1 254402
1 252610
252610 82579
129313 1
252610 17573
54043 129313
134839 129313
193261 54043
82220 193261
255023 134839
252610 73165
238757 82220
82220 285464
30717 252610
50315 193261
255023 53961
232125 285464
50315 124586
255023 19516
40430 252610
45118 134839
226864 50315
255023 172555
23...

output:

101403381
600599479
322132766
820808946
82389168
384993850
348398742
879688330
74903636
766488465
521760942
756280484
664471434
163208600
656680718
830206588
632292048
926406199
274909331
723007941
745191299
292860676
174521360
21897049
751165481
741902802
951921383
893348043
992483338
584017806
241...

result:

ok 50 numbers

Test #17:

score: 0
Accepted
time: 243ms
memory: 90028kb

input:

300000
88276 1
88276 291623
291623 124308
64828 124308
64828 283179
54955 283179
54955 114538
237872 114538
171274 237872
171274 89959
89959 74742
74742 133311
231114 133311
231114 53377
53377 278208
278208 60263
60263 14960
66029 14960
203922 66029
187948 203922
187948 199133
268663 199133
195990 2...

output:

300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000...

result:

ok 300000 numbers

Test #18:

score: 0
Accepted
time: 247ms
memory: 90140kb

input:

300000
1 200158
200158 204929
204929 175124
175124 163424
163424 122211
122211 216336
216336 99751
242162 99751
242162 110566
58614 110566
269289 58614
113939 269289
275427 113939
275427 18362
18362 240433
277922 240433
115450 277922
260218 115450
260218 180463
180463 217861
167004 217861
167004 170...

output:

242975209
278975062
218653813
820078006
877557165
785815804
996463108
471675053
885805263
796580156
593959680
345828647
910820175
936879112
255732469
488036952
168693353
324498016
948853560
497414888
482369037
566143744
480731660
657141281
819748157
96553522
838193472
471399958
347887581
333699175
6...

result:

ok 50000 numbers

Test #19:

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

input:

300000
1 244373
244373 92423
80274 92423
80274 153122
153122 203654
153122 650
203654 162374
162374 193992
94773 193992
41676 94773
21142 41676
21142 190593
190593 78733
8991 78733
8991 204884
252864 204884
252864 101491
101491 213501
213501 209879
209879 204589
166981 204589
134510 166981
206398 13...

output:

701014831
555476552
774114834
832491057
409784728
692926600
514015872
159250053
324279683
840620328
891506369
291095511
246562402
113739331
733759455
483229848
855801609
281470903
374915254
10743788
398053702
760940539
470882712
444812279
120062226
31341290
276433090
583731013
802362774
570467334
28...

result:

ok 10000 numbers

Test #20:

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

input:

300000
1 237123
132615 237123
63707 132615
164656 63707
164656 180423
253132 180423
140743 253132
212919 140743
212919 137558
211957 137558
211957 114792
114792 267283
267283 41950
110782 41950
61823 110782
123584 61823
123584 275500
11263 275500
11263 91585
274721 91585
93472 274721
68970 93472
689...

output:

126335323
609431114
11648358
674455090
451828152
215519504
926388017
188646708
797694123
627015046
349832315
393126257
952570178
504815973
76859769
386697740
634958334
401924126
5872216
275386739
101568960
697346171
510658515
576856368
327765316
271423401
408780775
849818009
383980890
611674548
4793...

result:

ok 1000 numbers

Test #21:

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

input:

300000
197841 1
197841 28211
28211 287442
287442 225884
225884 105615
89271 105615
191128 89271
191128 140346
140346 10421
93474 10421
159324 93474
16814 159324
16814 207188
108254 207188
108254 16116
16116 196007
114823 196007
114823 220389
110478 220389
49482 110478
287348 49482
60134 287348
18262...

output:

640288558
233700192
366092780
112077368
734948541
239056963
203907159
538251839
358711990
932101750
937763707
146342751
245484083
665163275
992717219
517204157
202076866
45324434
878588332
829534105
210187592
537461171
449056830
868111503
300517385
662349295
409057754
969176263
509467387
229408801
9...

result:

ok 50 numbers

Test #22:

score: 0
Accepted
time: 208ms
memory: 90116kb

input:

300000
85809 1
91524 1
147614 1
268522 1
149187 1
205779 1
103980 1
212487 1
238271 1
1 175480
1 238635
296255 1
1 25944
1 163173
1 39127
1 14294
281482 1
1 251908
1 232159
223416 1
290440 1
87575 1
16831 1
220294 1
202133 1
1 127541
1 198728
1 20381
1 111413
130156 1
128459 1
1 167874
1 42852
18000...

output:

300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000...

result:

ok 300000 numbers

Test #23:

score: 0
Accepted
time: 195ms
memory: 89960kb

input:

300000
1 10987
158187 1
17541 1
231118 1
1 295761
1 95333
51916 1
273629 1
149953 1
212885 1
1 253739
1 275823
1 226874
204455 1
1 9311
149350 1
1 97303
116541 1
1 220907
150179 1
1 247068
163188 1
1 169997
261322 1
1 2075
36141 1
74120 1
1 131134
1 33860
1 71068
1 135904
257861 1
288682 1
1 149180
...

output:

968052236
25461178
892937627
527602205
102832422
401539664
177867255
786775773
903965975
524432952
118494455
121601364
23261427
371857933
357337302
677084838
265105079
527130848
570459437
283519424
503850157
811362759
392610281
686256940
962295832
921821598
103013118
984601011
725960569
697282542
30...

result:

ok 50000 numbers

Test #24:

score: 0
Accepted
time: 193ms
memory: 90092kb

input:

300000
1 247162
1 208608
1 222730
260257 1
1 51283
1 273666
31675 1
1 268612
1 20966
102822 1
181658 1
239238 1
119991 1
47430 1
52070 1
1 130159
1 187633
1 274442
105479 1
57971 1
1 267486
1 615
1 201731
164573 1
1 81637
162381 1
287289 1
181675 1
69083 1
130512 1
1 64590
1 127898
122336 1
1 76185
...

output:

605076630
89933398
298059993
771735727
906051334
173118485
321827986
204951685
163137205
803077441
493332225
907537325
469248085
178211137
276672268
201790865
373925476
600399469
752000786
484833973
366352448
156521600
208645123
50234969
994282699
830993280
899199019
176689174
699400463
820041774
38...

result:

ok 10000 numbers

Test #25:

score: 0
Accepted
time: 212ms
memory: 90068kb

input:

300000
286160 1
175757 1
1 218032
1 240245
238529 1
16415 1
254174 1
1 99253
118948 1
211540 1
1 203190
107480 1
15406 1
125747 1
299018 1
203160 1
140116 1
1 89590
141366 1
1 75127
20437 1
96724 1
11181 1
1 130556
179658 1
1 250640
267216 1
1 125414
1 210610
1 253346
162704 1
287612 1
1 43160
1 265...

output:

13429460
452072017
508735212
487081088
25989977
236227534
750664676
115204506
401702469
994534978
788574214
238278830
175584904
770560052
834962656
844653544
353154991
213617682
797694393
820353381
371050804
27357623
322143312
702396622
811830035
643634080
803008587
909844796
751374112
678064595
105...

result:

ok 1000 numbers

Test #26:

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

input:

300000
118744 1
1 185792
170317 1
1 57213
1 214009
219688 1
269909 1
182565 1
1 189488
1 146840
17997 1
267888 1
173868 1
1 249040
1 138664
1 256325
136298 1
1 40731
1 257242
1 218459
84561 1
1 232152
1 134798
1 288853
74331 1
93201 1
177649 1
104345 1
261292 1
1 127394
1 158560
1 181057
14970 1
1 2...

output:

135286048
237937463
578393338
693020346
110302401
138219497
647385239
445269135
784364105
690575667
872108011
127479084
389682031
913285668
280834622
320987570
757732301
587064457
135775251
893316932
312863932
146801799
837648388
274906286
117079553
428394607
318567555
336969060
799534459
631809006
...

result:

ok 50 numbers

Test #27:

score: 0
Accepted
time: 218ms
memory: 90064kb

input:

300000
1 34177
34177 35585
71874 35585
71874 260861
260861 175301
175301 21891
21891 25007
180840 25007
180840 9834
9834 38625
38625 201354
106455 201354
106455 101579
101579 220851
220851 138824
264450 138824
264450 188792
205943 188792
205943 20107
78399 20107
78399 88369
88369 38296
292390 38296
...

output:

300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000
300000...

result:

ok 300000 numbers

Test #28:

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

input:

300000
270001 1
270001 291194
291194 155211
121155 155211
112857 121155
259480 112857
227561 259480
6661 227561
293920 6661
293920 288469
288469 131300
131300 141597
141597 110082
110082 165561
165561 5946
5946 290474
290474 68315
68315 166760
255789 166760
105034 255789
296926 105034
245600 296926
...

output:

326057695
774694914
620978376
286204412
224996581
449977589
994188869
743005434
797777487
872900034
739946556
342049887
215171126
840204774
268003170
225781043
672309450
321253876
399577117
277095195
263535571
56183794
588594847
512589772
547239133
804929561
764631765
548878674
955593748
799884272
1...

result:

ok 50000 numbers

Test #29:

score: 0
Accepted
time: 205ms
memory: 90104kb

input:

300000
1 296141
296141 292514
297185 292514
287687 297185
231592 287687
270766 231592
270766 215860
215860 231806
288865 231806
288865 223268
115669 223268
6647 115669
6647 216220
216220 1171
223432 1171
209788 223432
101724 209788
101724 15642
15642 12400
12400 278981
278981 74371
198544 74371
9625...

output:

368690104
684073600
974498261
958109055
879949647
550512223
215706975
313709845
492369208
342030276
551677414
235217402
772506010
643675176
633349428
839184839
805266405
259699135
10459692
729242915
523046282
889936820
857048055
812619230
837185741
103051020
137842234
289153763
251605666
557655485
5...

result:

ok 10000 numbers

Test #30:

score: 0
Accepted
time: 215ms
memory: 90136kb

input:

300000
70647 1
70647 297259
214202 297259
214202 217734
117524 217734
117524 15102
15102 218727
35296 218727
251218 35296
251218 164658
56541 164658
257406 56541
257406 54991
138581 54991
138581 146034
226168 146034
295055 226168
258423 295055
114410 258423
217792 114410
217792 165122
8867 165122
71...

output:

834815576
625771283
526605269
258439008
878370785
462286772
562445560
716005671
935386588
922796810
831023117
945788301
323719699
495736739
992021926
520592965
49306908
336965508
724081138
961637195
536330236
28024343
987346663
990629979
669146231
841392259
949385643
374721915
93879006
501218383
926...

result:

ok 1000 numbers

Test #31:

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

input:

300000
114262 1
114262 47224
47224 173943
173943 139017
101384 139017
187555 101384
8536 187555
169062 8536
169062 97730
97730 22460
125956 22460
125956 95277
95277 52924
98347 52924
193977 98347
44698 193977
52901 44698
52901 225160
225160 15945
15945 33897
74960 33897
74960 204486
204486 48722
120...

output:

224491839
129726798
426088554
582336341
813135494
874502979
958070738
580237799
480623747
371833319
974404779
48670027
787820364
712895453
570244697
865280828
176183255
184715660
81655281
638566554
815143821
221329668
475415440
78341193
284421751
733896090
974723634
750689334
366744159
769943861
316...

result:

ok 50 numbers

Test #32:

score: 0
Accepted
time: 204ms
memory: 90136kb

input:

300000
282514 1
139151 282514
151682 139151
71434 151682
71434 134444
202995 134444
31745 202995
115193 31745
177088 115193
177088 175961
175961 147791
147791 40231
40231 182258
182258 62256
187997 62256
187997 191761
16189 191761
16189 189379
99559 189379
272055 99559
272055 65504
82369 65504
34242...

output:

810383979
720320979
732435761
671252821
324820697
494499374
593168547
103690021
972051980
457390366
462390521
867091267
790467873
137419121
55655764
98040854
274064182
706130624
708872124
478871560
640888459
536697709
429185765
505436883
766155989
314617335
384805942
915732329
395488310
367623477
53...

result:

ok 50000 numbers

Test #33:

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

input:

300000
203867 1
203867 292210
35134 292210
11993 35134
11993 34635
34635 211749
291666 211749
10298 291666
10298 29597
174390 29597
160187 174390
160187 11019
259500 11019
62487 259500
125906 62487
125906 190348
190348 227444
227444 54756
54756 141773
276420 141773
276420 19653
19653 283409
4348 283...

output:

610250568
52803326
742023365
505045478
157583405
127138432
972416264
541114484
4882102
932234412
114090941
123795206
400563573
994432319
943717765
220556664
402242239
127250164
230344185
642580910
325113470
116403637
885726047
796419676
172522726
656467452
148807873
920152751
502007677
655921948
406...

result:

ok 6000 numbers

Test #34:

score: 0
Accepted
time: 216ms
memory: 90036kb

input:

300000
1 145454
24389 145454
60401 24389
96167 60401
96167 212701
212701 165296
165296 118887
118887 156189
156189 238487
238487 170747
170747 58805
288769 58805
288769 292940
55674 292940
55674 95504
95504 193118
193118 221605
221605 20257
16936 20257
16936 193904
49096 193904
23778 49096
3520 2377...

output:

452043567
319184138
958424255
69782760
827947061
237952092
410222236
693890920
82590322
104452637
567670123
290436165
337041853
947488637
200929435
553284677
992718660
722626760
970957811
610563888
880306362
53662786
776794279
833306801
758459018
161079828
367920369
290837353
968955603
970316209
609...

result:

ok 10000 numbers

Test #35:

score: 0
Accepted
time: 227ms
memory: 90136kb

input:

300000
1 17837
263495 17837
46594 263495
196991 46594
293114 196991
293114 171473
171473 99499
99499 220089
220089 16225
16225 22607
22607 186530
211140 186530
58026 211140
64135 58026
181022 64135
117141 181022
68601 117141
40980 68601
13150 40980
258041 13150
16193 258041
66234 16193
230952 66234
...

output:

348206793
155717194
756689335
928516777
659519405
234346908
182524529
146018856
707121770
983489753
309144532
333462810
841260056
830655845
923223524
195634828
771447932
517127024
34765800
794851208
941953983
72876316
21420144
342992825
943668463
413009435
62136314
921907131
105835227
597740541
3327...

result:

ok 1000 numbers

Test #36:

score: 0
Accepted
time: 212ms
memory: 89900kb

input:

300000
1 269779
269779 99471
295547 99471
144189 295547
144189 246725
220769 246725
220769 166674
166674 164678
12116 164678
226602 12116
80913 226602
15169 80913
15169 243643
243643 137508
137508 289532
81046 289532
81046 121121
110019 121121
110019 21721
21721 263452
268057 263452
268057 210719
64...

output:

773005917
952874932
249721921
231332202
387932192
970971166
512550096
532897355
361930684
976306231
420716640
851462722
83213730
266361246
74053471
428945622
257064083
199193084
764099431
337400146
899184723
319627454
570000574
651070145
884237848
902393102
64965120
915664434
397694657
290257410
588...

result:

ok 50 numbers

Test #37:

score: 0
Accepted
time: 202ms
memory: 90112kb

input:

300000
266401 1
43347 266401
86837 266401
279499 86837
86837 113349
113349 274066
113349 93736
93736 98499
93736 212377
70752 212377
255842 212377
255842 195379
88788 255842
207293 88788
88788 247478
84450 247478
247478 121503
121503 258705
62108 121503
262857 62108
62108 120845
120845 185447
120845...

output:

207400596
508702636
343483015
635851393
300000
590544712
712286731
468505160
955043329
227480612
665080914
300000
333255979
300000
371574872
300000
751228541
622101537
834652639
281881755
86570479
752866135
445673364
603321559
127232896
440619293
297978317
104442062
556001859
300000
300000
299722356...

result:

ok 100000 numbers

Test #38:

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

input:

300000
21269 1
115835 21269
151897 21269
70888 151897
151897 296584
278785 296584
35694 296584
35694 175143
34321 35694
34321 209931
34321 91302
91302 113002
50198 91302
1885 50198
23893 50198
23893 266721
44452 23893
44452 63240
44452 101165
101165 276961
69963 101165
69963 4323
3085 69963
3085 197...

output:

18967210
314946130
649310236
945793054
660153719
576271327
583998045
117139900
473131862
836760790
738804477
225237224
391311917
404665829
843006430
314363290
648800805
690562792
792456389
682903088
740004440
693675093
391271899
626421961
821462876
916294880
347320519
638763276
296874011
275172543
7...

result:

ok 50000 numbers

Test #39:

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

input:

300000
1 176859
43674 176859
176859 249838
249838 18170
249838 90937
226157 90937
90937 28986
25856 28986
117888 28986
219255 117888
185668 117888
45326 185668
185668 124847
51970 124847
131540 124847
131540 26594
131540 130971
55732 130971
293901 130971
44485 293901
293901 157240
157240 258769
9852...

output:

136941861
609636098
45408113
615348296
442100918
577394139
342135127
589657068
297736267
747198129
993455872
793686258
915133589
915545493
687402268
873730468
562188383
123751680
203833126
649121971
140577781
934869367
338109610
178110659
389620819
17022249
331499263
644043542
193556907
666460899
26...

result:

ok 10000 numbers

Test #40:

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

input:

300000
1 267352
223110 267352
267352 207936
207936 152704
207936 260433
260433 75124
290674 260433
290674 40603
31634 290674
150044 31634
294130 31634
168527 294130
65041 294130
65041 228106
46614 65041
46614 261127
46614 96766
219828 96766
96766 56258
183566 56258
56258 272349
272349 184221
272349 ...

output:

425875712
978629898
367917500
972018834
273818492
541742606
113887448
306685519
611379738
408493414
709928695
738050663
790786533
180681839
277424164
331818504
309755624
955609640
77663903
359075094
740156061
642512735
408258785
396633195
823521381
276757194
573356521
924068463
729740600
814136469
2...

result:

ok 1000 numbers

Test #41:

score: 0
Accepted
time: 202ms
memory: 89988kb

input:

300000
25888 1
33734 25888
25888 162482
245400 162482
838 162482
45848 838
838 105028
140741 105028
292024 105028
231556 292024
192925 292024
192925 94538
263214 192925
263214 82728
50242 263214
31616 50242
40316 50242
168955 40316
219110 40316
219110 112645
219110 293021
190878 293021
293021 91031
...

output:

551301818
545812764
778717800
941654430
836214632
103127978
49418419
508788521
757980091
265257517
161345901
778607737
508490134
148336070
722660638
848386334
327968634
603894600
29458978
52518958
117465205
254582327
943492387
849378659
963300632
39662170
924456070
436767371
262069218
713719733
7928...

result:

ok 60 numbers

Test #42:

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

input:

300000
1 169813
169813 239273
169813 245650
101711 245650
101711 82565
203043 245650
24070 203043
24070 47571
47571 175411
203043 84266
84266 132073
132073 61295
61295 20385
179962 20385
84266 154303
148648 154303
148648 123287
130783 123287
130783 228314
228314 115702
1389 154303
1389 40489
40489 4...

output:

860595202
40052298
52591266
289667679
539271521
932631819
406254057
360970949
53582207
219584327
820251419
325907568
300000
300000
534409098
611539324
540170595
300000
19044680
449153480
630368266
924578728
355343020
556355969
300000
300000
300000
394403151
320413574
503955028
820305672
331915289
30...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 210ms
memory: 89900kb

input:

300000
267729 1
267729 268530
260955 267729
183636 260955
183636 51841
260955 85075
85075 50881
33952 50881
33952 171992
85075 215648
215648 276686
276686 63124
286320 63124
6504 286320
158416 215648
71917 158416
257924 71917
296471 257924
296471 118080
118080 266321
70224 158416
70224 222904
278815...

output:

442470800
845001295
785100762
150936872
306009906
185845373
107199098
821106615
431028844
807953332
107667044
478112943
824695337
477288897
33002869
888413841
757034661
244708990
207347469
797994531
457214770
616657398
852968860
366151510
374606892
463772929
86267570
54372339
98519481
118785469
2490...

result:

ok 50000 numbers

Test #44:

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

input:

300000
1 148976
214364 148976
148976 279579
184696 279579
120047 184696
279579 6913
290625 6913
282053 290625
61777 282053
6913 166302
166302 151303
151303 33267
83680 33267
83680 232248
166302 116936
224783 116936
224783 288540
288540 42650
42650 5914
5914 79587
116936 2278
2278 206438
206438 25933...

output:

203121986
220130781
596158871
930686796
570197231
483843729
770532007
105716639
819230032
657933091
270648618
945803707
629870383
316788770
342942027
502668712
413514439
338695219
58894292
236851835
960895044
7838498
555945064
584108602
853292904
769538284
469918062
222396409
379818543
492062247
586...

result:

ok 10000 numbers

Test #45:

score: 0
Accepted
time: 211ms
memory: 90028kb

input:

300000
1 85238
85238 143115
171522 85238
131961 171522
131961 78318
171522 134304
134304 29060
29060 40433
40433 7724
129808 134304
278298 129808
278298 59085
59085 91170
91170 236062
289082 129808
264375 289082
49377 264375
49377 38116
185537 38116
192749 185537
289082 35279
136991 35279
136991 420...

output:

718142290
803454388
891042638
728728767
230857938
885830363
402017671
22600982
954944335
48978574
396457045
673806252
932056752
563294199
20130312
170662222
304622591
969592690
776575683
709673935
991585524
807443843
992615111
480510335
630455077
154146881
833290173
136985879
28784050
863457329
2261...

result:

ok 1000 numbers

Test #46:

score: 0
Accepted
time: 208ms
memory: 90116kb

input:

300000
298425 1
298425 166266
71801 298425
111143 71801
271056 111143
71801 65843
94866 65843
94866 144320
194172 144320
65843 9362
165564 9362
73967 165564
73967 170063
262021 170063
279973 9362
279973 239177
278136 239177
113688 278136
158408 113688
237595 158408
279973 141883
57564 141883
57564 2...

output:

67133123
980084193
234980399
304118677
793040073
498393863
303362895
175466726
115120568
897571193
838232426
882772372
783660396
830443381
525203157
164401514
755293565
574818530
515939830
344276676
564663727
642346876
456929183
673171607
209095928
94770696
64680138
839193077
116683780
92612682
5555...

result:

ok 60 numbers

Test #47:

score: 0
Accepted
time: 212ms
memory: 90596kb

input:

300000
93290 1
93290 298169
93290 114531
123201 114531
29862 123201
185648 114531
185648 222439
60439 222439
93114 60439
185648 284209
154300 284209
37873 154300
37873 93009
93009 292389
146409 284209
250154 146409
250154 269693
122447 269693
149445 122447
149445 206231
146409 50813
50813 258685
258...

output:

769583214
914917150
457402627
864899813
664019832

result:

ok 5 number(s): "769583214 914917150 457402627 864899813 664019832"

Test #48:

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

input:

300000
101620 1
254646 1
254646 91960
123506 254646
91960 288750
254646 100999
91960 99240
100999 75736
190331 99240
190331 158759
233249 100999
100999 112033
91960 120998
100999 18051
120998 285611
112033 242866
199126 158759
199126 270822
100999 118290
35219 270822
285611 88039
270822 256956
10099...

output:

482884810
948331706
970581775

result:

ok 3 number(s): "482884810 948331706 970581775"

Test #49:

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

input:

300000
1 86929
86929 109387
109387 137033
137033 51246
51246 140490
140490 269397
269397 45375
248827 45375
185959 248827
185959 132798
132798 207681
207681 15839
15839 206778
118874 206778
118874 150174
150174 77088
77088 67236
128598 67236
25736 128598
25736 27728
27728 263492
263492 270660
270660...

output:

135770453
516280792
643755007

result:

ok 3 number(s): "135770453 516280792 643755007"

Test #50:

score: 0
Accepted
time: 236ms
memory: 92228kb

input:

300000
1 280980
280980 40567
93984 280980
68545 40567
29856 1
93984 39107
39107 187944
29856 209441
84554 280980
125779 40567
52440 125779
84554 234312
187611 29856
211491 187611
202578 40567
202804 84554
187611 38671
264183 125779
124405 264183
124405 60309
182328 124405
263607 124405
55064 202578
...

output:

802558626

result:

ok 1 number(s): "802558626"

Test #51:

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

input:

300000
1 45086
283544 45086
118567 283544
118567 43251
132056 43251
132056 104687
104687 204558
196668 204558
35583 196668
35583 11556
11556 242565
235285 242565
171588 235285
171588 244242
198739 244242
165811 198739
165811 59172
262607 59172
255302 262607
219062 255302
219062 201107
201107 247448
...

output:

975637650

result:

ok 1 number(s): "975637650"