QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#587974#9372. Prefix of SuffixesshiqiaqiayaAC ✓60ms17488kbC++173.6kb2024-09-24 23:10:282024-09-24 23:10:28

Judging History

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

  • [2024-09-24 23:10:28]
  • 评测
  • 测评结果:AC
  • 用时:60ms
  • 内存:17488kb
  • [2024-09-24 23:10:28]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using ll = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K, class V = null_type, class C = less<>> using rb_tree = tree<K, V, C, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const ll mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

template <ll mod = mod> ll binpow(ll a, ll b, ll res = 1) {
    for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
        if (b & 1) (res *= a) %= mod;
    }
    return res;
}

vector<int> inv, fact, invfa;
auto INIT_FACT = ([](int n) {
    inv = fact = invfa = vector<int>(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        fact[i] = (ll)fact[i - 1] * i % mod, invfa[i] = (ll)invfa[i - 1] * (inv[i] = (mod - mod / i) * inv[mod % i] % mod);
    }
} (0), true);
ll C(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[m] % mod * invfa[n - m] % mod; }
ll P(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[n - m] % mod; }
ll LC(ll n, ll m) { return !m ? 1 : C(n % mod, m % mod) * LC(n / mod, m / mod) % mod; }

struct KMP : vector<int> {  // 数组表示 S[:i] 最长真前缀和真后缀的长度
    vector<int> uni;    
    KMP(const string & s = {}) : vector(s.size()), uni(s.size()) { // 从 0 开始,前缀函数
        for (int i = 1; i < size(); at(i++) += s[i] == s[at(i)]) {
            for (at(i) = at(i - 1); at(i) && s[i] != s[at(i)]; at(i) = at(at(i) - 1));
        }
    }
    KMP(const string & t, const string & s, char o = '#') : KMP(t + o + s) {}

    void Dy_ZFun(const string & s, int i) { // i 从 [0, n - 1] 都要
        static vector<int> uni; // 跳到下个 kmp[i] != kmp[kmp[i] - 1] 不同字母的位置
        if (!i) emplace_back(0), uni.emplace_back(0);
        else {
            // for (at(i) = at(i - 1); at(i) && s[i] != s[at(i)]; at(i) = at(at(i) - 1));
            // uni[i] = at(i) += s[i] == s[at(i)];
            // if (at(i) >= 1) uni[i] = s[at(i)] != s[at(at(i) - 1)] ? at(at(i) - 1) : uni[at(i) - 1];
            // for (int k = at(i - 1); k; k = s[i] == s[at(k - 1)] ? uni[k - 1] : kmp[k - 1]) 
        }
    }
};

void QAQ() {
    int n;
    cin >> n;

    vector<int> s(n), a(n), b(n), pre(n + 1), kmp(n), uni(n);

    int ans = 0, cnt = 0;

    for (int i = 0; i < n; i++) {
        cin >> s[i] >> a[i] >> b[i];
        (s[i] += ans) %= n, pre[i + 1] = pre[i] + a[i], cnt += b[i];

        int unable = 0;

        if (i > 0) {
            for (kmp[i] = kmp[i - 1]; kmp[i] && s[i] != s[kmp[i]]; kmp[i] = kmp[kmp[i] - 1]);
            uni[i] = kmp[i] += s[i] == s[kmp[i]];
            if (kmp[i] >= 1) uni[i] = s[kmp[i]] != s[kmp[kmp[i] - 1]] ? kmp[kmp[i] - 1] : uni[kmp[i] - 1];

            for (int k = kmp[i - 1]; k; ) {
                if (s[i] != s[k]) {
                    unable += b[i - k];
                }
                if (s[i] == s[kmp[k - 1]]) k = uni[k - 1];
                else k = kmp[k - 1];
            }
            if (s[i] != s[0]) {
                unable += b[i];
            }
        }

        cnt -= unable;
        ans += cnt * a[i];

        cout << ans << "\n";
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

input:

3
0 1 2
1 2 3
2 3 4

output:

2
12
18

result:

ok 3 lines

Test #2:

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

input:

100
14 14 932
64 528 396
32 293 948
27 757 520
31 620 590
41 157 353
17 858 394
20 927 729
36 722 94
44 567 360
82 123 320
22 935 893
2 142 6
45 668 346
33 625 617
15 550 105
48 691 923
75 569 300
57 768 381
31 288 541
63 829 37
12 395 25
5 959 974
57 31 635
15 880 113
79 310 959
84 618 516
69 951 9...

output:

13048
505144
778220
1483744
2061584
2207908
3007564
3871528
4544432
5072876
5187512
6058932
6191276
6813852
7396352
7908952
8552964
9083272
9799048
10067464
10840092
11208232
12102020
12130912
12951072
13239992
13815968
14702300
15007996
15761052
15934404
16122668
16309068
16858016
17299784
17661400...

result:

ok 100 lines

Test #3:

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

input:

200
159 568 113
118 305 83
124 449 131
67 501 610
68 943 507
71 611 75
162 798 171
133 607 586
153 943 955
156 437 778
153 414 456
23 639 623
177 84 221
141 887 638
87 326 405
27 90 723
6 804 167
57 197 900
96 358 490
82 92 244
84 869 315
143 761 514
128 750 4
110 113 946
130 459 543
31 893 612
92 3...

output:

64184
98649
149386
205999
312558
381601
471775
540366
646925
696306
743088
815295
824787
925018
961856
972026
1062878
1085139
1125593
1135989
1234186
1320179
1404929
1417698
1469565
1570474
1611719
1665846
1733194
1770597
1848454
1893654
1909700
2007219
2073663
2112874
2136152
2138977
2211636
225875...

result:

ok 200 lines

Test #4:

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

input:

300
203 17 783
71 81 66
12 308 609
206 245 404
205 266 424
94 169 797
111 251 757
42 990 443
261 164 8
76 307 4
231 809 184
35 943 57
48 617 332
138 1 123
46 514 784
139 334 637
269 726 923
254 18 92
30 245 815
137 600 459
89 500 593
75 422 299
256 349 138
159 899 665
142 335 974
191 180 161
296 919...

output:

13311
76734
317898
509733
718011
850338
1046871
1822041
1950453
2190834
2824281
3562650
4045761
4046544
4449006
4710528
5278986
5293080
5484915
5954715
6346215
6676641
6949908
7653825
7916130
8057070
8776647
9013896
9458640
9657522
9889290
10589292
10805400
10831239
10999584
11239182
11850705
121505...

result:

ok 300 lines

Test #5:

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

input:

1000
893 197 325
231 902 183
40 481 495
265 152 704
789 458 546
257 30 366
746 546 332
815 523 683
770 152 647
966 785 793
61 915 864
666 972 536
677 183 290
163 533 374
931 943 508
626 226 823
643 596 767
619 563 613
52 340 813
163 591 752
989 342 326
156 97 25
196 373 732
223 693 539
825 835 642
9...

output:

64025
357175
513500
562900
711750
721500
898950
1068925
1118325
1373450
1670825
1986725
2046200
2219425
2525900
2599350
2793050
2976025
3086525
3278600
3389750
3421275
3542500
3767725
4039100
4290975
4600050
4680000
4977050
5243550
5328700
5568225
5749900
5906225
5986500
6140550
6425575
6597825
6750...

result:

ok 1000 lines

Test #6:

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

input:

10000
8580 58 19
2150 140 553
5919 883 170
317 527 945
5344 7 709
7959 659 507
7187 939 849
3335 426 64
4764 262 265
8161 985 298
9284 280 622
3651 897 691
4134 185 682
2483 107 233
8425 867 526
313 574 777
4927 363 617
9582 748 482
9102 701 339
950 875 300
8414 167 489
283 960 449
2835 919 42
4475 ...

output:

1102
3762
20539
30552
30685
43206
61047
69141
74119
92834
98154
115197
118712
120745
137218
148124
155021
169233
182552
199177
202350
220590
238051
250534
256766
265658
272365
287318
293531
310289
317224
330334
338428
352849
355186
364762
378328
385301
392236
399228
407474
422009
422978
440800
45107...

result:

ok 10000 lines

Test #7:

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

input:

30000
13880 717 630
1191 299 825
26934 951 753
27101 515 619
182 545 346
7268 103 397
14684 303 868
19398 140 289
13206 176 697
17902 630 839
1162 848 736
15955 356 137
24417 510 780
4520 181 846
3314 34 957
26097 106 902
13858 363 891
23031 645 55
3772 839 241
12366 89 726
19788 426 447
7206 130 69...

output:

451710
640080
1239210
1563660
1907010
1971900
2162790
2250990
2361870
2758770
3293010
3517290
3838590
3952620
3974040
4040820
4269510
4675860
5204430
5260500
5528880
5610780
5728590
6162030
6723990
7332570
7620480
7716870
8107470
8141490
8196300
8646750
8940960
9420390
9450000
9667980
10007550
10460...

result:

ok 30000 lines

Test #8:

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

input:

60000
15141 46 199
19010 441 493
17912 498 72
52140 490 319
22639 488 113
29542 861 631
42826 636 204
54035 119 129
43166 655 738
34809 796 266
51140 553 958
51372 546 362
16130 538 274
11967 36 914
6393 181 392
13421 64 790
5904 710 67
15300 629 166
55840 406 998
26995 519 66
30498 772 245
32790 67...

output:

9154
96913
196015
293525
390637
561976
688540
712221
842566
1000970
1111017
1219671
1326733
1333897
1369916
1382652
1523942
1649113
1729907
1833188
1986816
2121539
2159150
2207905
2244322
2348797
2513171
2646302
2757742
2930275
3006293
3175045
3220218
3413049
3582000
3683689
3811447
3932837
4078505
...

result:

ok 60000 lines

Test #9:

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

input:

100000
41763 259 586
18012 415 257
49106 133 8
21008 815 804
63479 668 609
25833 967 333
87171 878 841
52931 676 498
37195 815 91
7676 715 764
76076 528 966
61688 836 66
33983 173 404
63347 432 931
95743 566 344
46797 588 984
24536 208 768
45169 165 81
82674 132 772
85254 678 526
33631 160 437
69689...

output:

151774
394964
472902
950492
1341940
1908602
2423110
2819246
3296836
3715826
4025234
4515130
4616508
4869660
5201336
5545904
5667792
5764482
5841834
6239142
6332902
6895462
7118728
7448060
7949676
8203414
8647016
9060146
9294546
9737562
10017670
10023530
10194642
10246796
10648206
11139860
11613934
1...

result:

ok 100000 lines

Test #10:

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

input:

200000
104981 915 978
72005 482 800
177948 444 819
60868 618 905
24176 877 566
90176 772 223
185967 142 556
180763 604 708
198471 724 841
34402 208 290
8187 897 955
88235 363 205
196825 836 315
97644 331 129
178234 937 695
84318 447 613
19259 154 29
131922 19 399
166202 191 667
124051 839 809
87123 ...

output:

894870
1366266
1800498
2404902
3262608
4017624
4156500
4747212
5455284
5658708
6535974
6890988
7708596
8032314
8948700
9385866
9536478
9555060
9741858
10562400
11465094
12236736
12573168
12763878
12901776
13215714
13596156
13952148
13954104
14520366
15281250
15641154
15815238
16357050
16569276
16765...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 46ms
memory: 15008kb

input:

250000
121542 607 158
231569 487 932
239941 651 529
45795 581 791
74176 655 970
91759 975 346
94309 839 207
11463 193 261
86873 925 19
44154 19 554
30042 763 99
88659 420 68
115717 893 99
241720 452 298
20794 955 560
57426 937 331
143339 797 775
60344 900 379
65644 192 326
180096 484 279
249207 16 8...

output:

95906
172852
275710
367508
470998
625048
757610
788104
934254
937256
1057810
1124170
1265264
1336680
1487570
1635616
1761542
1903742
1934078
2010550
2013078
2062690
2206470
2249130
2359730
2466380
2602576
2641602
2678732
2814770
2956812
3039762
3066780
3217828
3336486
3480582
3513288
3619306
3623888...

result:

ok 250000 lines

Test #12:

score: 0
Accepted
time: 49ms
memory: 17364kb

input:

300000
92392 788 667
125998 445 536
106789 562 630
143832 125 414
60682 87 818
230328 577 305
217466 702 568
165491 723 214
116644 442 488
28425 998 8
231786 562 161
47485 403 833
292372 99 930
99237 718 919
160725 12 853
121838 602 50
213981 589 802
242868 681 118
6625 249 562
295553 592 988
40616 ...

output:

525596
822411
1197265
1280640
1338669
1723528
2191762
2674003
2968817
3634483
4009337
4278138
4344171
4823077
4831081
5232615
5625478
6079705
6245788
6640652
7226278
7441719
7449056
7857260
8268799
8606301
8961145
9371350
9902282
10042352
10435882
10920791
11433047
11445720
11619807
11995995
1242154...

result:

ok 300000 lines

Test #13:

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

input:

10
7 518 71
0 121 862
6 607 138
3 513 337
8 873 337
6 647 917
5 417 1000
1 703 826
5 728 984
6 371 864

output:

36778
45369
88466
124889
481073
527010
556617
606530
658218
684559

result:

ok 10 lines

Test #14:

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

input:

300000
0 656 16
289505 337 134
284112 597 249
125908 340 198
35807 659 432
176485 203 109
34993 630 534
159464 900 189
251564 525 722
243164 591 933
233708 956 818
218412 245 398
214492 487 25
206699 587 984
219699 388 471
30743 20 816
14104 463 222
228887 460 311
3108 721 723
79005 43 882
78317 439...

output:

10496
15888
174093
264193
723516
865007
1640537
2748437
2756837
2766293
2781589
2785509
2793301
3380301
3569257
3585897
3971113
4496893
5320996
5321684
5328708
5331972
5338436
5374847
5408771
5620346
5838121
6584511
6682059
7001091
8582958
8586430
8591102
9349742
9692438
9701110
9701942
9763278
9793...

result:

ok 300000 lines

Test #15:

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

input:

300000
1 710 687
112231 151 233
273311 570 425
106660 563 20
19879 148 305
218203 293 631
16912 714 482
126395 768 498
116315 338 66
293477 755 760
275171 692 666
55151 690 800
137501 982 29
173831 875 240
36956 26 767
19094 39 863
292302 282 289
17070 484 954
282950 411 889
24341 152 925
99180 938 ...

output:

487770
626690
1393340
1780121
1881797
2083088
2573606
3483686
3906524
5424829
6244849
7062499
8226169
9263044
9280906
9307699
9582931
10517051
11675660
12200820
13740078
13905920
13965151
14345749
14922142
15452506
16315308
17334207
18020151
18770944
19847783
20533145
21332020
21426574
22101304
2310...

result:

ok 300000 lines

Test #16:

score: 0
Accepted
time: 60ms
memory: 17336kb

input:

300000
0 342 218
225444 175 812
45194 762 184
20127 331 432
247968 237 403
100792 120 129
74632 113 110
49998 237 155
298331 343 101
188915 408 749
99970 985 443
48885 405 477
187995 622 738
221123 629 412
260618 436 67
234958 539 631
119167 874 524
168547 97 400
147400 354 846
70744 446 27
184159 5...

output:

74556
254806
1179874
1252032
1399209
1425369
1450003
1501669
1611086
1700030
2351115
2812005
3978877
5139382
5765042
6480834
7031454
7052600
7429256
7915842
8035960
8063646
8175698
8472538
8552762
8750706
8966566
9669946
10704433
10738569
10816395
11668000
11883820
11935050
12716145
12770645
1307665...

result:

ok 300000 lines

Test #17:

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

input:

300000
1 599 472
17272 165 190
239393 446 244
220056 323 806
288788 604 743
3700 410 719
110181 537 355
266081 539 470
120328 893 538
298833 902 384
126721 300 398
165721 5 487
160926 755 37
76631 408 29
172223 270 544
197902 548 555
241134 888 723
121999 129 463
1383 800 518
153383 122 995
95800 48...

output:

282728
360608
679944
911212
1196300
1389820
1833919
2279672
2701168
3473280
3734280
3739075
4123370
4327778
4602098
5158866
5578002
5698617
6446617
6504201
6565065
7370245
8883045
10823333
11920153
11941237
12596845
13404317
13908110
15126350
15842750
16335950
16982245
17714115
18205955
18399785
189...

result:

ok 300000 lines

Test #18:

score: 0
Accepted
time: 52ms
memory: 17412kb

input:

300000
1 961 764
165797 639 239
124879 795 175
117500 362 426
286719 285 944
68980 701 287
232228 970 595
91149 991 509
29606 506 622
270735 846 380
93778 601 464
249840 559 668
138234 273 79
69138 834 5
261905 353 632
264327 363 483
82989 47 149
17376 790 109
232246 570 333
96767 600 49
208967 678 ...

output:

734204
1375121
1982501
2413281
2631021
3367772
4108852
5370395
6329265
7406223
8450160
9161767
9530863
10238095
10535674
11017012
11082624
12067754
12503234
12991034
13776158
14210300
14467004
14836573
15172539
16441380
18727362
18962397
19894133
20009497
21243037
23339797
24856697
24969005
25557675...

result:

ok 300000 lines

Test #19:

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

input:

300000
3 383 741
16200 685 25
91487 337 515
141772 711 779
214921 586 275
80693 74 986
25860 460 595
285000 100 71
210901 278 343
4902 424 374
290720 283 109
50170 70 86
284649 765 150
17784 523 250
230241 60 67
185780 90 55
119090 206 104
266446 740 633
149686 987 24
269860 183 331
69290 483 356
11...

output:

283803
808513
1058230
1585081
2019307
2074141
2415001
2489101
2695099
3009283
3249833
3315353
3882218
4269761
4314221
4380911
4533557
5550317
6930143
7130711
7488614
8140694
8806853
9248489
9537965
9706172
10034435
10045550
10522754
11017001
11414177
11562377
11754296
12137032
12342289
12823939
1338...

result:

ok 300000 lines

Test #20:

score: 0
Accepted
time: 57ms
memory: 17084kb

input:

300000
1 776 83
235592 641 187
182389 397 773
149439 616 887
151918 221 36
237549 723 455
148575 697 569
294131 712 146
131082 392 502
41315 687 831
13396 424 158
225861 156 160
187953 265 773
261112 660 943
296152 120 495
193432 675 23
137408 786 292
142657 653 543
197783 330 6
168412 393 956
13343...

output:

64408
117611
150562
748082
962452
1351426
1805870
1968918
2058686
2686604
3074140
3112048
3338888
3903848
4006568
4062593
4357343
4602218
4631588
4666565
5385179
5556918
6086022
6583227
6742567
7140901
7982945
8193883
8204923
8216587
8366275
8736226
8932822
9161803
9593559
9630704
10067132
10611050
...

result:

ok 300000 lines

Test #21:

score: 0
Accepted
time: 58ms
memory: 17300kb

input:

300000
0 6 130
299221 499 412
234352 148 358
215110 821 93
32028 47 506
21546 453 611
285874 764 929
19752 836 710
211069 496 166
64255 377 630
15244 676 620
227363 103 615
150630 897 486
34020 955 775
209868 872 248
180253 512 509
286717 8 307
285678 498 109
220939 509 458
154768 357 216
108357 724...

output:

780
65650
84890
267973
278454
614127
1180251
1288931
1435747
1484757
1572637
1649372
1765982
1890132
2219748
2413284
2414324
2479064
2545234
2591644
2685764
2805624
3567728
3757376
4094528
4427388
4536198
4662948
5149785
5158235
5392757
5497927
5544077
5566177
5591917
5792084
5872034
5957834
6015294...

result:

ok 300000 lines

Test #22:

score: 0
Accepted
time: 50ms
memory: 17280kb

input:

300000
0 499 459
70959 469 519
212278 707 118
187765 471 501
271576 595 830
298470 121 486
184125 881 220
57762 310 738
215472 734 972
178566 828 572
98514 640 916
104754 434 269
205546 762 230
280528 747 447
31936 651 285
156596 626 129
189440 356 691
166905 772 164
112556 57 265
86393 506 846
1541...

output:

229041
687723
1012236
1228425
1501530
1615875
2642240
2784530
3121436
3501488
3795248
3994454
4519472
5368064
6143405
6710561
7033097
7387445
7413608
7645862
7930901
8315033
8389850
8747480
9078878
9466274
10265450
10441247
10721237
11636753
11829533
12053525
12182963
12338105
12417971
12738353
1298...

result:

ok 300000 lines

Test #23:

score: 0
Accepted
time: 57ms
memory: 17344kb

input:

300000
2 748 571
172894 912 718
197325 492 604
216395 728 187
100707 343 97
204852 832 508
29781 934 729
15580 403 643
85468 129 809
207447 946 50
267280 214 593
145088 64 1
108481 356 254
205203 341 467
10493 62 202
262566 27 625
247148 551 721
232528 453 273
273866 842 416
42812 68 223
260532 922 ...

output:

427108
1602676
1883608
2299296
2495149
2970221
4184421
4414534
4592554
5132720
5254914
5291522
5494798
5689509
5737435
5752852
6067473
6326136
7157190
7239470
8026858
8086242
8238128
8408857
9493193
9614816
9786116
9819983
10364079
10587090
11106700
11356798
11469856
11802178
12261262
12326927
12430...

result:

ok 300000 lines

Test #24:

score: 0
Accepted
time: 54ms
memory: 17252kb

input:

300000
2 118 279
267080 249 789
1149 682 492
110871 388 827
2616 392 789
193250 679 108
230478 935 383
269613 994 383
292287 402 322
180126 155 727
136884 561 675
280365 834 958
47677 202 106
291318 896 627
41337 680 797
151616 788 176
93077 544 5
241301 444 116
117424 515 187
177433 100 892
149533 ...

output:

32922
298854
489132
597384
706752
969525
1230390
1507716
1619874
1663119
1819638
2052324
2108682
2358666
2548386
2906926
3058702
3182578
3422568
3450468
3512685
3584323
3598363
3842209
4104469
4312324
4452103
4687276
5761066
6243298
6492445
6542665
6766144
7028962
7067185
7145026
7303498
7516375
776...

result:

ok 300000 lines

Test #25:

score: 0
Accepted
time: 58ms
memory: 17488kb

input:

300000
3 202 286
242229 250 355
170729 390 965
59188 23 350
52613 257 767
81989 937 90
114008 991 229
130582 123 781
95403 240 878
26764 122 875
291874 910 346
16753 960 516
42193 672 424
150002 908 158
46850 177 168
266492 757 160
228867 624 752
50404 378 29
242298 847 138
183167 897 45
226625 94 2...

output:

57772
129272
240812
247390
518011
785993
1069419
1104597
1173237
1208129
1783249
2057809
2250001
2653153
2733511
3071133
3249597
3357705
3716833
3973375
4000259
4229759
4374475
4440827
4446261
4464279
4470285
4690791
5206761
5875993
6001547
6281255
6438269
6652197
6844389
7030192
7732714
7993390
812...

result:

ok 300000 lines

Test #26:

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

input:

300000
1 550 720
204001 865 139
60966 233 900
251120 726 499
28400 155 712
216799 154 687
121 920 907
271242 857 335
254201 905 545
9376 809 24
166576 374 682
197295 127 647
23685 816 970
36167 605 919
200567 585 93
79365 860 906
60167 841 227
54646 85 276
269987 919 477
208306 595 991
90262 242 935...

output:

396000
1139035
1548882
2071602
2183202
2399880
4528760
5145800
6290625
7333426
7602706
7776315
8363835
8799435
9220635
9839835
10445355
10530015
11191695
12209740
12383980
13614564
13756404
13932342
14156982
14626422
15171462
15445827
16064307
16332723
16579107
16720947
16725987
17421507
17434143
17...

result:

ok 300000 lines

Test #27:

score: 0
Accepted
time: 60ms
memory: 17340kb

input:

300000
0 779 632
107672 620 661
206013 635 644
104692 548 207
244921 569 962
185313 531 904
149720 731 208
135681 667 583
14136 387 310
249582 961 767
107234 467 52
267319 97 215
155090 31 53
127191 334 575
144292 744 21
98500 774 516
93695 543 840
39115 780 775
125276 829 365
183938 672 880
67875 1...

output:

492328
1293988
1695308
2155080
2514688
2850280
3464320
3885864
4250418
5892767
6332681
6444910
6472810
6755708
7401500
8306306
8660885
9774725
10316062
11332126
11450310
11533316
12076850
12107342
12316534
12442934
13057870
13967950
14464490
15006870
15751446
15864458
16280482
16657279
17578927
1774...

result:

ok 300000 lines

Test #28:

score: 0
Accepted
time: 54ms
memory: 17420kb

input:

300000
3 992 840
66722 922 875
192240 98 715
109923 850 701
72 873 697
154779 419 884
102817 830 851
5619 339 714
20859 723 324
13540 246 504
282916 326 351
194648 400 407
158647 133 148
46930 503 199
124313 563 332
64477 477 141
196538 919 926
24580 336 31
31923 556 155
147646 527 601
4966 57 951
2...

output:

833280
1607760
1690080
2999930
4345223
4697183
5394383
5679143
6286463
6617087
7005353
7341353
7453073
7975690
8635526
9103463
9875423
10168079
10652355
11095035
11142915
11532705
12187065
12376905
12943065
13377065
14234215
14586840
15347600
15761285
15821521
16581721
17344021
17365662
17585182
177...

result:

ok 300000 lines

Test #29:

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

input:

28
1 522 575
10 426 445
5 772 81
9 447 629
8 497 202
9 775 325
22 982 784
21 417 156
22 932 902
2 728 537
1 857 739
1 918 211
8 679 506
23 340 568
11 868 16
11 940 263
14 593 449
24 991 310
0 355 68
18 431 580
2 757 218
9 934 328
14 676 355
23 221 80
11 922 545
5 511 67
13 467 674
26 691 504

output:

300150
545100
1051532
1589720
2188108
3373083
5325299
6154295
8847775
10685975
12849900
15361548
15895242
16355602
17051738
17839458
18336392
18906217
19134482
19411615
20063392
20970306
21626702
21858973
22462883
22756708
23339991
24085580

result:

ok 28 lines

Test #30:

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

input:

300000
222211 801 726
240685 475 450
282085 475 730
276735 530 374
268335 982 26
103843 876 319
204343 742 791
69671 942 238
227603 714 862
3179 392 586
103195 517 878
11535 809 869
170694 806 771
28974 529 325
26069 632 327
198165 758 229
54407 395 180
225412 847 209
195582 921 578
175554 108 182
3...

output:

581526
1140126
2045476
3253876
5518368
7817868
10352540
13794608
17019032
19019016
22110676
27651517
33793237
37996142
43224046
49667804
53096799
60626629
69346657
70388857
76724603
77531419
88838563
94494703
97503643
106662727
109460667
114570342
122531743
133975897
139390783
145676824
158983024
16...

result:

ok 300000 lines

Test #31:

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

input:

300000
38339 691 618
298983 484 549
212189 819 420
49749 621 869
217469 477 570
138135 905 730
95213 985 313
90710 776 203
12332 110 246
161644 182 510
279568 523 717
58918 665 299
153376 986 498
206406 62 950
209040 39 564
142828 700 257
292946 469 173
248817 959 247
111014 257 851
121406 607 627
1...

output:

427038
726150
1576272
2220870
2987886
4443126
6335311
7826007
8064377
8458771
9967103
11884963
15219615
15429299
15583193
18345393
20277204
24227325
25504615
28521405
29456297
30137201
33249353
33657313
39177061
44402593
46177937
48033317
53466293
53739503
58885042
61309464
70548360
75993372
8422141...

result:

ok 300000 lines

Test #32:

score: 0
Accepted
time: 57ms
memory: 17336kb

input:

300000
21763 860 867
229246 798 256
186663 305 937
119842 765 21
93625 922 286
224172 604 915
185434 719 878
168783 253 57
71268 566 358
169326 552 109
87429 312 866
151712 319 718
51201 425 357
55704 99 64
184019 995 284
260793 117 35
48657 827 883
23131 94 485
7647 187 534
136963 583 435
53263 375...

output:

745620
1437486
1701921
2381241
3199977
3736329
5006083
5452881
6452437
7487437
8072437
8670562
9619162
9840130
12060970
12326209
14201018
14414116
14937903
16570886
17621261
18913594
19323626
20315757
23238757
25762807
27449457
31462872
32747932
32901372
33606090
39171125
42252868
42710248
47848348
...

result:

ok 300000 lines

Test #33:

score: 0
Accepted
time: 58ms
memory: 17332kb

input:

300000
5187 403 549
269759 292 257
55851 136 522
251014 586 790
127254 949 131
267753 751 556
3473 37 726
248140 489 91
113574 553 836
61045 554 844
67581 782 92
51896 674 825
128066 428 925
169137 291 61
5206 600 703
10433 292 440
95615 170 235
126514 896 836
75218 640 30
132405 644 283
107015 946 ...

output:

221247
381555
456219
777933
1423253
1933933
1959093
2291613
3129961
3969825
5155337
6177121
7221869
7932200
9396800
10109572
10564492
12962188
14674828
16398172
19288202
21866622
22465402
25049932
27251092
29844012
31673332
31829372
32993358
33462302
35706534
38273165
40047098
44230996
47942839
5269...

result:

ok 300000 lines

Test #34:

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

input:

300000
121315 801 259
108200 738 549
43551 689 944
59659 644 764
215443 226 591
218933 81 791
28227 351 519
86170 372 209
190129 374 619
120009 925 701
110783 553 434
84475 177 334
248300 566 888
202915 360 984
291255 560 107
122239 301 676
266423 475 110
266916 682 856
188355 91 257
14375 281 653
6...

output:

207459
398601
577052
743848
802382
887432
1255982
1646582
2039282
3010532
3831184
4093852
4933796
5468036
6299076
6949236
7975236
9448356
9644916
10251876
10645638
10690898
11915181
13881728
13954144
15900979
17301334
18801877
18858802
20379838
22518125
24257545
24533453
25433153
27532453
27606397
3...

result:

ok 300000 lines

Test #35:

score: 0
Accepted
time: 50ms
memory: 17332kb

input:

300000
104739 411 888
32239 933 403
29234 840 879
126796 122 700
60817 75 930
239107 60 287
37131 379 893
254600 431 750
12488 56 849
156234 270 419
17721 998 398
285173 745 205
9632 895 52
161565 490 922
88894 950 49
91026 351 328
90000 324 734
40998 844 618
145250 534 858
200724 126 265
87157 245 ...

output:

364968
1193472
1939392
2047728
2114328
2167608
2842607
3610218
3709954
4190824
5968262
7295107
8935642
9833812
11575162
12218545
12812437
14359489
15796483
16135549
16794844
17376100
19714579
21140809
23922679
25307500
28260562
29654554
29746264
32039014
34868310
36931946
36961114
39214342
42364486
...

result:

ok 300000 lines

Test #36:

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

input:

300000
220867 381 331
87236 73 55
177177 331 803
192727 531 1
289498 366 964
42766 576 160
101223 387 360
245372 79 881
142104 403 294
67772 987 299
196639 819 950
76543 412 523
51613 429 120
80778 124 633
202736 894 317
28290 123 441
254327 566 420
114024 892 683
222688 491 167
246363 373 724
22515...

output:

126111
150274
259835
435596
556742
747398
875495
971243
1459679
2655923
3648551
4147895
4667843
4818131
6185057
6373124
7238538
8602406
9353145
9923462
10189508
11373824
12521360
12590016
14487864
14728160
14926772
16846688
18554438
20251838
23249888
23387888
23425838
25933988
26316938
27038074
2793...

result:

ok 300000 lines

Test #37:

score: 0
Accepted
time: 54ms
memory: 17460kb

input:

300000
71587 508 2
161176 526 919
38641 427 301
79118 656 807
245922 988 928
172074 394 532
37799 239 11
167293 238 442
63635 808 179
7992 152 14
158997 591 737
93357 964 484
86989 862 448
159095 134 394
1354 703 259
4083 912 810
35829 452 45
24282 936 372
291263 29 79
26040 103 993
170878 454 613
2...

output:

1016
2068
2922
4234
6210
6998
7476
7952
154200
181712
288683
463167
619189
643443
770686
935758
1037910
1249446
1256000
1279278
1381882
1487424
1606074
1793428
2340988
2628808
3165838
3554863
3691168
3729193
3791203
4098913
4398704
4960490
4981106
5649408
6007611
6640694
6713709
7553811
7835197
8967...

result:

ok 300000 lines

Test #38:

score: 0
Accepted
time: 46ms
memory: 17480kb

input:

300000
12450 233 666
72425 725 627
220045 260 812
159932 42 402
31668 393 804
131890 577 734
260702 803 537
246940 97 361
65345 897 752
217599 289 353
115585 45 928
108024 848 936
164681 320 5
282511 518 820
165722 204 360
38622 888 935
178006 993 117
314 575 103
200200 792 915
14423 209 199
129261 ...

output:

155178
638028
811188
839160
1100898
1485180
2019978
2084580
2681982
2874456
2904426
4262922
4775562
5605398
5932206
7354782
8945568
9866718
11135502
11470320
12692646
13024260
13829835
15289185
15440985
15879135
15917085
16686435
17228085
17348835
18894435
20031210
20610810
22379594
23521858
2377791...

result:

ok 300000 lines

Test #39:

score: 0
Accepted
time: 52ms
memory: 17332kb

input:

300000
10679 981 367
51947 246 321
166904 172 456
173512 770 39
238887 698 336
112777 291 382
141926 33 757
258908 978 391
110289 231 216
258698 799 885
19822 323 801
67136 486 296
166753 588 985
14881 53 206
189340 106 38
75579 640 501
56014 595 699
261570 389 723
287968 152 485
231270 248 502
2317...

output:

360027
450309
513433
796023
1052189
1158986
1171097
1530023
1614800
1908033
2026574
2204936
2420732
2440183
2479085
2713965
2932330
3075093
3130877
3221893
3308872
3555496
3618620
3656788
4013145
4259402
4529881
4541992
4837427
4859080
5199289
5547201
5846757
5880041
6045833
6371765
6931941
7488349
...

result:

ok 300000 lines

Test #40:

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

input:

300000
231321 27 524
187525 615 748
276658 99 84
25663 420 608
271467 150 396
296640 333 545
269103 462 950
242397 687 65
187617 988 702
250857 860 472
267184 12 855
15609 667 761
93021 662 76
156765 853 906
1618 255 638
37934 914 904
55358 526 868
32872 946 312
30679 87 615
16305 269 655
8203 115 1...

output:

14148
336408
388284
608364
686964
861456
1103544
1463532
1981244
2431884
2438172
2787680
3134568
3581540
3715160
4194096
4469720
4965424
5011012
5151968
5212228
5226900
5494140
5672824
5949496
6000848
6410092
6671568
7105964
7352768
7757296
8083748
8345224
8791672
8811060
9052100
9120744
9318292
941...

result:

ok 300000 lines

Test #41:

score: 0
Accepted
time: 57ms
memory: 17352kb

input:

300000
147013 763 337
155488 240 237
222536 141 715
269332 509 64
143158 920 554
137528 97 430
182916 652 924
261263 587 461
39013 601 92
113739 54 475
241623 749 496
182878 667 656
192054 873 667
48166 157 905
133544 332 692
179293 307 791
95832 214 398
2792 905 230
266972 286 398
176861 487 38
220...

output:

257131
338011
385528
557061
867101
899790
1119514
1317333
1519870
1538068
1790481
2015260
2309461
2362370
2474254
2577713
2649831
2954816
3051198
3215317
3243962
3518954
3648699
3750136
4047707
4225643
4430876
4482437
4780682
4855159
4899306
4907731
5120378
5285845
5317186
5560500
5805499
5948724
60...

result:

ok 300000 lines

Extra Test:

score: 0
Extra Test Passed