QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404727#3508. Sprinklerszzjz12 607ms85128kbC++141.1kb2024-05-04 15:49:012024-05-04 15:49:02

Judging History

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

  • [2024-05-04 15:49:02]
  • 评测
  • 测评结果:12
  • 用时:607ms
  • 内存:85128kb
  • [2024-05-04 15:49:01]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pub emplace_back
#define pob pop_back
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,mod;
ll dt[N][41];
vector<int> to[N];
int fa[N];
void dfs(int x){
	for(int y:to[x]){
		if(y==fa[x]) continue;
		fa[y]=x;
		dfs(y);
	}
}
int main(){
	//freopen("dd.in","r",stdin);
	ios::sync_with_stdio(false);
	cin>>n>>mod;
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		to[x].pub(y);to[y].pub(x);
	}
	for(int i=1;i<=n;i++){
		cin>>dt[i][0];
		for(int j=1;j<=40;j++) dt[i][j]=1;
	}
	dfs(1);
	int qs;cin>>qs;
	while(qs--){
		int tp;cin>>tp;
		if(tp==1){
			int x,d,w;
			cin>>x>>d>>w;
			while(d>=0){
			//	cout<<x<<" "<<d<<endl;
				dt[x][d]=dt[x][d]*w%mod;
				if(d==0) break;
				dt[x][d-1]=dt[x][d-1]*w%mod;
				d--;
				if(x==1){
					while(d>=0){
						dt[x][d]=dt[x][d]*w%mod;
						d--;
					}
					break;
				}
				x=fa[x];
			}
		}else{
			int x;
			cin>>x;
			ll ans=1;
			for(int d=0;d<=40&&x>0;d++){
				ans=ans*dt[x][d]%mod;
				x=fa[x];
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8792kb

input:

1000 548641563
31 369
77 278
249 820
390 623
320 777
479 743
698 791
272 557
802 894
215 852
70 730
444 781
256 861
841 948
12 511
642 777
354 527
388 828
304 407
34 914
102 342
190 880
69 765
281 352
254 255
340 790
61 457
134 229
564 988
151 837
49 959
588 783
80 766
28 806
628 705
14 274
580 725
...

output:

268317771
47097484
421588776
102282451
333095282
43378680
509278870
417494919
313574910
441579995
275157500
408044257
106786594
493318960
33612243
361972926
26121135
532347062
28310592
274208907
196254071
62662155
105003812
156303449
481444165
371156216
75975939
402873126
242366241
363224679
3985588...

result:

wrong answer 178th lines differ - expected: '483271068', found: '540336840'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 9
Accepted
time: 456ms
memory: 79472kb

input:

200000 892371480
22998 49553
81275 113185
5727 132878
82654 169356
71699 140286
125888 186861
100837 142296
106066 140656
74252 149480
27501 176100
83345 88242
66303 115915
12674 130725
1674 63588
1364 156886
15385 17886
75399 75822
86036 186555
1531 179090
89516 172228
115155 176119
44396 128552
14...

output:

273234182
449437106
242099755
333821140
233724926
123405654
394821271
546278602
291329778
653757142
74962316
203008878
296806541
569404826
79844982
145831433
279268910
789682109
554828797
57305870
152411988
447931917
350986222
77173213
654165447
107322515
179403121
296292234
658242000
570287501
9772...

result:

ok 359724 lines

Test #7:

score: 9
Accepted
time: 235ms
memory: 79444kb

input:

200000 892371480
59051 108138
709 18432
3373 4160
81820 138763
14879 82923
123421 149974
39235 56724
138428 142067
26518 139163
83834 155808
28218 175867
157538 176578
127227 168352
57459 73378
20717 92801
41621 131217
96587 119662
16588 56440
98874 166447
169289 179377
91422 198094
33692 196507
179...

output:

166592295
234150952
346022216
77124613
396993404
51930524
87028258
682916517
571418944
749769222
101036056
464653245
845360352
664987832
16751161
512198631
130100685
443938801
525806938
296296172
581330059
314473922
373986734
402769385
672503208
122066525
834490544
748443511
221373021
199161375
7874...

result:

ok 39673 lines

Test #8:

score: 9
Accepted
time: 357ms
memory: 83232kb

input:

200000 299686896
43575 91632
34874 171258
68367 135161
77949 176826
45957 156843
70983 137807
158756 187544
166228 194932
63061 145247
24977 72898
369 135302
88594 172689
1744 4534
26884 91588
8795 12685
7657 128097
141409 194997
41564 193750
51880 186976
113683 179533
88287 107019
26419 60202
51500...

output:

153703089
190057045
7136020
168830450
76879480
87879584
87719325
175158784
54891124
279979227
255510362
53577925
31856903
128267600
255038568
246273049
117408256
226987337
65917427
204281939
33090545
107283491
81352055
81662606
286835567
296857103
50560651
15009143
35067904
68217762
34236867
6665884...

result:

ok 199657 lines

Test #9:

score: 9
Accepted
time: 310ms
memory: 79460kb

input:

200000 838643955
94492 164730
2276 69401
168965 199995
32415 149619
5285 62321
24849 158718
121409 137255
127343 143306
10860 59336
30874 172699
54593 107388
58066 168225
93496 96759
104453 194549
95637 136061
175330 194582
84978 197679
33177 164924
85323 177163
154607 160859
72160 171674
104044 195...

output:

150279949
239544566
772318800
631522163
127335806
333963322
422318031
618695058
250373273
765301422
815124961
735825783
642708164
163793816
61924565
155726680
295497478
222237471
534822095
535965168
325904580
346513704
252783720
38659518
426821837
151230138
796936758
488862744
703201275
19235569
250...

result:

ok 200018 lines

Test #10:

score: 9
Accepted
time: 244ms
memory: 79536kb

input:

200000 97283126
78195 199069
98371 171423
133827 176140
56548 71686
33430 167348
24420 151089
11536 29535
45921 72472
72495 185053
52393 96821
153769 168875
141267 169335
63605 162319
26762 191960
92449 124826
17179 41752
134769 136743
9048 118644
53516 98316
28157 186562
79306 167664
63804 184299
4...

output:

81717490
64959421
94165084
80751499
5532863
65043181
4789120
89461299
90408913
37815589
73068866
21349361
91226766
26915871
9941908
1333155
55225179
85014627
2551676
53058470
28524407
92510940
81250073
75799400
22518341
80563542
69887489
21444944
49346167
32034550
32481227
34562669
50497378
26869833...

result:

ok 199658 lines

Test #11:

score: 9
Accepted
time: 258ms
memory: 79744kb

input:

200000 957083944
72167 164334
61424 79796
2366 129990
13044 45656
83062 147164
88207 161766
40685 73564
124918 146264
131555 138584
49209 134190
29818 55412
18951 114823
58121 159486
92105 92215
1249 160390
44097 113265
78751 134928
155205 164875
55051 154353
73409 150521
15227 74285
122002 172296
1...

output:

605094958
606526750
195579649
691174516
216138578
469992305
870832146
597427306
759452219
10446966
320553455
823784587
399699096
101905742
671398460
865184715
928982320
404977938
169518408
365494071
763819226
768915251
162048421
399829055
750586986
26297583
181412268
427023299
291501222
178094537
59...

result:

ok 200005 lines

Test #12:

score: 9
Accepted
time: 202ms
memory: 79820kb

input:

200000 620494303
110107 194555
186984 194555
140306 194555
64033 194555
98077 194555
173973 194555
74413 194555
167697 194555
194555 195790
105875 194555
145519 194555
168901 194555
145944 194555
168864 194555
194555 198185
76155 194555
64103 194555
154730 194555
145591 194555
23218 194555
70146 194...

output:

387208036
269749605
143825776
386221309
166148501
571207988
86520130
146623168
191313259
224947001
302185025
362343829
53680445
134285655
602000909
381478180
405387372
366107234
124504123
96242506
63394255
345466691
363682198
180785126
75522637
231612992
407331498
6758635
568245455
148930353
5144059...

result:

ok 199709 lines

Test #13:

score: 9
Accepted
time: 559ms
memory: 85128kb

input:

200000 210207444
40880 113562
63189 84942
44038 94475
17523 128534
971 4860
77855 118375
1874 195741
78504 105215
49547 57282
51622 120638
70123 122046
84655 168187
20248 158711
86016 161594
3249 87623
174046 185318
92703 150374
104055 148044
10040 168532
28256 84058
29262 199444
95661 110258
89502 ...

output:

66427112
49813607
65709506
95309216
48820824
157726838
65958214
199470364
125375142
71979313
655184
132264066
117706996
49221763
138345349
53361591
99450429
79852964
37046148
40284510
20359264
46796096
143956793
73782122
190442723
175127269
144757745
80292991
166449041
7571847
169064624
191309356
13...

result:

ok 359988 lines

Test #14:

score: 9
Accepted
time: 269ms
memory: 84596kb

input:

200000 277396202
134706 182577
88090 174965
17284 118366
19675 26563
53972 76358
98188 106350
89114 134859
56578 153366
27467 76764
75829 143042
111314 187242
89185 132517
78909 103096
104370 141106
113171 155958
90860 92666
130798 187617
179916 182473
34709 155321
186193 199194
20994 140011
35791 1...

output:

61971359
211732659
94197822
101967010
49532755
258380297
151367208
39145182
36037104
118590068
56170690
115922074
211204890
254479280
1184872
107466510
143174573
237645059
142663782
1584735
214544052
191408538
48863042
18232642
258857202
80710580
219275054
122524527
31442236
276858087
65401641
20777...

result:

ok 40090 lines

Test #15:

score: 0
Wrong Answer
time: 404ms
memory: 79400kb

input:

200000 663859441
97099 132215
66284 76389
527 42627
21777 82415
55986 69105
33126 164763
82045 151137
38333 45983
19013 85129
28545 127260
100764 123787
99699 128444
4688 177262
130166 162319
133691 166019
43881 122390
92948 129723
52215 133069
24938 169712
82254 171002
139552 167491
56603 113815
10...

output:

429150847
324200889
636632593
646525880
494717234
351534682
392148941
301540911
264814346
86975357
592339700
379872161
46360788
67412424
628105156
613787311
6007585
212673835
31260951
235860987
458313526
19109503
600385154
607884448
6830430
543603370
298230208
643763133
186555189
484008078
216262484...

result:

wrong answer 256332nd lines differ - expected: '440049453', found: '227756728'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 12
Accepted

Test #43:

score: 12
Accepted
time: 574ms
memory: 84928kb

input:

200000 892371480
85218 172641
32760 178929
67472 90740
137725 140228
7283 158683
38909 179144
136916 199945
183437 185978
39771 151379
27581 52887
45716 131957
94463 189969
108714 189877
42691 162639
70675 137777
2216 64496
11562 156673
60130 75992
23866 79156
52433 110066
69048 131110
155123 164884...

output:

782082073
824401298
599790916
294215187
203019461
236590667
661026646
147203543
602124019
438408587
537428705
8355752
124805730
541572457
511706673
449606645
118068138
91082179
417223715
31471407
815086590
322359719
669024622
189907169
517409848
114211575
497857100
605205022
21390597
260171160
53244...

result:

ok 360337 lines

Test #44:

score: 12
Accepted
time: 564ms
memory: 83528kb

input:

200000 892371480
38926 59792
1046 100481
70909 193250
14941 102234
151917 163694
143498 152451
58679 110145
19676 152650
11890 89518
98248 167023
153201 166560
14146 21902
92856 163644
88635 190236
58360 105381
28619 196565
64433 83386
35490 194841
86075 163020
64133 79679
3891 180981
40734 154706
6...

output:

287217258
104698622
113402660
143630662
842548369
291495782
100942131
522065313
638437129
836867071
220409917
44532456
757753501
24635505
202985156
873094642
298895685
519161292
858608463
577411258
144913537
226730132
836380146
728814804
868242366
49413373
873978578
472667815
675907568
686422276
651...

result:

ok 39880 lines

Test #45:

score: 12
Accepted
time: 506ms
memory: 83936kb

input:

200000 188196148
44004 110744
119075 131142
134955 186670
105184 130580
46090 72442
24857 61737
32412 153566
74004 112881
105444 197511
32005 77219
21749 122596
44943 92576
126350 184879
136289 164176
12299 189721
142057 150079
14682 126186
123862 153693
95297 153796
72798 174864
58382 63250
109556 ...

output:

164872790
111989360
102694654
110150546
148486948
178618977
66065978
67785495
95726526
169069885
56984507
25766510
136143708
146281678
171273218
78687225
177625703
56232282
124610224
115950876
126922484
127260341
46920091
152957176
136838518
28510256
51511177
139490439
139289786
32664672
137105092
1...

result:

ok 199927 lines

Test #46:

score: 12
Accepted
time: 319ms
memory: 79416kb

input:

200000 662065623
17012 186375
139107 187333
68029 177819
133038 182865
69220 94226
85929 97563
25806 183239
77239 126964
120144 150744
163591 174290
30121 119752
70785 116391
36667 72605
21588 69327
27727 97808
56892 158308
55419 132454
156271 163206
66589 87326
143720 166544
59920 189035
12160 1547...

output:

538838581
512398805
185741050
164585109
504661638
489570645
419302729
307518175
609666199
204592784
554224034
513258796
178031705
324511211
386685367
130064805
474125756
338845791
225273704
559655261
405680043
241383209
594661419
503899839
398592253
550764196
54178278
511548000
407200254
0
357047627...

result:

ok 199713 lines

Test #47:

score: 12
Accepted
time: 320ms
memory: 79556kb

input:

200000 599373789
15489 149962
24589 44816
39961 94700
2039 166654
1503 151097
75648 96512
21587 62693
152927 176032
35258 48377
95624 104547
33042 169752
28123 191864
181481 187375
52619 106366
79914 152324
1039 129301
79648 186396
20377 70333
4210 28193
20298 73791
101902 183222
55750 135327
23048 ...

output:

461383686
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200148 lines

Test #48:

score: 12
Accepted
time: 243ms
memory: 79740kb

input:

200000 467128531
168232 183473
97463 116522
101718 187682
45691 114426
115216 117582
84909 147753
101157 175713
5373 184169
5860 157902
31096 109776
49417 157953
43601 72738
65424 159849
5114 93705
32437 121075
68813 118038
88415 172566
83656 111488
31930 197923
93191 114772
167234 192929
78693 1286...

output:

424135263
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200245 lines

Test #49:

score: 12
Accepted
time: 185ms
memory: 79596kb

input:

200000 529800161
66087 182777
124207 182777
56358 182777
115852 182777
182777 191395
162549 182777
147518 182777
142767 182777
77710 182777
96058 182777
182777 191802
112914 182777
163269 182777
165546 182777
138220 182777
182777 194801
57665 182777
175404 182777
142637 182777
96157 182777
7137 1827...

output:

5719329
522400395
167189938
396160789
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200063 lines

Test #50:

score: 12
Accepted
time: 605ms
memory: 83384kb

input:

200000 736323910
49905 62680
7934 32290
2141 130197
22856 170332
76508 111296
26289 102348
14563 145328
20292 53098
15928 73685
148229 191517
6699 9048
77901 139333
51541 53354
46543 87713
51810 199186
41562 45672
60676 141582
57381 60912
94965 155682
115405 128452
125251 178391
128128 198094
16627 ...

output:

195639953
655721075
79249833
203118083
432653802
371935512
48578995
342243160
693203348
357252565
655705094
269562011
670452690
389923972
696227489
705852937
54194206
622696017
320788156
258618323
602897546
314495903
192492129
129537524
208148062
567331443
440609760
599911890
715181674
231315157
229...

result:

ok 360023 lines

Test #51:

score: 12
Accepted
time: 607ms
memory: 84604kb

input:

200000 47086694
69405 91827
18957 120164
111718 190701
28458 162242
49740 98892
1194 178638
136262 168799
53467 145891
68032 85652
66050 178448
113129 151231
76614 179271
152980 185590
117193 169993
72112 142742
157343 160858
8985 76913
135901 147233
106073 121863
6274 160108
80117 186437
30085 1124...

output:

34115011
25037864
41352354
16496587
43275093
625657
46420229
1865668
41667114
8073380
31071913
18710358
11850637
43423456
6135185
36327275
8414705
40070623
14065861
23991422
21990139
13425393
34717444
9602871
43697485
19790828
35382090
38871029
45080760
35927647
7228042
31514476
27392108
46106270
17...

result:

ok 39897 lines

Test #52:

score: 12
Accepted
time: 473ms
memory: 79404kb

input:

200000 895994585
544 65800
126040 127143
24538 116187
47644 140785
13294 18675
119729 171800
15816 50532
51720 143679
3840 10086
29754 53235
1705 99992
125437 198819
88763 192949
104995 111132
49154 88053
30274 184287
26991 113727
77070 139263
37309 84766
172484 182541
119894 192699
11531 55721
8504...

output:

531999518
353806527
531539889
551453863
371312988
657410738
272612410
131381986
139757297
56547447
348406350
666509610
92484443
448146333
98477621
477061557
751488976
175334857
209386945
374229164
404327665
212673821
202592742
624609222
329225155
87791957
81654882
354465041
278420595
891125007
30499...

result:

ok 359857 lines

Test #53:

score: 12
Accepted
time: 386ms
memory: 79408kb

input:

200000 766680139
13465 24354
57831 194424
96485 147612
19430 184641
134158 177962
149 192203
102763 111787
50272 169399
113551 132635
42566 89560
49016 82230
15232 15289
125065 145096
52778 70487
72336 102362
93034 126939
179901 187557
53411 141345
64821 197875
25527 123290
11459 18861
2869 168073
6...

output:

730613066
574099774
508066563
499742342
516031888
752153997
182766822
0
14229226
235852318
646740274
381168674
0
422327736
0
715073441
0
1105445
0
613326747
714395260
0
322067660
99379522
683739107
0
0
0
0
0
0
760706891
571514535
0
0
0
564848491
170251398
0
0
0
419424054
0
0
0
0
0
707615716
0
904757...

result:

ok 39841 lines

Test #54:

score: 12
Accepted
time: 233ms
memory: 80372kb

input:

200000 188196148
35355 167903
133463 136446
87018 121364
105657 138542
14877 191556
139515 192775
124965 126074
57373 63552
75995 163407
52349 62648
156048 157678
28062 119443
68765 167924
42246 199820
16247 38579
93397 100112
14337 125121
778 184216
102091 134796
44962 158688
164503 195382
145184 1...

output:

20265682
131270479
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 20026 lines

Test #55:

score: 12
Accepted
time: 256ms
memory: 80800kb

input:

200000 662065623
22431 134843
56539 143967
27871 30764
89263 124261
61091 158555
72924 150203
57820 97240
51354 145448
95864 112405
131148 139652
115952 165297
68479 174861
4280 148396
28847 138840
10384 129785
52993 183911
22868 56764
45135 87156
15006 106750
1664 167597
30144 91699
29870 127696
40...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 19785 lines

Test #56:

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

input:

2 235833654
1 2
163301191
228563240
1000
2 1
1 2 0 0
2 1
1 1 1 0
1 2 2 0
2 2
1 2 0 0
2 1
1 2 1 0
1 2 1 0
2 1
2 2
1 2 0 0
2 2
1 1 2 0
1 2 1 0
1 1 1 0
2 2
1 1 2 0
2 2
2 1
2 1
1 1 1 0
1 2 1 0
2 2
1 1 1 0
2 2
1 2 1 0
1 1 2 0
2 1
2 2
1 2 2 0
2 1
2 2
1 1 0 0
2 2
1 1 2 0
1 1 0 0
1 2 0 0
1 2 0 0
2 1
1 1 2 0...

output:

163301191
163301191
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 501 lines

Test #57:

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

input:

5 710493752
3 4
1 4
2 3
1 5
23397106
478077388
381508110
698911874
254936774
1000
2 4
2 1
2 1
1 4 1 0
1 2 1 0
1 1 2 0
2 1
1 5 1 0
1 4 0 0
2 1
2 2
1 4 1 0
1 3 1 0
1 1 1 0
2 1
2 4
1 3 0 0
1 5 2 0
2 1
1 2 0 0
2 1
1 5 0 0
1 3 0 0
1 5 0 0
1 5 1 0
2 1
2 5
2 1
1 5 1 0
1 5 0 0
1 1 0 0
1 4 2 0
2 2
1 4 0 0
1 ...

output:

698911874
23397106
23397106
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 497 lines

Test #58:

score: 12
Accepted
time: 3ms
memory: 8768kb

input:

8 915391419
4 6
4 5
7 8
2 3
3 5
1 8
2 7
901265339
437873454
274762177
906096966
792616192
250219799
832794769
452046866
1000
2 2
1 5 0 0
2 3
2 8
1 5 0 0
2 3
2 3
2 8
2 2
2 1
2 3
1 8 1 0
2 3
2 5
2 2
1 8 2 0
1 4 2 0
2 6
2 8
1 4 1 0
2 3
2 5
1 6 2 0
1 8 2 0
1 7 1 0
2 1
2 2
2 5
2 3
2 8
1 7 0 0
1 2 0 0
2 2...

output:

437873454
274762177
452046866
274762177
274762177
452046866
437873454
901265339
274762177
274762177
0
437873454
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 505 lines

Test #59:

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

input:

11 911171690
2 3
1 8
5 11
1 6
3 5
9 10
7 10
6 11
4 7
2 4
578796711
389137122
258900984
785708872
430771144
326384633
707167833
22682772
477784148
194579330
361976038
1000
1 2 2 0
1 6 1 0
1 7 1 0
1 8 1 0
1 10 0 0
1 7 1 0
1 1 0 0
1 7 2 0
2 4
1 4 1 0
2 7
1 3 1 0
2 3
2 10
1 5 1 0
1 11 0 0
1 7 0 0
1 7 1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 486 lines

Test #60:

score: 12
Accepted
time: 3ms
memory: 10360kb

input:

14 33032541
3 10
1 11
5 10
6 8
9 11
13 14
4 7
7 12
9 12
1 2
4 8
5 13
3 6
17430914
23228004
2444846
15384251
12882858
11556791
27850692
10245673
7033594
23589281
24499742
24952860
1181203
6486916
1000
1 6 0 0
2 3
2 4
1 3 0 0
1 6 0 0
1 11 1 0
2 7
1 8 2 0
2 11
2 8
1 11 0 0
2 14
1 8 0 0
1 3 0 0
1 6 2 0
...

output:

2444846
15384251
27850692
0
0
6486916
0
0
12882858
0
0
0
0
0
23228004
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 476 lines

Subtask #5:

score: 0
Wrong Answer

Test #61:

score: 0
Wrong Answer
time: 567ms
memory: 83048kb

input:

200000 892371480
53225 130450
30850 181698
17803 177493
8780 107369
5103 129868
105068 193082
45556 96552
107511 188440
77104 166564
15995 132714
99128 181477
22868 55561
12946 104306
108248 191490
32697 180631
143427 188480
47296 68977
54677 109873
112693 132105
71875 137093
82514 158424
20701 2978...

output:

5118074
498125396
251749089
21578201
169648223
89138431
486735724
430589511
60128044
296727358
96494797
683654223
25434588
641217539
292066134
753877167
349591450
696055657
528160411
318336519
357452444
83471033
302900015
623037539
678896657
732784430
849466722
310755541
488624956
497664716
77194996...

result:

wrong answer 51715th lines differ - expected: '311487684', found: '622975368'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%