QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359260#3508. SprinklerRikku_eq100 ✓703ms91512kbC++141.6kb2024-03-20 15:27:122024-03-20 15:27:12

Judging History

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

  • [2024-03-20 15:27:12]
  • 评测
  • 测评结果:100
  • 用时:703ms
  • 内存:91512kb
  • [2024-03-20 15:27:12]
  • 提交

answer

#include <bits/stdc++.h>
#define N 200005
#define mxD 43
using namespace std;
typedef long long ll;

int n, mod, Q, d[N], p[N];
vector <int> to[N];
ll f[N][mxD], val[N];

void dfs (int u, int fa)
{
    p[u]=fa; d[u]=d[fa]+1;
    for (int i=0; i<(int)to[u].size(); i++) {
        int v=to[u][i];
        if (v==fa) { continue; }
        dfs(v, u);
    }
}
inline void mul (ll &a, ll b) { a=a*b%mod; }

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d %d", &n, &mod);
    for (int i=1; i<n; i++) {
        int u, v; scanf("%d %d", &u, &v);
        to[u].push_back(v); to[v].push_back(u);
    }
    dfs(1, 0);
    for (int i=1; i<=n; i++) { scanf("%lld", &val[i]); }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=40; j++) { f[i][j]=1; }
    }
    
    scanf("%d", &Q);
    for (int t=1; t<=Q; t++) {
        int op; scanf("%d", &op);
        if (op==1) {
            int u, dst, num; scanf("%d %d %d", &u, &dst, &num);
            int v=u;
            while (v && d[u]-d[v]<=dst) {
                mul(f[v][dst-(d[u]-d[v])], num);
                if (d[u]-d[v]<dst) mul(f[v][dst-(d[u]-d[v])-1], num);
                if (v==1) {
                    for (int i=0; i<dst-(d[u]-d[v])-1; i++) { mul(f[v][i], num); }
                }
                v=p[v];
            }
        }
        else {
            int u; scanf("%d", &u);
            int v=u; ll ans=val[u];
            while (v && d[u]-d[v]<=40) { mul(ans, f[v][d[u]-d[v]]); v=p[v]; }
            printf("%lld\n", ans);
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 2ms
memory: 9024kb

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:

ok 499 lines

Test #2:

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

input:

1000 810247152
806 836
53 453
111 311
110 195
559 603
525 873
242 737
802 816
126 650
52 62
133 866
120 232
677 906
37 211
471 748
295 885
470 689
335 645
335 478
563 695
392 666
270 612
288 445
639 815
474 849
190 704
554 605
84 905
26 319
52 977
197 939
83 313
20 538
281 476
586 827
327 732
206 28...

output:

112207026
689567736
632864549
171111072
756893592
244213618
555106900
62474701
34797048
632864549
331617936
445150992
693957264
554154744
773524752
17022720
37128234
72114900
7207668
71227728
115706448
785372016
416509444
487115484
752796096
133223376
119615496
7959536
205493184
218787504
404543568
...

result:

ok 516 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 8976kb

input:

1000 138698102
604 926
291 548
224 834
622 714
123 601
611 806
426 685
631 977
641 675
291 908
55 321
354 372
486 496
122 623
482 677
686 800
495 878
879 910
132 937
92 421
265 893
645 709
337 820
544 601
301 990
760 885
205 822
3 526
271 380
249 486
182 860
627 688
75 851
330 477
553 884
682 705
15...

output:

122571360
53145402
34591852
18266540
14632244
132417536
110525724
20355174
31803672
29430008
63366360
102283270
128553818
66915524
108042252
47617032
138273042
2411956
127795774
20264124
70592470
87016810
86696398
106138880
82063936
90784450
136171920
32844014
26164514
118671866
69482714
32800798
50...

result:

ok 489 lines

Test #4:

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

input:

1000 737395595
123 334
480 948
195 453
100 785
135 746
7 661
249 656
558 943
28 416
473 689
410 571
267 406
804 846
412 552
57 408
189 551
515 612
171 693
384 442
148 414
90 582
763 982
658 885
189 386
685 718
113 241
338 427
68 985
132 439
434 607
357 630
480 970
422 848
359 566
166 795
28 537
307 ...

output:

118682550
359728954
129482937
568786024
663997251
591015686
499561978
729365182
130000300
82697729
685309025
642910500
707637535
48808450
1747605
69095480
162071375
277950890
274507195
416781000
539990415
597956555
539313225
584355020
61154155
14919175
22479900
722248275
301813895
705490725
71358296...

result:

ok 480 lines

Test #5:

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

input:

1000 578005157
217 1000
958 1000
670 1000
431 1000
367 1000
695 1000
132 1000
408 1000
371 1000
591 1000
834 1000
92 1000
144 1000
5 1000
727 1000
772 1000
341 1000
995 1000
71 1000
141 1000
181 1000
519 1000
658 1000
906 1000
346 1000
626 1000
698 1000
16 1000
459 1000
961 1000
250 1000
782 1000
49...

output:

117183265
326422151
132504576
440174510
321319607
316889895
570830637
387617530
493553546
234089435
563923155
215738389
53326988
247783806
162894849
575863483
397195841
24592383
449977137
52935495
355408491
240958258
308896141
397356372
181332276
156963155
234091838
289197400
119490106
85881586
2843...

result:

ok 513 lines

Subtask #2:

score: 9
Accepted

Test #6:

score: 9
Accepted
time: 406ms
memory: 85236kb

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: 0
Accepted
time: 249ms
memory: 85264kb

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: 0
Accepted
time: 384ms
memory: 89412kb

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: 0
Accepted
time: 302ms
memory: 85192kb

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: 0
Accepted
time: 226ms
memory: 85340kb

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: 0
Accepted
time: 237ms
memory: 85352kb

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: 0
Accepted
time: 185ms
memory: 85160kb

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: 0
Accepted
time: 512ms
memory: 91512kb

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: 0
Accepted
time: 260ms
memory: 91016kb

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
Accepted
time: 408ms
memory: 85148kb

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:

ok 360163 lines

Test #16:

score: 0
Accepted
time: 241ms
memory: 85196kb

input:

200000 474791189
20030 76483
72905 104045
78831 163796
104384 174115
141704 146477
63086 133326
69607 89867
127531 178706
138528 138940
37518 184850
158596 190130
13616 56674
44133 194074
12887 97910
66495 186126
92687 188518
121091 127667
68215 107738
31115 104057
94396 150432
25951 163620
85439 16...

output:

123502650
199850667
431654344
2331830
448569687
72304654
241019414
355806270
104155562
318300669
87865155
73140503
431136683
283692007
416130897
103912639
173452438
124679084
472638484
257412346
2993444
147732346
246489573
466811222
378786305
226118253
5737116
212550115
257225072
446402329
192959508...

result:

ok 39919 lines

Test #17:

score: 0
Accepted
time: 153ms
memory: 85288kb

input:

200000 299686896
70964 100366
70964 164697
108536 149205
51293 70964
70964 198326
70964 147834
70964 151506
70964 130323
56203 70964
70964 158775
51567 70964
70964 112848
70964 97207
70964 137813
70964 141114
13429 124704
70964 154718
22128 77415
70964 186659
63412 70964
70964 78723
70964 110481
461...

output:

63419544
83623968
290413872
165811104
290983392
64688400
231874992
285278832
244788336
138240288
202860528
537552
247535424
28865376
172884240
94932000
45292032
43177824
272103840
242262144
162296496
281719008
19005696
243921017
88729056
5316768
111956688
84129696
51425136
21633984
276851862
1237740...

result:

ok 39930 lines

Test #18:

score: 0
Accepted
time: 151ms
memory: 85196kb

input:

200000 838643955
61269 119598
119598 142230
109276 119598
77002 119598
15927 107003
13771 126383
67458 126383
82219 126383
12247 15927
44243 119598
41257 126383
56452 126383
117425 126383
42091 126383
15927 192214
119598 148941
126383 148854
85189 171341
120593 126383
15927 142279
16973 119598
11152...

output:

97488315
415703430
468411135
332575196
754107345
14564535
645610395
798915300
301266405
522940860
6137550
461231790
301742475
468076260
300066645
332817090
104856195
621382824
306257380
1630395
42655350
462414750
389409135
345077460
229228325
611868735
276495975
538396935
327049950
409167222
7586678...

result:

ok 39762 lines

Test #19:

score: 0
Accepted
time: 153ms
memory: 85560kb

input:

200000 97283126
123408 168722
43195 58685
27180 33153
161002 184777
33153 45684
12445 185488
18380 66270
53802 134901
18380 112044
88244 168722
23969 24127
133015 177770
48859 185488
86284 88958
45522 128944
130391 147813
12863 58685
25100 53802
19827 23969
33153 130830
60954 128944
58685 84931
4975...

output:

56460514
19940512
2154890
92617092
32872222
51203112
42861794
48124982
52707920
15182838
75577068
19132464
72500924
5847226
40039772
45055290
8798475
81162006
81463833
92595866
54305258
66645846
63781088
60697654
33686346
6544562
8186428
4059932
66596814
14920228
89602870
18872082
78756146
44082410
...

result:

ok 40048 lines

Test #20:

score: 0
Accepted
time: 158ms
memory: 85784kb

input:

200000 957083944
35107 54512
59955 178657
83844 173420
89728 108858
107902 147723
22000 74350
97213 158624
143572 174444
72820 143572
107240 149591
60787 104709
15946 93241
83844 136779
51953 83844
83844 133211
45413 157075
82664 145373
150449 157072
35416 131421
35023 173073
63458 143572
105176 107...

output:

405258568
422627830
925539096
631414816
300746546
7941471
88073541
459660759
438630481
540573125
653803958
872160250
833565851
694460048
341171568
714961088
443647280
530781048
865128076
845353975
34589914
52907216
150065552
361271304
108266626
496972096
655547992
17460680
68762816
8458688
601957320...

result:

ok 39784 lines

Test #21:

score: 0
Accepted
time: 150ms
memory: 86072kb

input:

200000 620494303
42440 46628
105812 149570
108878 144601
169256 192366
56494 163953
45712 135966
54726 128235
49786 80037
46664 62820
101 96642
96417 142795
20680 29967
46628 138477
5855 125271
46230 53640
30279 54726
90511 180479
40516 81369
12774 127421
62820 160270
89644 135444
90424 173622
6420 ...

output:

360369471
226310795
485172591
177390139
57640881
466611540
243047932
152044768
56572207
366751977
576015824
373601338
217255642
170649420
288215686
551596317
574681263
153273
267652189
203573279
89558601
503443760
594420174
227143465
260634127
407964700
339861753
616837769
413856521
447434375
191312...

result:

ok 40149 lines

Test #22:

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

input:

2 820765898
1 2
107025336
215163294
1000
1 1 1 193096547
2 1
1 2 0 41852054
2 2
2 1
1 1 1 698818553
1 2 0 475139569
1 2 0 133557035
2 2
1 1 1 293954373
1 1 0 404029058
2 2
2 1
1 2 1 430222549
1 2 1 607030741
2 1
2 1
1 2 1 132640928
2 2
2 2
1 1 1 459810447
1 1 1 389362544
2 2
2 1
1 1 0 82625075
2 2
2...

output:

690320376
62869268
690320376
491381826
666758786
365602488
366310706
366310706
259492106
259492106
524101358
399495912
524101358
524101358
349854316
349854316
524101358
269508146
12742700
664489082
664489082
299846742
290238428
290238428
514362112
711807816
514362112
267093888
613273016
543228380
29...

result:

ok 492 lines

Test #23:

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

input:

5 686629684
1 5
2 3
1 3
4 5
511695984
555955461
265146213
75408357
210424340
1000
2 4
1 2 1 653398187
1 4 1 296623062
2 2
1 5 0 122518318
2 3
1 3 0 167933015
2 5
2 2
2 2
2 1
1 2 1 568012604
2 2
1 5 1 371956331
2 1
1 5 0 217982529
2 3
1 5 0 327595875
1 5 1 413231433
2 3
1 3 1 142316118
1 1 1 23245143...

output:

75408357
561632435
49765235
245620284
561632435
561632435
511695984
566731152
565167008
161221788
161221788
427565628
667953734
385727732
212591600
667953734
427565628
667953734
37734516
586373112
586373112
37734516
527023796
670916114
679580644
679580644
292022432
679580644
482693276
164972344
3043...

result:

ok 501 lines

Test #24:

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

input:

8 478269876
4 5
1 7
7 8
2 4
1 5
3 6
6 8
227392056
462547254
161908751
327683549
152259033
152555035
52187173
440610453
1000
1 7 0 256374461
1 1 1 113126554
2 3
1 5 1 470048828
1 7 0 394318553
2 5
1 8 0 106880176
2 8
1 4 1 184559304
2 7
2 2
2 4
1 2 0 437650135
1 5 1 32943844
2 3
1 7 0 209655691
2 3
2...

output:

161908751
357429432
342826524
245467894
426942732
238472988
161908751
161908751
152555035
375999090
375999090
112198020
112198020
288768732
208215960
199847364
83217820
357338160
357338160
33508356
249668160
11666268
357338160
15730296
357338160
417494112
240655944
315815832
240655944
137955288
3253...

result:

ok 492 lines

Test #25:

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

input:

11 362333726
1 10
8 11
8 10
3 9
3 5
2 9
7 11
4 6
5 7
2 4
232803083
91914477
212812736
115134220
217225700
54761676
251326707
181588813
41304573
268105683
261272685
1000
1 9 0 92348249
1 11 1 192765305
2 10
1 5 1 213687147
1 2 1 143462234
2 1
2 3
2 8
1 6 0 92112490
1 7 0 27928580
1 9 1 109042976
1 8 ...

output:

268105683
232803083
281101118
102131681
293752076
248526918
181721648
248526918
232803083
232803083
253206160
253206160
293525074
293525074
44645908
139479436
232803083
220347433
293525074
293525074
320138350
119050512
293525074
220347433
172831814
75878050
201854920
232803083
138044899
337308264
10...

result:

ok 542 lines

Test #26:

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

input:

14 764371137
3 8
1 9
3 5
11 12
12 13
7 9
1 11
2 4
4 10
2 14
6 7
8 10
6 14
389971024
383408316
522977682
252668893
7371363
165814760
11665346
468610654
204761981
362148770
406895090
662239452
175391465
696207378
1000
1 5 0 312602793
1 12 1 353306302
1 8 0 171589250
1 10 0 25448449
2 11
2 4
2 12
2 9
2...

output:

150419189
252668893
452599077
204761981
11665346
11665346
452599077
712842524
452599077
389971024
452599077
483416448
434082862
452599077
598237920
290690738
99574071
290690738
99574071
165814760
137362494
136739298
136739298
345064946
733875299
573805399
99574071
136739298
99574071
99574071
2713443...

result:

ok 512 lines

Subtask #3:

score: 29
Accepted

Dependency #2:

100%
Accepted

Test #27:

score: 29
Accepted
time: 399ms
memory: 85176kb

input:

200000 892371480
45417 110315
147359 189239
117291 180132
159630 183102
130024 189557
164855 167226
98133 157668
15053 137747
124400 181297
82219 146820
81096 113913
38664 125127
84558 173661
30562 52135
29787 76935
102436 188510
216 178861
53850 72084
58431 159839
845 47821
14410 169053
76651 15936...

output:

594284535
640239614
1464336
823224962
76651484
110879393
321529319
884603103
675372255
538518027
211857220
46971085
235439278
770194485
145826241
152434523
853775968
191686118
199123923
63352290
156639563
879240989
645130444
628337043
377902707
245900492
440107830
293610586
872950481
254331916
55399...

result:

ok 360029 lines

Test #28:

score: 0
Accepted
time: 272ms
memory: 85192kb

input:

200000 892371480
93832 154017
62437 186860
22156 88304
90665 126608
101866 194562
57254 145075
116781 162572
29477 156514
31537 89020
68429 121070
12116 80492
189844 198940
23635 142152
19049 111911
40589 147564
37556 42144
3000 95453
14424 59939
132142 172241
100344 130209
24097 39498
93242 130013
...

output:

885162606
267164248
342466731
655626099
135720761
778734912
275108279
510053977
63946474
891950741
708995024
470255169
305386347
560048820
374914433
393191349
147166271
851736999
515091198
399838418
888365757
521276202
763585836
413484820
570204461
610173912
759517342
734240232
627629167
60840288
17...

result:

ok 40135 lines

Test #29:

score: 0
Accepted
time: 385ms
memory: 91260kb

input:

200000 601047767
96401 125712
28453 108185
154921 172064
96583 131868
12499 44727
38028 120351
66743 156355
76228 112282
106994 175356
27558 176464
52648 186827
51455 173443
20175 135082
45812 59149
130531 139657
47282 115819
8228 8730
112093 132500
14450 64513
81383 150099
117654 128086
4285 176347...

output:

309315125
382372001
387846393
371731828
490941482
15082287
22418430
380337127
116634192
497573765
529941738
222177650
463802508
166516757
52731099
233205845
572967829
567974254
571234490
63237461
586341943
534834480
73133823
317733072
62925169
142087941
17027946
124701079
37034363
274045171
46655413...

result:

ok 199914 lines

Test #30:

score: 0
Accepted
time: 297ms
memory: 85080kb

input:

200000 453591910
21881 166170
65906 172039
35762 66748
168774 175609
106079 174033
133891 176503
33232 196551
186338 189227
52475 93705
85468 168691
53404 179232
125746 184674
25604 65331
95720 169465
91069 135449
18054 84274
69617 189331
85256 138335
59673 68017
98474 165982
28029 51652
47836 90601...

output:

428191326
68316955
136343022
25013884
76997372
318941688
30297201
364618072
420915541
304121045
424132343
217529143
289587538
280339715
350398925
50881484
129448994
372613444
126576895
330509380
158051872
28668772
66586042
165010395
290604410
208210313
107400245
178163204
370345748
162437972
1455414...

result:

ok 200311 lines

Test #31:

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

input:

200000 524592679
30163 50467
114682 196059
119857 173807
6269 20876
96660 184889
108900 180986
108402 124204
61996 104208
139446 187920
193455 194333
9415 191818
19891 124443
20794 107343
129313 177378
11383 138145
103236 141276
6931 184386
19721 72413
2740 20676
39723 87521
37006 153079
59464 14882...

output:

183417370
400549761
483554887
266111539
140104556
342524240
128284100
420226326
183277775
393617752
512554737
385701143
90685524
245496848
79752914
498750470
336951025
175741769
319479324
361162718
506340894
23428882
239631335
98669193
121443435
187854754
285671296
90438315
314977022
110538959
37694...

result:

ok 199813 lines

Test #32:

score: 0
Accepted
time: 234ms
memory: 85504kb

input:

200000 118435465
63873 73617
49140 79113
6462 37484
134064 160041
103681 104663
139084 184802
54180 158946
13129 66282
4142 182001
7298 196150
162189 187190
86789 118461
95140 182778
3227 29733
35671 132824
28799 39836
95178 121055
38885 100144
5222 29097
83777 150749
84499 111723
93750 134774
92751...

output:

97699939
71469978
21235837
18892198
1208219
89515425
18792274
97258345
72256415
36862514
54142869
40686443
118191097
89916258
59303019
43853925
60716260
71901304
114531656
16641661
66902971
116152633
48557779
69832530
4973483
86159886
50954221
4097167
50015036
11819838
3502942
10131264
16732741
3527...

result:

ok 200236 lines

Test #33:

score: 0
Accepted
time: 182ms
memory: 85176kb

input:

200000 794555724
143556 184414
8162 184414
86805 184414
125195 184414
124312 184414
180180 184414
94907 184414
4753 184414
184414 196582
96480 184414
21058 184414
121398 184414
36665 184414
183161 184414
151057 184414
15898 184414
18538 184414
184414 193451
161108 184414
119896 184414
2870 184414
14...

output:

321237771
36833892
191046079
691451056
92203152
588838160
358124996
521292300
106333816
143007996
747011120
307263844
221604632
316481992
189941604
225372804
400919432
91304720
623087212
711865776
591106068
662093676
274370004
149944320
371950344
632925048
367563528
383484744
88953516
286166472
7467...

result:

ok 199679 lines

Test #34:

score: 0
Accepted
time: 528ms
memory: 89588kb

input:

200000 932732894
76264 133556
30468 74583
133739 160450
156339 168900
116120 144114
71102 103424
175944 196732
39449 199731
15647 107694
141019 148408
160992 182531
111372 136704
92188 136154
10072 186242
18467 89148
108338 110225
31507 43326
8442 90107
72808 83186
84393 111116
17045 196530
37085 45...

output:

766902489
81988081
661764848
66165120
405746782
801019631
306959195
859331034
290798051
607337160
139803623
124473794
523612479
759358899
540665273
235894487
489427987
54875971
666513961
317295162
730372929
609482691
721345247
23432328
128687062
830800202
387738049
821118638
873134430
365074901
3235...

result:

ok 359624 lines

Test #35:

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

input:

200000 336686118
135366 166839
45350 139904
159671 170058
120428 191987
89668 121835
81044 177044
8391 100363
45370 67196
88711 197110
105185 190639
52533 191686
51115 87768
84729 145924
104888 132007
47826 74094
135845 137337
26681 192652
23948 90426
2779 22400
12151 116043
41007 59794
36610 138263...

output:

236619619
42646449
258150542
4582480
4816763
69595975
8026636
76204446
55974780
261332041
290758786
196023885
48420013
170585214
61740111
310935990
76999396
251752926
65296455
199635352
183230892
288373777
123674826
53543537
22205261
308353477
172404437
213258555
173768326
128417205
65075903
2358602...

result:

ok 39903 lines

Test #36:

score: 0
Accepted
time: 399ms
memory: 85208kb

input:

200000 660153402
15357 105508
30699 132572
99697 155530
26332 41270
83794 152333
77283 129270
31154 144269
68129 145165
189326 192701
175075 179460
27655 159558
140661 140858
51283 93986
5639 36360
14287 32658
16427 36856
89327 136650
27504 67243
11550 73783
64089 75619
90239 195788
36317 108641
566...

output:

322269999
123550476
469829285
131855595
337357257
250933469
584304339
636490839
193176595
280021105
528254114
367293912
417710977
248776364
536452751
379428842
16717042
386780920
4279638
579647611
404655246
391037942
164687852
490711620
231695905
64206279
348335518
602784261
46864702
266843257
56445...

result:

ok 360261 lines

Test #37:

score: 0
Accepted
time: 249ms
memory: 85188kb

input:

200000 526201007
64774 71847
77497 125603
141089 179423
140802 180328
80083 187016
147945 189180
98635 150045
1640 145973
49457 84983
93847 198846
50232 199874
97706 145645
819 54868
64301 197903
112560 116952
42657 123906
42437 160866
61936 189935
75199 107324
44597 106911
72860 94448
6450 98816
11...

output:

464642454
517279291
140648161
370322711
295601015
30327994
391447910
460232852
525578169
356413664
443150743
238489577
13000652
263516094
143880060
508582663
91928334
319789903
41784149
329031133
67227985
77167139
469207734
139977806
500832103
26234148
77723312
396661811
341388291
359569688
44258528...

result:

ok 39822 lines

Test #38:

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

input:

2 37304419
1 2
29626812
12442488
1000
1 2 0 29944224
1 1 0 29790797
1 1 0 35671101
2 2
1 2 1 5308319
1 1 0 10945865
1 2 0 20159800
1 1 2 4011276
2 1
1 2 2 1570746
2 1
1 2 0 26192449
1 1 0 19577455
2 1
1 1 2 7642770
2 2
2 2
2 2
2 2
2 2
1 2 2 15217784
1 2 2 30434890
1 1 1 30269900
2 2
2 2
1 1 1 260067...

output:

2499806
5964173
16748426
918307
13019644
13019644
13019644
13019644
13019644
28010182
28010182
30992781
24699004
24699004
20838434
5233281
12296037
12296037
12296037
6006320
6006320
6006320
34958424
16024098
9254202
26861423
27737009
27737009
17252441
29505039
29505039
29505039
34720199
8329559
2070...

result:

ok 499 lines

Test #39:

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

input:

5 555198320
1 5
1 3
2 4
2 3
383701832
300776219
26088429
411016312
61629662
1000
2 1
2 2
2 1
2 2
2 3
1 1 2 104187894
1 5 2 487610856
2 3
1 5 1 184138469
1 1 1 273019062
1 3 0 430338431
1 1 1 403637434
1 1 1 554957964
2 4
1 5 2 101615896
2 5
2 2
1 3 1 201120671
1 4 0 284571925
1 5 2 433594152
1 4 2 1...

output:

383701832
300776219
383701832
300776219
26088429
435827536
411016312
183931104
497282146
356149456
269552800
198631840
282384000
245622000
402709120
198631840
4074320
39376880
551507200
29039760
456690400
456690400
297287600
499976560
499976560
66610400
548567920
401769680
25183680
401769680
4017696...

result:

ok 491 lines

Test #40:

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

input:

8 902440550
1 4
2 6
3 5
1 6
4 7
3 8
2 5
367088587
49553470
118122846
369327908
157485348
615437631
27764020
227751499
1000
1 8 1 372179556
2 6
2 4
1 2 1 196727248
1 8 0 772734423
1 3 1 260341858
1 5 0 505341869
2 4
2 6
1 5 2 423776788
2 4
2 4
2 8
2 6
2 6
1 6 1 39676956
2 8
2 2
1 4 1 781292051
2 4
1 ...

output:

615437631
369327908
369327908
563695238
369327908
369327908
568454848
216202644
216202644
568454848
389570280
581746708
288882990
581746708
151679364
3095972
3095972
3095972
398824250
751670170
789486942
447544350
225615930
447544350
447544350
15007730
15007730
218713572
218713572
74677024
421118786...

result:

ok 505 lines

Test #41:

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

input:

11 102517931
5 11
4 10
1 3
4 11
2 9
3 6
5 7
6 7
8 10
2 8
93205850
73076419
20819297
84526973
91672399
47857436
65327125
87354488
91285121
36025628
27851064
1000
2 1
2 10
2 8
2 1
2 9
2 4
1 2 2 14653208
2 4
1 10 0 21258423
2 4
1 9 0 17641492
2 6
2 7
1 7 2 27451703
1 11 1 39116683
1 4 1 18292194
2 11
1...

output:

93205850
36025628
87354488
93205850
91285121
84526973
84526973
84526973
47857436
65327125
11935313
99811218
41442780
71390789
71390789
84564613
32128057
75286105
75286105
43231594
94364607
97072410
94364607
43231594
83339446
74211865
85022788
35457563
12250788
7136477
95571886
72931972
50268610
6292...

result:

ok 510 lines

Test #42:

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

input:

14 572275646
1 10
5 11
2 7
6 12
4 9
10 13
2 8
4 6
3 14
11 12
7 9
1 3
5 14
162681902
398647380
550212050
505842464
329150380
429736651
329722401
46771889
441707857
306200422
112576470
22210229
380938488
441572193
1000
1 7 2 502800212
2 3
2 2
2 12
1 10 0 195737779
1 13 1 111057257
1 13 2 3697026
2 7
2...

output:

550212050
368945848
22210229
45570170
408503292
376422810
550212050
368945848
368945848
551312918
213570306
312585264
329150380
368945848
2669312
329150380
441572193
441572193
288328542
220446482
151016962
220446482
441572193
368945848
368945848
270881862
386718306
448390382
497534004
497534004
1496...

result:

ok 539 lines

Subtask #4:

score: 12
Accepted

Test #43:

score: 12
Accepted
time: 560ms
memory: 91344kb

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: 0
Accepted
time: 630ms
memory: 89896kb

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: 0
Accepted
time: 482ms
memory: 90204kb

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: 0
Accepted
time: 374ms
memory: 85136kb

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: 0
Accepted
time: 262ms
memory: 85388kb

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: 0
Accepted
time: 237ms
memory: 85428kb

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: 0
Accepted
time: 171ms
memory: 85308kb

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: 0
Accepted
time: 545ms
memory: 89644kb

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: 0
Accepted
time: 638ms
memory: 90808kb

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: 0
Accepted
time: 437ms
memory: 85248kb

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: 0
Accepted
time: 446ms
memory: 85252kb

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: 0
Accepted
time: 289ms
memory: 86124kb

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: 0
Accepted
time: 284ms
memory: 86568kb

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: 0
Accepted
time: 3ms
memory: 8492kb

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: 0
Accepted
time: 3ms
memory: 8520kb

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: 0
Accepted
time: 0ms
memory: 8632kb

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: 0
Accepted
time: 0ms
memory: 8516kb

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: 0
Accepted
time: 0ms
memory: 8560kb

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: 30
Accepted

Test #61:

score: 30
Accepted
time: 564ms
memory: 89288kb

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:

ok 360189 lines

Test #62:

score: 0
Accepted
time: 616ms
memory: 88436kb

input:

200000 892371480
29283 186212
53253 131705
53820 182665
63053 73696
58575 104420
51754 160167
102223 185976
76959 198806
114136 199067
74079 159240
38474 92525
3848 115396
79584 199006
56267 73593
133783 137813
93479 170264
25086 101549
5466 104706
46711 107942
28355 159823
43616 87237
78378 86915
1...

output:

854444577
446034873
886587297
181297848
80741959
631374794
839621260
209408955
681589652
873598559
327656018
741004609
562124360
677868402
840776944
103459954
811856582
493473265
649874608
193926875
623568562
643619595
133311199
799525677
876358260
620745946
295065470
864433229
20121050
502062803
59...

result:

ok 40090 lines

Test #63:

score: 0
Accepted
time: 487ms
memory: 89028kb

input:

200000 193336276
81452 167991
20427 78000
79832 84342
24866 128327
76920 195554
23065 51260
77533 150604
72708 86254
83832 171853
25786 51846
22577 115764
19404 180758
6891 148212
11359 179037
163531 188755
100325 103512
51153 171205
42291 138622
7915 173631
52554 195408
30759 62497
69634 139445
790...

output:

147467270
78272610
131208045
192863622
95045402
90757095
190091888
31453730
161215248
102434730
79805294
41125625
3857401
149208517
85688462
11724432
188575348
188176097
182388333
86518895
135197966
143824749
116446940
71653679
84331240
67372038
154775882
2891290
160813688
166407199
24095959
1151797...

result:

ok 200007 lines

Test #64:

score: 0
Accepted
time: 410ms
memory: 85088kb

input:

200000 948305414
133251 170371
46992 69783
36042 96631
57960 101909
71750 116399
14077 121601
61493 161593
32440 159552
68315 93528
3349 23351
70178 101857
57946 191714
137904 162801
13684 161150
106519 135707
18978 61081
38110 74369
12116 95575
57969 150715
83964 157789
9684 113933
8537 70007
41931...

output:

429808045
664148272
540070551
70877810
106910480
742444419
552392006
60172973
80102812
2043321
606460233
797333124
538369270
524671764
99615328
124617457
629221019
231911663
799238141
288785838
805840345
608735884
415245557
442447154
141719381
162913447
927503777
382344281
239872308
133313063
556436...

result:

ok 199633 lines

Test #65:

score: 0
Accepted
time: 252ms
memory: 85372kb

input:

200000 814517151
6699 161511
3760 64371
71634 114422
4111 44097
55341 79524
31466 63672
40454 119144
47395 65652
111238 112225
51516 165736
120082 129098
15446 48939
50333 95385
37292 59307
37299 110677
32597 175248
46947 102030
9917 82817
14689 66282
9899 120909
83705 194181
61934 163706
40266 6611...

output:

462345301
651471194
186924377
408632240
194440941
322309499
720373177
546301858
626409421
741206469
342311921
438754683
304789637
112355664
271332920
347103338
219067019
735567557
372220557
517226800
201171468
625202178
697060593
20154432
58452318
230518287
485516306
560155077
497460414
121127810
18...

result:

ok 199536 lines

Test #66:

score: 0
Accepted
time: 234ms
memory: 85420kb

input:

200000 84345443
10673 178471
56519 167958
105131 108649
106583 107820
155295 157687
36665 55390
101312 134122
99517 193737
31594 182520
64393 183487
63534 185154
148825 191964
47218 74698
20567 43862
144641 174672
22755 108790
110778 132185
170052 170921
103522 109303
38244 144154
149155 164913
5990...

output:

79936245
59462805
23276695
77861129
58939143
50009260
69992659
75297365
8177635
12798839
65981155
70662401
56333101
11262523
44976728
796923
49839017
10621977
21840354
52506845
36010778
67577535
14422589
68180072
19746762
28761207
80048681
70665790
48953614
31608167
47430004
20405962
30154811
563110...

result:

ok 199741 lines

Test #67:

score: 0
Accepted
time: 188ms
memory: 85336kb

input:

200000 67895236
26733 85127
85127 108468
85127 159210
85127 100103
27460 85127
85127 157264
33694 85127
51549 85127
37814 85127
42986 85127
85127 187654
85127 132165
84961 85127
52351 85127
85127 130196
2324 85127
16737 85127
85127 171429
85127 187481
74326 85127
56906 85127
21702 85127
85127 149171...

output:

30291702
42241772
30828052
61065588
22560340
14090492
30980384
47882656
4220356
1234156
49677556
63642508
13184196
5349240
3084100
30095344
10742676
1670132
17559744
51364752
41853056
29723008
60738700
42661996
67379616
7174336
17009912
26844964
41814300
52742296
61660816
36415308
20174712
22097004
...

result:

ok 199555 lines

Test #68:

score: 0
Accepted
time: 586ms
memory: 91104kb

input:

200000 399036954
34607 62652
65135 88493
11540 30787
60293 83726
7576 16706
91828 128826
24812 96504
118306 162815
59626 78343
44484 177731
84744 176242
135881 184128
34973 66541
111477 145496
37894 147527
27599 38637
19954 52747
76469 137537
129068 194299
9980 60034
36405 146192
4928 145918
129011 ...

output:

359283766
8806341
364095453
134353113
397363780
44450526
261901728
251503916
285145999
121409965
4811949
161473494
306675944
316133478
295888843
224248452
237481529
78927982
44928412
53485213
243200663
291722722
26993596
363196510
188999093
137448708
391129051
45993725
178316204
314604980
189016506
...

result:

ok 359725 lines

Test #69:

score: 0
Accepted
time: 703ms
memory: 91028kb

input:

200000 399984153
15648 198766
17951 116305
74338 123254
10952 187313
29110 136270
133294 141868
57219 96710
104122 105957
1367 165433
95558 141537
28948 118796
120740 122537
101740 159387
8860 102113
99429 126913
32241 80281
87995 153121
4658 120370
77180 103516
43479 93680
95837 198636
95952 132197...

output:

202703290
317779494
356810907
96720997
397289748
135128650
361315824
355076276
190273325
365984564
254870033
264560834
20762265
395300399
123530930
177221183
292307936
367896374
11185710
26373318
153548310
308999701
117993836
15448589
394589428
93356115
306197420
158613363
296560881
298830699
357049...

result:

ok 40192 lines

Test #70:

score: 0
Accepted
time: 444ms
memory: 85128kb

input:

200000 329145231
11142 178664
41253 182686
47216 173020
136001 188624
16605 77230
86190 165748
22094 134884
36369 194586
8496 170747
75350 138997
10863 75434
87782 170588
112895 153391
30398 178751
44729 110074
20812 57450
14246 99548
56893 190727
63022 159217
109639 154417
56375 141131
140713 14768...

output:

91697865
311057458
196819751
198569456
39118136
309033434
265236993
128184918
155688796
51146927
249372861
298812716
98845946
117671439
123296855
74626705
36116453
191292142
160844712
47397767
48981163
136221862
329096775
253767244
259949191
266757245
264370880
302663769
17532636
236808067
21567556
...

result:

ok 360438 lines

Test #71:

score: 0
Accepted
time: 458ms
memory: 85116kb

input:

200000 595314045
80098 145622
93942 112153
19460 85413
99144 141787
2075 190534
51718 140810
56157 191671
142338 196029
18241 43040
63453 156761
81441 165511
51561 185801
58791 127705
112375 117916
111277 134799
99344 156017
27893 99031
44711 152209
58850 141812
9469 20615
7062 156888
31427 188992
7...

output:

524856939
143355449
505210097
100248444
34517281
465145195
270513495
170892124
321613969
526194793
57908142
102507936
355626400
290080403
184177603
263888356
528217697
263101162
20314449
61665868
192078904
499493879
4334189
343217074
407500923
230693811
585270525
537991369
109402335
550293260
530244...

result:

ok 40121 lines

Test #72:

score: 0
Accepted
time: 290ms
memory: 86124kb

input:

200000 193336276
42627 182561
6098 79195
5045 102764
97335 133047
114977 153710
40856 123426
95749 138493
74017 165994
38421 142029
58589 95683
68619 152003
124021 198565
72592 121854
49744 128435
101584 124597
107833 192775
96989 192772
36244 76304
57359 116376
39349 63292
9364 101420
2073 86289
14...

output:

15414628
162837860
137325156
128472016
35780068
163800520
146744428
161486700
146137552
160352192
137005628
16477788
136221768
158465048
57459108
69123740
53419384
159526852
168282964
61217760
13356656
116444088
186852568
28152116
168009448
152915912
139557532
4827684
118962808
42943324
12463156
161...

result:

ok 20254 lines

Test #73:

score: 0
Accepted
time: 278ms
memory: 86524kb

input:

200000 948305414
5025 66080
67566 102512
885 140314
40661 124847
105568 122465
124594 140059
146779 176139
4750 48049
141218 148086
79864 92589
37422 87593
44774 55977
126070 174431
34031 162685
70393 89350
138553 186096
11126 87306
89894 182828
29524 89627
174253 186783
99170 135658
27023 29163
164...

output:

268985502
403614100
160631742
732646016
417990796
293673740
598394656
449850788
676058682
312885204
784895856
676485390
188792034
184934520
300709502
540212906
184357740
521321230
102496742
750593038
692514370
33321234
943148130
258964076
604368576
504977576
294836968
478973028
786631692
657481524
5...

result:

ok 19904 lines

Test #74:

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

input:

2 470537017
1 2
337073319
1786497
1000
1 1 0 2
2 2
1 2 2 2
2 1
2 1
1 2 1 2
2 1
1 1 2 2
2 1
1 1 2 2
2 2
1 1 2 2
2 2
2 2
2 1
2 2
2 2
1 1 1 2
1 2 0 2
1 2 0 2
2 2
1 1 1 2
1 1 0 2
2 1
2 2
1 2 1 2
1 2 0 2
1 1 2 2
1 1 1 2
2 2
2 2
2 2
2 2
1 1 0 2
1 1 1 2
1 2 1 2
2 1
1 1 0 2
2 1
1 2 0 2
1 2 1 2
2 2
1 1 2 2
1...

output:

1786497
407219242
407219242
343901467
217265917
28583952
57167904
57167904
398526651
57167904
57167904
457343232
364991106
444149447
48335897
48335897
48335897
48335897
303116951
135696885
302837335
214934334
179143486
429868668
389200319
43073674
172294696
172294696
220447766
344589392
411254047
41...

result:

ok 501 lines

Test #75:

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

input:

5 332823899
1 5
2 4
1 4
3 5
131665499
248297744
236261163
313919671
270831875
1000
1 3 1 2
2 5
2 3
1 3 0 2
1 1 0 2
2 1
2 5
1 3 2 2
2 4
2 4
2 5
1 1 2 2
1 1 1 2
2 4
1 5 0 2
2 2
1 5 2 2
1 2 1 2
1 2 0 2
2 3
2 5
1 2 1 2
2 5
2 4
2 1
2 2
2 5
1 3 0 2
1 2 0 2
2 2
1 1 2 2
1 3 2 2
1 5 2 2
2 4
1 4 0 2
1 1 1 2
1...

output:

208839851
139698427
263330998
208839851
313919671
313919671
84855803
257206987
163771589
238231438
26397252
26397252
60712502
219409180
311701015
26397252
290578131
242850008
305752234
248332363
248332363
248332363
278680569
179064266
248332363
182307890
248332363
278680569
101218532
202437064
20664...

result:

ok 496 lines

Test #76:

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

input:

8 790311037
2 6
1 2
3 7
4 5
6 8
1 3
4 8
581353649
284854635
166465719
389586802
281463734
70964583
426190153
17655635
1000
2 1
1 4 2 2
1 6 2 2
1 6 0 2
2 7
2 2
1 7 0 2
2 1
2 4
1 7 1 2
1 7 1 2
2 2
2 1
1 1 2 2
1 5 2 2
1 5 0 2
2 1
2 7
2 6
1 3 1 2
1 8 0 2
2 5
1 7 2 2
2 8
2 3
1 5 2 2
1 1 2 2
1 4 0 2
1 8 2...

output:

581353649
426190153
569709270
372396261
768036171
569709270
372396261
744792522
496554152
345122291
671087798
282490160
585036786
590178127
77515325
62014797
692527426
594743815
334048496
136411537
109557289
496118376
668096992
668096992
399176593
438229156
438229156
300981259
301454857
403851430
30...

result:

ok 492 lines

Test #77:

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

input:

11 459456351
1 9
7 8
2 4
5 11
4 7
3 6
2 6
10 11
1 5
8 10
54708953
107324429
257487712
26016978
5850435
3874838
221650892
26824157
192059522
374926865
89636170
1000
2 11
2 10
2 8
1 3 2 2
2 4
1 5 2 2
1 7 0 2
2 6
2 10
2 1
1 1 2 2
1 1 2 2
2 11
2 9
2 6
1 5 0 2
1 11 2 2
2 7
2 5
2 1
2 5
1 4 0 2
2 7
1 4 0 2...

output:

89636170
374926865
26824157
26016978
7749676
290397379
109417906
257633009
158107123
7749676
443301784
187213920
415886897
187213920
443301784
55519073
443301784
7749676
53648314
7749676
7749676
427147217
222076292
107296628
427147217
104067912
55809667
399139081
107296628
242676814
55809667
2181872...

result:

ok 512 lines

Test #78:

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

input:

14 255535920
10 12
2 11
6 11
9 14
2 8
7 8
5 10
12 14
3 5
4 9
1 13
1 4
7 13
70054243
141080194
194430532
146999749
222085915
56957281
100466730
128129158
206616100
130616108
79228519
241090797
26668317
29905289
1000
2 1
2 10
2 14
2 11
1 14 1 2
1 4 0 2
1 6 2 2
1 3 2 2
2 9
2 3
1 11 0 2
2 7
2 14
2 5
2 5...

output:

70054243
130616108
29905289
79228519
157696280
133325144
100466730
59810578
188635910
188635910
128129158
128129158
11392592
197755428
227829124
24681052
59856640
11392592
76927156
24681052
76927156
22785184
245512624
2889584
86778384
86778384
22785184
250374112
24413952
235489328
200122328
24413952...

result:

ok 503 lines

Subtask #6:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #79:

score: 17
Accepted
time: 394ms
memory: 85196kb

input:

200000 892371480
50686 95046
87074 194753
16371 25118
146885 158366
128106 195515
78324 147382
135960 197046
72342 117748
95470 110101
25038 128628
77135 143267
107112 173639
39295 122766
73475 163023
65828 78293
21915 115679
49759 100192
40319 196912
38458 73505
57017 196095
63574 191416
190775 198...

output:

730157739
539775493
13191953
453729238
260292138
91892037
386541048
655930043
168244441
197152951
587423774
882528838
21193359
242898572
4978764
476233406
57376112
731683143
642663895
717135592
551814860
162862995
782131154
135883192
647640288
875001010
859506332
455246224
723777706
760089479
707431...

result:

ok 359943 lines

Test #80:

score: 0
Accepted
time: 478ms
memory: 85132kb

input:

200000 892371480
80267 137574
41855 118703
63122 101464
63641 121980
13831 24964
58741 77539
118305 197601
53254 90515
57775 161170
46192 188798
60207 128123
129334 152752
62307 105329
5344 112726
30718 100144
7672 70371
62497 172322
15141 174459
44907 191253
34305 144843
20175 72554
53648 163444
17...

output:

126385014
738799474
399040719
812379731
719403194
290175255
537951071
604047907
495409464
778395999
689983180
469071807
231661263
354010921
494751207
330075384
227171728
134432469
263322290
258901224
839850072
646008148
261972233
823950981
586798278
541553760
814178470
664678672
357569629
210664886
...

result:

ok 39903 lines

Test #81:

score: 0
Accepted
time: 521ms
memory: 91188kb

input:

200000 239134939
61219 95050
27383 43853
30244 71619
131289 194077
145991 191870
6512 35413
19368 141380
29051 96577
124320 198006
42672 131978
8777 29169
54981 70465
54295 197053
31367 105493
33353 152827
148228 194190
4784 55578
34310 178829
956 167714
43604 118128
47767 179634
39563 159650
12956 ...

output:

71945585
61937740
7010096
28312764
167258157
78275613
84373808
229522716
124309734
86078447
168687810
14117347
227808539
180736558
209938850
93461625
60194391
176591552
55215353
66559473
188637264
74308929
66931791
134944359
84053693
127224116
207390432
78662083
160887878
141467012
225927404
4901720...

result:

ok 200067 lines

Test #82:

score: 0
Accepted
time: 398ms
memory: 85188kb

input:

200000 382185570
50600 186008
160338 181055
1909 76142
49662 183518
26759 156258
2121 113676
100791 165461
79404 159851
31363 147660
163559 183308
98787 126575
57415 126775
26984 196882
71327 97336
112095 196465
90034 131454
7397 11095
127525 142229
158079 199136
120274 191769
3757 42536
112477 1605...

output:

108599467
64062699
221972344
106925243
158639964
216914121
224672130
366427684
212908226
262230491
51946762
174577259
317344989
33047467
113100259
40060267
215612424
255563472
366624329
85887661
149959630
274438612
191082915
318730570
10076536
157058583
307357471
107703501
206490974
2343363
21890071...

result:

ok 200474 lines

Test #83:

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

input:

200000 54607786
131158 182978
120674 197192
27462 30050
3769 128458
43662 45449
29589 96520
161414 193087
130733 170581
16179 183733
87267 164560
38151 130205
99094 172615
745 166477
28365 96379
55719 165892
138336 159864
92493 127211
70288 80879
94149 161758
43208 120533
72098 130001
20287 146239
7...

output:

33552470
10740644
44587146
41091072
27195118
2375152
23111106
41006978
1835742
33182816
22317742
29416066
11181956
26889636
48705208
38012198
40869266
27674640
44690926
52332992
50189602
33907628
8861410
12542052
23613390
15442288
29755292
54371806
2754886
40903542
47551756
40051658
23264132
9353206...

result:

ok 200008 lines

Test #84:

score: 0
Accepted
time: 259ms
memory: 85420kb

input:

200000 961229051
75632 93085
102781 134540
88796 157202
26919 101936
2846 46967
135748 199376
84444 173416
163092 196676
109849 140548
87854 170086
91681 126636
158582 199049
157243 194017
55938 185216
63417 101512
108398 109241
61603 188580
91597 155942
2836 43127
33640 176266
13214 168594
88575 97...

output:

423027005
455249905
7766790
546845181
624354501
532554735
417905578
325925344
760647901
232712334
282495566
831206150
4271661
880804873
336096257
951408242
400156315
2915714
697775842
742827016
37941242
324334510
701362216
545189745
508696838
148079964
235898578
339810373
613086824
581388135
2565093...

result:

ok 200084 lines

Test #85:

score: 0
Accepted
time: 177ms
memory: 85156kb

input:

200000 759696069
23245 83398
23245 27961
23245 157939
23245 38947
23245 181484
23245 155299
23245 124844
8073 23245
23245 186917
23245 25992
23245 133100
23245 65862
23245 26945
15262 23245
23245 92995
23245 76142
23245 161531
5283 23245
23245 91403
23245 96785
23245 145915
23245 112717
23245 163124...

output:

600971978
255959223
219366834
328414521
324945156
655217049
542259261
160737225
121415877
528631257
731540832
118007934
301718703
507034143
367078833
416619357
416429970
701453841
712207353
454164909
182746245
316917282
463646007
409839606
713012883
609622926
541175580
589621857
443561844
695856084
...

result:

ok 200798 lines

Test #86:

score: 0
Accepted
time: 545ms
memory: 90208kb

input:

200000 649669688
135491 190089
112417 153702
143912 184667
83412 193400
83705 115129
42897 185366
86307 131291
173603 199889
1549 121895
1123 31728
88935 162234
41258 48786
39895 153433
89992 142709
4997 148145
16190 171713
149119 196134
185852 196348
124638 173895
165538 171857
194172 197791
59581 ...

output:

626502315
195522664
490288108
336329770
37850487
42271540
349472785
392639983
88543897
612580407
308712446
595967899
294496968
261167641
265906125
44724096
339041120
639506889
371285065
463604843
549149993
399669500
122300336
367128563
251817563
215672976
93396598
434744956
542094083
147355309
49502...

result:

ok 359932 lines

Test #87:

score: 0
Accepted
time: 661ms
memory: 89028kb

input:

200000 49185357
87086 181791
161462 169590
155715 190851
113997 187552
112415 195141
54915 79644
37079 82787
136063 160851
49589 177003
123927 138740
37394 182956
26100 190965
146497 168303
90688 130409
4531 48936
83223 100350
60588 64083
38621 175818
14499 141647
18705 30430
44190 148680
79023 1689...

output:

5569465
6297835
30829301
48489820
45433720
44682637
14994541
14609266
1023267
2527610
28545836
17126384
14614775
35920695
27714906
48952883
33675773
26665639
38001029
14877720
33691794
20734549
9773676
28044576
37686622
25636823
35628315
1126725
4844852
45834038
18116657
1714380
23206552
2151397
379...

result:

ok 39771 lines

Test #88:

score: 0
Accepted
time: 429ms
memory: 85140kb

input:

200000 105579969
13709 78647
53676 59136
60028 74531
83264 100037
41890 75595
65277 91937
54377 138172
12598 135783
61727 88645
3659 182502
99930 108220
51925 75401
76813 176614
104136 173811
15638 62402
31009 77304
8752 60363
54369 127831
139785 159475
73075 143730
19434 164577
90674 121235
111297 ...

output:

26386366
34344634
41420929
19256120
100047546
43998671
45924369
10470163
10784399
17122869
9526957
56453575
15735855
44955890
42481842
90907414
102342153
16457072
41836091
61528549
96918329
90163717
5967012
12509698
55355948
14608526
28431882
1790562
21432846
82039961
43114903
19100690
60175539
4852...

result:

ok 360264 lines

Test #89:

score: 0
Accepted
time: 477ms
memory: 85076kb

input:

200000 236870928
654 107504
7944 17218
124950 178201
62581 114746
24661 84160
55678 141604
36470 178620
11511 35501
27157 164566
38281 76838
100841 164314
26560 45398
13228 62636
101188 199017
4105 70154
26773 124605
84327 199363
49311 191792
87374 135737
48894 148433
87234 116956
131716 144371
1046...

output:

155292183
98494309
201744551
133329781
21170493
231971077
124736528
121207959
177766454
217240704
109832262
159066684
175370112
34497912
204164160
88268442
59161040
177930486
111800343
153827580
18003618
81111772
218961418
105945138
44452583
105345270
44274528
212370698
131253072
83074512
214600896
...

result:

ok 39918 lines

Test #90:

score: 0
Accepted
time: 505ms
memory: 85200kb

input:

200000 985313144
113932 131779
127288 130562
3093 100418
6582 183022
49772 74851
70601 199986
62757 198348
60068 77801
154454 157499
20435 34218
63225 157450
48515 180991
122714 151187
6520 94140
88008 115063
87877 178473
22636 56787
79222 156032
31211 54554
178757 193191
135019 189327
24380 119213
...

output:

387974521
15229752
156429560
391175099
171577312
127193776
730184716
58483658
638401387
525538688
696538758
524490551
652359689
227907248
344697144
516285630
548402722
803809224
666719500
308797973
185541016
981049314
254519246
708836116
928889135
159667464
840003510
951226264
310596621
195363280
75...

result:

ok 19876 lines

Test #91:

score: 0
Accepted
time: 308ms
memory: 86080kb

input:

200000 239134939
78045 83640
28607 160823
5658 71041
33053 182983
58189 94569
62500 148359
39942 172570
27151 41696
139686 159154
3028 97184
105302 124979
54470 134948
77664 183433
107404 174037
5502 44132
12019 162409
5924 147114
88370 153617
71568 164580
44841 185291
130007 146336
53567 69327
5781...

output:

78384547
121504048
190694975
15851256
93409390
96994317
222108641
221073479
86525981
163166582
5207923
225852300
20242569
71877674
127176599
214682731
124674446
82942876
15189901
175578239
176798742
44376283
183383711
37441232
78637193
63787372
37320215
101896960
155080524
223811019
68063489
2286411...

result:

ok 19784 lines

Test #92:

score: 0
Accepted
time: 305ms
memory: 86452kb

input:

200000 382185570
14359 190144
193497 198665
63534 146342
45562 175663
145572 170022
131470 137890
1846 106114
91868 191547
53697 157070
178650 182538
85110 134106
145183 179170
116847 161133
21218 47356
79794 108285
9302 110746
6648 92033
19803 46564
150476 159168
16593 68629
46572 91677
52964 11230...

output:

357929503
215504010
178366110
357087900
174799620
300085620
11863410
257497500
97285890
272235990
201481800
72484620
68520270
200707260
182982540
291057390
303439500
241832760
74214570
140589930
321549540
85037160
162692400
258527490
304810350
84407310
290494230
259409280
310456770
282409920
3137097...

result:

ok 19985 lines

Extra Test:

score: 0
Extra Test Passed