QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200817#62. Examinationjames1BadCreeper100 ✓255ms19560kbC++171.8kb2023-10-04 20:37:332023-10-04 20:37:33

Judging History

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

  • [2023-10-04 20:37:33]
  • 评测
  • 测评结果:100
  • 用时:255ms
  • 内存:19560kb
  • [2023-10-04 20:37:33]
  • 提交

answer

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

int n, q, b[2000005], tot; 
struct Node {
    int a, b, c, id; 
    bool operator< (const Node &a) const { 
        if (this->a != a.a) return this->a > a.a; 
        if (this->b != a.b) return this->b > a.b; 
        if (this->c != a.c) return this->c > a.c; 
        return this->id < a.id; 
    }
} a[200005], T[200005]; 
int ans[100005]; 

int C[2000005]; 
void add(int x, int k) { for (; x; x -= x & -x) C[x] += k; }
int sum(int x) { int r = 0; for (; x <= tot; x += x & -x) r += C[x]; return r; }
void CDQ(int l, int r) {
    if (l == r) return; 
    int mid = l + r >> 1; CDQ(l, mid); CDQ(mid + 1, r); 
    int p = l, q = mid + 1; 
    for (int i = l; i <= r; ++i) {
        if (p <= mid && (q > r || a[p].b >= a[q].b)) {
            if (!a[p].id) add(a[p].c, 1); 
            T[i] = a[p++]; 
        } else {
            if (a[q].id) ans[a[q].id] += sum(a[q].c); 
            T[i] = a[q++]; 
        }
    }
    for (int i = l; i <= mid; ++i) if (!a[i].id) add(a[i].c, -1); 
    for (int i = l; i <= r; ++i) a[i] = T[i]; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> q; 
    for (int i = 1; i <= n; ++i) cin >> a[i].a >> a[i].b, a[i].c = a[i].a + a[i].b, b[++tot] = a[i].a, b[++tot] = a[i].b, b[++tot] = a[i].c; 
    for (int i = n + 1; i <= n + q; ++i) cin >> a[i].a >> a[i].b >> a[i].c, a[i].id = i - n, b[++tot] = a[i].a, b[++tot] = a[i].b, b[++tot] = a[i].c; 
    sort(b + 1, b + tot + 1); tot = unique(b + 1, b + tot + 1) - b - 1; 
    auto find = [&] (int &x) { return x = lower_bound(b + 1, b + tot + 1, x) - b; }; 
    for (int i = 1; i <= n + q; ++i) find(a[i].a), find(a[i].b), find(a[i].c); 
    sort(a + 1, a + n + q + 1); 
    CDQ(1, n + q); 
    for (int i = 1; i <= q; ++i) cout << ans[i] << "\n"; 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 7452kb

input:

10 10
28 2
78 81
39 79
61 31
36 99
90 5
20 55
91 4
48 19
80 7
52 43 78
64 65 171
34 68 124
37 80 161
53 19 123
49 58 109
95 46 30
45 48 60
47 13 54
64 30 144

output:

1
0
2
0
1
1
0
1
3
1

result:

ok 10 lines

Test #2:

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

input:

10 10
6 67
36 99
13 45
100 87
60 72
55 41
62 92
55 39
90 22
0 99
34 89 79
17 17 23
60 26 171
29 88 190
32 71 98
20 29 192
50 7 34
14 21 139
54 35 103
86 91 1

output:

2
7
1
0
4
0
6
2
3
0

result:

ok 10 lines

Test #3:

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

input:

10 10
67 72
94 99
34 22
1 71
68 18
90 94
29 44
98 61
46 9
94 76
73 36 11
30 26 75
5 85 112
38 35 111
39 72 143
6 64 130
31 24 134
82 86 188
80 20 151
91 32 62

output:

4
5
2
5
3
4
5
1
4
3

result:

ok 10 lines

Test #4:

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

input:

10 10
667489048 282547819
694873877 525794923
605957229 147658688
928289876 455560133
465507205 531350815
397977066 913356070
351069660 834164613
611261253 238522918
683770744 737447844
351350094 473152918
514777487 599392520 569824365
137189600 455145855 1628925058
608994260 433029864 1934471803
80...

output:

1
0
0
1
2
0
10
0
1
0

result:

ok 10 lines

Test #5:

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

input:

10 10
263981199 52332634
326795173 857652684
184061837 846545137
39542400 348620078
96871071 314776708
19327149 702608210
486997547 362493836
734600837 228406106
676322287 184313447
205910594 985010975
928597138 172342418 665625750
340192959 922085230 1825805421
805685495 219541540 475070350
4658221...

output:

0
0
0
3
0
0
3
0
0
0

result:

ok 10 lines

Test #6:

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

input:

10 10
938568749 622216614
473949650 794427283
821003445 932759572
521639872 980300286
221194869 486910867
809253866 513217132
566374168 282501808
288139033 402357178
916473963 145958981
592255402 968995324
113069862 909714805 1855286879
572813519 935368048 360790753
835912982 28401519 1522137034
943...

output:

0
1
1
0
2
0
7
0
2
9

result:

ok 10 lines

Test #7:

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

input:

3000 3000
40944019 692692877
645016109 145199524
568250169 363353983
626494606 558783087
161612818 101360006
34139264 867093007
708172540 84650861
45799594 79255002
364942843 522551858
327755779 907461393
429041284 748255933
912770818 886733119
19971581 580290777
717292638 606814849
840433536 332990...

output:

1602
171
930
467
30
1316
125
475
883
1105
135
427
478
89
840
1466
3
0
591
34
368
4
936
590
246
270
1168
18
79
9
303
533
19
491
163
287
1350
445
23
151
2006
184
1233
11
175
1348
515
229
717
889
60
37
4
273
324
81
4
471
1275
11
207
444
1214
232
85
686
182
709
513
207
1451
418
2041
729
3
871
466
51
198...

result:

ok 3000 lines

Test #8:

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

input:

3000 3000
907627167 686752093
462625412 852663910
500152795 14286796
910681862 200991087
109311919 35030354
156913954 564324169
181028206 930471944
686123971 163012566
732920495 314853990
910305661 51938497
868182462 323159996
777537241 919935911
714475342 334517770
927209935 435695974
747799830 888...

output:

70
62
456
163
1557
359
169
428
194
70
364
593
296
99
4
166
435
632
1
1315
21
137
72
375
111
674
491
1398
96
339
280
1
211
94
890
0
757
106
428
478
637
133
357
1009
422
706
224
111
231
677
21
990
1361
113
682
393
6
186
295
288
28
1586
82
186
21
92
64
416
127
453
174
500
8
374
257
10
195
441
213
2292
...

result:

ok 3000 lines

Test #9:

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

input:

3000 3000
334978095 565095638
78003245 739839219
211920625 294829
835598279 911193731
640309078 196393030
930111636 843404908
272429756 299106119
421405869 635269635
422157528 163791651
220891615 341620330
768573478 656606438
898559946 184092507
551655307 968524071
495019662 642996661
48050546 23559...

output:

305
17
1801
760
1981
737
261
136
282
495
8
58
117
102
1053
922
6
872
1305
1011
443
286
458
14
22
72
150
1341
537
403
4
885
626
1328
39
442
324
0
1456
210
35
539
1153
278
162
961
55
4
790
90
3
957
155
891
396
2412
63
0
1018
2211
176
432
152
33
440
230
238
139
314
69
311
3
936
136
730
1366
106
440
823...

result:

ok 3000 lines

Test #10:

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

input:

3000 3000
670721945 0
918363246 4
530498664 8
151236440 1
551302032 5
744761966 3
677885226 8
425828663 4
806962929 7
86226431 3
553505514 6
229344072 1
495287254 4
742717671 8
107255479 2
872256841 10
891288366 1
344265685 9
837502103 4
146091952 6
611328716 3
592876764 10
641850002 6
898856374 8
4...

output:

381
125
529
344
665
51
17
830
103
605
395
668
1507
1322
189
387
590
828
510
84
960
14
491
377
520
770
101
369
839
31
217
830
524
1477
205
87
12
996
235
521
2051
1117
238
178
1127
47
222
281
11
363
158
34
302
587
1408
287
1768
67
680
327
400
118
1591
804
84
162
1278
0
258
173
655
101
502
1012
565
269...

result:

ok 3000 lines

Test #11:

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

input:

3000 3000
8 375396159
8 368119562
1 575071003
0 713872346
8 587408547
7 78445830
3 900615065
0 97512137
4 875603716
3 187655071
3 321929391
4 341544316
5 427645484
5 264570850
8 560506150
8 208439714
3 264016831
2 461763351
1 831864441
5 487169227
3 762640963
4 222377711
10 632245214
7 14464390
9 40...

output:

1504
128
221
73
789
375
3
1103
2391
155
307
592
149
25
106
112
393
461
842
403
752
119
51
896
392
631
71
93
1182
753
334
2273
624
530
488
1465
13
5
1289
3
162
1744
511
164
612
435
801
1720
1017
855
1291
952
1096
593
299
31
158
219
420
37
66
991
193
2231
117
1357
388
363
18
1443
1054
486
107
72
32
39...

result:

ok 3000 lines

Test #12:

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

input:

3000 3000
8 9
5 2
9 2
6 5
3 3
9 10
6 10
5 1
4 9
4 3
0 9
4 3
0 4
10 3
2 2
8 7
10 5
4 0
9 9
7 9
2 2
10 3
1 2
10 5
7 2
7 8
0 10
4 3
2 10
10 1
5 9
3 5
5 4
7 1
4 4
7 6
7 2
6 4
9 7
2 9
3 2
0 10
3 6
6 7
8 0
5 10
0 2
6 3
0 6
2 3
4 2
5 3
10 6
9 0
5 5
3 10
5 0
1 7
9 9
0 7
7 3
8 9
2 3
3 1
8 10
4 7
10 10
10 3
0...

output:

1325
19
361
137
168
434
170
57
896
360
168
950
324
2158
338
510
116
215
1550
1163
132
896
2054
94
137
359
259
297
1973
1061
199
1475
510
365
343
225
804
235
235
279
19
281
365
236
894
1554
1619
116
1163
2443
1964
510
484
784
294
91
660
132
739
983
1087
195
1319
273
583
33
1932
876
146
365
371
203
59...

result:

ok 3000 lines

Test #13:

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

input:

3000 3000
877137497 911480796
105327974 808804262
727937300 637853442
718031794 765195805
838206925 484239980
607467843 605792963
38697321 332194606
273988991 323047106
798562928 435509930
372308224 443534703
707117309 487932296
211775547 761591409
77454450 882287786
277784786 263090911
819288578 17...

output:

1524
1296
1606
226
1445
158
382
435
13
182
1983
223
81
1832
469
1188
375
353
617
882
244
939
819
612
448
355
458
296
1024
301
855
732
1256
553
1143
755
978
1995
1263
1652
2018
239
38
1472
916
1172
662
1021
366
1480
136
716
1246
420
1549
24
257
831
143
164
466
1551
1476
499
1488
937
511
85
652
134
85...

result:

ok 3000 lines

Test #14:

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

input:

3000 3000
10427381 302072811
305423535 159511618
389241521 972714841
87239050 654013994
553105278 55046924
721109311 612092521
522048131 811507269
616929981 759331556
694803970 82587802
55757168 4610834
227644683 145826047
767743895 527337462
664853723 570569400
225987816 848995384
922146032 1350592...

output:

149
135
169
182
111
161
1515
1355
1736
2239
249
682
1721
1992
2006
1036
652
1810
577
810
471
1122
513
107
64
1907
1482
1707
531
972
679
197
34
382
7
107
623
573
132
767
61
106
60
1957
69
34
103
456
4
896
1516
1571
570
1885
573
1237
1652
433
1428
1
133
31
761
31
2282
591
1418
2078
102
21
212
1090
687...

result:

ok 3000 lines

Test #15:

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

input:

3000 3000
81888039 43067130
107207950 11840118
12213117 1564707
591852272 88838686
961663048 516561908
168803247 844631606
873195252 827482721
743609372 619362988
538294586 82184626
144127316 243409881
211682136 271003480
663591068 168473714
654369343 16498796
591919034 700712174
385773732 618206738...

output:

128
125
1701
799
67
1725
1166
370
80
481
533
606
82
8
2273
272
2646
637
955
661
484
2418
63
47
269
162
1864
364
873
135
947
401
126
1380
56
54
2756
279
352
327
633
1453
114
319
1142
219
5
1100
495
88
13
1948
37
773
823
284
1012
612
195
248
1585
1517
37
159
1940
768
482
419
659
245
1599
923
879
99
47...

result:

ok 3000 lines

Test #16:

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

input:

3000 3000
0 265577685
0 279712461
0 865961338
0 715526160
0 152109041
0 720516447
0 663839583
0 572363102
0 15684570
0 774105531
0 355480679
0 318103883
0 809487980
0 566618853
0 399560845
0 428122875
0 406123722
0 227690500
0 306745648
0 787880089
0 156872708
0 469927843
0 869358593
0 484045893
0 4...

output:

216
312
0
4
0
2580
1282
0
0
2331
0
0
1108
0
710
1405
0
2129
0
0
1820
0
0
1698
0
1215
1389
0
0
2892
2456
2856
0
0
111
1849
205
0
795
0
0
0
2288
849
1432
927
0
0
227
1335
0
1565
17
398
1512
282
1611
0
2268
2894
0
337
0
277
2501
0
2182
0
21
0
1568
0
1706
1102
0
454
0
2457
0
0
0
0
0
0
0
1993
0
78
0
0
0
...

result:

ok 3000 lines

Test #17:

score: 0
Accepted
time: 5ms
memory: 7616kb

input:

3000 3000
905574076 0
62086925 0
984401157 0
900477115 0
688562084 0
607520732 0
679335141 0
4786510 0
595168939 0
16199355 0
932151269 0
333912126 0
772707530 0
544868665 0
863264108 0
492456951 0
971680943 0
930894040 0
405136186 0
728899221 0
800538513 0
145763793 0
544013589 0
250213891 0
317696...

output:

0
0
0
0
0
411
811
625
2171
0
0
0
1283
992
0
0
0
41
0
0
10
843
672
876
876
1217
2327
0
0
0
0
77
0
0
0
0
888
1891
563
0
1508
1284
1618
546
0
0
1391
0
688
270
989
106
0
0
1711
1461
0
1923
0
2260
435
0
0
1759
1353
0
0
843
1301
0
547
0
373
0
823
0
1864
492
0
0
0
0
1058
0
0
0
0
682
0
186
1198
0
544
1200
2...

result:

ok 3000 lines

Test #18:

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

input:

3000 3000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
0
0
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
3000
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3000 lines

Subtask #2:

score: 20
Accepted

Test #19:

score: 20
Accepted
time: 202ms
memory: 17880kb

input:

100000 100000
26753 11234
32815 62591
34318 93262
77179 57605
88208 33327
48449 99060
42403 58561
85715 7001
2418 90938
77409 6957
546 83283
53957 8374
49470 1483
65866 64950
4269 8745
19041 85833
22344 90706
92926 35603
54697 75311
72601 66401
77598 8193
3751 54202
32710 5877
23835 38264
34381 3338...

output:

3392
12465
20237
13565
11736
28514
4108
33065
27851
26019
23511
12295
30617
229
20830
1461
3465
17020
36047
23196
69812
24530
13442
8259
24433
733
10411
20119
15897
75646
27339
73794
46246
61350
520
59415
6149
798
2836
4628
14774
40980
38231
7313
39010
14774
27553
20182
82757
35655
3811
29324
5084
6...

result:

ok 100000 lines

Test #20:

score: 0
Accepted
time: 200ms
memory: 14176kb

input:

100000 100000
36183 27642
41135 83584
70122 47356
53931 91393
18974 31405
24368 55518
10497 80811
48033 26530
64308 48589
68190 3786
2581 71927
88230 32477
43296 50536
88504 21426
14146 80077
53732 78665
79135 26660
86542 61452
4123 6597
44250 67766
56783 45985
22533 26926
52239 41762
51757 22717
67...

output:

73744
15573
3541
33582
45046
39539
8350
49949
26717
17310
51586
47422
27917
42623
22829
63447
17401
12617
46091
44926
33866
27094
2221
16429
18302
430
4537
875
22513
38949
3644
46728
7026
24266
328
41880
57894
6183
43148
17215
16219
28014
27938
50069
4104
1210
15102
25625
82753
23423
65093
5498
1715...

result:

ok 100000 lines

Test #21:

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

input:

100000 100000
61202 15303
17580 33912
58858 33470
70876 51214
84031 58237
23244 98448
65047 44425
49136 49506
40012 94044
68675 20279
42664 71753
45063 63883
66897 52949
47780 97851
31836 7559
22380 17745
24710 85337
35743 19683
82997 58382
58574 53595
47799 67394
90082 73911
39464 80374
38376 21112...

output:

1541
54000
34218
2175
8151
4219
8339
17842
16126
11861
20519
28683
35226
40705
46908
22901
3528
56957
16314
79164
844
23691
50609
44957
8551
62222
32891
859
48694
12759
24914
42690
672
81296
36765
1769
44302
3584
11073
10474
39060
17180
10162
48316
44979
43869
10455
10438
9888
51411
53010
5393
32677...

result:

ok 100000 lines

Test #22:

score: 0
Accepted
time: 157ms
memory: 14116kb

input:

100000 100000
71417 10
2561 2
98727 8
46876 8
47953 4
12675 7
42287 1
33941 1
85798 1
41398 8
22588 10
552 8
89891 5
82384 2
57149 3
28445 9
88248 8
88460 0
85250 7
71373 4
86754 9
89467 3
22493 6
6189 5
59883 0
63865 7
83979 8
48535 1
80407 3
36181 0
90781 1
99580 9
95056 1
276 0
34940 8
3059 0
327...

output:

3828
24801
13620
43570
70088
31578
8899
54600
1651
4502
18442
46620
15022
61296
30279
35147
5674
6413
57193
41261
28498
12570
1346
59248
12610
35555
7355
9293
46366
60596
3343
5118
8843
41436
13517
13785
55234
22798
56680
6933
66367
13924
15466
18014
5583
23109
4463
14174
9680
44018
24446
54065
9190...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 155ms
memory: 14052kb

input:

100000 100000
1 41869
9 19183
9 55137
1 85647
4 57461
10 52473
3 78990
9 57080
10 71084
2 76290
2 82919
4 93821
6 3994
8 11800
8 81833
6 66729
2 79529
3 73951
1 3288
4 49246
2 95984
0 76298
0 54478
0 28108
8 19171
8 18851
8 98271
0 98642
4 55247
6 53198
10 48223
1 37502
3 84842
8 37860
4 97053
6 981...

output:

36629
4922
38944
47314
59748
48310
779
20349
372
32987
50348
26069
3108
1436
13356
51963
11910
71350
31011
20695
1536
1645
21253
74319
18542
58746
2118
35286
21362
56522
30619
51319
11290
15157
49479
87630
42334
35111
37612
10421
8882
51232
6288
27008
43089
1225
79570
18817
8247
24811
48750
16065
29...

result:

ok 100000 lines

Test #24:

score: 0
Accepted
time: 75ms
memory: 15748kb

input:

100000 100000
1 10
7 6
8 3
8 7
1 7
9 3
10 8
2 5
6 2
8 5
2 3
3 8
4 9
4 9
2 3
4 1
4 1
2 9
6 5
10 6
2 8
5 6
10 9
4 2
5 7
8 10
6 5
7 7
5 5
7 5
6 10
1 2
7 10
5 6
10 4
5 6
1 7
5 8
5 1
1 1
1 7
1 10
9 2
9 8
2 8
0 0
10 4
1 8
2 9
9 7
4 4
6 2
10 7
5 10
6 8
8 3
4 8
3 6
10 1
2 3
4 9
1 2
3 2
4 4
3 10
7 5
2 8
9 6
...

output:

90980
4148
26481
66183
52352
1707
5010
11562
41513
4186
9905
44902
44902
39944
34933
37356
33122
24744
16533
66183
8260
63815
54738
41513
81968
27188
11601
74542
11562
39944
40738
46544
100000
41513
34933
19883
9192
100000
23187
3370
58145
26481
37356
40738
19820
27231
3321
33122
5870
34965
24902
59...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 181ms
memory: 14328kb

input:

100000 100000
16920 19840
10231 41386
38820 28123
22445 48220
65273 14725
54341 37461
37309 38346
89318 49204
17563 46620
6200 18547
8585 85811
4158 53520
5367 18135
45995 61479
60176 54604
69845 49932
34752 86343
54172 22714
67106 1791
81239 72100
52593 48897
33004 16395
27326 51396
76573 36715
904...

output:

43529
6180
65700
23480
40397
85154
85769
56441
90410
52044
74129
37519
32556
25470
8134
79327
73561
4137
20383
80319
29834
70473
666
90574
35292
47942
16929
41871
87875
51538
28277
38977
71837
89569
62619
73414
31188
6042
88365
135
87886
57374
51061
33869
73320
73986
833
46634
14497
55071
11607
6334...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 179ms
memory: 16396kb

input:

100000 100000
80510 30388
9721 43273
40267 87543
65390 76001
77038 15874
33199 77180
23703 73089
92577 83381
37244 27711
25511 93263
36203 51427
72191 29253
75585 81599
65961 80439
57254 55591
11526 36556
84158 68297
24375 75601
2424 16884
2486 15011
80114 75230
32317 60536
53661 27802
74904 32826
1...

output:

75225
22073
8677
12476
63971
34472
70152
62739
40445
45352
14682
24315
75913
55893
1911
91500
78728
95301
17042
49369
31943
28742
2189
79551
17655
50090
33004
10997
88916
42312
79437
79206
72337
22883
25894
55092
43626
91154
47019
7317
24756
29319
82474
1899
19612
13128
85857
9766
71916
74376
56771
...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 171ms
memory: 18040kb

input:

100000 100000
24722 64079
53023 15276
79634 88362
79225 25145
55071 51471
96159 84348
44084 10360
56846 4615
95408 85606
9622 15031
60868 44114
98814 10255
89674 21401
21512 50032
67875 21498
93831 45524
13730 92755
48841 68189
13543 24767
99085 83616
9261 40668
83802 17864
16220 72318
57846 59018
8...

output:

94286
85379
89888
91498
88313
83601
94402
84061
89279
92079
97216
88168
89994
84246
90897
85745
86351
87963
84359
87398
89211
88076
82636
90567
92707
84529
93362
87930
92259
84973
82940
85710
92502
94306
84133
89477
94688
88883
89635
87601
88472
84889
86317
92827
95789
91341
83802
90631
82365
85152
...

result:

ok 100000 lines

Test #28:

score: 0
Accepted
time: 139ms
memory: 14032kb

input:

100000 100000
0 87333
0 47306
0 73616
0 83810
0 58737
0 92470
0 76873
0 82155
0 71275
0 94285
0 84390
0 86081
0 48955
0 62659
0 7736
0 61906
0 35018
0 64239
0 83486
0 45630
0 33826
0 54456
0 74126
0 32328
0 90642
0 52130
0 47228
0 74867
0 40395
0 40579
0 82415
0 1211
0 21030
0 24189
0 3690
0 98386
0...

output:

0
0
0
0
0
0
97463
0
0
0
0
0
0
65532
0
93513
11054
0
24870
87413
14693
59413
96405
0
75773
39653
0
61698
0
0
52126
0
0
55595
70498
81181
0
97398
25199
0
0
48286
52988
0
85327
64978
64451
0
0
0
28171
0
71231
0
57581
0
0
18457
0
41176
0
0
0
28454
0
58910
88736
0
20802
86195
0
0
4950
0
0
15907
0
0
0
0
5...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 137ms
memory: 13968kb

input:

100000 100000
1265 0
66200 0
23977 0
67462 0
2582 0
21654 0
96330 0
83421 0
43548 0
20762 0
63237 0
18611 0
81518 0
38930 0
65200 0
27472 0
16764 0
98231 0
369 0
19043 0
91768 0
37924 0
12639 0
9034 0
46618 0
78051 0
4952 0
27008 0
15869 0
76420 0
81000 0
46122 0
61780 0
4881 0
26128 0
81569 0
70762...

output:

0
0
53648
0
0
74532
90
48308
0
0
31128
62682
0
0
89790
68851
5421
0
0
0
11086
0
0
20888
0
0
0
0
51238
0
98603
74339
0
51949
0
43895
80241
0
0
0
62659
79786
18550
12654
0
66825
42309
77425
0
34366
41806
51554
0
37090
14922
0
0
0
0
66148
78242
0
0
2768
98798
0
0
0
83697
0
0
0
94656
0
41872
34920
3357
...

result:

ok 100000 lines

Test #30:

score: 0
Accepted
time: 53ms
memory: 13688kb

input:

100000 100000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
10000...

result:

ok 100000 lines

Subtask #3:

score: 21
Accepted

Dependency #2:

100%
Accepted

Test #31:

score: 21
Accepted
time: 223ms
memory: 17984kb

input:

100000 100000
92665 39585
18318 75712
55464 95016
91413 92286
1143 98091
80611 74738
79009 23540
38987 57835
29236 84070
82706 4071
66995 63808
18498 12274
49964 24682
74388 38237
22999 67441
3612 47396
47896 58014
6258 1844
19088 60890
61212 68488
41162 8272
31552 39640
59441 18422
29743 72631
9780...

output:

26052
82525
25458
2723
27843
542
27702
1819
19650
1921
30583
4866
5740
2956
15591
11040
4526
37595
40198
7889
14421
5944
21723
16653
2990
280
2221
16626
50446
1042
376
82
2069
2059
539
17707
2900
18460
7886
12892
8605
2309
20125
31534
7825
4858
223
17324
5709
15433
40535
91
1615
9512
25066
76178
674...

result:

ok 100000 lines

Test #32:

score: 0
Accepted
time: 213ms
memory: 16384kb

input:

100000 100000
27739 57991
27805 26806
88089 66955
19082 53745
36505 71775
88778 67018
63734 20436
45986 16662
73250 63441
99661 71052
17995 64536
14290 18482
91791 30407
59499 11855
57614 32289
82829 17348
29922 7743
32567 49735
56057 23625
44776 40225
43090 87065
58871 87865
57845 47636
26806 83912...

output:

16627
29026
59106
4403
9649
9540
43319
338
82522
71265
7192
28509
588
23711
49401
62451
41982
1722
1429
9759
3141
2783
597
30487
34727
36347
272
16739
16030
11602
65811
12480
72998
13347
54590
55665
1791
28336
39612
10498
9735
43021
1088
41710
15070
40288
12603
16387
6065
1173
4657
21210
36360
442
6...

result:

ok 100000 lines

Test #33:

score: 0
Accepted
time: 197ms
memory: 16268kb

input:

100000 100000
37455 23366
46551 98951
52751 22524
99354 91794
5655 78501
42556 12691
21257 39994
69082 35277
18879 29507
58091 98344
94386 62617
15089 47772
12582 39741
18416 51116
15943 1003
66221 48020
22677 27340
70610 2705
74085 61253
90818 35044
21555 77278
76576 4397
68570 93848
31743 81411
28...

output:

52183
27074
5219
1005
12069
13447
12459
21465
47817
547
2866
12391
13125
21877
22365
871
40713
18982
22916
3742
11751
6061
60054
41904
2355
37595
3399
21625
15427
4292
23509
39812
300
12601
57426
2007
43552
42475
36508
56084
36999
16737
5592
74765
607
22340
17766
33854
821
10557
67766
47106
7501
140...

result:

ok 100000 lines

Test #34:

score: 0
Accepted
time: 175ms
memory: 16024kb

input:

100000 100000
21392 9
44734 2
86458 3
56572 5
45737 4
60141 8
6885 0
60880 5
88197 3
4229 9
66519 7
5868 10
75499 8
33724 1
31019 6
8192 10
56763 0
37600 10
65687 8
20764 6
94595 7
10864 0
83954 3
64257 9
39381 7
22352 2
59622 3
33035 7
20759 0
69670 0
96861 8
68774 4
40459 1
45885 8
46365 1
83613 5...

output:

38375
1788
24362
33111
5428
16403
9591
8243
36425
6771
62991
1871
39644
20611
63019
9688
51847
34262
5128
20114
14420
6371
8489
565
25574
6914
6819
13780
44763
13224
19800
6235
56899
64359
6215
48824
9163
60776
20372
5287
3303
37933
44467
24015
48576
9318
16253
17095
4926
11554
5841
10668
571
6736
1...

result:

ok 100000 lines

Test #35:

score: 0
Accepted
time: 173ms
memory: 14032kb

input:

100000 100000
5 19584
10 88921
3 57705
7 58958
8 14209
3 17909
10 51267
10 1975
9 31747
0 56743
0 42665
1 35684
7 35664
2 63293
1 40337
10 91156
2 52032
2 41140
4 48372
10 29534
8 6627
4 26149
3 28670
5 96786
9 79645
0 83735
8 52825
3 49446
4 29965
1 49424
10 26317
9 89591
2 60070
3 56362
3 53400
2 ...

output:

44368
1099
9378
13932
55177
77007
2631
2474
29618
129
14846
53877
36167
6324
71886
1416
1209
12291
24095
14065
6993
17145
292
152
25517
53082
69
4420
10162
41905
12177
10147
7418
18769
903
20591
24562
16858
32098
57292
21474
38146
54976
6160
5795
1606
20006
3406
83151
26024
7886
30302
93458
40711
68...

result:

ok 100000 lines

Test #36:

score: 0
Accepted
time: 70ms
memory: 13820kb

input:

100000 100000
8 0
4 10
5 10
1 0
7 9
6 0
9 8
0 3
3 0
2 5
7 7
6 9
1 2
8 2
2 7
10 8
9 10
0 3
0 6
7 4
2 4
4 2
2 4
0 10
4 9
9 2
10 0
10 6
0 10
5 2
7 9
6 2
0 7
7 7
5 2
0 3
1 6
8 7
8 10
3 4
10 9
7 2
8 9
5 6
5 8
5 1
1 7
2 1
10 8
9 5
6 0
10 1
5 1
1 4
2 7
5 6
3 4
10 10
5 7
3 6
9 2
7 2
0 0
1 10
7 8
6 6
8 6
9 1...

output:

40630
14693
11799
14693
34879
33224
17530
82750
19968
13433
55447
46384
4962
17917
33244
3345
79462
12531
14693
51338
15010
6598
61973
15010
6785
36570
58746
5020
22662
53772
24952
3345
4199
52091
24827
91819
3358
20131
9846
49625
37281
16738
53772
10124
57132
39828
18521
8226
41389
23408
2503
14693...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 222ms
memory: 14320kb

input:

100000 100000
34446 93404
59218 73358
33242 58044
77136 46020
7857 93773
47342 60729
22182 68315
93044 8810
62564 80841
61596 77830
3562 88951
96929 58184
18165 48565
89269 44624
78578 99862
75523 86764
73468 25904
24793 25394
5519 96840
36694 89083
78485 88417
60243 55804
8136 42698
70327 78193
390...

output:

13615
1265
2172
35360
14
9468
23046
6080
18817
21978
16555
4124
0
8041
16538
10958
2227
2306
21276
25287
80811
19724
72
27976
12342
1058
6517
15794
6582
9669
7311
12394
51474
834
1874
141
9399
2600
46391
36496
25696
7
9992
22173
40686
2316
14403
24721
3372
3650
11020
66537
6090
11684
3121
1905
2173
...

result:

ok 100000 lines

Test #38:

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

input:

100000 100000
40840 31510
32100 96217
99112 85439
6492 7623
90481 63130
858 10078
24431 42002
38925 39990
90907 99254
5391 55846
85045 24654
37877 42804
14846 96652
15044 3006
55610 70915
96668 12607
87224 53734
39153 31389
249 64844
30515 84929
90334 27395
58459 98797
10267 52015
60942 84821
61247 ...

output:

10069
888
8375
16822
16489
7441
515
3052
16758
14931
4334
18776
35131
35144
8323
12162
17639
27336
27245
51198
6211
16786
16890
12460
31741
81881
6132
13310
8793
22369
11437
11552
13104
29825
25952
70211
19322
28363
20689
8178
45611
16597
21182
74
14975
54173
2621
34434
57698
1847
19671
37734
18279
...

result:

ok 100000 lines

Test #39:

score: 0
Accepted
time: 209ms
memory: 14324kb

input:

100000 100000
53506 22469
65631 23126
66581 39225
46858 18835
27068 68620
86060 28508
99596 69827
73769 59088
18935 20031
40128 64022
86966 79245
21217 93773
19000 31298
67571 25268
58566 4156
35597 83158
94525 27496
22095 4579
68632 30188
22207 61688
38199 72001
37418 83238
5115 16965
28643 10157
6...

output:

50568
55547
80966
87656
52533
8188
30400
63225
1397
2452
41286
2068
18279
5596
63088
297
31769
15726
57525
24554
42271
10698
15445
4224
20022
5663
33630
254
24973
38230
9796
37985
4695
51274
41275
12
60227
38693
90300
74578
64197
61322
57354
83237
59100
45687
1347
41411
66720
31403
23697
14535
43313...

result:

ok 100000 lines

Test #40:

score: 0
Accepted
time: 133ms
memory: 14028kb

input:

100000 100000
0 62908
0 44286
0 35900
0 636
0 81069
0 41095
0 55069
0 33978
0 96832
0 59613
0 15387
0 97561
0 59790
0 13237
0 2803
0 71781
0 56169
0 14962
0 49072
0 98106
0 78656
0 21577
0 67594
0 95141
0 26694
0 92579
0 75958
0 4183
0 9407
0 83799
0 60955
0 24262
0 36556
0 9876
0 51362
0 5708
0 769...

output:

14058
46301
8288
0
40213
0
0
48997
65768
28136
16573
76028
0
0
0
91525
30802
46840
0
21734
42082
55149
861
96305
68183
0
44621
17457
0
0
0
0
90441
0
0
0
78286
0
0
0
0
0
20781
33283
21894
97233
0
59504
78262
0
0
34602
0
86838
37610
38782
80263
31939
0
0
36599
80538
0
0
72326
0
0
0
59794
0
0
0
8480
81...

result:

ok 100000 lines

Test #41:

score: 0
Accepted
time: 148ms
memory: 13988kb

input:

100000 100000
45182 0
32434 0
70111 0
29649 0
21098 0
64730 0
28110 0
94326 0
62793 0
42328 0
26327 0
79544 0
28928 0
67860 0
77937 0
39277 0
61585 0
46347 0
7054 0
20742 0
44885 0
2987 0
9020 0
10859 0
35825 0
56004 0
36216 0
25118 0
99016 0
8903 0
10624 0
11243 0
54606 0
5114 0
12178 0
72464 0
891...

output:

81043
0
57227
44228
33662
0
39835
0
0
0
64720
49755
98403
3443
0
20751
49295
91346
84556
0
2502
88468
14122
0
62159
59275
0
0
54930
68974
85877
3396
0
14991
91529
62573
9063
93967
0
73982
0
0
75930
99605
55719
0
0
87974
5383
24478
0
0
10777
0
52551
0
64866
0
0
81816
84319
89151
19310
26645
0
33912
8...

result:

ok 100000 lines

Test #42:

score: 0
Accepted
time: 56ms
memory: 13600kb

input:

100000 100000
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 ...

output:

0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100000
0
0
100000
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
100000
100000
0
0
0
0
0
0
100000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Subtask #4:

score: 57
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #43:

score: 57
Accepted
time: 240ms
memory: 15984kb

input:

100000 100000
565202808 947984704
153915528 131046785
606381427 868085230
565035705 820745648
636886527 158249878
344249996 80730142
10849644 190176768
407396861 846442650
262129929 996836272
764872527 631148466
339347284 131889396
894286203 945772651
880702358 61935196
52356591 396688993
264344339 ...

output:

907
11514
13005
1102
65848
976
4070
47460
16568
35856
8673
43008
13921
20991
880
20249
24925
9379
1369
19325
23273
5189
250
3123
7190
3842
7745
9216
39771
42785
5735
42133
30912
1419
72933
11480
5676
1356
11209
29223
13473
4883
3022
2188
23223
5349
18534
11856
190
21163
52332
58092
13795
15458
1491
...

result:

ok 100000 lines

Test #44:

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

input:

100000 100000
630508667 110404792
845304802 982383110
410629104 882479557
660871874 938901328
896704978 68655142
438642841 366107935
79487852 78479256
198921397 44557530
220128217 663177962
597033973 418707951
520947139 423646474
594525904 974489218
330237087 109614239
231725215 110016852
391564736 ...

output:

7386
31095
3407
23269
5319
1501
2568
14443
13719
18739
30539
7560
4570
725
3069
13628
15522
2427
2502
3272
10116
49450
50
14935
2243
2134
8725
354
417
42921
83
16569
59
10368
6381
14892
7213
1415
5066
13761
29417
57544
2828
18695
8181
4415
5158
33889
28488
22521
36
9404
822
13356
47857
188
66104
487...

result:

ok 100000 lines

Test #45:

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

input:

100000 100000
758790769 65219208
803678181 257220195
583153577 477033721
656490222 895818857
830546476 68959826
365195827 726396608
870590315 62904644
880043929 549071991
576870940 683290116
425402280 623804511
704736420 628779546
201199111 518558046
727583153 32994162
337061101 264817870
725656700 ...

output:

9300
43343
34536
17549
35972
18828
8027
6152
13015
34252
33926
2736
3792
9694
2109
58072
50040
15260
8700
45201
676
71572
4160
6181
11473
22421
25981
566
19586
4072
50741
17298
17820
11872
70141
13139
3849
15173
34383
51449
37292
1719
5388
1389
32152
32699
45929
17520
8113
32994
6504
25950
51924
199...

result:

ok 100000 lines

Test #46:

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

input:

100000 100000
950809986 6
281111249 4
921371767 3
461054493 6
225759600 4
500373371 1
654674340 9
404045674 3
304803381 9
204198414 7
441745119 6
817967285 6
384582851 8
216859990 1
821338548 8
195574486 6
169983434 5
538560136 2
267532440 5
380299088 5
349329493 10
875938824 5
66393407 1
354154236 ...

output:

39343
21825
93
972
9038
51831
19193
5523
11664
8536
442
13934
1438
33547
4414
1846
4134
24633
5282
4901
51177
7938
15367
37192
19288
14309
6928
315
16497
15193
79874
13020
45321
25614
47238
16056
31261
30460
2367
1667
54630
2192
2017
5174
6115
3980
5050
31334
1555
24248
8466
3963
50044
12131
6194
22...

result:

ok 100000 lines

Test #47:

score: 0
Accepted
time: 190ms
memory: 17256kb

input:

100000 100000
4 950932494
4 535758034
0 180901007
1 349183768
9 855133529
10 406050234
7 248600135
3 262084297
5 371533737
6 607809030
4 761788008
2 565285554
5 156055992
8 108553462
8 981488919
7 728155283
3 267957670
6 736986721
5 488483121
3 599559535
7 423271918
7 821858081
8 833429760
3 1104685...

output:

14148
55834
4545
8835
20441
2707
5188
17402
21114
15074
34748
14145
1480
11920
8535
36695
12454
13190
1569
20380
6323
7868
39714
59384
33672
49583
44214
5208
39636
15324
27488
3039
26875
1788
7572
53748
3811
180
1607
17191
18078
1851
29553
15462
775
49715
49986
7103
9092
16391
2112
10725
25562
9413
...

result:

ok 100000 lines

Test #48:

score: 0
Accepted
time: 79ms
memory: 13684kb

input:

100000 100000
9 0
1 10
1 8
3 8
3 2
3 0
6 10
6 5
2 8
4 10
6 6
1 2
7 3
4 2
8 5
0 2
10 2
8 1
8 7
3 4
9 0
6 5
2 2
9 7
0 1
6 2
10 8
6 1
0 6
7 7
3 5
8 8
6 3
2 9
6 7
1 1
10 6
6 5
0 0
6 2
1 6
5 5
1 10
4 4
6 7
4 7
1 6
9 2
10 6
9 5
4 1
8 9
5 0
3 2
6 7
0 4
3 5
6 4
7 0
2 5
2 0
2 7
3 3
1 4
2 10
6 7
8 1
5 5
5 10
...

output:

0
8268
52057
0
0
0
45708
28888
0
0
29842
0
0
0
0
4177
0
0
0
0
0
0
6632
0
28888
20791
0
0
0
0
0
0
52794
23172
0
0
0
37935
29676
0
0
0
12358
0
40347
0
0
0
0
0
0
24639
0
0
24749
0
3260
814
0
0
9940
0
0
9942
54508
0
6618
41294
20791
29596
0
16566
30444
0
0
2442
0
0
0
0
0
9940
0
6618
0
0
0
0
0
4990
0
0
0...

result:

ok 100000 lines

Test #49:

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

input:

100000 100000
59058182 293428811
945096548 293526020
727723334 238996565
29450563 170102905
871559781 579612929
424442107 995856
348324992 798965265
364658181 721716186
460438123 213315345
248866154 953871715
691596702 736243541
257351907 456163153
381474771 230983028
857911134 880038301
506402253 5...

output:

51650
76238
89475
73842
9284
68937
44608
52834
71318
52990
36136
63747
71467
5401
55238
73929
23094
62541
9663
88098
14351
25244
79808
58158
40043
89269
57072
51622
47735
1534
41472
73256
27422
52313
17459
82058
71793
49157
16733
46273
29460
13838
47712
47231
40164
23579
53174
36445
18182
7097
72018...

result:

ok 100000 lines

Test #50:

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

input:

100000 100000
470746507 499793807
307941649 505349388
736745042 105259492
687288766 191019435
600020583 698360888
751341977 162804395
922479956 214758034
598891375 114709601
540911545 131414503
294583107 845585243
952519325 159900723
72599229 690462873
7686835 665423226
381974418 49495739
596449062 ...

output:

19901
17083
57633
26947
17135
5788
36921
33541
56406
4283
82000
13826
32778
2478
14075
11693
51316
293
1554
55705
28857
40208
14195
37312
61653
1772
14806
510
92825
25562
23880
44576
32073
2867
38011
24954
27518
10733
72301
28866
22965
52167
15978
56271
18840
23814
43722
55747
2643
327
29721
29953
3...

result:

ok 100000 lines

Test #51:

score: 0
Accepted
time: 222ms
memory: 16676kb

input:

100000 100000
606007520 760789451
201269023 297365926
781229749 928392572
299001195 684151134
466915263 214205102
587119479 288758974
632147185 552613437
954656963 49560767
458619109 437235544
637226869 687796500
877546586 746172454
114147950 411596706
73013029 869469937
926986743 836920997
42038916...

output:

93365
88130
69005
89048
58850
69212
89773
86824
86551
66504
68291
69818
87065
62249
88751
85500
85909
87751
80882
76121
64200
87922
92771
80528
89634
87936
83795
87118
80636
85390
50299
78553
82544
90442
65831
53132
86870
91468
68623
90035
81696
88033
89263
84131
78081
75195
50862
72820
75313
91493
...

result:

ok 100000 lines

Test #52:

score: 0
Accepted
time: 171ms
memory: 14980kb

input:

100000 100000
0 928494282
0 370004172
0 243704565
0 295421462
0 982994033
0 793904624
0 991484735
0 181703373
0 737602220
0 875868424
0 318272755
0 861318528
0 892540555
0 332252856
0 541051216
0 919446524
0 491778385
0 170042871
0 31026118
0 900541371
0 316338561
0 25844215
0 232621337
0 243916172
...

output:

94185
0
0
33204
5915
0
44126
0
18716
65027
3238
0
16962
0
93
7673
65912
41202
0
0
21555
8512
0
25979
29939
13571
0
28924
2214
12610
13047
0
25603
0
18863
0
27890
0
71763
0
2513
60343
6518
41230
48343
6742
75621
40729
29414
16908
0
0
0
0
48423
0
0
65713
0
24109
13855
26656
78331
71480
0
0
2768
0
2452...

result:

ok 100000 lines

Test #53:

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

input:

100000 100000
381792933 0
71070687 0
122519795 0
797240710 0
299745242 0
449307915 0
167133684 0
952129454 0
40289932 0
26555560 0
33466731 0
24300338 0
34002871 0
902931266 0
673155802 0
677993884 0
785166501 0
226244300 0
490828254 0
747624377 0
895978416 0
992552780 0
909134232 0
651393652 0
2364...

output:

0
0
94423
42904
0
0
23670
0
0
0
4774
0
48914
0
0
0
0
70209
0
0
60497
0
0
21752
38818
93669
81152
0
31002
0
0
0
38938
0
0
97504
22831
0
0
4641
0
49336
0
0
69416
99978
16529
0
0
0
22243
91583
0
41549
0
22981
19551
97152
0
40145
0
51309
5865
86953
36520
88247
0
0
0
13900
17283
0
0
94618
0
4869
0
80319
...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed