QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810007#5110. Splitstreamucup-team173AC ✓85ms5296kbC++202.3kb2024-12-11 19:05:312024-12-11 19:05:32

Judging History

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

  • [2024-12-11 19:05:32]
  • 评测
  • 测评结果:AC
  • 用时:85ms
  • 内存:5296kb
  • [2024-12-11 19:05:31]
  • 提交

answer

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

using ll = long long;

void solve() {
    int m, n, Q;
    cin >> m >> n >> Q;
    vector<string> op(n + 1);
    vector<int> x(n + 1), y(n + 1), z(n + 1);
    vector<int> sz(4 * n, -1), fr(4 * n);
    sz[1] = m;
    for(int i = 1; i <= n; i++) {
        cin >> op[i] >> x[i] >> y[i] >> z[i];
        if(op[i][0] == 'S') {
            fr[y[i]] = fr[z[i]] = i;
            // sz[z[i]] = sz[x[i]] / 2, sz[y[i]] = sz[x[i]] - sz[z[i]];
        } else {
            // sz[z[i]] = sz[x[i]] + sz[y[i]];
            fr[z[i]] = i;
        }
    }
    function<int(int)> getSz = [&](int cur) {
        if(sz[cur] != -1) return sz[cur];
        int t = fr[cur];
        if(op[t][0] == 'S') {
            sz[z[t]] = getSz(x[t]) / 2, sz[y[t]] = getSz(x[t]) - getSz(z[t]);
        } else {
            sz[z[t]] = getSz(x[t]) + getSz(y[t]);
        }
        return sz[cur];
    };
    while(Q--) {
        int pos, val;
        cin >> pos >> val;
        auto slv = [&]() {
            while(pos > 1) {
                if(val > getSz(pos)) {
                    cout << "none\n";
                    return;
                }
                int t = fr[pos], npos, nval;
                if(op[t][0] == 'S') {
                    if(y[t] == pos) {
                        npos = x[t], nval = 2 * val - 1;
                    } else {
                        npos = x[t], nval = 2 * val;
                    }
                } else {
                    int szmn = min(getSz(x[t]), getSz(y[t]));
                    if(val <= 2 * szmn) {
                        if(val % 2) nval = (val + 1) / 2, npos = x[t];
                        else nval = (val + 1) / 2, npos = y[t];
                    } else {
                        if(getSz(x[t]) > getSz(y[t])) npos = x[t];
                        else npos = y[t];
                        nval = val - szmn;
                    }
                }
                pos = npos, val = nval;
            }
            cout << val << '\n';
        };
        slv();
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}
/*
5 8 1
M 8 9 13
S 2 4 5
S 1 2 3
M 6 5 8
S 4 9 10
S 10 14 15
S 3 6 7
S 7 11 12
8 2

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

5 8 26
M 8 9 13
S 2 4 5
S 1 2 3
M 6 5 8
S 4 9 10
S 10 14 15
S 3 6 7
S 7 11 12
2 3
2 4
3 2
3 3
4 2
4 3
5 1
5 2
6 1
6 2
7 1
7 2
8 2
8 3
9 1
9 2
10 1
10 2
11 1
11 2
12 1
13 3
13 4
14 1
14 2
15 1

output:

5
none
4
none
5
none
3
none
2
none
4
none
3
none
1
none
5
none
4
none
none
3
none
5
none
none

result:

ok 26 lines

Test #2:

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

input:

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

output:

1
3
999999999
499999999
333333331
999999997
499999997
333333329
2
4
1000000000
500000000
333333332
999999998
499999998
333333330
1
5
999999997
499999997
333333329
999999993
499999993
333333325
3
7
999999999
499999999
333333331
999999995
499999995
333333327
2
6
999999998
499999998
333333330
999999994...

result:

ok 1000 lines

Test #3:

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

input:

1000000000 8190 1000
S 1 2 3
M 8193 8194 8192
S 2 4 5
M 8195 8196 8193
S 3 6 7
M 8197 8198 8194
S 4 8 9
M 8199 8200 8195
S 5 10 11
M 8201 8202 8196
S 6 12 13
M 8203 8204 8197
S 7 14 15
M 8205 8206 8198
S 8 16 17
M 8207 8208 8199
S 9 18 19
M 8209 8210 8200
S 10 20 21
M 8211 8212 8201
S 11 22 23
M 821...

output:

1
2
1000000000
500000000
333333333
999999999
499999999
333333332
1
1
3
3
999999999
999999999
499999999
499999999
333333331
333333331
999999997
999999997
499999997
499999997
333333329
333333329
2
2
4
4
1000000000
1000000000
500000000
500000000
333333332
333333332
999999998
999999998
499999998
4999999...

result:

ok 1000 lines

Test #4:

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

input:

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

output:

1
1
536870913
1000000000
2
999999998
3
999999999
4
999999996
5
999999995
6
999999994
7
999999997
8
999999992
9
999999991
10
999999990
11
999999989
12
999999988
13
999999987
14
999999986
15
999999993
16
999999984
17
999999983
18
999999982
19
999999981
20
999999980
21
999999979
22
999999978
23
9999999...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 85ms
memory: 4880kb

input:

1000000000 10000 1000
S 1 2 3
S 2 4 5
M 5 3 6
S 4 7 8
M 8 6 9
S 7 10 11
M 11 9 12
S 10 13 14
M 14 12 15
S 13 16 17
M 17 15 18
S 16 19 20
M 20 18 21
S 19 22 23
M 23 21 24
S 22 25 26
M 26 24 27
S 25 28 29
M 29 27 30
S 28 31 32
M 32 30 33
S 31 34 35
M 35 33 36
S 34 37 38
M 38 36 39
S 37 40 41
M 41 39 4...

output:

1
999999998
536870913
999999996
268435457
999999994
134217729
999999992
805306369
999999990
67108865
999999988
402653185
999999986
33554433
999999984
671088641
999999982
201326593
999999980
939524097
999999978
16777217
999999976
335544321
999999974
100663297
999999972
469762049
999999970
8388609
999...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 14ms
memory: 5296kb

input:

1000000000 10000 120
S 1 2 3
M 3 2 4
S 4 5 6
M 6 5 7
S 7 8 9
M 9 8 10
S 10 11 12
M 12 11 13
S 13 14 15
M 15 14 16
S 16 17 18
M 18 17 19
S 19 20 21
M 21 20 22
S 22 23 24
M 24 23 25
S 25 26 27
M 27 26 28
S 28 29 30
M 30 29 31
S 31 32 33
M 33 32 34
S 34 35 36
M 36 35 37
S 37 38 39
M 39 38 40
S 40 41 42...

output:

1
999999999
3
999999997
5
999999995
7
999999993
9
999999991
11
999999989
13
999999987
15
999999985
17
999999983
19
999999981
2
1000000000
4
999999998
6
999999996
8
999999994
10
999999992
12
999999990
14
999999988
16
999999986
18
999999984
20
999999982
2
999999999
1
1000000000
4
999999997
3
999999998...

result:

ok 120 lines

Test #7:

score: 0
Accepted
time: 9ms
memory: 4840kb

input:

1000000000 9998 260
S 1 2 3
S 2 4 5
S 3 6 7
M 4 6 8
M 5 7 9
S 8 10 11
S 9 12 13
M 10 12 14
M 11 13 15
S 14 16 17
S 15 18 19
M 16 18 20
M 17 19 21
S 20 22 23
S 21 24 25
M 22 24 26
M 23 25 27
S 26 28 29
S 27 30 31
M 28 30 32
M 29 31 33
S 32 34 35
S 33 36 37
M 34 36 38
M 35 37 39
S 38 40 41
S 39 42 43
...

output:

1
999999997
5
999999993
9
999999989
13
999999985
17
999999981
21
999999977
25
999999973
29
999999969
33
999999965
37
999999961
2
999999998
6
999999994
10
999999990
14
999999986
18
999999982
22
999999978
26
999999974
30
999999970
34
999999966
38
999999962
3
999999999
7
999999995
11
999999991
15
99999...

result:

ok 260 lines

Test #8:

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

input:

1000000000 10000 1000
S 2816 2882 2883
S 625 669 670
S 6854 7128 7129
M 5200 5017 5204
M 14100 14126 14151
M 13883 13804 13914
M 6816 6875 6901
M 11434 11803 11832
S 1681 1710 1711
S 1271 1312 1313
S 12100 12196 12197
M 347 378 456
M 4096 4064 4190
S 9177 9253 9254
M 554 225 746
M 10210 10256 10345
...

output:

410542848
488844679
937935067
819832776
719109937
692579778
736124132
68676658
543140981
273960384
244177174
146341334
492672362
52284117
658245275
542648314
373316895
325695562
344652426
896047680
626880168
425102056
481091069
406672794
530596564
889101874
842378664
486416028
643174340
754279819
33...

result:

ok 1000 lines

Test #9:

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

input:

1000000000 10000 1000
M 5215 5209 5225
S 6624 6750 6751
S 12896 12936 12937
S 5790 5819 5820
S 1101 1160 1161
S 11444 11500 11501
S 11803 11909 11910
S 11713 11771 11772
S 4227 4295 4296
S 8171 8267 8268
S 6511 6659 6660
M 13671 13774 13823
M 183 306 392
S 11310 11868 11869
M 4599 4401 4623
M 13434 ...

output:

158545516
276771801
872580399
227403884
326752219
708606434
866158890
578794373
549989532
721061337
843206532
99079001
475183478
883716291
579165343
555386147
336634476
739477362
485935976
265683774
771204600
107456831
845075569
414509171
349595259
357305487
616396118
205650066
298870564
465702962
4...

result:

ok 1000 lines

Test #10:

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

input:

1000000000 10000 1000
M 9932 9892 9977
M 8446 8364 8573
M 12477 12381 12493
S 7746 7826 7827
M 2698 2653 2735
M 9532 9541 9581
S 2334 2443 2444
S 8507 8726 8727
S 8512 8611 8612
M 1964 1959 2054
M 1218 1209 1256
M 8633 8583 8707
M 11304 11219 11348
M 5544 5501 5724
M 13579 13789 13793
S 6811 6948 69...

output:

358216369
765714662
720619982
383094630
583222016
403904399
540799071
732725672
529435876
467351271
344056601
570019702
221689159
201296808
982834620
39561719
777523667
846368600
271296
384939959
513016697
736586673
272490880
913146907
78750430
191506974
99535212
616919370
317530836
761192053
650871...

result:

ok 1000 lines

Test #11:

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

input:

1000000000 10000 1000
S 13981 14119 14120
M 4081 4061 4355
M 5542 5302 5711
S 7989 8330 8331
S 3733 3767 3768
S 14329 14364 14365
S 8472 8501 8502
M 13897 13909 13957
S 5940 5971 5972
S 2642 2843 2844
S 5699 5702 5703
M 464 392 502
S 717 980 981
M 13890 13671 13902
S 6210 6224 6225
S 10149 11187 111...

output:

946583475
39950867
12114520
344042237
925236152
196637666
522940481
585398886
153165178
111583555
605886099
982385470
322756559
612482216
897028405
972371026
571912484
93984365
630146423
284805281
584957467
351316787
631855216
707739262
808047962
89733919
834604257
813408335
454854794
759626715
5796...

result:

ok 1000 lines

Test #12:

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

input:

1000000000 10000 1000
S 14044 14074 14075
S 10989 11010 11011
S 3009 3171 3172
M 1137 1186 1222
S 13599 13802 13803
S 345 506 507
S 10014 10147 10148
M 11082 11316 11319
S 13661 13776 13777
S 18 20 21
S 14734 14780 14781
M 4887 4827 4888
S 5241 5279 5280
M 9803 9583 9806
S 13548 13589 13590
S 2439 2...

output:

373564651
135588323
235943754
310533534
357785906
269064756
846167599
701246756
372231499
246040914
128072793
305568608
131705549
141589287
379549707
264932775
106219309
675198886
11065755
143823582
201985355
560673344
890446547
435573742
295516854
942017776
426261404
471127122
628046718
577131205
9...

result:

ok 1000 lines

Test #13:

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

input:

6807 1363 1000
S 166 284 285
M 1818 1848 1870
M 477 486 492
M 1836 1827 1838
M 1958 1964 1965
M 875 840 930
S 1379 1427 1428
M 1634 1639 1653
S 245 251 252
M 1536 1700 1733
S 1780 1794 1795
S 426 515 516
M 1708 1703 1740
S 1734 1785 1786
M 427 409 466
M 449 423 457
S 1212 1236 1237
S 1122 1130 1131
...

output:

3857
6410
388
610
4546
6570
3907
5794
2201
3916
3863
5557
2009
1782
942
879
1395
4980
1955
784
5424
4493
1186
6665
6744
4501
5774
4549
4496
1240
1433
2386
667
3323
2230
6234
163
3108
4022
4343
1503
5806
1295
4783
3085
1090
4278
4496
2424
2581
584
6049
1950
25
6646
1124
449
5248
5442
5799
5594
5991
6...

result:

ok 1000 lines

Test #14:

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

input:

1900 5736 1000
S 3071 3162 3163
S 2435 2454 2455
S 180 209 210
M 4303 4279 4313
M 93 124 126
S 85 91 92
S 4359 4420 4421
M 7328 7378 7384
S 3804 3807 3808
M 5154 5155 5178
S 8230 8287 8288
M 2981 2886 3040
S 3029 3077 3078
S 6331 6342 6343
M 3706 3663 3710
M 7325 7276 7330
S 305 524 525
S 7469 7573 ...

output:

1215
72
554
995
937
1349
1878
198
558
570
1137
493
1217
1057
1322
292
250
177
1032
316
793
1151
714
77
123
1223
1836
1262
842
1531
235
1443
1732
41
176
1151
837
307
340
662
445
1472
38
1808
1043
1067
1780
869
1369
271
1172
871
1813
227
1484
1349
667
31
295
77
377
1643
934
638
1027
811
934
165
781
45...

result:

ok 1000 lines

Test #15:

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

input:

7794 7236 1000
M 1425 1036 1429
M 469 338 472
M 4284 4411 4414
S 1013 1356 1357
S 6979 6994 6995
S 1653 1876 1877
S 62 81 82
M 5145 5090 5260
S 2017 2060 2061
M 7588 7612 7700
S 172 383 384
S 4025 4065 4066
M 1037 1044 1054
S 6407 6603 6604
S 8354 8419 8420
S 8966 9192 9193
S 330 361 362
M 3417 3409...

output:

1250
6640
4138
126
4249
5828
2883
3362
7205
3447
1312
3239
6717
6217
3684
1247
651
3141
5848
1885
2387
4964
6382
3516
385
7682
4488
2631
2114
6338
3870
3125
1550
4200
5004
1543
7517
483
5121
5272
3485
3231
1
3065
7361
6621
291
2521
3216
178
6073
4148
6403
7496
365
1383
1753
7213
171
7300
5170
1063
6...

result:

ok 1000 lines

Test #16:

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

input:

5563 4583 1000
S 2441 2706 2707
M 2339 2227 2392
S 4216 4251 4252
S 6010 6168 6169
M 1769 1779 1792
M 1809 1755 1815
S 6395 6451 6452
M 1352 1500 1517
S 286 399 400
M 5355 5161 5401
M 3163 3122 3180
M 1766 1859 1860
S 119 124 125
M 3266 3517 3537
S 5165 5196 5197
S 6290 6336 6337
M 6714 6672 6723
M ...

output:

1073
3728
3078
1217
2337
3532
5106
2251
635
2081
5230
2656
3248
3396
1626
3119
1970
4947
3995
852
2857
3301
2884
518
4776
1705
2775
1415
2488
4981
422
330
1518
2331
539
4140
1160
2453
3912
2802
5381
2173
3704
5044
1121
509
4696
2735
1193
5415
1121
1239
1310
1485
4799
4793
1846
4157
3878
4544
3503
39...

result:

ok 1000 lines

Test #17:

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

input:

190 2488 1000
M 3666 3728 3729
M 3670 3595 3705
M 67 72 112
S 2413 2451 2452
S 2608 2689 2690
S 1851 1997 1998
S 3078 3091 3092
S 3243 3291 3292
S 1164 1202 1203
S 2338 2343 2344
S 600 739 740
S 1982 2035 2036
S 1595 1768 1769
S 301 316 317
M 2354 2292 2422
S 1223 1227 1228
S 40 58 59
S 1343 1432 14...

output:

182
140
166
178
38
166
186
170
63
133
66
100
157
123
48
138
126
46
31
56
154
70
133
180
83
56
66
120
53
182
171
184
3
23
167
190
11
53
119
143
111
156
163
13
126
63
138
174
70
160
80
78
12
162
156
96
70
187
165
145
91
69
154
93
155
21
115
178
39
140
33
146
189
80
156
154
128
185
91
56
188
107
64
48
...

result:

ok 1000 lines

Test #18:

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

input:

889966903 51 1000
M 31 34 40
M 27 33 35
M 23 10 29
S 20 24 25
S 71 73 74
M 13 11 14
S 57 63 64
M 14 28 30
S 30 36 37
S 29 38 39
M 61 76 77
S 5 15 16
M 54 37 60
S 40 41 42
M 12 9 13
M 67 73 76
S 51 56 57
S 66 68 69
M 65 63 67
M 77 75 78
M 7 8 10
S 2 8 9
S 50 51 52
M 60 55 66
M 59 49 65
M 42 47 50
M 4...

output:

187821228
366651030
52852727
308067944
354657940
232789970
421616206
283181248
792111684
852513733
324668148
429039954
767584290
796252534
699591398
425184006
302588861
59135876
110071181
844739244
864085254
363892328
273236460
439943138
177830156
711773080
883025868
295196499
273307628
879769376
49...

result:

ok 1000 lines

Test #19:

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

input:

77957119 65 1000
S 1 2 3
S 55 65 66
M 58 36 67
M 60 62 69
S 71 82 83
M 14 9 15
M 90 84 96
M 51 44 57
S 47 48 49
M 69 70 79
M 76 66 85
M 52 73 78
M 97 87 98
S 29 42 43
M 95 98 99
M 19 11 23
S 49 70 71
S 17 29 30
M 46 54 60
M 96 88 97
S 45 52 53
M 79 89 92
S 32 34 35
S 8 13 14
S 43 46 47
S 50 58 59
S ...

output:

7244754
75815519
63867856
19261728
27671677
29262969
51363826
67136232
45909545
77466057
47958265
75764413
70563711
58188431
40107756
64606749
7396261
30335055
3067797
69529315
10413795
55662713
43804189
31621753
59669028
43367108
49932119
66653748
73768429
61628007
4796742
1499769
38379529
14814508...

result:

ok 1000 lines

Test #20:

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

input:

932606225 84 1000
M 59 70 87
S 25 36 37
M 23 20 24
M 114 108 119
S 8 11 12
S 67 71 72
M 107 93 111
S 58 61 62
M 55 63 78
M 39 35 40
M 102 116 121
M 112 76 118
M 124 109 125
S 62 65 66
M 4 5 6
M 11 14 17
S 54 63 64
S 41 73 74
M 83 85 86
M 113 126 127
S 31 34 35
S 40 56 57
S 46 69 70
S 111 116 117
S 4...

output:

297785242
767782226
329525408
238753421
589014545
196439
716569482
793586469
111978010
337673357
551190181
65637101
910296365
323397495
114704557
318644061
398416612
779212165
401642016
552417679
416261925
777396753
156308553
724568460
901148794
412862125
489363181
304669602
311601098
182736621
5428...

result:

ok 1000 lines

Test #21:

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

input:

738288629 10 1000
M 11 7 13
M 5 3 6
M 12 9 14
S 10 11 12
M 13 14 15
M 8 15 16
S 6 9 10
S 1 2 3
S 4 7 8
S 2 4 5
3 144898429
5 179099894
14 407173237
12 45071559
10 63787611
3 75703850
14 407423271
11 77199450
16 369144315
14 240478995
16 289809196
11 131099163
8 25467178
8 48302013
16 22294402
6 7899...

output:

289796858
716399575
705832164
180286236
127575222
151407700
706832300
308797798
276858235
592771670
197523118
679648986
203737421
386416101
11147202
157982583
161616302
136587577
721287752
487314094
114446860
696269527
556222903
39271525
347991137
156778506
322677217
587625785
3733975
31740394
61502...

result:

ok 1000 lines

Test #22:

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

input:

579670505 57 1000
S 2 10 11
M 12 13 21
M 25 27 36
M 17 23 50
S 40 46 47
M 80 77 82
S 51 53 54
M 52 53 61
M 63 45 64
S 29 30 31
S 44 59 60
S 14 28 29
M 74 72 78
M 15 41 45
S 64 67 68
S 30 32 33
M 81 82 86
M 57 47 62
M 85 84 87
M 39 59 63
M 20 22 24
S 42 48 49
M 50 48 51
M 78 83 85
S 5 8 9
M 11 6 16
M...

output:

490516041
276198308
260178073
164424472
225172489
230558037
263862494
181393514
378418700
411889473
465552649
547691491
444655513
241325582
153163097
541171254
325216335
207379744
183329830
223634697
558433800
288402680
551468779
92649852
314556049
348241381
332854236
454428873
55707918
431001288
20...

result:

ok 1000 lines

Test #23:

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

input:

262178919 1731 1000
M 1387 1330 1439
S 238 327 328
S 1320 1341 1342
M 2122 2209 2227
S 1224 1256 1257
M 1180 1341 1344
M 2123 1974 2173
S 1869 1930 1931
S 408 425 426
M 2265 2248 2271
S 2388 2421 2422
S 1015 1040 1041
M 1421 1452 1499
M 279 261 354
S 1671 1673 1674
M 709 616 740
M 2211 2171 2216
S 2...

output:

36861506
75598374
215920001
53814626
258605628
72821323
37772269
138976772
155740957
81455781
170915901
52850210
14970296
237155533
239370764
258833640
81669416
32064004
113415265
68710893
157459250
92388045
124640990
165418481
134768645
153664267
65355009
3017357
201885550
92923048
186128815
573446...

result:

ok 1000 lines

Test #24:

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

input:

590815836 2506 1000
M 1230 1211 1268
M 1555 1573 1677
S 1450 1502 1503
S 2782 2796 2797
M 1327 1285 1334
M 3185 3202 3203
M 2306 2360 2365
M 1201 1187 1224
M 613 680 682
S 2731 2752 2753
M 1654 1495 1669
M 426 450 499
M 1633 1634 1671
M 1880 1895 1908
M 156 173 183
M 973 991 1000
S 1775 1779 1780
M ...

output:

144739841
190818288
407227877
305665810
261142779
473422340
62982076
140138681
199588252
551480089
131934764
484834046
117986195
478720214
511281558
144208648
473483206
430140840
395521167
284913873
342583548
428192945
378530132
294740200
171068527
32729310
202344672
21275340
475500979
192021812
224...

result:

ok 1000 lines

Test #25:

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

input:

913061886 6716 1000
M 4692 4646 4710
S 4719 4721 4722
M 5385 5415 5428
S 9350 9580 9581
M 9766 9596 9779
M 10037 9895 10057
M 1381 1254 1382
S 6129 6200 6201
S 2486 2494 2495
M 4640 4609 4661
M 1276 1239 1296
S 2071 2085 2086
M 2103 2372 2385
S 1144 1190 1191
S 9014 9110 9111
M 1925 1941 1974
M 7860...

output:

377133143
190602560
286780231
153531397
278035873
37533385
368688301
607456509
729060747
681448088
912196732
701786927
226214356
427746035
833699032
166733016
502052497
882584673
817538701
3479737
829636321
800344201
635163888
654435489
137361597
509623921
646031982
684397906
481347895
701087854
906...

result:

ok 1000 lines

Test #26:

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

input:

660068944 4003 1000
M 1386 1373 1390
S 4827 4885 4886
M 3362 3216 3410
M 3671 3555 3697
M 2598 2602 2649
S 4228 4339 4340
S 2239 2258 2259
S 5605 5635 5636
S 2986 3004 3005
S 3847 3927 3928
S 407 439 440
M 1375 1156 1448
M 2972 3110 3125
S 4121 4196 4197
S 492 515 516
M 3333 3494 3495
S 318 335 336
...

output:

326435589
4360343
91529785
567798927
78628032
355085057
372301336
100807429
150952222
256497691
342941648
656490157
581284190
193815818
59861051
70527983
235966082
592467702
633326075
518341065
201871328
226796643
136880954
90238250
90728216
289631436
397507732
264874932
271675568
638832537
26222270...

result:

ok 1000 lines

Test #27:

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

input:

220296099 6091 1000
S 25 32 33
M 6042 6067 6095
S 6879 7092 7093
M 1966 2037 2045
S 1803 1810 1811
S 5064 5077 5078
S 1413 1434 1435
S 989 1099 1100
M 8398 8712 8781
M 5726 5794 5798
M 5445 5359 5453
S 7282 7283 7284
S 4285 4339 4340
S 3677 3736 3737
M 2835 2805 2848
M 7487 7416 7545
M 1120 1147 115...

output:

73932123
36563359
36495488
105077878
103950940
143940377
121108561
95044744
11161914
108779671
174798595
190927766
151596009
53052965
121534395
5064668
116743698
213336900
11651720
125591207
27907940
9670623
85129877
39263350
108697512
129932484
102733716
215292543
184349467
34587402
152836639
84310...

result:

ok 1000 lines

Test #28:

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

input:

67 84 1000
S 5 18 19
M 60 56 66
S 41 85 86
S 24 25 26
M 70 68 77
M 123 126 127
M 76 73 78
S 45 56 57
S 80 81 82
M 109 116 120
M 95 105 109
M 47 26 52
S 3 6 7
S 23 35 36
M 97 94 105
S 11 61 62
S 2 4 5
S 99 101 102
S 93 103 104
S 9 11 12
M 124 125 126
M 30 15 32
M 64 46 72
S 29 49 50
S 27 37 38
M 102 ...

output:

27
26
2
19
54
18
36
14
11
25
49
60
39
12
41
36
31
2
34
58
19
35
14
6
12
28
2
12
61
41
40
30
5
4
25
34
9
31
63
41
19
6
23
63
12
39
62
53
25
5
10
32
30
15
36
20
25
18
47
1
13
5
54
13
21
41
25
27
49
31
66
42
30
11
35
12
31
35
28
47
14
25
19
16
46
33
6
22
50
38
9
57
58
31
22
31
7
28
41
2
65
25
28
9
21
5...

result:

ok 1000 lines

Test #29:

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

input:

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

output:

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

result:

ok 1000 lines

Test #30:

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

input:

83 16 1000
M 17 15 18
M 3 7 10
S 4 6 7
M 12 8 19
S 1 2 3
M 20 21 23
S 10 15 16
S 9 11 12
M 24 23 25
M 14 5 17
S 2 4 5
S 18 20 21
S 11 13 14
S 6 8 9
M 13 16 22
M 22 19 24
17 8
12 2
9 2
13 1
13 1
7 1
14 1
11 3
20 2
7 10
16 15
16 22
5 3
16 19
19 1
23 25
16 1
2 39
9 1
12 2
5 8
25 22
16 25
21 5
19 4
9 2
...

output:

27
57
25
9
9
5
41
73
3
77
40
68
11
56
25
47
5
77
9
57
31
19
80
10
17
25
34
9
63
39
57
41
66
27
25
9
26
75
33
31
39
77
51
23
9
3
27
7
7
41
25
5
65
68
8
57
57
41
33
41
4
23
41
25
15
57
5
65
55
41
49
10
73
61
58
51
36
6
25
73
3
57
35
41
41
81
71
65
74
14
7
81
54
9
81
49
41
60
82
41
24
41
4
71
57
17
41
...

result:

ok 1000 lines

Test #31:

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

input:

60 20 1000
S 14 19 20
M 22 16 24
S 1 2 3
S 5 7 8
M 21 29 30
M 20 18 21
S 4 5 6
S 12 25 26
S 19 22 23
M 15 10 16
M 27 28 29
S 9 10 11
M 26 30 31
M 6 8 9
M 25 24 27
M 2 3 4
S 11 17 18
S 13 14 15
S 7 12 13
M 17 23 28
15 3
23 1
7 14
28 3
17 5
28 6
23 1
11 10
20 2
12 7
16 15
7 12
14 3
9 24
15 1
25 3
31 8...

output:

45
37
53
11
35
35
37
39
53
49
24
45
37
47
13
33
3
49
31
5
48
16
35
47
37
19
41
40
45
29
11
36
27
31
37
5
10
29
5
1
60
29
55
39
5
2
13
30
4
21
11
45
31
43
19
6
50
41
38
2
53
19
47
31
53
47
51
8
39
27
34
11
11
57
37
21
32
36
59
21
5
25
29
59
58
47
22
37
1
13
40
60
21
49
23
55
33
58
9
9
21
23
5
37
37
2...

result:

ok 1000 lines

Test #32:

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

input:

61 48 1000
M 60 49 61
M 61 53 68
S 3 9 10
S 40 42 43
M 29 26 31
S 1 2 3
S 11 13 14
M 31 24 32
M 8 9 15
M 52 65 66
M 68 66 69
M 59 69 70
S 55 56 57
S 20 28 29
S 16 36 37
M 7 6 8
M 51 58 60
S 5 6 7
M 32 19 38
M 27 33 39
S 12 22 23
S 57 62 63
S 50 58 59
S 23 24 25
S 4 11 12
M 30 38 41
M 67 62 72
M 36 3...

output:

51
39
13
16
9
23
59
55
19
53
33
13
11
28
59
39
13
10
5
41
5
52
3
12
12
15
9
43
55
9
47
53
39
17
23
53
45
46
31
13
33
22
37
35
5
23
43
39
17
37
53
30
59
29
37
17
25
25
39
10
41
51
33
61
5
25
59
33
27
10
23
25
31
46
36
37
45
33
9
58
1
33
59
57
5
20
2
45
46
33
37
2
35
33
18
43
11
37
33
41
55
30
21
37
1...

result:

ok 1000 lines

Test #33:

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

input:

6720 1 1000
S 1 2 3
3 1077
3 2134
2 129
3 2471
2 501
3 499
2 1775
3 279
3 3282
2 1751
2 3253
3 3019
2 1511
3 2441
3 2662
2 174
3 2588
3 23
2 2408
3 1879
3 666
2 460
2 2560
3 3068
3 504
3 781
3 2987
3 2136
2 1981
2 2186
3 936
3 2176
3 2391
3 2092
3 1419
2 979
2 986
3 1571
2 653
2 532
2 1955
3 703
2 1...

output:

2154
4268
257
4942
1001
998
3549
558
6564
3501
6505
6038
3021
4882
5324
347
5176
46
4815
3758
1332
919
5119
6136
1008
1562
5974
4272
3961
4371
1872
4352
4782
4184
2838
1957
1971
3142
1305
1063
3909
1406
2577
3152
1075
4508
3324
4131
4508
2020
3129
3911
568
5967
2295
2568
4518
736
5784
3820
4644
4733...

result:

ok 1000 lines

Test #34:

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

input:

4527 9 1000
M 9 3 11
S 4 6 7
M 13 12 14
M 5 8 10
S 11 12 13
S 7 8 9
M 6 14 15
S 2 4 5
S 1 2 3
7 566
6 513
7 191
13 1143
15 1560
4 230
6 188
15 1411
10 532
6 428
9 13
4 738
14 86
7 378
4 879
11 1509
7 4
12 1104
5 577
4 428
6 262
3 2106
15 797
12 913
10 628
2 1549
3 1943
2 1356
8 125
6 315
6 548
2 171...

output:

4525
4097
1525
4006
1420
917
1497
1126
4245
3417
205
2949
685
3021
3513
2452
29
3848
2307
1709
2089
4212
3185
3084
1379
3097
3886
2711
1989
2513
4377
3429
4464
318
4454
1741
1310
461
1165
1831
744
3028
4492
3745
2862
3549
435
949
2925
275
3250
2613
2109
3853
3483
738
3807
1680
2348
2905
330
411
3527...

result:

ok 1000 lines

Test #35:

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

input:

686 7 1000
S 8 9 10
M 4 5 6
S 6 7 8
M 9 7 11
S 1 2 3
S 3 4 5
M 10 2 12
11 53
5 38
11 86
3 105
5 56
12 377
4 83
3 31
5 114
5 3
12 360
2 68
12 50
5 6
7 14
12 123
7 95
2 129
3 260
2 128
8 63
10 40
8 66
5 117
7 103
6 299
7 58
12 287
11 202
5 92
2 119
7 168
5 32
7 11
2 60
4 127
7 90
10 65
3 290
9 25
5 14...

output:

212
152
170
210
224
583
330
62
456
12
549
135
49
24
54
496
378
257
520
255
252
320
264
468
410
598
230
403
462
368
237
670
128
42
119
506
358
520
580
196
56
500
146
405
30
607
640
414
622
14
388
547
58
227
118
156
211
399
668
484
352
368
666
412
288
580
155
638
417
304
52
468
422
258
422
523
296
208...

result:

ok 1000 lines

Test #36:

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

input:

2394 3 1000
M 4 3 6
S 1 2 3
S 2 4 5
3 259
3 627
3 826
2 320
2 275
6 1389
4 202
3 910
3 1090
2 1097
2 161
5 383
2 742
4 579
6 1785
4 146
6 1161
3 689
4 214
5 567
4 268
6 1796
3 852
4 188
2 78
3 327
5 585
3 717
6 661
5 415
2 846
6 1620
4 587
3 531
6 1573
2 1047
5 112
2 786
6 284
2 987
2 1105
4 429
5 3...

output:

518
1254
1652
639
549
1580
805
1820
2180
2193
321
1531
1483
2313
2372
581
2321
1378
853
2267
1069
2394
1704
749
155
654
2339
1434
1321
1659
1691
2042
2345
1062
1948
2093
447
1571
284
1973
2209
1713
1355
1997
1789
1754
177
168
685
559
341
386
179
759
973
801
585
194
2349
1028
1397
954
310
1909
2017
9...

result:

ok 1000 lines

Test #37:

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

input:

126 3 1000
S 4 5 6
M 3 2 4
S 1 2 3
4 20
2 27
6 30
2 61
6 56
5 9
2 34
2 25
3 4
5 60
2 37
6 50
6 42
6 32
3 14
2 1
5 10
2 16
3 32
6 53
4 126
3 53
3 5
6 39
4 7
3 34
3 12
5 3
2 3
4 55
6 19
3 59
6 63
2 19
3 16
2 49
3 4
3 32
2 29
5 9
5 29
4 80
6 60
4 52
6 6
5 1
4 35
4 71
2 9
5 15
4 28
6 1
6 54
4 11
2 10
5 ...

output:

19
53
59
121
111
18
67
49
8
120
73
99
83
63
28
1
20
31
64
105
125
106
10
77
8
68
24
6
5
56
37
118
125
37
32
97
8
64
57
18
58
79
119
51
11
2
36
72
17
30
27
1
107
12
19
126
95
56
88
49
34
53
104
27
29
6
69
83
7
55
6
47
40
55
93
6
7
126
98
108
29
77
120
88
23
17
11
122
111
73
81
56
34
8
15
37
92
1
82
2...

result:

ok 1000 lines

Test #38:

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

input:

9372 92 1000
S 64 86 87
S 108 116 117
S 18 22 23
S 4 12 13
M 130 124 135
S 106 109 110
S 63 76 77
M 73 74 75
S 41 49 50
M 134 138 139
S 91 123 124
M 8 10 11
S 127 130 131
M 57 53 58
M 114 109 118
S 45 55 56
M 107 84 111
S 86 92 93
M 113 121 122
S 78 82 83
S 126 127 128
M 70 83 84
M 67 69 70
S 30 36 ...

output:

2713
3135
7424
8962
5813
6814
8984
9112
4565
8002
2752
6949
975
2763
2107
6221
9050
495
2941
6690
9368
1009
3343
7504
1018
3288
8002
9263
4017
279
355
8112
3042
1125
2965
5951
7687
4288
7233
6848
769
499
2658
6080
7398
6594
7170
8230
5953
8148
6848
5050
6848
6431
4917
6339
7631
2769
3263
2243
6046
2...

result:

ok 1000 lines

Test #39:

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

input:

925 68 1000
M 88 82 91
M 14 53 55
S 45 48 49
M 49 48 50
S 74 80 81
S 41 53 54
S 91 95 96
S 19 39 40
S 29 34 35
S 68 70 71
S 15 16 17
S 52 57 58
S 22 23 24
S 21 46 47
M 40 33 42
M 62 78 79
M 100 96 101
M 9 18 20
M 87 84 94
S 39 43 44
M 51 61 66
M 50 43 56
S 71 75 76
S 10 11 12
M 38 37 41
S 13 14 15
S...

output:

731
175
166
758
557
694
148
126
78
374
502
389
131
725
775
383
254
58
528
467
17
774
393
212
316
270
853
751
316
260
694
739
193
644
141
404
444
332
284
632
118
310
590
479
777
246
519
342
196
58
547
404
712
157
431
153
142
758
438
502
668
78
278
692
614
551
165
324
196
318
60
482
78
879
823
686
566...

result:

ok 1000 lines

Test #40:

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

input:

8951 75 1000
S 77 79 80
M 51 58 59
M 50 69 70
M 73 94 95
M 12 13 14
S 3 4 5
M 92 76 108
M 107 91 109
M 100 93 107
M 64 53 69
M 30 43 44
S 38 42 43
M 26 21 29
S 28 32 33
S 67 85 86
S 35 50 51
M 68 83 89
S 17 34 35
M 74 78 88
S 41 45 46
S 63 67 68
S 22 23 24
S 44 47 48
M 108 112 114
M 54 46 56
S 96 10...

output:

6271
6618
1149
3948
2764
6514
3410
2860
5897
8738
1010
3441
2522
6693
2396
4305
6906
738
2553
8770
194
7890
4688
8738
962
802
6241
5538
7784
3643
7354
290
4898
5283
4876
8623
8859
442
394
5984
2284
3684
1058
4825
2242
7676
8698
6832
8039
6970
8120
7961
8911
4754
827
7458
8430
8828
7474
4082
8288
606...

result:

ok 1000 lines

Test #41:

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

input:

5916 90 1000
S 53 67 68
S 99 114 115
M 80 75 86
S 108 118 119
S 117 124 125
M 12 14 20
S 78 79 80
S 35 44 45
S 107 112 113
S 66 77 78
S 8 9 10
M 21 32 36
S 10 14 15
S 39 41 42
M 50 72 76
M 41 24 66
M 93 91 100
M 106 103 107
M 38 26 46
S 23 31 32
S 47 93 94
M 127 110 128
M 33 45 52
S 67 73 74
M 121 1...

output:

2899
1865
1884
2758
4782
2672
4927
147
4730
4425
2286
3480
5569
5347
4368
4873
5330
2385
3269
285
2188
4781
3677
4733
3791
4870
1661
1392
3866
4921
4543
4809
2465
2484
5289
4546
5469
3947
3578
5230
788
5441
1353
877
2980
5753
3175
3977
5456
5577
3108
3423
1833
1841
4105
307
564
4810
5020
2735
4486
1...

result:

ok 1000 lines

Test #42:

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

input:

4632 49 1000
S 52 55 56
S 19 39 40
S 25 30 31
M 72 60 75
M 57 54 64
S 6 10 11
M 62 66 73
S 50 57 58
M 37 43 45
M 56 58 67
S 44 47 48
S 48 51 52
S 12 13 14
S 39 53 54
M 3 15 21
S 14 19 20
M 46 42 50
S 5 8 9
M 49 68 72
S 64 65 66
S 24 33 34
M 65 63 68
S 26 62 63
S 51 60 61
M 59 67 69
M 22 16 27
S 11 1...

output:

4225
2029
4231
3049
2629
4104
1975
2199
4345
2309
553
3657
4477
4297
4133
4201
689
2207
4259
2373
1608
54
783
3433
1505
1257
71
3791
3079
3223
1921
665
3533
297
2609
52
1279
4549
121
1425
159
2665
2111
4265
3321
2025
3005
1705
304
4409
873
3817
761
889
2115
4473
3113
4489
1143
1298
2729
3705
1072
39...

result:

ok 1000 lines

Test #43:

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

input:

73 1 1000
S 1 2 3
2 1
2 7
3 28
3 12
3 27
3 25
3 35
2 4
3 2
2 33
2 23
3 27
3 7
3 4
2 6
3 5
3 3
3 11
2 31
3 19
3 17
3 12
3 29
2 24
2 5
3 18
3 24
2 8
2 9
3 14
3 22
3 8
2 33
2 5
2 16
3 24
3 25
2 17
3 17
2 31
3 35
2 19
2 10
2 19
3 12
3 12
3 33
3 23
3 33
2 33
3 19
3 19
3 9
2 37
2 4
3 19
3 27
2 36
2 20
3 2...

output:

1
13
56
24
54
50
70
7
4
65
45
54
14
8
11
10
6
22
61
38
34
24
58
47
9
36
48
15
17
28
44
16
65
9
31
48
50
33
34
61
70
37
19
37
24
24
66
46
66
65
38
38
18
73
7
38
54
71
39
58
71
26
22
26
58
8
11
65
54
22
34
28
27
70
2
56
30
22
55
32
23
7
60
13
25
69
67
68
57
71
35
19
45
20
26
41
3
63
21
68
34
11
52
19
...

result:

ok 1000 lines

Test #44:

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

input:

65 2 1000
S 1 2 3
M 3 2 4
2 30
4 25
2 18
4 39
4 64
3 28
2 2
3 22
3 13
2 23
3 26
2 23
2 23
2 18
3 5
2 25
3 25
4 50
3 23
4 28
3 19
2 32
2 20
2 28
3 12
2 3
2 30
2 29
3 20
2 11
4 19
2 7
3 17
2 25
4 57
2 8
2 23
4 24
3 9
3 10
2 1
2 14
2 28
3 20
4 58
3 24
3 16
3 23
4 1
4 39
2 14
2 25
3 3
4 33
3 19
4 8
3 20...

output:

59
26
35
40
63
56
3
44
26
45
52
45
45
35
10
49
50
49
46
27
38
63
39
55
24
5
59
57
40
21
20
13
34
49
58
15
45
23
18
20
1
27
55
40
57
48
32
46
2
40
27
49
6
34
38
7
40
49
19
26
64
44
12
64
64
35
38
1
61
29
12
51
42
27
63
36
40
21
25
53
9
1
32
6
29
17
14
57
47
64
8
60
9
23
36
19
52
45
50
12
28
61
6
25
4...

result:

ok 1000 lines

Test #45:

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

input:

70 8 1000
M 4 3 8
S 2 4 5
M 7 10 11
M 11 8 12
M 9 12 13
S 5 6 7
S 1 2 3
S 6 9 10
5 8
2 34
5 16
5 9
11 5
4 2
9 4
13 36
3 24
10 1
8 53
12 37
8 50
2 24
9 2
9 4
3 27
10 4
13 32
9 1
4 6
11 11
13 27
2 12
8 15
10 4
7 5
13 24
4 1
5 11
10 4
8 40
9 4
3 4
10 2
4 6
9 2
4 6
7 3
4 8
4 9
5 16
7 4
9 1
12 55
6 3
6 8...

output:

31
67
63
35
23
5
51
37
48
11
70
49
64
47
19
51
54
59
29
3
21
55
21
23
29
59
39
47
1
43
59
44
51
8
27
21
19
21
23
29
33
63
31
3
50
19
59
3
7
19
66
27
49
27
43
59
17
41
42
56
55
55
23
27
20
14
31
49
59
12
53
22
64
37
34
43
27
3
33
55
35
29
5
58
15
38
29
19
7
19
64
10
59
24
63
46
33
9
36
5
31
23
51
36
...

result:

ok 1000 lines

Test #46:

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

input:

40 9 1000
M 14 4 15
S 2 4 5
S 8 12 13
M 7 5 10
S 3 6 7
S 6 8 9
M 10 9 11
S 1 2 3
M 11 13 14
12 2
12 3
14 21
8 5
13 1
10 18
14 2
6 2
6 6
6 5
4 8
12 1
2 13
12 2
7 7
2 1
11 19
7 2
13 2
6 7
2 15
14 3
9 3
13 2
6 1
10 17
8 1
8 1
8 4
4 6
14 1
2 12
6 8
9 3
12 1
11 20
14 17
4 4
13 1
15 4
14 5
12 1
5 5
7 2
15...

output:

18
34
27
34
10
35
10
6
22
18
29
2
25
18
28
1
27
8
26
26
29
6
22
26
2
36
2
2
26
21
4
23
30
22
2
32
19
13
10
5
3
2
19
8
19
15
35
34
14
10
1
32
6
10
27
36
34
32
40
30
3
40
32
22
19
27
22
19
26
15
11
6
19
33
37
20
29
23
28
1
19
38
30
37
36
24
2
34
2
24
28
35
7
26
10
10
37
18
34
39
23
12
36
10
26
9
24
4
...

result:

ok 1000 lines

Test #47:

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

input:

71 1 1000
S 1 2 3
3 28
3 24
2 24
2 35
2 5
2 13
3 9
3 23
3 15
3 7
3 13
3 14
2 12
3 28
2 1
3 33
2 14
3 17
3 8
3 20
2 3
2 9
2 19
2 13
3 12
3 29
2 7
2 17
3 27
3 30
3 23
2 36
3 8
2 26
2 7
2 32
2 35
3 11
2 7
2 18
3 5
2 18
3 35
3 32
3 18
3 13
2 8
2 34
3 28
3 25
2 16
3 20
2 4
3 18
3 25
2 9
2 25
2 36
3 33
3 ...

output:

56
48
47
69
9
25
18
46
30
14
26
28
23
56
1
66
27
34
16
40
5
17
37
25
24
58
13
33
54
60
46
71
16
51
13
63
69
22
13
35
10
35
70
64
36
26
15
67
56
50
31
40
7
36
50
17
49
71
66
66
1
59
9
36
20
38
58
52
25
54
69
3
9
41
13
6
25
58
35
29
2
49
29
31
26
60
55
63
11
58
18
66
29
17
67
54
6
31
43
56
19
55
32
17...

result:

ok 1000 lines

Test #48:

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

input:

1 1 1
S 1 3 2
3 1

output:

1

result:

ok single line: '1'

Test #49:

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

input:

250000000 1 36
S 1 3 2
3 1
2 1
3 2
2 2
3 500000000
2 500000000
3 333333333
2 333333333
3 250000000
2 250000000
3 200000000
2 200000000
3 166666666
2 166666666
3 142857142
2 142857142
3 125000000
2 125000000
3 111111111
2 111111111
3 499999999
2 499999999
3 333333332
2 333333332
3 249999999
2 2499999...

output:

1
2
3
4
none
none
none
none
none
none
none
none
none
none
none
none
249999999
250000000
222222221
222222222
none
none
none
none
none
none
none
none
none
none
none
none
249999997
249999998
222222219
222222220

result:

ok 36 lines

Test #50:

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

input:

1 1 18
S 1 3 2
3 1
2 1
3 2
2 2
3 3
2 3
3 499999999
2 499999999
3 500000000
2 500000000
3 500000001
2 500000001
3 999999998
2 999999998
3 999999999
2 999999999
3 1000000000
2 1000000000

output:

1
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none

result:

ok 18 lines

Test #51:

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

input:

5 2 16
S 1 4 2
S 4 3 5
3 1
5 1
2 1
4 1
3 2
5 2
2 2
4 2
3 3
5 3
2 3
4 3
3 1000000000
5 1000000000
2 1000000000
4 1000000000

output:

1
3
2
1
5
none
4
3
none
none
none
5
none
none
none
none

result:

ok 16 lines

Test #52:

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

input:

16 15 74
S 1 2 3
S 2 4 5
S 3 6 7
S 4 8 9
S 5 10 11
S 6 12 13
S 7 14 15
S 8 16 17
S 9 18 19
S 10 20 21
S 11 22 23
S 12 24 25
S 13 26 27
S 14 28 29
S 15 30 31
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
2...

output:

1
2
1
3
2
4
1
5
3
7
2
6
4
8
1
9
5
13
3
11
7
15
2
10
6
14
4
12
8
16
15
16
13
15
14
16
9
13
11
15
10
14
12
16
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none

result:

ok 74 lines

Test #53:

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

input:

995272436 2151 506
S 2097 2529 2530
M 2550 1866 2807
S 628 778 779
M 1526 1318 1570
S 1429 1647 1648
S 2221 2235 2236
M 851 585 915
M 1090 1601 1968
M 896 886 962
S 181 212 213
S 3068 3175 3176
S 2337 2870 2871
S 187 203 204
S 1046 1154 1155
M 1497 1636 1795
S 1694 1848 1849
S 852 863 864
M 355 362 ...

output:

none
none
none
none
none
none
966422933
none
none
none
none
none
none
none
none
none
none
176105641
none
none
none
none
none
none
none
none
none
none
none
106733368
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
...

result:

ok 506 lines

Test #54:

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

input:

239753794 5185 937
S 3932 5019 5020
M 152 163 179
S 7465 7681 7682
S 5345 6178 6179
S 4715 5563 5564
M 2354 2334 2394
S 506 580 581
S 3477 3547 3548
S 3888 4174 4175
M 1108 1083 1238
S 2322 2755 2756
M 1886 2000 2012
S 4842 5707 5708
S 2602 2731 2732
S 894 901 902
S 566 591 592
M 5734 5785 5997
M 74...

output:

none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
...

result:

ok 937 lines

Test #55:

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

input:

647308029 718 994
S 759 807 808
S 240 287 288
S 277 539 540
M 218 195 255
S 870 932 933
M 284 407 408
S 924 1040 1041
M 320 385 424
S 563 659 660
S 631 886 887
S 64 89 90
S 674 789 790
S 394 437 438
M 892 1068 1069
S 499 573 574
S 517 663 664
S 286 299 300
S 594 595 596
S 463 476 477
S 148 220 221
S...

output:

none
none
none
none
none
none
none
none
none
none
none
none
none
290589196
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
369577481
none
206898817
none
none
none
...

result:

ok 994 lines

Test #56:

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

input:

526896050 9262 711
M 11866 10104 12352
S 7467 8831 8832
M 7944 9083 9732
M 2986 2765 3073
S 7858 9062 9063
S 11373 12553 12554
S 11043 12061 12062
S 632 763 764
M 1677 1595 1951
M 8901 6972 10301
S 9108 9213 9214
S 12962 13586 13587
S 10250 10431 10432
M 7845 7211 8311
S 5396 5593 5594
M 1938 1634 2...

output:

none
none
none
none
10028583
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
400839...

result:

ok 711 lines

Test #57:

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

input:

77 10 29
S 9 16 17
M 13 5 4
S 15 14 2
S 1 11 12
S 14 9 13
M 17 10 5
S 2 6 8
M 6 8 3
S 3 7 10
M 11 12 15
6 69
6 45
6 9
4 48
2 46
8 72
3 20
7 2
4 22
9 53
8 21
3 33
6 13
3 15
8 20
4 18
7 27
4 49
8 32
9 1
2 31
6 36
3 32
3 35
7 31
7 32
6 69
5 42
5 22

output:

none
none
34
76
none
none
40
6
45
none
none
66
50
30
none
37
none
none
none
1
62
none
64
70
none
none
none
none
48

result:

ok 29 lines

Test #58:

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

input:

96 18 27
S 26 14 21
M 19 4 24
S 2 20 19
M 18 10 3
S 1 11 2
M 21 23 9
S 6 12 15
S 13 28 17
M 17 28 4
S 24 22 29
M 11 20 13
S 8 5 16
M 29 22 8
S 27 7 23
M 15 12 26
S 25 27 18
S 14 10 25
M 16 5 6
8 96
18 28
12 33
16 3
6 75
9 68
2 56
3 17
6 25
5 95
16 64
12 57
6 79
17 90
15 17
3 63
14 12
6 97
2 40
6 88
...

output:

95
none
82
12
55
none
none
47
52
none
none
none
63
none
34
none
11
none
80
77
67
none
68
none
none
59
none

result:

ok 27 lines

Test #59:

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

input:

77 18 25
S 1 4 23
S 27 29 17
M 7 18 6
S 24 20 16
S 23 21 5
M 26 19 18
S 8 28 11
M 30 28 13
S 4 14 24
S 22 25 26
M 13 14 10
M 21 15 7
S 29 8 3
S 12 2 27
M 16 2 19
M 17 5 9
S 9 30 22
S 20 12 15
12 41
10 7
17 66
8 29
14 28
17 33
15 4
13 77
7 31
3 77
7 69
16 47
9 53
17 17
9 61
9 47
16 25
2 47
3 61
3 57
...

output:

none
16
none
none
none
none
59
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
34
none
none

result:

ok 25 lines

Test #60:

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

input:

45 13 10
S 1 9 21
S 5 23 4
S 17 6 10
S 13 7 17
S 20 11 18
S 22 8 15
S 14 2 12
M 9 21 5
M 8 15 16
M 23 4 14
S 6 20 19
M 12 2 22
S 16 13 3
2 5
5 10
6 25
9 42
2 41
13 13
6 27
4 32
4 11
5 39

output:

9
10
none
none
none
26
none
none
22
39

result:

ok 10 lines

Test #61:

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

input:

56 16 21
M 10 9 28
M 3 18 26
M 12 8 16
S 17 14 11
S 15 4 23
S 13 20 8
M 20 4 5
S 16 10 15
S 6 18 12
S 11 19 7
S 29 3 27
S 22 17 24
S 1 2 6
S 2 29 13
S 26 9 21
S 27 22 25
13 18
5 6
16 4
7 13
3 29
7 44
7 6
12 20
8 17
12 21
13 25
7 31
2 50
7 2
7 15
16 7
13 7
3 30
6 54
8 3
14 48

output:

none
39
15
none
none
none
none
none
none
none
none
none
none
none
none
16
27
none
none
23
none

result:

ok 21 lines

Test #62:

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

input:

30 3 40
M 4 2 3
S 1 2 4
S 3 5 6
3 26
3 15
2 9
2 3
3 28
2 12
3 26
2 15
2 12
3 15
2 16
2 14
3 7
2 29
3 19
3 26
3 5
2 4
3 1
2 18
2 24
2 20
2 8
2 12
2 22
3 20
2 5
2 15
2 12
2 13
3 16
3 21
3 22
2 8
3 10
2 27
3 31
3 24
3 29
3 17

output:

25
16
17
5
27
23
25
29
23
16
none
27
8
none
20
25
6
7
2
none
none
none
15
23
none
19
9
29
23
25
15
22
21
15
9
none
none
23
30
18

result:

ok 40 lines

Test #63:

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

input:

36 8 12
S 11 10 2
S 12 13 14
S 13 8 5
M 14 8 3
M 7 2 12
M 4 10 6
S 1 4 9
S 9 11 7
3 1
5 1
7 9
5 9
3 7
6 2
8 6
6 9
3 11
4 6
4 2
3 22

output:

6
8
36
none
30
2
none
9
none
11
3
none

result:

ok 12 lines

Test #64:

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

input:

916980909 8655 600
M 6053 5955 1419
M 10599 4088 713
M 4895 10996 4835
S 983 11982 6086
M 7348 890 7682
S 341 6889 2869
M 10546 3600 5669
M 7202 7398 4994
M 9687 13696 10626
M 7176 3226 12966
S 4873 12060 425
M 6043 9647 1150
S 9770 9129 11643
S 10806 12324 474
S 12949 437 12969
S 4312 280 9530
S 74...

output:

none
116846677
none
37441144
502003407
12989285
499897959
405991204
680182056
419384074
none
47563206
none
none
none
none
279336654
38757657
none
263288440
103048048
209202840
700699560
876148412
104976821
65667860
797487159
none
341893853
94157790
402462131
3387
42943011
728677989
398990231
5954195...

result:

ok 600 lines

Test #65:

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

input:

104504033 5990 174
S 3249 5338 2352
M 9134 2815 6739
S 5032 2979 118
M 8114 3419 9244
M 872 5336 2230
M 1514 2301 1473
S 7066 2925 4532
S 388 5279 3642
S 7907 4631 1968
M 4422 670 9545
M 1980 3589 5832
S 213 8844 3400
S 949 9243 9139
S 502 3446 1433
S 1977 7646 8386
S 8623 2599 5963
S 2010 5707 8281...

output:

43481671
66049856
5622011
none
106368
none
none
33084284
12648669
32658355
5088960
51934005
none
none
60315838
none
57653674
21214855
none
35323773
16183344
131
none
98008472
none
54857827
3806994
2450944
45454088
58152482
86468466
none
none
13389607
13507900
15749120
97248
none
13075812
none
177343...

result:

ok 174 lines

Test #66:

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

input:

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

output:

1
73
509
1127
108
824
753
213
2055
39
1724
408
1368
4881
4177
1257
2869
4205
4381
123
1631
4906
454
2518
238
4382
702
292
3436
508
1896
3128
7937
4993
1361
7465
6969
none
none
2389
4821
6517
6029
2381
none
3261
none
4699
none
3471
3615
none
3914
6278
5062
6678
6294
none
1654
2062
none
5460
1612
2492...

result:

ok 1000 lines

Test #67:

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

input:

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

output:

16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
none
14
5
none

result:

ok 20 lines

Test #68:

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

input:

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

output:

20
40
60
80
100
120
140
160
180
200
220
240
260
280
300
320
340
360
380
400
420
440
460
480
500
520
540
560
580
600
620
640
660
680
700
720
740
760
780
800
820
840
860
880
900
920
940
960
980
1000

result:

ok 50 lines

Test #69:

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

input:

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

output:

1
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none
none

result:

ok 20 lines

Extra Test:

score: 0
Extra Test Passed