QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297827#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》Kevin530765 2444ms254584kbC++203.8kb2024-01-05 11:39:262024-01-05 11:39:27

Judging History

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

  • [2024-01-05 11:39:27]
  • 评测
  • 测评结果:65
  • 用时:2444ms
  • 内存:254584kb
  • [2024-01-05 11:39:26]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[1001000];
int n;
ll a[1001000];
int depth[1001000];
int anc[20][1001000];
int mx[20][1001000];
int dfn[1001000],son[1001000],siz[1001000],tp[1001000],tot;
void dfs1(int u,int fa)
{
	siz[u]=1;
	depth[u]=depth[fa]+1;
	anc[0][u]=fa;
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])
				son[u]=v;
		}
}
void dfs2(int u,int fa)
{
	if(!tp[u]) tp[u]=u;
	dfn[u]=++tot;
	if(son[u])
	{
		tp[son[u]]=tp[u];
		dfs2(son[u],u);
	}
	for(auto v:G[u])
		if(v!=son[u]&&v!=fa)
			dfs2(v,u);
}
ll b[1001000];
int range_max(int l,int r)
{
	int x=__lg(r-l+1);
	return (b[mx[x][l]]>b[mx[x][r-(1<<x)+1]])?mx[x][l]:mx[x][r-(1<<x)+1];
}
struct _comp_{const bool operator ()(const array<int,3> &a,const array<int,3> &b){return ::b[a[0]]<::b[b[0]];}};
#define count _count
int cnt[1001000],count;
int trans[1001000][2];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define int ll
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
#undef int
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=rd();
	for(int i=1;i<n;i++)
	{
		int u,v;
		u=rd();
		v=rd();
		G[u].pb(v);
		G[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		a[i]=rd();
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		b[dfn[i]]=a[i];
	for(int i=1;i<=n;i++)
		mx[0][i]=i;
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			if(j+(1<<(i-1))<=n)
				mx[i][j]=(b[mx[i-1][j]]>b[mx[i-1][j+(1<<(i-1))]])?mx[i-1][j]:mx[i-1][j+(1<<(i-1))];
			else
				mx[i][j]=mx[i-1][j];
	int q;
	q=rd();
	ll lstans=0;
	while(q--)
	{
		int u,v,m;
		ll a,b;
		a=rd();
		b=rd();
		m=rd();
		u=(a^lstans)%n+1;
		v=(b^lstans)%n+1;
		priority_queue<array<int,3>,vector<array<int,3>>,_comp_> pq;
		while(tp[u]!=tp[v])
		{
			if(depth[tp[u]]<depth[tp[v]]) swap(u,v);
			pq.push({range_max(dfn[tp[u]],dfn[u]),dfn[tp[u]],dfn[u]});
			u=anc[0][tp[u]];
		}
		if(dfn[u]>dfn[v]) swap(u,v);
		pq.push({range_max(dfn[u],dfn[v]),dfn[u],dfn[v]});
		vector<ll> vec;
		while(sz(vec)<(m-1)*63&&!pq.empty())
		{
			array<int,3> arr=pq.top();
			pq.pop();
			vec.pb(::b[arr[0]]);
			if(arr[0]!=arr[1])
				pq.push({range_max(arr[1],arr[0]-1),arr[1],arr[0]-1});
			if(arr[0]!=arr[2])
				pq.push({range_max(arr[0]+1,arr[2]),arr[0]+1,arr[2]});
		}
		count=1;
		for(auto val:vec)
		{
			int cur=1;
			cnt[cur]++;
			for(int i=61;i>=0;i--)
			{
				int c=val>>i&1;
				if(!trans[cur][c]) trans[cur][c]=++count;
				cur=trans[cur][c];
				cnt[cur]++;
			}
		}
		vector<int> cn;
		ll ans=0;
		cn.pb(1);
		for(int i=61;i>=0;i--)
		{
			int sum=0;
			for(auto nd:cn)
				sum+=cnt[trans[nd][1]];
			vector<int> ncn;
			for(auto nd:cn)
				if(trans[nd][1])
					ncn.pb(trans[nd][1]);
			if(sum<m)
			{
				for(auto nd:cn)
					if(trans[nd][0])
						ncn.pb(trans[nd][0]);
			}
			else
				ans|=(1ll<<i);
			swap(cn,ncn);
		}
		for(int i=1;i<=count;i++)
			cnt[i]=trans[i][0]=trans[i][1]=0;
		cout<<(lstans=ans)<<'\n';
	}
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 4ms
memory: 83540kb

input:

931
184 700
485 184
419 485
386 419
308 386
114 308
301 114
598 301
120 598
144 120
595 144
812 595
236 812
7 236
543 7
327 543
858 327
68 858
177 68
398 177
899 398
408 899
848 408
202 848
269 202
304 269
540 304
647 540
672 647
314 672
157 314
241 157
745 241
300 745
343 300
92 343
117 92
30 117
2...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #2:

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

input:

915
911 748
514 911
805 514
729 805
753 729
40 753
671 40
664 671
94 664
61 94
726 61
690 726
597 690
216 597
644 216
533 644
605 533
22 605
307 22
455 307
377 455
114 377
660 114
589 660
569 589
409 569
408 409
821 408
736 821
599 736
60 599
475 60
57 475
412 57
85 412
524 85
846 524
595 846
262 59...

output:

288230376151711752

result:

ok 1 number(s): "288230376151711752"

Test #3:

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

input:

930
111 896
637 111
559 637
289 559
103 289
759 103
341 759
605 341
778 605
154 778
169 154
721 169
631 721
741 631
750 741
344 750
641 344
639 641
769 639
48 769
389 48
25 389
70 25
508 70
185 508
199 185
602 199
89 602
473 89
565 473
373 565
865 373
867 865
658 867
271 658
685 271
269 685
317 269
...

output:

268435456

result:

ok 1 number(s): "268435456"

Test #4:

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

input:

948
537 716
933 537
605 933
563 605
801 563
860 801
19 860
717 19
908 717
820 908
885 820
693 885
69 693
263 69
129 263
295 129
880 295
303 880
12 303
299 12
1 299
421 1
312 421
720 312
100 720
438 100
380 438
386 380
223 386
627 223
293 627
387 293
709 387
193 709
640 193
906 640
34 906
405 34
790 ...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #5:

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

input:

928
626 381
247 626
97 247
358 97
886 358
898 886
736 898
776 736
75 776
123 75
512 123
223 512
355 223
530 355
95 530
523 95
903 523
144 903
324 144
382 324
487 382
127 487
538 127
171 538
836 171
129 836
259 129
914 259
574 914
7 574
141 7
246 141
65 246
482 65
865 482
265 865
690 265
925 690
449 ...

output:

134217728

result:

ok 1 number(s): "134217728"

Test #6:

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

input:

941
87 448
396 87
398 396
623 398
837 623
234 837
896 234
258 896
700 258
52 700
27 52
515 27
308 515
774 308
76 774
21 76
753 21
493 753
902 493
878 902
58 878
146 58
342 146
414 342
312 414
621 312
88 621
460 88
683 460
150 683
845 150
535 845
467 535
326 467
247 326
280 247
474 280
124 474
22 124...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #7:

score: 0
Accepted
time: 9ms
memory: 83788kb

input:

947
635 486
821 635
758 821
504 758
470 504
170 470
468 170
778 468
560 778
864 560
308 864
213 308
43 213
849 43
525 849
126 525
681 126
785 681
640 785
254 640
354 254
263 354
455 263
295 455
714 295
474 714
64 474
794 64
582 794
325 582
676 325
176 676
393 176
624 393
86 624
205 86
359 205
704 35...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #8:

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

input:

920
889 920
64 889
647 64
482 647
798 482
368 798
593 368
169 593
788 169
469 788
59 469
71 59
611 71
779 611
675 779
272 675
703 272
237 703
525 237
485 525
483 485
266 483
160 266
302 160
321 302
697 321
82 697
516 82
817 516
428 817
857 428
23 857
319 23
918 319
359 918
749 359
681 749
849 681
33...

output:

4398046511104

result:

ok 1 number(s): "4398046511104"

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 5
Accepted
time: 2405ms
memory: 83884kb

input:

949
158 116
73 158
131 73
252 131
596 252
9 596
488 9
555 488
828 555
150 828
388 150
586 388
903 586
24 903
405 24
746 405
321 746
48 321
588 48
431 588
225 431
299 225
325 299
593 325
516 593
829 516
369 829
775 369
90 775
610 90
45 610
793 45
745 793
859 745
422 859
342 422
91 342
773 91
32 773
4...

output:

4194304
2199023255552
288230376151711744
1152921504606846976
1152921504606846976
536870912
536870912
1152921504606846976
144115188075855872
576460752303423488
576460752303423488
2199023255552
2199023255552
1152921504606846976
128
1152921504606846976
1152921504606846976
0
70368744177664
0
11529215046...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 2398ms
memory: 84844kb

input:

990
751 145
499 751
976 499
107 976
401 107
941 401
987 941
237 987
467 237
690 467
56 690
124 56
61 124
419 61
280 419
986 280
368 986
851 368
106 851
818 106
955 818
381 955
295 381
808 295
64 808
126 64
547 126
71 547
383 71
974 383
149 974
553 149
631 553
924 631
431 924
827 431
248 827
135 248
...

output:

68719476736
18014398509481984
35184372088832
1125899906842624
1152921504606846976
64
1152921504606846976
1152921504606846976
0
18014398509481984
32768
549755813888
1152921504606846976
1125899906842624
1125899906842624
2199023255552
144115188075855872
72057594037927936
1152921504606846976
0
115292150...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 2444ms
memory: 84884kb

input:

941
145 851
347 145
164 347
242 164
298 242
666 298
877 666
624 877
130 624
161 130
133 161
251 133
917 251
629 917
598 629
277 598
370 277
63 370
32 63
502 32
457 502
791 457
455 791
719 455
331 719
478 331
578 478
387 578
46 387
547 46
685 547
213 685
518 213
364 518
369 364
212 369
870 212
417 87...

output:

18014398509481984
144115188075855872
1152921504606846976
1048576
576460752303423488
18014398509481984
8
2199023255552
128
2251799813685248
1152921504606846976
1152921504606846976
144115188075855872
1152921504606846976
144115188075855872
8589934592
18014398509481984
0
1152921504606846976
115292150460...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 2424ms
memory: 83144kb

input:

922
594 757
328 594
297 328
199 297
285 199
724 285
591 724
42 591
560 42
195 560
367 195
372 367
107 372
160 107
708 160
85 708
32 85
441 32
14 441
528 14
820 528
97 820
34 97
527 34
27 527
65 27
23 65
572 23
387 572
277 387
259 277
211 259
482 211
635 482
244 635
182 244
147 182
674 147
135 674
92...

output:

1152921504606846976
562949953421312
128
36028797018963968
1152921504606846976
274877906944
1152921504606846976
1073741824
72057594037927936
17179869184
144115188075855872
36028797018963968
576460752303423488
1073741824
1152921504606846976
2147483648
36028797018963968
576460752303423488
1152921504606...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 2414ms
memory: 86420kb

input:

968
323 906
42 323
767 42
750 767
645 750
19 645
617 19
834 617
588 834
807 588
428 807
244 428
606 244
787 606
777 787
654 777
10 654
89 10
693 89
920 693
947 920
497 947
125 497
526 125
923 526
612 923
530 612
214 530
403 214
651 403
785 651
696 785
836 696
69 836
883 69
177 883
87 177
899 87
623 ...

output:

576460752303423488
18014398509481984
288230376151711744
0
36028797018963968
33554432
576460752303423488
549755813888
9007199254740992
576460752303423488
1152921504606846976
72057594037927936
576460752303423488
576460752303423488
1152921504606846976
288230376151711744
1152921504606846976
576460752303...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 2382ms
memory: 84856kb

input:

933
158 663
512 158
109 512
226 109
704 226
799 704
492 799
796 492
836 796
439 836
76 439
497 76
544 497
30 544
5 30
592 5
294 592
186 294
140 186
103 140
659 103
426 659
421 426
343 421
253 343
413 253
106 413
92 106
281 92
562 281
884 562
487 884
69 487
664 69
214 664
757 214
169 757
21 169
204 2...

output:

0
72057594037927936
288230376151711744
144115188075855872
8192
288230376151711744
576460752303423488
72057594037927936
576460752303423488
72057594037927936
1152921504606846976
68719476736
1152921504606846976
1152921504606846976
35184372088832
34359738368
562949953421312
576460752303423488
8192
87960...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 2396ms
memory: 84856kb

input:

901
438 539
372 438
163 372
673 163
559 673
595 559
478 595
830 478
832 830
883 832
506 883
665 506
861 665
119 861
555 119
76 555
220 76
751 220
113 751
72 113
196 72
834 196
228 834
354 228
491 354
893 491
529 893
212 529
150 212
53 150
746 53
85 746
796 85
583 796
530 583
393 530
467 393
459 467
...

output:

576460752303423488
36028797018963968
0
1152921504606846976
36028797018963968
0
9007199254740992
72057594037927936
2199023255552
576460752303423488
144115188075855872
1152921504606846976
4096
35184372088832
1152921504606846976
35184372088832
1152921504606846976
1152921504606846976
2199023255552
11529...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 2394ms
memory: 83664kb

input:

905
587 47
409 587
793 409
100 793
637 100
274 637
247 274
530 247
229 530
893 229
585 893
617 585
653 617
832 653
414 832
374 414
784 374
772 784
458 772
780 458
613 780
870 613
766 870
115 766
760 115
300 760
890 300
830 890
819 830
873 819
535 873
520 535
444 520
208 444
433 208
717 433
66 717
59...

output:

9007199254740992
72057594037927936
0
4398046511104
1152921504606846976
16384
1152921504606846976
72057594037927936
72057594037927936
1152921504606846976
281474976710656
1152921504606846976
72057594037927936
1152921504606846976
9007199254740992
9007199254740992
281474976710656
576460752303423488
1152...

result:

ok 100000 numbers

Subtask #3:

score: 10
Accepted

Test #17:

score: 10
Accepted
time: 25ms
memory: 102464kb

input:

99115
98506 98914
1961 98506
45808 1961
23027 45808
16655 23027
66393 16655
77250 66393
68284 77250
53684 68284
21189 53684
84955 21189
73464 84955
47574 73464
40651 47574
21101 40651
6589 21101
59680 6589
6185 59680
25529 6185
207 25529
33286 207
98459 33286
92565 98459
85446 92565
97388 85446
1630...

output:

2050

result:

ok 1 number(s): "2050"

Test #18:

score: 0
Accepted
time: 34ms
memory: 109548kb

input:

99546
79711 12863
50539 79711
13393 50539
27933 13393
13465 27933
79157 13465
53742 79157
51081 53742
32220 51081
21079 32220
85595 21079
50222 85595
14565 50222
4589 14565
13763 4589
58913 13763
93835 58913
34953 93835
2185 34953
10246 2185
64420 10246
44274 64420
63093 44274
8007 63093
85947 8007
...

output:

512

result:

ok 1 number(s): "512"

Test #19:

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

input:

99762
90013 76047
42293 90013
7801 42293
75274 7801
59320 75274
60896 59320
10435 60896
5384 10435
34648 5384
15596 34648
92041 15596
67457 92041
20760 67457
65611 20760
81462 65611
38984 81462
17583 38984
83787 17583
59980 83787
71477 59980
31143 71477
92168 31143
71205 92168
69348 71205
6111 69348...

output:

16386

result:

ok 1 number(s): "16386"

Test #20:

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

input:

99132
46469 40521
51811 46469
47968 51811
10584 47968
73 10584
27351 73
16693 27351
12495 16693
53425 12495
95973 53425
24901 95973
82771 24901
49155 82771
35995 49155
50432 35995
91209 50432
5781 91209
83457 5781
41361 83457
37973 41361
48829 37973
62896 48829
77593 62896
21307 77593
86547 21307
61...

output:

8194

result:

ok 1 number(s): "8194"

Test #21:

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

input:

99403
81802 91324
60321 81802
76749 60321
70097 76749
16085 70097
8301 16085
61886 8301
72994 61886
23906 72994
18815 23906
6781 18815
7774 6781
18318 7774
54769 18318
39330 54769
55677 39330
46758 55677
36164 46758
10159 36164
24678 10159
29603 24678
14941 29603
7966 14941
42934 7966
35909 42934
24...

output:

32770

result:

ok 1 number(s): "32770"

Test #22:

score: 0
Accepted
time: 19ms
memory: 104288kb

input:

99468
33859 68644
12306 33859
44304 12306
18200 44304
27325 18200
35907 27325
88149 35907
71599 88149
86384 71599
83793 86384
19513 83793
4843 19513
3007 4843
52878 3007
83019 52878
5275 83019
61517 5275
21453 61517
55993 21453
50710 55993
16211 50710
76061 16211
12048 76061
41970 12048
86181 41970
...

output:

514

result:

ok 1 number(s): "514"

Test #23:

score: 0
Accepted
time: 20ms
memory: 103948kb

input:

99179
45430 91876
8718 45430
75718 8718
15306 75718
21806 15306
78221 21806
74287 78221
66218 74287
66830 66218
64948 66830
16118 64948
33879 16118
81821 33879
69640 81821
27802 69640
25979 27802
6393 25979
63447 6393
48459 63447
53612 48459
27525 53612
52654 27525
80810 52654
767 80810
23808 767
82...

output:

32768

result:

ok 1 number(s): "32768"

Test #24:

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

input:

99240
8561 98467
49571 8561
13264 49571
94195 13264
85879 94195
53012 85879
29828 53012
25813 29828
57793 25813
10678 57793
88525 10678
70070 88525
54163 70070
51466 54163
3857 51466
77958 3857
29023 77958
154 29023
5173 154
4349 5173
24310 4349
21821 24310
36125 21821
75498 36125
7147 75498
22336 7...

output:

32770

result:

ok 1 number(s): "32770"

Subtask #4:

score: 5
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Test #25:

score: 5
Accepted
time: 359ms
memory: 236592kb

input:

992362
488995 967308
576776 488995
440373 576776
199494 440373
436524 199494
260014 436524
157103 260014
693611 157103
218612 693611
590935 218612
701779 590935
112004 701779
322594 112004
53706 322594
442686 53706
659639 442686
567880 659639
786210 567880
289019 786210
599273 289019
188834 599273
1...

output:

1152921504606846984

result:

ok 1 number(s): "1152921504606846984"

Test #26:

score: 0
Accepted
time: 596ms
memory: 223344kb

input:

992770
411251 413303
421801 411251
751171 421801
294667 751171
506990 294667
136648 506990
288093 136648
514687 288093
886681 514687
75611 886681
178157 75611
99736 178157
277007 99736
744383 277007
226929 744383
53879 226929
617778 53879
170759 617778
467641 170759
123171 467641
732929 123171
90501...

output:

1152921504606847232

result:

ok 1 number(s): "1152921504606847232"

Test #27:

score: 0
Accepted
time: 338ms
memory: 225388kb

input:

992506
78169 990749
904956 78169
8556 904956
618930 8556
318854 618930
643267 318854
255067 643267
635064 255067
911717 635064
932598 911717
323834 932598
620573 323834
172635 620573
541580 172635
96011 541580
745144 96011
403925 745144
60605 403925
118756 60605
219373 118756
253153 219373
30380 253...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #28:

score: 0
Accepted
time: 338ms
memory: 254584kb

input:

998381
898343 893428
759432 898343
531529 759432
497678 531529
960345 497678
211399 960345
268908 211399
804788 268908
48879 804788
567713 48879
934755 567713
587571 934755
2755 587571
357711 2755
312979 357711
758254 312979
494581 758254
906640 494581
80127 906640
558475 80127
694426 558475
34296 6...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Subtask #5:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #29:

score: 10
Accepted
time: 743ms
memory: 110524kb

input:

99226
5279 56171
56708 5279
93918 56708
46612 93918
92631 46612
23135 92631
10349 23135
53057 10349
56629 53057
54566 56629
2518 54566
39322 2518
2240 39322
31992 2240
97583 31992
68136 97583
69869 68136
37827 69869
1210 37827
50065 1210
6617 50065
57500 6617
57892 57500
89598 57892
10109 89598
8431...

output:

1152921504606846976
1152921504606846984
1152921504606846984
1152921504606846976
281474976710656
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
274877906944
1152921504606846976
1152921504606846976
144115188075855874
115292150460...

result:

ok 9965 numbers

Test #30:

score: 0
Accepted
time: 725ms
memory: 104288kb

input:

99131
86117 49115
12523 86117
18106 12523
31418 18106
61736 31418
77297 61736
37409 77297
21866 37409
73758 21866
33590 73758
8327 33590
47474 8327
78931 47474
63290 78931
407 63290
84058 407
8558 84058
6242 8558
89267 6242
42248 89267
34160 42248
3134 34160
6579 3134
7405 6579
47360 7405
46220 4736...

output:

1152921504606846976
72057594037927936
1152921504606846978
1152921504606846976
17592186044416
1152921504606846976
524288
1152921504606846976
4194304
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
576460752303423488
1152921504606846976
1441151880758...

result:

ok 9909 numbers

Test #31:

score: 0
Accepted
time: 736ms
memory: 105712kb

input:

99615
95650 89972
29012 95650
19894 29012
77233 19894
14383 77233
87222 14383
85565 87222
61993 85565
71297 61993
73788 71297
8626 73788
67633 8626
1885 67633
65599 1885
10040 65599
31321 10040
55933 31321
28063 55933
56351 28063
40756 56351
42362 40756
28551 42362
47749 28551
48770 47749
40567 4877...

output:

262144
1152921504606846976
576460752303423488
1152921504606846976
1152921504606846976
576460752303423488
1152921504606846992
1152921504606846976
36028797018963968
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
11529215046068469...

result:

ok 9947 numbers

Test #32:

score: 0
Accepted
time: 737ms
memory: 108024kb

input:

99501
54076 23445
75253 54076
64548 75253
89989 64548
50278 89989
90578 50278
12194 90578
9923 12194
35987 9923
41698 35987
1578 41698
41232 1578
378 41232
95959 378
80008 95959
22021 80008
71293 22021
32789 71293
84262 32789
36733 84262
58067 36733
30161 58067
43171 30161
47202 43171
1689 47202
753...

output:

1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1048576
1152921504606846976
576460752303423488
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606...

result:

ok 9933 numbers

Test #33:

score: 0
Accepted
time: 740ms
memory: 100984kb

input:

99293
50859 98730
98591 50859
32948 98591
80691 32948
9920 80691
27594 9920
84857 27594
25772 84857
14792 25772
14973 14792
71451 14973
55376 71451
33920 55376
93689 33920
44355 93689
18986 44355
58274 18986
51746 58274
75969 51746
81440 75969
91096 81440
24271 91096
2460 24271
83026 2460
71901 8302...

output:

18014398509481984
1152921504606846976
1152921504606846980
140737488355328
1152921504606846980
1152921504606846976
1152921504606846976
562949953421312
18014398509481984
1152921504606846976
9007199254740992
1152921504606846976
1152921504606846976
16777216
1152921504606846976
1152921504606846976
288230...

result:

ok 9960 numbers

Test #34:

score: 0
Accepted
time: 738ms
memory: 102940kb

input:

99870
41281 68626
3628 41281
3207 3628
85989 3207
70200 85989
4817 70200
18845 4817
50730 18845
4026 50730
42926 4026
78127 42926
70770 78127
55171 70770
552 55171
59073 552
11064 59073
25328 11064
87894 25328
7477 87894
22659 7477
28619 22659
37254 28619
86444 37254
6889 86444
50846 6889
55534 5084...

output:

1152921504606846978
1152921504606846976
1152921504606846978
1073741824
1152921504606846976
1152921504606846976
1152921504606846976
576460752303423488
1152921504606846976
1152921504606846976
1152921504606846976
1152921504606846976
576460752303423488
2147483648
1152921504606846976
1152921504606846976
...

result:

ok 9928 numbers

Test #35:

score: 0
Accepted
time: 742ms
memory: 108904kb

input:

99141
35571 77107
36738 35571
94150 36738
56455 94150
86575 56455
99060 86575
32548 99060
5443 32548
22637 5443
37290 22637
10646 37290
90761 10646
55035 90761
37297 55035
46976 37297
37918 46976
72075 37918
78292 72075
53160 78292
77446 53160
16425 77446
13001 16425
66243 13001
39211 66243
15168 39...

output:

1152921504606846976
1152921504606846976
36028797018963968
1152921504606846976
1152921504606846976
512
1152921504606846976
137438953472
18014398509481984
1152921504606846976
72057594037927936
1152921504606846976
1152921504606846976
2199023255552
72057594037927936
72057594037927936
562949953421312
576...

result:

ok 9996 numbers

Test #36:

score: 0
Accepted
time: 725ms
memory: 104596kb

input:

99022
97091 76784
39255 97091
95281 39255
34487 95281
94367 34487
1575 94367
84183 1575
33838 84183
39271 33838
78809 39271
21521 78809
25277 21521
78537 25277
96267 78537
25696 96267
88635 25696
41012 88635
39376 41012
93351 39376
29213 93351
36277 29213
15302 36277
29206 15302
44983 29206
69989 44...

output:

1152921504606846976
1152921504606846976
4503599627370496
1152921504606846976
1152921504606879744
1152921504606879744
1152921504606846976
1152921504606846976
1152921504606846976
1125899906842624
1152921504606847040
1152921504606846976
35184372088832
1152921504606846976
1152921504606846976
11258999068...

result:

ok 9959 numbers

Subtask #6:

score: 15
Accepted

Dependency #5:

100%
Accepted

Test #37:

score: 15
Accepted
time: 647ms
memory: 98220kb

input:

99703
27900 98506
73621 98506
65967 98506
99084 98506
64267 98506
56800 98506
37555 98506
71856 98506
70274 98506
92346 65967
54463 98506
49909 98506
36645 92346
74593 54463
6270 98506
30425 74593
26211 98506
5099 98506
50305 30425
44107 98506
57865 36645
41363 70274
18689 36645
7422 73621
16591 503...

output:

536870912
562949953421312
32768
2048
8192
18014398509481984
268435456
8
68719476736
4398046511104
2
576460752303423488
18014398509481984
1024
536870912
549755813888
8388608
134217728
144115188075855872
128
268435456
140737488355328
4398046511104
4
1073741824
2097152
18014398509481984
900719925474099...

result:

ok 9907 numbers

Test #38:

score: 0
Accepted
time: 664ms
memory: 101796kb

input:

99932
43560 3726
51011 43560
74749 51011
80900 3726
79242 80900
22947 74749
24282 3726
24468 22947
73971 51011
62733 22947
65271 3726
86759 22947
38411 74749
36727 24468
21505 22947
82990 51011
60505 86759
90448 43560
29157 73971
67618 22947
91883 74749
58638 79242
31978 51011
49121 24468
21121 2915...

output:

262144
134217728
8589934592
16777216
67108864
16777216
134217728
1073741824
8
18014398509481984
134217728
32768
134217728
134217728
8589934592
137438953472
65536
8589934592
18014398509481984
1024
18014398509481984
137438953472
16777216
8192
8589934592
524288
1073741824
18014398509481984
180143985094...

result:

ok 9994 numbers

Test #39:

score: 0
Accepted
time: 647ms
memory: 106572kb

input:

99782
55146 78372
8134 78372
84051 78372
54282 78372
55921 78372
45845 78372
66967 78372
8750 78372
27237 78372
11677 78372
53352 78372
96197 78372
41543 78372
68196 78372
24324 8134
63730 78372
88022 78372
76165 41543
6771 78372
15970 55146
98523 78372
64562 55146
30421 78372
25803 78372
28270 6456...

output:

34359738368
2251799813685248
137438953472
137438953472
1073741824
576460752303423488
4294967296
64
137438953472
137438953472
576460752303423488
0
8192
576460752303423488
4096
576460752303423488
524288
576460752303423488
33554432
2097152
8192
137438953472
1073741824
131072
16777216
1073741824
16
1374...

result:

ok 9902 numbers

Test #40:

score: 0
Accepted
time: 644ms
memory: 99316kb

input:

99958
75201 37320
9692 37320
10807 37320
14157 37320
82391 37320
37761 37320
7406 37320
62164 37320
93034 37320
48603 37320
10109 37320
23985 82391
98999 82391
55282 37320
91441 37320
50305 37320
6235 37320
50000 98999
14786 37320
59396 23985
21058 37320
61759 50000
75630 50000
58957 61759
91725 752...

output:

9007199254740992
512
2199023255552
2
536870912
65536
137438953472
4096
16384
33554432
262144
524288
536870912
72057594037927936
8
576460752303423488
536870912
1099511627776
536870912
536870912
34359738368
9007199254740992
1099511627776
524288
140737488355328
16384
70368744177664
2199023255552
140737...

result:

ok 9947 numbers

Test #41:

score: 0
Accepted
time: 651ms
memory: 99564kb

input:

99490
25639 26126
55163 26126
68405 26126
43121 26126
76625 26126
4490 26126
92431 26126
1968 26126
6078 26126
93767 26126
12470 26126
58025 26126
98269 92431
21669 25639
55010 1968
33104 26126
13201 98269
10577 26126
62359 26126
67473 55010
20637 13201
75341 13201
47597 13201
12821 26126
77928 1320...

output:

68719476736
256
8796093022208
16
1048576
1152921504606846976
274877906944
68719476736
4194304
8
274877906944
274877906944
16
137438953472
262144
8388608
4194304
2147483648
35184372088832
2147483648
288230376151711744
4194304
4096
1152921504606846976
8388608
524288
2147483648
1152921504606846976
6871...

result:

ok 9952 numbers

Test #42:

score: 0
Accepted
time: 649ms
memory: 98100kb

input:

99207
17783 95040
84551 95040
81241 95040
9621 95040
91183 95040
6319 95040
11497 95040
74083 95040
94250 95040
29861 95040
17050 95040
33286 95040
90508 95040
20782 95040
82486 95040
57412 95040
66783 95040
77936 95040
92863 17783
67985 95040
74668 95040
50306 57412
84449 95040
11096 95040
33392 95...

output:

8388608
268435456
72057594037927936
268435456
4398046511104
0
18014398509481984
8388608
34359738368
4398046511104
131072
4096
64
8388608
4194304
1048576
18014398509481984
281474976710656
72057594037927936
16384
72057594037927936
33554432
34359738368
8388608
18014398509481984
17592186044416
1048576
4...

result:

ok 9910 numbers

Test #43:

score: 0
Accepted
time: 654ms
memory: 98396kb

input:

99962
8418 48533
43838 48533
45127 48533
32976 48533
13465 45127
98430 8418
4583 48533
12701 48533
87334 48533
91109 4583
77403 48533
86629 48533
42208 48533
99557 48533
801 48533
45638 48533
11189 45127
18142 48533
76993 91109
11658 86629
28482 48533
74164 42208
57107 48533
60092 48533
95867 99557
...

output:

288230376151711744
144115188075855872
576460752303423488
2199023255552
549755813888
1048576
8388608
144115188075855872
536870912
131072
576460752303423488
576460752303423488
576460752303423488
34359738368
512
549755813888
576460752303423488
128
549755813888
0
549755813888
524288
288230376151711744
1...

result:

ok 9905 numbers

Test #44:

score: 0
Accepted
time: 660ms
memory: 98072kb

input:

99625
25315 86141
74751 86141
89028 86141
97585 86141
73523 86141
65649 25315
15981 86141
36679 86141
78866 86141
50917 25315
64912 86141
99535 86141
12991 86141
15354 65649
17947 97585
13613 25315
24775 15354
7852 73523
1166 24775
8798 89028
40176 89028
34310 24775
36138 64912
36596 36138
32512 975...

output:

281474976710656
33554432
281474976710656
18014398509481984
2048
34359738368
8589934592
128
128
256
281474976710656
8192
256
8589934592
281474976710656
18014398509481984
18014398509481984
256
18014398509481984
8192
32768
2048
512
2
33554432
262144
268435456
8388608
33554432
33554432
18014398509481984...

result:

ok 9931 numbers

Subtask #7:

score: 15
Accepted

Test #45:

score: 15
Accepted
time: 1091ms
memory: 183944kb

input:

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

output:

4
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
8
0
0
0
0
16
0
0
4096
0
0
0
0
4096
0
0
0
0
2
0
0
0
0
4
0
0
0
0
32
64
0
0
0
512
64
4
4096
0
2
0
0
131072
0
0
0
0
0
0
0
0
2
0
0
0
2
0
4096
2
0
0
0
0
0
512
2
8
0
0
4096
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
512
0
0
36
0
0
0
0
0
0
0
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 99210 numbers

Test #46:

score: 0
Accepted
time: 1087ms
memory: 183528kb

input:

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

output:

0
0
4096
2
0
0
8
0
0
16
0
0
0
0
0
128
0
532
2
640
0
16384
514
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
0
2
0
128
0
0
0
2
0
0
2
0
128
0
0
0
0
132
2
0
0
0
0
128
0
4
0
0
0
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
0
0
0
0
0
0
0
0
128
0
256
0
0
0
0
0
0
0
0
16
2
0
2
0
0
0
264
0
0
0
0
0
0
0
0
0
2
0
0
4
5...

result:

ok 99668 numbers

Test #47:

score: 0
Accepted
time: 1117ms
memory: 183500kb

input:

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

output:

0
0
0
0
2
0
0
0
2
0
0
0
0
0
0
0
0
1024
0
0
0
256
0
2
0
0
131104
0
0
131104
2
0
1024
0
0
0
258
0
0
16388
0
0
0
256
0
0
0
0
2
2
0
32
0
0
0
16384
0
0
32
4
0
0
2
0
0
0
2
0
0
1026
8
0
8
4
0
4
2
0
0
0
0
0
1024
0
2
0
36
0
2
0
4
0
32
0
2
2
0
8192
0
0
0
0
0
0
0
4098
0
0
0
0
0
32
4098
1024
0
2
2
0
0
0
4
4096
...

result:

ok 99396 numbers

Test #48:

score: 0
Accepted
time: 1141ms
memory: 183788kb

input:

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

output:

0
0
0
0
0
0
4
0
4096
1024
0
4
0
16
64
8
0
0
0
0
1024
0
0
0
0
256
0
0
0
0
8192
0
0
1028
0
4
4
0
0
0
0
0
0
0
1024
0
0
0
16
0
0
2
0
0
0
0
0
0
0
4
0
64
4
0
524288
0
0
0
36
0
0
0
0
0
0
0
0
0
0
0
4096
1024
0
0
0
0
0
2
0
0
8
0
16
0
0
0
96
64
64
0
0
0
2
64
0
0
66
0
2
0
4096
0
0
0
2
64
0
0
0
0
2
0
0
256
0
0
...

result:

ok 99733 numbers

Subtask #8:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #49:

score: 0
Time Limit Exceeded

input:

997985
283598 479403
647272 479403
348858 479403
419926 479403
398228 479403
331550 479403
3555 479403
142988 479403
88121 479403
597844 479403
397265 479403
527676 479403
912537 479403
831398 479403
494040 142988
715887 494040
562090 479403
300327 479403
953427 715887
220729 715887
752782 398228
25...

output:

4503599627370496
4398046511104
288230376151711744
524288
288230376151711744
1073741824
256
562949953421312
4398046511104
1152921504606846976
1152921504606846976
288230376151711744
4503599627370496
562949953421312
70368744177664
35184372088832
70368744177664
1152921504606846976
4503599627370496
10995...

result: