QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116455#6629. Travelling TraderAFewSuns11 45ms25928kbC++142.5kb2023-06-29 09:22:302023-06-29 09:22:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 09:22:32]
  • 评测
  • 测评结果:11
  • 用时:45ms
  • 内存:25928kb
  • [2023-06-29 09:22:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
vector<ll> ans;
ll n,k,head[200020],cnt=0,a[200020];
struct node{
	ll nxt,to;
}e[400040];
void add(ll u,ll v){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct sub1{
	ll f[200020],son[200020];
	void dfs(ll fa,ll u){
		go(u){
			ll v=e[i].to;
			if(v==fa) continue;
			dfs(u,v);
			if(f[u]<f[v]){
				f[u]=f[v];
				son[u]=v;
			}
		}
		f[u]+=a[u];
	}
	void solve(){
		dfs(0,1);
		writeln(f[1]);
		ll u=1;
		while(u){
			ans.push_back(u);
			u=son[u];
		}
		writeln(ans.size());
		fr(i,0,(ll)ans.size()-1) writesp(ans[i]);
	}
}sub1;
struct sub2{
	void solve(){
		
	}
}sub2;
struct sub3{
	void dfs(ll fa,ll u,bl o){
		if(o){
			ans.push_back(u);
			go(u){
				ll v=e[i].to;
				if(v==fa) continue;
				dfs(u,v,0);
			}
		}
		else{
			go(u){
				ll v=e[i].to;
				if(v==fa) continue;
				dfs(u,v,1);
			}
			ans.push_back(u);
		}
	}
	void solve(){
		ll sum=0;
		fr(i,1,n) sum+=a[i];
		writeln(sum);
		dfs(0,1,1);
		writeln(ans.size());
		fr(i,0,(ll)ans.size()-1) writesp(ans[i]);
	}
}sub3;
int main(){
	n=read();
	k=read();
	fr(i,2,n){
		ll u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	fr(i,1,n) a[i]=read();
	if(k==1) sub1.solve();
	else if(k==2) sub2.solve();
	else sub3.solve();
}

详细

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 2ms
memory: 7492kb

input:

2 1
1 2
255959470 961356354

output:

1217315824
2
1 2 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 1ms
memory: 7668kb

input:

1000 1
730 89
762 280
923 523
740 22
679 350
448 769
102 712
154 965
219 32
238 289
484 502
183 311
999 682
806 450
275 101
131 197
749 720
131 937
960 202
503 320
95 262
595 133
809 560
659 451
843 218
258 842
564 316
729 727
413 237
606 531
469 258
612 8
707 539
359 680
957 639
381 708
104 490
234...

output:

95535
17
1 173 449 472 396 545 668 270 981 489 852 836 763 6 218 843 758 

result:

ok correct!

Test #3:

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

input:

200000 1
111811 133538
179217 151840
171974 117009
187613 169656
64662 13136
132434 89348
52802 175565
194821 191312
196047 99457
40339 152969
29669 180026
147677 57771
119598 58048
80707 146623
72232 101624
48109 11800
71536 69
31573 129
24409 17263
1033 148614
66977 149926
138624 87653
141889 1178...

output:

221
35
1 145832 90178 52464 3517 55709 39776 67451 59386 143855 102872 38865 13093 177086 7366 190908 160039 69864 196809 13257 612 171083 182883 14221 93359 52156 27994 103745 151704 138607 5346 14735 29598 89600 128747 

result:

ok correct!

Test #4:

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

input:

200000 1
102636 78442
179388 84484
161437 35179
102313 154299
62439 71542
176361 125315
174129 186376
180886 54947
154823 114239
174647 112385
136495 187134
157035 96260
101101 192444
58209 23947
55494 191600
168007 162648
140149 73180
130665 180633
129328 67380
90262 134914
185905 104220
111321 154...

output:

21795891322
36
1 13557 199188 104317 71891 69787 1221 63258 191536 179446 83510 187880 124824 43888 83237 194602 59080 196038 195977 18490 43421 110298 60011 137785 140692 48345 68279 128780 198550 29394 56331 112092 192199 177180 16418 142142 

result:

ok correct!

Test #5:

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

input:

200000 1
682 75953
92444 160568
113369 93705
154622 193304
149619 128186
104784 48913
131684 161196
25886 151867
89191 19511
99233 137377
104650 120096
64347 93526
111350 71598
7568 120116
123497 76821
25436 190715
99884 33654
109438 69462
165464 2475
163215 34551
33926 85078
101208 193355
50705 828...

output:

99327575017
197
1 178606 82034 53029 10508 21404 203 109187 121716 142023 3901 36728 9916 192913 18250 170199 113960 179753 163922 179588 31797 31645 183321 83207 13973 128176 38001 160968 9055 62809 168173 43933 187373 123795 114656 2192 193151 25062 141855 133596 155793 64049 57320 93903 33957 139...

result:

ok correct!

Test #6:

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

input:

200000 1
91999 92900
195726 58991
132067 99937
168188 152017
188495 19779
105961 45241
53406 75757
85118 170259
46250 47585
132248 8609
195110 32777
164307 95643
133411 739
170952 145623
19297 14414
171045 97619
74663 193421
139543 189434
36319 56453
77520 91164
91469 30021
128798 62259
183807 15271...

output:

9098893435
13
1 164355 56677 150505 174723 115829 88068 105453 199874 190131 165416 182628 114943 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 15ms
memory: 16012kb

input:

200000 1
189797 1
1 148138
1 95067
141831 1
168151 1
1 25692
95612 1
1 135979
1 141581
119622 1
1 131946
86508 1
98799 1
1 189104
1 117526
46338 1
1 166375
1 28026
165221 1
54204 1
1 98743
1 181414
1 34313
1 71302
1 161200
1 146339
1 47014
1 137258
1 57857
1 196493
1 99105
54487 1
104725 1
1 45203
1...

output:

1175349557
2
1 153544 

result:

ok correct!

Test #8:

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

input:

199999 1
56367 178046
1 156890
170478 1
111308 177326
1 188427
1 90169
126610 1
161930 167698
96500 126424
118330 158517
186608 1
95505 107863
1 142887
72279 27494
1 114700
118535 1
68584 63156
97555 19966
39239 1
128030 1
1 86200
66974 1
34616 47100
173578 1
1 117279
89769 43412
1 89670
103573 1
13...

output:

2999144210
3
1 52552 129910 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 45ms
memory: 23148kb

input:

200000 1
95601 67789
174512 65854
198542 123861
153390 92355
141969 168754
177054 101194
25665 15524
131869 168080
171051 30732
97293 119758
103002 59019
141990 124310
161550 116618
2585 170410
132999 38200
99202 98733
73949 155033
144918 64086
1594 34916
37138 165382
13452 170885
136973 62178
15250...

output:

200000000000000
200000
1 47213 179780 132180 145558 41335 179095 156350 24912 104386 94658 54370 97034 108043 73905 141018 157563 199841 176455 147422 87545 190562 135095 24903 62484 36389 156106 45144 120321 4911 173474 102976 13602 68252 7332 141515 59337 182112 124040 38089 15458 161370 41901 144...

result:

ok correct!

Test #10:

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

input:

200000 1
122636 169264
76896 89915
72116 125306
186356 74852
84394 177419
21725 144848
106395 111991
189102 195804
6151 170169
185460 146764
6304 149801
147880 99539
6202 175326
104277 26515
39402 33436
116555 185545
44341 92305
197925 125286
28215 102176
182103 160554
105237 169007
105618 75618
190...

output:

49951940813408
100001
1 88700 18534 14218 21693 84470 150823 121376 192964 139616 11067 93019 188349 55336 13628 87630 31553 28945 29827 140175 179655 10038 38915 99968 89953 72978 102045 45280 176852 171879 100086 93399 183932 84482 111738 112608 136016 101850 19371 96135 54333 95939 2865 140685 13...

result:

ok correct!

Test #11:

score: 0
Accepted
time: 12ms
memory: 15276kb

input:

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

output:

13954593167
18
1 2 5 10 20 40 80 161 323 647 1295 2590 5181 10363 20727 41454 82908 165817 

result:

ok correct!

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 2ms
memory: 7484kb

input:

2 2
2 1
243296356 635616793

output:


result:

wrong output format Unexpected end of file - int64 expected

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 4
Accepted

Test #83:

score: 4
Accepted
time: 2ms
memory: 5628kb

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:

1008611451196
2000
1 1091 961 1613 377 540 454 1237 1101 359 864 99 1617 1369 562 243 1831 1256 901 1040 709 1341 1291 129 1967 260 745 523 674 890 1961 452 1903 1656 560 739 183 544 1024 1240 877 899 1973 1548 191 1265 1344 33 1679 565 1314 774 276 139 926 1397 1019 545 741 1846 965 16 1684 616 121...

result:

ok correct!

Test #84:

score: 0
Accepted
time: 1ms
memory: 7552kb

input:

2000 3
1727 567
1783 1850
205 985
323 1094
1153 821
1756 117
377 1928
1026 1303
1343 1814
268 745
242 948
1140 1218
7 1675
101 1798
1403 1752
1184 671
87 248
1953 30
1580 1441
507 1438
525 419
901 421
1585 1405
1575 883
1952 1930
1988 1325
615 722
994 1202
178 474
1978 1500
899 481
216 409
999 1817
...

output:

1012330476243
2000
1 269 1545 1724 1454 88 1123 246 701 1364 1158 1696 1918 1725 693 61 718 554 220 105 917 1784 257 1071 802 1369 993 1046 1275 319 794 140 670 838 477 723 163 1205 1561 1875 1243 1739 1768 1224 781 1990 1631 975 1321 1689 827 1129 1298 292 1615 1763 224 1994 653 56 1091 1873 708 15...

result:

ok correct!

Test #85:

score: 0
Accepted
time: 1ms
memory: 5508kb

input:

2000 3
1213 130
101 508
72 1199
1550 1096
1099 861
1515 627
1299 1672
1338 105
1444 1019
15 1560
1949 971
52 1312
30 529
186 1687
1917 484
1971 349
537 1223
1955 1377
300 1060
1786 1811
1960 90
1959 1353
1831 1548
303 511
1073 1197
863 1527
1379 994
31 9
1247 1707
1395 1532
29 1544
119 296
1919 1554...

output:

1001405462082
2000
1 1557 1450 1896 942 718 1710 1636 346 1246 954 729 1955 1377 1703 146 295 242 1503 1153 1997 1241 1169 1732 1649 563 1069 388 1208 1310 1801 710 1303 1483 832 1472 1417 1181 852 1847 262 63 1152 1374 450 1659 372 1766 112 1855 434 281 666 1307 898 333 578 1008 65 821 413 1687 151...

result:

ok correct!

Test #86:

score: 0
Accepted
time: 2ms
memory: 7424kb

input:

2000 3
532 64
99 960
1271 519
1141 1056
1986 1889
930 817
639 1188
841 771
1334 179
1336 1163
1687 1909
281 1300
1410 207
1018 1471
1645 972
711 1504
623 1739
1905 1959
1423 738
1747 34
1684 204
61 1012
1092 1350
1977 1130
62 473
1623 1021
1157 227
427 832
1900 1792
1910 584
265 330
1874 1186
1797 1...

output:

1002207066842
2000
1 1253 938 1552 628 475 84 425 1510 435 861 619 18 1280 1082 1265 1482 410 365 333 1513 762 1255 182 1295 1106 1637 1773 466 1808 228 997 1143 1799 1830 923 1834 857 595 317 618 554 1345 805 1061 551 945 1755 959 582 240 1100 1017 269 1634 789 1882 926 547 828 1503 1130 25 106 197...

result:

ok correct!

Test #87:

score: 0
Accepted
time: 2ms
memory: 5508kb

input:

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

output:

995663027103
2000
1 7 31 127 511 1023 1022 510 1021 1020 255 509 1019 1018 508 1017 1016 254 126 507 1015 1014 506 1013 1012 253 505 1011 1010 504 1009 1008 252 63 125 503 1007 1006 502 1005 1004 251 501 1003 1002 500 1001 2000 1000 250 124 499 1999 1998 999 1997 1996 998 498 1995 1994 997 1993 1992...

result:

ok correct!

Test #88:

score: 0
Accepted
time: 2ms
memory: 7556kb

input:

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

output:

1000109641799
2000
1 13 121 1093 1092 1091 364 1090 1089 1088 363 1087 1086 1085 362 120 1084 1083 1082 361 1081 1080 1079 360 1078 1077 1076 359 119 1075 1074 1073 358 1072 1071 1070 357 1069 1068 1067 356 40 118 1066 1065 1064 355 1063 1062 1061 354 1060 1059 1058 353 117 1057 1056 1055 352 1054 1...

result:

ok correct!

Test #89:

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

input:

2 3
1 2
820567835 309877233

output:

1130445068
2
1 2 

result:

ok correct!

Test #90:

score: 0
Accepted
time: 2ms
memory: 7488kb

input:

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

output:

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

result:

ok correct!

Test #91:

score: 0
Accepted
time: 2ms
memory: 7528kb

input:

2000 3
1651 76
620 463
764 704
1648 768
1235 1183
915 523
1417 75
758 442
1952 271
1018 947
659 320
1976 562
337 965
1184 35
1234 1609
664 1444
580 737
1331 720
1314 973
945 1890
1760 1986
210 567
186 12
1306 1774
224 1073
1885 314
641 1144
1524 446
1148 1576
859 1438
1991 343
89 1665
140 537
183 14...

output:

994118359072
2000
1 1969 1145 974 1493 1596 1468 999 1374 581 559 1997 1214 917 723 1621 1005 941 1108 555 80 1111 442 758 61 34 1188 1746 1610 450 221 19 226 1326 187 1741 865 560 1890 472 639 1273 1858 945 613 1358 1150 866 76 1651 249 1120 1001 582 1211 223 1762 609 1065 757 144 203 1212 1244 577...

result:

ok correct!

Test #92:

score: 0
Accepted
time: 2ms
memory: 7704kb

input:

2000 3
574 1963
1305 849
1271 853
1365 1853
12 1402
1010 1462
1353 494
74 1688
1786 1435
405 1012
1229 924
1085 1565
713 1742
796 1929
1844 1725
801 79
1089 1137
1255 1331
1659 754
341 1929
1233 956
615 1455
1798 867
1105 1943
196 790
1357 678
1160 1797
1310 1963
857 792
35 1464
1576 1251
1628 913
1...

output:

1002312168974
2000
1 480 1317 1153 330 1257 1733 634 1425 1782 1235 797 863 857 1986 632 1792 959 1751 669 1459 294 1464 1162 862 1050 1220 324 1004 141 1996 1707 911 1194 898 35 1156 1511 964 1121 1776 1492 670 1552 226 1199 1561 147 636 1166 451 685 1651 788 53 148 1246 1817 52 804 712 1714 819 11...

result:

ok correct!

Test #93:

score: 0
Accepted
time: 1ms
memory: 7628kb

input:

2000 3
684 1375
1184 445
1723 1722
473 1351
1019 941
1595 1572
718 56
974 696
308 1015
650 1134
338 1313
210 277
1735 1134
1053 283
1112 1862
90 450
1762 1042
1903 1927
1472 337
312 1925
815 1234
1226 206
1371 994
108 1604
1249 674
1509 1501
1232 1669
1519 1474
1368 780
953 749
1201 1422
351 325
101...

output:

1000468940262
2000
1 335 1877 224 241 911 1927 1125 1510 568 66 1716 693 1447 485 306 1165 1943 648 458 1856 383 1333 930 413 684 74 912 1375 439 613 1613 909 1055 1306 244 917 987 67 1645 1895 369 416 1736 1051 1779 895 899 593 232 233 1119 1678 19 228 375 781 1597 1726 83 240 408 525 1876 433 521 ...

result:

ok correct!

Test #94:

score: 0
Accepted
time: 2ms
memory: 7556kb

input:

2000 3
1317 1228
1811 1659
491 1756
1622 1016
730 1196
873 59
1567 441
144 1469
1726 647
698 1631
1985 1711
1005 616
1286 964
1408 625
246 1404
125 1488
16 982
1576 1223
750 1845
1831 604
1502 458
1043 1552
1360 921
180 1800
266 1261
1021 1308
1421 625
99 403
891 1500
602 482
1520 610
486 1899
843 1...

output:

977343950277
2000
1 112 649 280 1250 707 1313 1653 1707 593 111 1947 272 844 1248 1869 797 1234 1684 1216 448 1138 382 1371 835 1576 239 1332 1921 1594 139 1358 1736 1191 1980 1538 343 1291 1344 1049 1223 715 1185 401 392 583 365 1308 1021 397 502 335 211 1835 718 998 1599 792 1853 1812 402 1299 200...

result:

ok correct!

Test #95:

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

input:

2000 3
1188 1181
1574 1619
944 1974
626 789
1798 27
159 547
1759 1110
1304 1360
1172 997
1815 1043
1496 1948
1781 1513
1884 993
652 1079
1983 1436
88 1953
1221 174
383 1741
48 814
1532 1319
1039 1401
1737 1829
996 920
222 1902
590 1270
692 1504
1918 654
928 1602
208 1165
1251 1596
329 856
1068 577
2...

output:

985678197158
2000
1 219 617 1949 938 1255 1605 463 1104 1175 381 130 1863 1119 1654 998 837 754 372 1770 68 666 1271 1784 1135 934 1162 1842 1009 1479 1282 555 1187 833 900 259 1328 1039 304 1154 358 305 1401 620 1297 1310 490 1114 936 1468 586 1444 1832 1014 1274 1413 33 447 405 919 723 747 1712 77...

result:

ok correct!

Test #96:

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

input:

2000 3
892 807
1866 64
123 674
1147 1184
1897 1873
385 1877
7 1697
1753 234
191 1453
625 850
91 1195
320 1560
1827 43
426 1801
1338 1775
55 1070
1138 127
627 1985
225 882
232 1144
124 1208
1665 54
819 898
1038 1676
1642 327
1827 1548
559 1243
69 854
1806 195
943 654
1426 905
691 1598
532 1304
235 53...

output:

1023444069399
2000
1 1850 669 1125 1544 1213 889 344 1898 1254 629 1451 791 264 531 441 675 62 439 1174 1537 162 1162 825 821 1734 188 1648 102 381 549 1607 9 895 659 145 1861 1716 316 330 70 906 1192 905 1442 232 1615 1589 1808 1839 1359 619 343 1144 1995 1034 848 1967 348 1579 1211 1678 214 488 23...

result:

ok correct!

Test #97:

score: 0
Accepted
time: 2ms
memory: 7524kb

input:

2000 3
1367 159
1497 1532
1105 440
1955 1658
129 1964
272 956
1165 1745
625 1694
257 726
645 476
623 1098
648 303
665 847
1304 1665
307 926
319 1098
619 1582
1920 1770
874 1257
1443 815
121 578
1280 943
555 1602
1575 583
545 447
1708 1104
911 146
347 1466
1108 1412
1548 567
451 1182
1449 813
634 168...

output:

1010882805670
2000
1 1857 1498 1846 627 1076 512 1721 618 812 332 1828 196 151 1119 174 1167 1706 1476 40 1922 227 884 1660 443 496 1545 1734 1895 828 3 117 1490 1301 962 916 1459 724 1929 1444 970 1821 260 1656 1815 554 1374 241 1760 181 1635 839 1288 1272 1305 992 296 666 815 237 1186 1707 1259 13...

result:

ok correct!

Test #98:

score: 0
Accepted
time: 1ms
memory: 7540kb

input:

2000 3
1611 477
1551 698
1677 1706
712 1391
685 1755
1645 749
1510 671
1952 809
1398 368
213 1597
361 1006
651 971
437 409
1563 1815
704 16
42 404
930 26
1857 1089
1832 173
877 850
1876 1304
349 628
515 241
1700 787
1627 1311
1106 1040
1527 1685
591 1374
1350 359
240 359
456 1245
397 637
297 972
83 ...

output:

1014963178537
2000
1 469 1360 742 104 1338 1587 896 1878 1241 1458 1634 504 1948 1362 382 1183 1688 1032 451 1524 1728 1445 1208 468 1897 27 1001 221 1178 562 1301 1475 1137 99 1118 1838 1419 1707 408 88 641 277 1158 1969 878 1433 542 96 1195 1441 120 1438 612 1023 500 152 413 1020 1621 343 1900 761...

result:

ok correct!

Test #99:

score: 0
Accepted
time: 2ms
memory: 7532kb

input:

2000 3
1595 236
1251 497
809 946
633 735
282 191
1643 1997
1563 640
366 1468
640 1510
1781 1617
1157 1659
535 1144
990 1887
687 1221
675 931
214 809
196 724
330 427
596 271
221 1994
947 841
520 640
1251 1215
1331 1042
640 149
1617 1887
202 1223
1400 1429
1127 898
106 1015
615 1707
968 1043
490 1299
...

output:

1003217858982
2000
1 1074 1463 891 1532 379 596 83 1723 488 1472 531 1876 478 1462 1621 1600 575 1127 322 357 1618 837 504 756 898 1169 1265 543 741 241 178 1355 1210 1088 1507 1508 1701 1910 1853 370 1915 1945 61 1948 1963 1738 1066 229 50 1353 1627 640 1411 1085 134 1475 280 1665 1900 1071 1469 16...

result:

ok correct!

Test #100:

score: 0
Accepted
time: 2ms
memory: 5496kb

input:

2000 3
988 1
204 1
1 1855
1 226
26 1
1 1079
1 1825
572 1
50 1
1 1215
1 1532
1 1118
1 770
108 1
1 1207
1845 1
432 1
1369 1
1 879
1 203
460 1
154 1
135 1
492 1
1 873
1 1625
1212 1
1 107
1321 1
1818 1
1 292
1 1427
49 1
1 1233
1 1712
1579 1
418 1
1 793
1 1090
1 1842
1302 1
1 227
201 1
1 912
654 1
1 69
1...

output:

996901666648
2000
1 1200 1886 1197 401 523 1956 716 1245 1379 1724 27 195 1763 1142 1461 858 1318 1854 1878 1149 1737 1560 789 827 713 1758 123 947 747 857 491 2 891 1961 293 1325 1647 330 995 1013 850 63 1670 1128 1775 10 644 1452 267 543 1180 761 1408 1441 1904 1673 459 513 1770 39 1494 1710 1155 ...

result:

ok correct!

Test #101:

score: 0
Accepted
time: 2ms
memory: 7704kb

input:

1999 3
1773 1351
1 1076
1754 1646
1267 1
1157 983
1 978
1 1751
1392 1119
379 1
1 5
1 360
613 769
1 1472
1 1447
851 1
1867 1319
175 1
976 1
1760 1519
1 1718
1 1919
1 835
757 1060
1000 1
1331 1412
338 1
1341 11
1563 1415
1713 1127
772 477
1855 1
168 1248
600 1
335 1825
704 928
236 919
1815 1692
729 57...

output:

1997213132735
1999
1 1637 773 1179 435 420 486 1678 238 1294 252 426 1257 1811 140 1346 1429 1368 1915 951 1254 1195 223 1994 84 993 1236 1988 1545 329 1053 437 607 189 434 1606 1463 908 1344 407 1691 80 1531 860 1903 1221 1289 1533 1024 263 408 895 15 1803 1293 1092 909 68 970 1679 1848 359 768 188...

result:

ok correct!

Test #102:

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

input:

1997 3
1399 516
1 716
1426 1537
965 594
1856 855
1284 1479
1566 927
1454 1924
890 1748
84 1373
95 1672
185 1374
1 1082
34 1
211 782
1298 176
1310 776
1661 594
1931 428
980 916
693 1664
1598 91
981 1
30 1
536 121
154 1558
668 641
1637 1
777 13
302 673
889 360
1 1282
929 1
1035 204
1168 1923
190 151
8...

output:

1995219549052
1997
1 503 587 1519 1031 794 1837 1841 645 1162 1169 1430 47 1198 1409 1092 817 526 276 1906 1199 1394 524 610 1141 1058 1110 1243 1548 872 231 1174 1369 549 812 1532 1126 770 699 1414 486 303 16 517 1337 956 1210 1718 1556 1265 1776 1636 1756 1053 273 1463 583 1712 1858 969 472 165 16...

result:

ok correct!

Test #103:

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

input:

1936 3
341 1240
946 1597
1195 959
1733 1240
615 937
184 592
1258 1799
1601 1409
880 1258
91 1718
1417 1139
916 1592
184 911
1852 180
452 1793
803 1343
180 1895
575 1888
171 1778
1176 1912
1173 107
1173 372
1108 1094
1066 1293
1139 1561
771 1835
651 1675
1637 1675
41 1879
1396 771
1772 497
1687 752
1...

output:

959283331124
1936
1 785 516 815 1329 1274 269 1437 1064 1722 262 537 231 1254 16 1039 361 1650 1181 1742 1216 1929 948 1457 676 23 21 1833 1046 307 338 1823 1713 1233 1791 365 835 266 594 1801 1924 451 204 1555 458 1247 1756 1821 1537 136 1710 499 1633 286 513 1817 940 1304 1362 915 1694 881 1775 76...

result:

ok correct!

Test #104:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

2000 3
1370 1319
6 1661
982 1460
654 816
1368 70
841 1391
332 1111
107 46
387 1390
928 196
369 1792
742 337
1906 1604
1278 672
154 1991
1518 308
849 846
705 158
1835 1612
780 1779
881 1867
597 1965
1956 409
1099 1242
828 1821
1662 344
760 1126
911 306
948 1909
1296 830
1642 892
516 1614
957 796
1038...

output:

2000000000000
2000
1 1699 152 1065 1008 155 1616 1486 1792 616 1577 945 383 525 444 690 1212 1542 1749 1436 876 1571 654 661 1267 898 1056 729 846 53 507 430 1433 1430 1923 586 937 454 1987 46 1609 1359 1982 1000 712 241 148 775 16 310 866 1150 713 1518 673 831 695 739 59 1856 1621 1579 208 596 1963...

result:

ok correct!

Test #105:

score: 0
Accepted
time: 2ms
memory: 7712kb

input:

2000 3
531 824
1828 527
489 1172
118 1355
370 562
1080 1962
535 1707
1302 1749
1996 347
424 1282
236 30
1937 1327
395 1060
672 1730
850 1700
19 1215
1989 1284
762 1946
646 1551
1478 249
446 1426
906 1103
1765 267
177 785
1231 699
410 415
1905 1059
1518 1948
219 987
825 1030
1812 995
1260 962
149 786...

output:

987613898700
2000
1 252 1554 1741 1308 1428 981 1492 859 1465 686 314 1519 554 1419 884 526 614 1412 72 396 459 1304 1141 140 845 107 592 201 106 473 1935 866 332 40 930 335 1423 1962 1988 12 1460 544 198 1718 1573 39 1670 1732 1290 1529 496 242 286 321 774 93 155 497 620 1902 1279 1843 167 392 1854...

result:

ok correct!

Subtask #6:

score: 5
Accepted

Dependency #5:

100%
Accepted

Test #106:

score: 5
Accepted
time: 30ms
memory: 15464kb

input:

200000 3
147012 182751
154277 181776
95094 76426
30313 86629
126223 49995
166060 157842
122541 40371
6521 182375
175030 110447
78367 175134
131250 97285
132337 99771
133031 2158
102720 163461
104670 46325
70722 156875
99733 7253
130400 31525
38020 23547
104556 120340
152061 174001
112957 138331
6972...

output:

99966483941576
200000
1 97392 193630 173393 85401 164694 114963 61624 61981 96517 2100 7527 113272 78346 139822 188020 87765 25833 147324 15690 194528 162304 3583 34831 5928 149334 104727 177425 83205 20155 188151 121341 83476 74692 170356 99229 17199 173141 1959 29414 65043 138025 140397 193224 791...

result:

ok correct!

Test #107:

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

input:

200000 3
88318 81002
165280 125130
123213 158997
170916 134482
177516 24669
83023 47275
56744 198831
61378 114675
142731 71814
37961 109617
197131 149557
68375 143769
129315 188798
47241 2192
45374 89479
141586 98813
117482 28948
47723 198356
153753 15033
74174 89660
120110 20697
166201 153612
56703...

output:

100200484512997
200000
1 65465 189467 188624 90568 1618 42302 182279 142801 82162 165183 27584 60015 103873 186440 98874 126676 136974 111487 65956 7946 193562 74855 55467 137498 45878 95008 70655 27347 104789 166163 132560 132387 78329 191565 2481 81337 57925 110240 171361 142774 64747 28400 149028...

result:

ok correct!

Test #108:

score: 0
Accepted
time: 33ms
memory: 16200kb

input:

200000 3
158080 150707
87713 27325
92660 116209
54409 23694
2943 189354
174240 164818
63040 89575
78660 136513
161745 60054
17228 137313
33135 77303
46614 163540
176388 144256
20069 160599
164840 98121
163973 193193
93832 65863
151238 29299
13510 176374
95565 29436
172499 151626
4052 2523
149429 151...

output:

99876819168945
200000
1 172557 99867 1012 199872 195498 91544 27166 158121 36848 182251 163194 130092 151455 48990 143309 69692 191314 73425 175494 57416 52351 138454 113664 122505 63429 153652 119428 15277 49156 185932 175215 97604 144922 101477 52034 88368 170367 75573 31595 132540 162590 2150 412...

result:

ok correct!

Test #109:

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

input:

200000 3
13458 31389
54935 62559
19438 94761
190500 137721
133057 27282
118646 10976
158688 189150
50966 88936
64367 138380
1248 98893
70840 18433
7913 117595
102418 46367
54395 8227
170625 128662
95469 29899
156391 75448
147167 88351
146838 184391
77624 107403
24058 128408
178325 168636
48464 73268...

output:

99910494745784
200000
1 886 144195 141975 120139 36377 54718 191608 34650 158812 43115 21252 113834 22015 173517 132891 190506 140314 125218 6000 46410 29293 118431 122494 32099 106312 171940 182317 30292 48930 21905 154405 37458 12752 90881 63830 119500 142315 2640 157631 178159 95499 93878 191673 ...

result:

ok correct!

Test #110:

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

input:

200000 3
57046 131800
29987 88605
171474 148623
99129 28902
45321 30680
75505 16586
12530 86028
120454 7164
33933 150164
82906 37260
121117 104053
192033 47278
37159 45570
153727 27709
16556 116173
105577 75450
55530 147064
27341 46913
36453 101815
29637 43794
123623 61867
3629 59534
75839 5762
3583...

output:

100006037268766
200000
1 38806 140958 158632 153251 99513 18685 79533 6320 144390 33239 177576 1846 125250 49469 93369 136064 168949 158459 113763 58768 12491 17652 172558 38889 188295 187530 197104 144371 189855 172331 105473 133415 164387 70928 145149 54482 137474 82663 54592 127232 107430 121726 ...

result:

ok correct!

Test #111:

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

input:

200000 3
139477 43272
191114 76077
179020 189948
28137 1021
65951 108562
103570 145873
115851 178975
178592 72360
173350 154567
84335 161076
142716 153606
185307 176576
104994 143521
73511 116320
168667 92228
160372 179510
78166 57346
137423 155483
76454 179369
194690 69013
2700 101118
100200 94223
...

output:

99890707584446
200000
1 130935 71778 170549 54517 124378 29393 78733 102037 137017 110170 121575 181240 157205 17189 74174 75596 134135 175474 139523 93212 66733 54176 23364 189798 90837 4190 183274 133795 104206 134632 62273 184986 140743 16755 122427 33418 63209 92048 113608 10515 189976 160534 12...

result:

ok correct!

Test #112:

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

input:

200000 3
179253 61326
193064 25770
101250 104257
127308 168366
75652 156351
48789 45946
3246 138024
161405 143701
41976 91073
162591 27995
104694 9725
96951 60586
170891 35876
127049 121655
51111 162908
75978 187533
87785 85717
12359 132567
161307 112872
153158 48573
98012 48629
103902 196093
99788 ...

output:

99804652763041
200000
1 123524 49022 78090 135568 166807 127998 58559 59707 1022 148682 151528 78809 13358 193943 22432 38190 185465 2166 14090 159818 79537 182699 69489 198161 114860 150174 130409 120150 154486 110026 194028 154996 60171 177460 165218 197330 72938 35587 187403 31020 50241 163650 11...

result:

ok correct!

Test #113:

score: 0
Accepted
time: 26ms
memory: 15420kb

input:

200000 3
62838 75939
87826 180015
72625 160066
31793 97154
87330 68381
163447 73473
12778 146477
175129 158989
171461 14472
86022 120141
194508 29080
158722 75883
50290 83476
106106 21819
178861 182937
166058 96930
179108 125006
199570 132827
170051 193208
121118 189720
86617 54823
184821 60430
8819...

output:

100006003713207
200000
1 45277 175509 108618 119049 25172 55649 97051 139505 108035 186184 139646 193082 161892 112599 155710 109743 129993 80155 160314 112295 72482 143543 100890 37967 89442 95694 115523 102242 47914 77164 57391 6809 22212 96565 174355 54585 183417 159609 147520 127820 107122 77798...

result:

ok correct!

Test #114:

score: 0
Accepted
time: 17ms
memory: 15568kb

input:

200000 3
153989 10517
27314 72036
93500 132724
93638 100042
192943 181118
59968 98240
154528 61181
20366 181919
7218 87940
38589 133947
154187 77410
116666 2957
70560 16300
128562 51840
109869 105397
60196 3012
161863 18667
36797 61682
180020 54807
127767 42942
90184 125480
96410 114460
178356 14309...

output:

100132596896132
200000
1 176997 183492 47162 104212 66389 139522 170106 59550 180780 183658 146492 124242 27450 110052 198442 177118 159319 35861 196052 101557 69931 160785 168140 93584 131384 154889 32623 52180 158036 151031 38923 165749 189447 53662 56269 76445 193389 199684 101371 12417 128129 26...

result:

ok correct!

Test #115:

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

input:

200000 3
193823 30011
91709 11809
501 45254
82025 86617
184348 23880
103950 119507
37454 8974
174384 115451
23634 107320
97650 182412
42066 177636
111315 60332
130053 54528
1558 155819
7733 158979
164488 110559
46281 59042
72138 22510
13718 2327
133303 92964
105935 168350
39293 164483
15208 86000
84...

output:

99823050174586
200000
1 98461 16660 171079 55072 191402 89853 140207 113015 45547 64424 36177 63256 32897 31568 6680 10859 169223 11756 166773 45408 187788 7177 91222 51249 151754 76653 14269 83020 39141 167257 13004 35394 185189 60638 177826 43826 33822 198406 110035 86012 37260 184352 30794 94534 ...

result:

ok correct!

Test #116:

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

input:

200000 3
167904 154479
99791 26520
66032 21354
89797 127514
81807 174766
2597 165492
80439 48156
101761 132200
96442 63449
199372 164659
160562 84653
92296 7081
71393 42324
196440 127414
61112 184736
80407 46397
193310 58007
189525 22158
112277 132008
187852 91575
33497 40060
121384 1910
174332 7252...

output:

100032502601811
200000
1 114247 114264 20546 83222 165313 137008 48520 79096 148580 133797 181357 31025 176710 123215 126467 51707 82538 108959 3634 51791 161060 148272 30466 176152 17561 195752 69847 185183 123393 122008 157813 180308 157858 104090 186359 16269 153411 120130 90788 153450 35995 1213...

result:

ok correct!

Test #117:

score: 0
Accepted
time: 33ms
memory: 14740kb

input:

200000 3
57696 1
1 118308
1 63302
143342 1
1 32977
169723 1
1 99113
1 20536
104991 1
1 176676
1 35771
1 199270
1 140871
1 71858
77751 1
133782 1
1 116525
63323 1
1 82450
125231 1
1 57698
1 192616
1 127854
168916 1
25125 1
73904 1
38396 1
1 4002
192295 1
150580 1
1 159320
1 62139
46661 1
1 150820
1 4...

output:

100188092398438
200000
1 116467 4401 36981 37683 190919 172405 8106 75584 114121 160776 129097 199334 194688 194666 131082 195617 190694 91987 199985 86279 26882 138518 140493 160609 189729 143056 146161 101995 43453 171249 11372 148931 115457 99063 152457 98290 173976 192682 163050 34260 10762 1928...

result:

ok correct!

Test #118:

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

input:

199999 3
85151 130580
91456 1
1 126463
75828 52651
1 166438
97319 1
142822 72349
86125 191843
42036 15244
79975 99266
1 43347
1 136116
144573 104329
70554 1
154747 1
36845 1805
44410 1
182186 83316
155755 1
71223 129018
1 127862
1 78098
195817 18601
1 194275
1 85673
12603 92383
14771 191475
112155 1...

output:

199823206822200
199999
1 195208 3511 162316 6480 18699 75849 83020 149503 180843 190803 99569 100428 113231 149342 147354 160138 38558 180526 28028 143705 132712 86365 130870 71576 30130 97749 136762 139783 395 68747 177399 95333 34992 188200 104155 148625 145835 96600 46093 141060 173554 9740 885 1...

result:

ok correct!

Test #119:

score: 0
Accepted
time: 17ms
memory: 15520kb

input:

199997 3
131613 140540
69978 138510
168678 157222
178811 3528
18491 28791
101558 152962
181277 930
134819 58137
2395 48734
147095 1
186977 95913
8298 1
179118 19885
27772 137115
62062 22064
27659 63226
91886 588
2211 1
1 2193
27574 1
96584 59043
46821 111679
6754 156644
140820 130625
114787 1
57183 ...

output:

199821436893275
199997
1 48967 91721 95889 62334 99450 128262 157872 13319 168132 105344 13064 69097 97951 117688 62071 152252 51519 165225 120781 51827 33457 72463 21417 102536 85008 110401 31486 119352 19410 86731 175712 93295 16336 115015 62362 26731 158599 157791 743 47330 61373 110399 106986 17...

result:

ok correct!

Test #120:

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

input:

199809 3
94685 130894
41571 74291
26864 192447
123025 103411
12655 63756
121771 108019
65438 48656
176986 96765
10202 194287
108921 26742
51953 110771
87549 119680
133398 172870
85286 49434
144205 158162
157948 108072
59452 52518
103411 185204
170486 73773
140828 61920
160006 153902
186600 142638
33...

output:

100198293228920
199809
1 51223 58395 30268 124509 179219 107870 153440 117901 128500 47483 35675 128454 68331 26926 185805 81952 18035 174268 54633 109192 64402 157225 23492 111682 136946 131638 154438 180659 132541 90387 124456 187584 199006 112454 2693 180250 46556 7622 87091 94132 174373 56076 21...

result:

ok correct!

Test #121:

score: 0
Accepted
time: 43ms
memory: 25928kb

input:

200000 3
9586 193144
171563 40905
6622 65112
70106 27821
188019 98031
47484 179201
43370 65160
62820 27032
152546 143501
125446 69794
135672 118195
27893 16069
172623 134805
164806 148766
108617 14368
66935 108798
159549 983
14719 163836
173818 163624
24054 100996
151308 144701
130442 142208
142769 ...

output:

200000000000000
200000
1 4538 121952 179585 86793 149077 188525 103155 143762 89783 97753 192471 184882 142397 168109 178895 57407 103744 128769 118927 136732 64237 63338 47463 95403 1323 174747 122411 103074 127920 369 3539 115111 4291 116221 146572 91034 109240 106855 61817 85620 91238 146022 1632...

result:

ok correct!

Test #122:

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

input:

200000 3
5381 142906
195916 107149
28028 86513
140805 179412
120296 155640
88810 138241
67680 36075
18302 103548
197422 113736
107225 185275
96224 191998
71426 84989
148160 128735
7180 115757
72027 78126
132940 2260
68261 167840
11075 11586
136344 159122
71717 66896
3688 131894
188506 19576
177339 4...

output:

99938006915289
200000
1 135207 100188 2376 69269 192438 53259 73911 196612 90763 184158 137009 73659 175682 48472 143147 168822 4314 153557 25845 125391 30013 155556 195837 50388 17170 183880 106065 5101 161919 73021 86928 31820 151047 39175 179397 197234 11207 82017 102918 129199 70341 28843 22908 ...

result:

ok correct!

Test #123:

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

input:

200000 3
81359 23709
47617 60906
88252 102848
98019 112549
30197 80744
65659 97659
158878 19909
94219 11691
86418 94004
59681 135769
143977 151753
77274 138576
30461 150335
85619 146257
168877 47780
141821 36612
36628 12386
3027 198618
98013 74369
156285 199585
5968 75053
144088 37775
44797 3792
133...

output:

100070095386096
200000
1 140046 37006 18430 76517 55602 61689 189414 2587 139855 16166 33532 194737 187102 69706 117307 50107 82523 20655 106818 84913 91836 80279 176508 58979 31721 39276 88058 58331 170165 67816 78019 65699 54946 194265 62094 70605 103147 150970 68424 35519 142998 182223 73490 5736...

result:

ok correct!

Test #124:

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

input:

200000 3
44823 19469
157522 45675
35223 33063
48384 43574
153370 51203
50021 198093
2217 130181
148628 37413
65646 9542
12916 145699
99195 110491
55343 51767
71138 8376
188306 160428
198328 139379
70854 18315
48129 43378
142336 95958
25165 189153
174301 27234
184222 93794
179422 38902
76681 78714
11...

output:

100106249361173
200000
1 66109 49344 156914 68073 194409 72853 115523 2491 23825 29523 177739 29922 126119 92516 109896 30682 35827 22346 34940 135751 170504 168819 174717 135748 76094 143991 52200 54149 109848 19331 188869 182659 161635 195592 191392 76360 91113 29350 77832 34321 112911 16339 17357...

result:

ok correct!

Test #125:

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

input:

200000 3
66925 159827
183145 173667
142615 151805
40331 125850
86779 21981
193285 55703
16332 64097
128674 29528
54281 177585
19905 93782
8189 66728
71597 107045
32330 126864
156780 162970
13291 153811
79967 4617
56093 197260
58256 844
51390 86594
192713 154318
161746 34026
127522 198605
36672 18301...

output:

100002327466724
200000
1 67468 3459 173292 72130 13423 63155 9137 82414 117053 60008 108858 174271 27170 115811 146327 162200 139618 139738 99649 47052 155217 158944 86393 152665 159650 174136 27673 135101 93457 51549 94919 67507 63522 159331 107832 129019 194598 55025 87246 135933 119528 47521 1417...

result:

ok correct!

Test #126:

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

input:

200000 3
50618 142550
5660 103232
108320 43974
83591 71194
150884 191741
143985 51298
153093 87002
46612 90512
140403 27213
68268 191693
192026 183039
4113 198531
149099 49121
21431 59973
76644 153024
66828 94440
178145 174081
162793 31269
101449 54928
110314 93043
58967 49470
136375 71440
174999 11...

output:

99965628723367
200000
1 125263 100389 42591 32012 172278 192976 120632 82474 12228 18411 184606 143567 174052 112474 42455 76959 49213 78058 133477 1844 64686 103985 32804 130756 104013 178309 172611 83422 154223 180012 37069 197591 35644 191542 48341 112383 57257 163081 126179 77451 157401 64646 16...

result:

ok correct!

Test #127:

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

input:

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

output:

99887916695349
200000
1 7 31 127 511 2047 8191 32767 131071 131070 65535 131069 131068 65534 32766 131067 131066 65533 131065 131064 65532 16383 32765 131063 131062 65531 131061 131060 65530 32764 131059 131058 65529 131057 131056 65528 16382 8190 32763 131055 131054 65527 131053 131052 65526 32762 ...

result:

ok correct!

Test #128:

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

input:

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

output:

100298991530485
200000
1 13 121 1093 9841 88573 88572 88571 29524 88570 88569 88568 29523 88567 88566 88565 29522 9840 88564 88563 88562 29521 88561 88560 88559 29520 88558 88557 88556 29519 9839 88555 88554 88553 29518 88552 88551 88550 29517 88549 88548 88547 29516 3280 9838 88546 88545 88544 2951...

result:

ok correct!