QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80027#5402. 术树数crescent100 ✓944ms27492kbC++143.4kb2023-02-21 18:10:492023-02-21 18:10:53

詳細信息

Subtask #1:

score: 2
Accepted

Test #1:

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

input:

30 7 3
1 1 301
1 1 236
1 2 278
3 2 4
3 2 4
2 1 4 265
1 1 242
1 4 278
1 6 337
3 2 3
2 5 7 304
2 5 6 34
1 4 178
3 6 7
3 5 7
3 1 4
1 1 178
3 3 4
3 1 6
3 3 4
2 6 7 131
1 1 213
3 1 3
2 3 10 11
3 4 6
2 5 9 169
1 6 9
2 5 10 29
1 9 111
3 9 11

output:

0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 12 lines

Test #2:

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

input:

30 9 3
1 1 694
1 2 251
1 2 623
2 2 4 109
3 3 4
3 1 2
2 2 4 611
1 4 595
2 2 5 477
2 2 5 363
3 1 3
2 1 5 121
1 2 225
2 1 5 214
2 3 6 706
3 3 4
2 2 3 122
2 2 3 621
3 2 3
3 2 4
2 1 5 630
1 5 598
3 4 5
3 1 3
1 2 665
2 1 2 331
2 1 6 449
1 2 387
3 3 6
3 4 6

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 lines

Test #3:

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

input:

30 4 5
1 1 854
1 1 467
1 2 708
2 2 4 529
1 4 115
1 4 444
2 3 4 108
2 2 5 724
2 1 3 375
1 5 827
2 5 6 974
1 3 73
3 2 3
2 2 3 140
3 5 6
2 6 8 787
3 1 5
1 5 971
3 4 6
2 4 5 816
3 7 8
3 2 4
1 6 855
2 5 10 39
2 6 9 280
2 6 10 662
3 7 10
1 6 412
3 4 7
1 6 276

output:

0
256
256
256
0
0
0
0

result:

ok 8 lines

Test #4:

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

input:

30 6 4
1 1 1246
1 1 825
1 3 843
2 1 3 186
2 2 3 228
2 1 3 1187
3 2 3
3 1 4
1 3 942
3 1 2
1 5 779
2 3 4 775
2 1 2 275
2 1 3 309
2 5 6 1175
3 2 6
1 6 1084
3 4 6
1 7 176
3 5 6
2 3 8 431
3 2 6
3 1 4
1 8 725
3 7 9
3 1 4
3 6 7
3 2 4
3 1 6
1 5 972

output:

1
6
7
0
0
0
0
0
0
0
0
0
0

result:

ok 13 lines

Test #5:

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

input:

30 6 4
1 1 1050
1 2 312
1 3 665
2 1 4 49
2 1 3 394
2 3 4 1225
3 1 4
1 1 381
3 1 2
1 3 933
1 3 551
2 2 6 521
3 3 5
2 2 6 1219
3 3 7
1 6 953
1 3 403
2 1 7 624
1 8 981
3 1 2
1 9 1052
2 4 9 971
2 5 8 575
3 1 7
2 6 9 953
2 1 10 347
3 3 11
2 3 9 878
1 6 991
2 6 11 681

output:

1
0
1
1
0
0
0

result:

ok 7 lines

Test #6:

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

input:

30 4 5
1 1 48
1 2 924
1 2 587
3 3 4
2 1 3 63
1 1 600
2 2 5 747
1 5 252
2 2 5 777
2 2 3 119
1 3 914
1 1 708
2 2 3 670
2 3 5 526
3 3 7
1 5 816
1 9 401
1 2 364
2 7 10 16
2 10 11 254
1 6 641
1 10 406
2 6 10 324
1 5 29
1 12 493
2 3 15 125
1 12 95
1 4 370
2 8 16 766
1 11 307

output:

341
0

result:

ok 2 lines

Test #7:

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

input:

30 3 6
1 1 358
1 2 16
1 1 636
1 1 156
1 4 512
3 3 4
3 5 6
3 1 2
2 2 5 271
3 4 6
2 3 5 5
1 2 566
3 3 4
3 4 6
3 2 3
2 4 6 472
2 2 6 119
1 1 260
2 1 8 488
1 7 345
1 8 368
2 6 9 649
1 1 553
2 1 9 416
3 8 9
1 10 630
1 9 156
1 3 14
1 4 407
3 4 10

output:

0
0
0
0
0
0
0
0
0

result:

ok 9 lines

Test #8:

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

input:

3 8 3
1 1 401
1 2 0
3 1 2

output:

179

result:

ok single line: '179'

Subtask #2:

score: 11
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 11
Accepted
time: 1ms
memory: 26864kb

input:

996 4 8
1 1 43515
1 1 674
1 1 0
3 3 4
1 3 26873
3 3 5
3 3 4
1 2 0
1 5 26201
1 7 0
3 1 3
3 2 6
1 2 2722
1 4 674
1 10 35328
3 3 5
1 2 2048
3 10 11
2 2 8 34808
3 10 11
3 1 4
3 3 11
3 3 7
3 1 2
1 2 10753
3 12 13
3 3 4
1 12 32928
3 9 13
3 3 8
2 3 10 3
3 5 8
1 9 34978
1 13 2722
3 8 14
3 2 3
1 9 43681
3 7 ...

output:

0
26873
0
0
0
24825
0
0
0
0
1024
504
0
0
0
1024
17496
1528
504
1528
16640
504
1024
1528
1528
16640
16472
16640
16472
0
0
504
504
504
0
16640
1024
504
504
504
0
0
504
0
504
16640
0
504
0
504
16640
16640
16640
0
0
0
0
0
504
0
0
16472
0
0
1024
1024
504
504
0
504
0
16640
504
0
0
0
504
16640
0
0
504
504
...

result:

ok 459 lines

Test #10:

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

input:

997 6 6
1 1 12369
1 1 31248
3 1 2
2 1 2 43616
3 1 2
3 1 2
1 1 15625
1 4 15627
3 2 4
1 1 31251
1 1 31249
3 3 6
1 5 31253
1 3 4
1 7 31252
1 2 3
1 7 15626
3 6 7
1 4 15627
3 5 12
1 6 2
1 12 0
3 4 6
3 8 14
3 1 7
1 8 31252
1 6 4
3 12 17
1 9 31249
1 10 0
1 18 4
3 5 19
1 8 12861
1 3 16431
1 5 16155
1 16 405...

output:

12369
12366
12366
12366
0
0
0
0
0
0
0
0
0
9474
9474
9474
0
0
0
0
0
9330
9330
9330
0
9330
9330
9330
0
0
0
0
0
9330
9330
0
9330
0
0
0
0
9330
0
9330
9330
0
0
0
0
9330
9330
9330
9330
9330
9330
0
0
9330
0
0
9330
0
0
9330
9330
0
9330
9330
9330
9330
0
0
0
9330
0
0
0
9330
9330
9330
9330
0
9330
9330
9330
933...

result:

ok 454 lines

Test #11:

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

input:

1000 8 5
1 1 14822
3 1 2
2 1 2 20801
3 1 2
3 1 2
3 1 2
3 1 2
1 2 8322
1 2 2337
1 4 10659
3 3 4
3 1 2
3 1 3
1 4 18469
1 4 18469
3 5 7
3 3 4
1 6 7608
3 1 6
3 3 5
1 3 2226
1 5 26902
2 3 6 289
1 3 26672
1 1 10547
1 2 16530
3 10 13
1 3 10263
3 7 9
1 8 10257
1 8 26674
1 10 16531
1 16 26899
3 2 13
3 1 9
1 ...

output:

6498
4161
4161
4161
4161
0
4161
4161
0
0
4161
0
0
0
0
4160
4160
4160
5160
1112
5160
5160
0
4160
0
0
0
0
0
0
0
5160
5160
0
0
1112
5160
0
0
5160
0
0
0
0
0
0
5160
5160
0
5160
0
0
0
0
0
1112
0
5160
5160
0
0
0
5160
5160
5160
5160
5160
0
5160
0
0
5160
0
4104
0
0
4104
4104
4104
0
0
0
0
0
0
4104
0
4104
4104...

result:

ok 446 lines

Test #12:

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

input:

994 12 4
1 1 12377
1 2 18746
3 2 3
3 1 3
2 2 3 11
1 3 18751
3 3 4
1 1 7587
1 4 7592
1 2 18753
2 3 6 7586
2 5 7 16102
1 5 6
3 5 7
2 6 7 7591
3 4 6
2 5 6 6526
2 1 4 19821
3 3 5
3 2 8
1 1 11307
1 7 7595
3 1 6
1 9 15032
1 2 18748
2 2 10 15027
3 8 11
1 4 7591
3 4 7
3 6 11
2 2 10 15033
3 1 4
1 12 3865
1 1...

output:

0
2807
0
2796
0
2796
2796
2796
0
0
2796
2796
0
2796
2796
0
2796
0
0
2796
0
0
0
2796
2796
0
0
0
0
0
2796
0
2796
0
0
2796
0
0
0
2796
0
0
2796
2796
2796
2796
2796
0
2796
0
2796
2796
0
2796
2796
0
0
0
2796
0
0
0
0
2796
0
0
2796
0
2796
2796
2796
0
0
1932
0
1932
1932
1932
0
0
1932
1788
0
0
1932
1932
1932
...

result:

ok 459 lines

Test #13:

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

input:

995 30 3
1 1 23137
1 2 384
1 1 192
3 2 4
1 2 18728
1 5 18566
3 2 4
1 2 9364
1 3 546
2 2 6 9555
3 1 3
3 3 8
3 2 8
3 3 5
2 2 8 557
3 4 7
1 2 9741
3 6 7
3 2 5
1 8 16
1 7 541
3 3 8
3 1 8
1 2 9730
1 3 18188
3 5 11
1 1 18555
3 4 5
3 1 6
3 9 13
3 2 4
1 13 389
1 11 9725
1 11 749
1 15 18014
3 11 13
1 7 9007
...

output:

4601
4601
4590
0
0
0
4590
0
0
0
4590
0
4590
4590
0
4590
0
0
0
0
4590
0
0
0
4590
0
0
0
0
4590
0
4590
4590
4590
0
0
0
0
0
0
4590
0
0
4590
0
4590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4590
0
0
0
0
0
0
0
0
4590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 445 lines

Test #14:

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

input:

1000 280 2
1 1 71565
1 2 53290
1 3 8650
3 1 2
1 4 22600
1 4 47710
1 5 58870
1 3 50500
3 2 4
1 5 53290
3 1 8
3 2 8
2 3 4 279
2 1 7 40860
3 3 9
3 4 9
1 8 56234
3 1 6
3 3 4
1 5 8663
1 1 22551
3 8 12
3 3 9
3 9 12
1 11 50597
3 10 11
3 5 6
1 7 70250
1 2 42162
1 10 44800
3 3 13
1 11 5793
2 14 15 67433
3 11...

output:

1535
0
1535
0
0
0
1400
0
1400
0
1400
0
0
0
0
0
0
1400
1400
0
0
1400
0
1400
0
1400
0
1400
0
0
0
1400
0
1400
1400
0
1400
0
1400
0
0
1400
0
0
1400
0
0
0
0
1400
0
0
0
0
0
1400
1400
0
0
1400
1400
1400
0
1400
0
0
0
0
0
0
1400
1400
1400
0
1400
1400
1400
1400
0
1400
0
1400
1400
0
1400
0
1400
1400
1400
0
0
0...

result:

ok 440 lines

Test #15:

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

input:

998 6 6
1 1 39091
1 2 0
3 1 3
1 3 15640
2 1 3 23456
3 2 4
1 3 31277
3 2 4
2 1 5 7821
1 3 15640
3 4 6
1 3 31275
1 3 15640
1 8 15638
1 4 3
3 2 4
1 8 4
3 5 11
3 6 9
2 3 8 3
3 1 7
3 7 10
1 2 31274
1 5 15638
1 8 31272
1 10 0
1 3 3
1 14 15638
3 3 11
2 4 11 31277
1 9 31273
3 10 13
3 6 12
3 15 17
3 14 18
3 ...

output:

7823
0
0
0
0
0
0
7818
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7818
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7818
0
0
0
0
0
0
0
0
0
0
7818
0
0
0
0
0
0
0
0
7818
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2076
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 458 lines

Test #16:

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

input:

992 8 5
1 1 26
1 1 32
1 1 24963
3 2 4
1 2 4
3 2 3
1 3 16690
1 1 16690
3 4 6
1 1 16691
1 8 16694
1 6 16642
3 1 10
3 2 3
1 9 16
2 1 7 16693
1 1 16660
2 2 10 43
1 9 51
2 3 11 54
1 4 16675
1 7 16643
1 8 55
1 15 49
3 10 13
1 10 49
1 3 33
1 2 16644
3 16 20
3 9 19
3 18 20
1 13 20
1 4 16672
3 12 20
1 22 166...

output:

8331
10
8321
0
8
0
8
0
8
8
8320
8320
0
0
0
0
0
8
8320
0
0
8320
0
0
0
8
8320
8320
0
8320
8320
8328
0
0
8
0
8
0
8320
8320
0
0
8320
0
0
8320
8
8320
0
8
0
0
0
8320
0
8320
0
0
0
8320
8320
0
0
0
8320
0
0
8
8320
0
8
8320
0
0
1152
0
1152
0
0
0
8320
0
0
0
0
8320
1152
8
8320
8320
0
0
0
0
0
8320
8320
8320
0
83...

result:

ok 447 lines

Test #17:

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

input:

1000 12 4
1 1 19140
3 1 2
1 1 17400
3 1 2
1 3 0
2 1 4 7523
3 1 2
3 3 4
3 1 2
3 1 4
1 3 3555
1 5 13920
1 6 7517
1 6 7592
1 4 15034
1 4 18439
3 3 10
1 10 14477
1 6 11003
1 9 17406
3 1 9
1 4 4037
1 4 15097
1 2 632
3 14 16
1 4 14477
3 12 15
1 11 10997
3 1 3
2 1 2 19621
2 1 11 1249
1 17 11071
3 5 13
3 4 ...

output:

1740
1740
1740
0
1740
0
0
0
1740
0
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
1740
0
0
1740
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
0
0
0
0
0
0
1740
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 479 lines

Test #18:

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

input:

991 16 4
1 1 0
1 2 35536
3 2 3
3 2 3
3 2 3
1 2 2112
1 1 2240
3 1 3
3 4 5
1 2 1056
1 4 3296
3 1 3
2 1 6 1199
3 1 6
3 1 6
1 2 3172
1 8 3297
1 2 132
1 9 2251
3 2 11
3 4 10
3 4 8
1 10 6
3 4 6
1 9 1070
1 7 3179
1 11 2244
1 14 132
1 6 8
3 8 17
1 9 1191
1 10 2112
3 2 18
3 11 12
3 2 5
1 1 12
1 8 1060
3 16 1...

output:

33296
33296
33296
33296
0
33296
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33296
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33296
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33296
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8448
0
0
0...

result:

ok 451 lines

Test #19:

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

input:

997 60 2
1 1 3578
2 1 2 2357
2 1 2 459
3 1 2
3 1 2
3 1 2
2 1 2 2825
3 1 2
1 1 1696
1 3 840
1 4 1334
1 4 2791
3 3 6
1 6 515
1 3 1332
3 6 7
1 8 2418
3 5 8
3 4 9
3 2 6
1 7 2293
1 5 148
1 6 2078
1 1 3015
1 2 1578
1 11 2293
2 4 15 3286
3 1 15
3 6 12
3 7 13
2 1 4 415
3 3 7
3 1 4
1 2 392
1 1 2938
3 8 17
3 ...

output:

60
60
60
60
0
0
0
0
60
0
0
0
0
0
0
0
0
0
60
60
0
0
0
0
0
0
0
60
0
60
0
60
0
60
0
0
0
60
0
60
0
0
0
0
60
0
0
0
0
0
60
60
0
0
0
0
0
60
0
0
0
0
0
0
60
0
0
60
0
0
0
0
60
0
0
0
60
0
0
0
0
0
0
60
0
0
0
60
60
60
0
0
0
0
60
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
60
0
0
0
0
60
0
0
0
0
60
60
0
0
0
0
0
0
60
0
60
...

result:

ok 460 lines

Test #20:

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

input:

997 280 2
1 1 0
3 1 2
3 1 2
1 1 267
3 2 3
1 3 162
3 3 4
3 2 3
1 4 216
3 2 3
1 1 238
2 2 4 60
1 1 57
1 5 39
1 5 10
3 2 7
3 6 9
1 9 268
1 9 171
3 3 5
3 5 9
1 1 110
1 12 90
1 3 6
1 14 133
1 3 202
1 1 214
3 12 14
3 4 10
3 3 7
1 5 178
3 9 14
3 8 14
1 13 44
1 1 180
1 14 43
3 1 8
1 6 23
3 17 21
2 16 17 216...

output:

0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 466 lines

Subtask #3:

score: 11
Accepted

Test #21:

score: 11
Accepted
time: 944ms
memory: 26292kb

input:

198517 3 16
1 1 40710744
1 2 21885097
1 1 23592366
1 4 7387074
1 5 16074177
1 1 41027400
1 4 18082971
1 2 12822448
1 1 2286557
1 1 27896295
1 11 14532760
1 8 2357296
1 11 9190559
1 6 40503152
3 4 11
3 1 7
3 3 7
3 8 14
3 12 15
3 2 3
1 10 34606866
1 13 42718465
1 16 30353561
3 5 11
3 2 6
3 16 18
1 3 2...

output:

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

result:

ok 99662 lines

Test #22:

score: 0
Accepted
time: 537ms
memory: 26576kb

input:

198073 8 8
1 1 4007183
1 1 411647
1 1 3301064
1 1 2747675
1 3 11141272
1 3 4308435
1 4 15582931
1 5 11340890
1 2 9172283
1 9 542280
1 10 12209796
1 3 2829956
3 1 3
1 3 724504
3 2 14
3 3 14
3 9 12
3 7 10
1 1 3594204
1 14 13600647
1 15 4589767
3 10 14
1 4 10564184
1 13 1781174
1 19 6067505
1 9 6735060...

output:

262729
2097224
520
4673
2097672
2134081
2101769
2134080
2101832
2130432
584
2129992
2392584
2134024
2101824
2363904
295424
36864
4608
0
295489
299593
1
33353
2359305
2130440
2130497
2363969
4161
294976
37440
2359361
299080
2101248
299592
33344
2392576
2359816
2097160
8
2359880
262657
2101832
2363464...

result:

ok 99445 lines

Test #23:

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

input:

198343 50 4
1 1 4597949
1 1 1140260
1 1 1078946
1 3 4494430
1 4 3030702
1 5 5215333
1 4 5366961
1 2 4836213
1 5 3721812
1 1 486900
1 3 2631122
3 7 11
1 1 384111
3 6 10
3 1 3
1 1 6239546
3 6 10
1 5 4354709
3 11 12
3 6 13
1 9 863486
1 15 5296752
1 12 1997611
3 15 16
1 11 6087993
3 1 13
1 9 4926906
3 1...

output:

2551
125050
125050
125050
125050
125001
1
127501
127550
125050
125000
2500
2550
125000
125001
50
50
51
50
127550
127501
2500
125000
50
127500
2550
125000
50
127500
125051
1
2550
127551
51
127501
1
127551
2500
125000
2551
2551
125000
127501
1
50
51
2551
2550
125001
0
2500
125001
2500
50
127500
125001...

result:

ok 99620 lines

Test #24:

score: 0
Accepted
time: 396ms
memory: 27492kb

input:

199495 2675 2
1 1 6874452
1 1 2927709
1 1 4714827
1 1 341697
1 1 5807384
1 2 6029400
1 6 3410507
1 1 4255734
1 9 7116423
1 3 5647617
3 5 11
1 5 2479935
3 9 10
3 2 6
1 4 6921813
1 12 4608236
1 11 932260
1 11 5347104
3 1 11
3 11 14
1 12 715746
3 8 17
1 14 1418580
1 3 6123273
1 4 6481423
1 1 4166639
1 ...

output:

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

result:

ok 100058 lines

Test #25:

score: 0
Accepted
time: 335ms
memory: 26968kb

input:

199531 45237947 1
1 1 15260546
1 1 30197693
1 2 3455446
1 1 29660068
1 5 5406610
1 2 32468080
1 6 33471078
1 7 3670881
1 7 11684247
1 7 8493599
1 1 4296342
3 5 6
1 9 41359920
3 2 11
1 4 37376116
3 2 5
1 9 44209222
3 2 14
1 13 11322652
3 11 13
1 7 3505613
1 14 30321158
1 3 3184527
1 11 14996243
1 19 ...

output:

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

result:

ok 99829 lines

Subtask #4:

score: 19
Accepted

Test #26:

score: 19
Accepted
time: 322ms
memory: 25872kb

input:

198891 26426880 1
1 1 0
2 1 2 0
3 1 2
1 1 0
3 2 3
3 1 2
1 2 0
1 2 0
1 3 0
1 6 0
2 1 6 0
2 3 6 0
3 2 3
1 2 13213440
1 2 13213440
1 4 13213440
3 4 10
1 1 13213440
2 3 4 0
2 3 8 13213440
1 1 0
1 12 0
1 13 0
1 3 0
3 2 11
3 2 12
2 11 14 13213440
1 6 0
2 12 14 0
2 1 2 0
1 10 0
1 12 0
2 3 13 0
3 12 14
3 1 ...

output:

0
0
0
0
13213440
13213440
0
0
0
13213440
0
0
13213440
0
13213440
0
13213440
0
13213440
13213440
13213440
13213440
13213440
0
13213440
13213440
0
13213440
13213440
0
0
0
13213440
0
13213440
0
13213440
0
0
0
13213440
13213440
0
13213440
13213440
13213440
13213440
0
13213440
13213440
13213440
13213440
...

result:

ok 66344 lines

Test #27:

score: 0
Accepted
time: 303ms
memory: 26972kb

input:

199011 22494024 1
1 1 11247012
1 1 11247012
2 1 2 11247012
3 1 3
1 3 11247012
2 1 4 0
1 1 11247012
1 2 11247012
2 4 5 11247012
3 1 2
1 5 0
3 2 5
2 5 6 11247012
2 2 3 0
1 1 11247012
3 4 8
2 1 5 11247012
3 5 7
1 6 11247012
1 4 0
3 1 7
2 1 9 11247012
1 7 11247012
2 3 4 11247012
3 4 5
2 1 9 11247012
3 5...

output:

11247012
11247012
0
11247012
0
11247012
11247012
11247012
0
11247012
0
0
0
11247012
11247012
11247012
11247012
11247012
11247012
11247012
0
11247012
11247012
11247012
11247012
11247012
11247012
0
0
0
11247012
11247012
11247012
0
0
0
0
11247012
0
11247012
11247012
0
11247012
0
0
11247012
0
11247012
1...

result:

ok 66431 lines

Test #28:

score: 0
Accepted
time: 303ms
memory: 27044kb

input:

198242 23269680 1
1 1 11634840
2 1 2 11634840
3 1 2
2 1 2 11634840
1 1 11634840
1 1 0
1 2 0
1 1 0
2 2 6 11634840
2 2 6 11634840
3 4 6
3 5 6
1 6 11634840
2 3 6 11634840
3 2 7
2 2 5 0
2 2 3 0
2 2 3 0
2 3 7 0
2 2 3 0
3 1 3
3 2 5
2 1 3 11634840
3 3 6
3 2 5
3 5 7
2 1 6 0
1 4 0
1 4 11634840
2 7 8 11634840...

output:

11634840
0
11634840
0
11634840
0
11634840
0
0
0
0
11634840
11634840
0
11634840
11634840
0
0
11634840
0
11634840
11634840
11634840
11634840
11634840
11634840
11634840
11634840
11634840
0
11634840
11634840
11634840
11634840
0
11634840
11634840
11634840
11634840
0
0
11634840
0
11634840
11634840
1163484...

result:

ok 66135 lines

Test #29:

score: 0
Accepted
time: 324ms
memory: 25736kb

input:

198177 22462440 1
1 1 15723708
3 1 2
1 2 0
3 2 3
2 2 3 17969952
2 1 2 20216196
1 1 15723708
3 2 3
2 1 3 11231220
2 1 2 11231220
1 1 11231220
2 1 3 2246244
2 1 2 20216196
3 3 4
1 4 8984976
2 5 6 4492488
2 3 6 4492488
2 2 5 4492488
1 4 17969952
1 6 20216196
3 3 7
1 1 15723708
1 4 0
3 3 9
3 1 5
1 7 449...

output:

2246244
0
0
0
0
0
2246244
2246244
2246244
0
0
2246244
0
0
0
0
2246244
2246244
0
2246244
0
0
0
0
0
2246244
2246244
0
0
2246244
2246244
0
0
0
2246244
2246244
2246244
0
2246244
0
2246244
0
0
0
0
2246244
0
0
2246244
2246244
0
0
0
0
2246244
0
2246244
0
0
0
2246244
0
2246244
2246244
2246244
0
2246244
0
22...

result:

ok 66146 lines

Subtask #5:

score: 15
Accepted

Test #30:

score: 15
Accepted
time: 792ms
memory: 27092kb

input:

199458 2 25
1 1 31252443
2 1 2 22827339
1 2 13517756
1 2 5635412
1 3 33397078
1 3 33542998
2 3 5 1484991
3 5 6
2 1 3 7938846
2 1 2 3665458
1 3 29150948
3 4 5
1 3 733545
1 7 4698781
1 7 21699192
1 6 10854390
3 3 8
3 4 8
1 2 6889338
2 1 12 27646676
2 6 8 24407215
1 11 20847453
3 4 13
1 6 16891344
3 4 ...

output:

150016
891079
733545
1048849
7306736
7012
6336311
7310241
705870
794721
112806
777734
2522042
203310
370916
2339461
699806
747148
597151
969956
2633367
376785
884917
884917
331441
2696956
2423527
2304668
2457533
2783258
690228
864462
360811
124716
2098167
48248
2869827
605003
235881
2739062
2861794
...

result:

ok 66461 lines

Test #31:

score: 0
Accepted
time: 805ms
memory: 25692kb

input:

198986 2 25
1 1 11331234
1 2 24833898
2 1 3 10628416
3 2 3
1 3 6115878
2 2 4 23717273
1 3 18406568
2 2 4 1949969
1 4 6063130
1 6 25760596
3 1 2
3 5 7
3 5 6
3 2 6
3 1 7
1 6 31753825
3 1 4
2 3 4 6115878
3 2 6
2 3 5 22447229
3 1 3
2 3 4 6115878
2 4 7 1813362
3 2 4
2 1 8 8192320
3 3 5
1 7 114729
1 9 188...

output:

969698
11331234
9443776
2324169
990686
1086581
11610035
990686
10628416
1949969
2269429
1949969
571284
3254790
682010
502346
824812
623366
377762
377762
2376509
884877
2316090
2244147
665245
341785
922389
928237
744294
69811
404242
789948
620664
513259
317968
222762
169970
969698
12365
1046658
91964...

result:

ok 65927 lines

Test #32:

score: 0
Accepted
time: 791ms
memory: 25552kb

input:

198119 2 25
1 1 1988220
2 1 2 10935842
2 1 2 10935842
3 1 2
1 2 9175257
2 1 2 30426983
1 3 21520990
1 2 7244347
2 3 5 19700729
1 3 24753647
3 4 6
2 1 2 30426983
3 2 4
1 6 25686082
2 1 6 22244116
1 7 20608501
3 3 6
1 2 29561714
2 2 3 21107138
1 1 21122181
1 6 7460982
2 7 9 19503627
1 9 8058976
3 1 8
...

output:

1988220
3266481
684956
994474
48107
1167209
4443137
4685362
1360512
4639448
238700
348592
278885
295451
489693
344667
180320
328346
407326
454344
485048
139415
148539
301162
209675
136220
454344
201497
48475
346271
411773
397728
487925
400145
418154
120548
273314
523155
476405
141994
243836
128983
7...

result:

ok 65949 lines

Subtask #6:

score: 3
Accepted

Test #33:

score: 3
Accepted
time: 34ms
memory: 25976kb

input:

49958 1023 2
1 1 122428
1 1 917186
2 2 3 53148
1 3 876461
2 1 3 968146
2 2 4 569341
2 3 4 199413
2 1 4 238371
1 3 127427
1 2 887225
2 1 4 776059
2 4 6 155479
2 1 6 795533
1 5 159578
3 5 6
2 2 5 758778
2 5 6 601115
3 4 7
1 4 202224
2 5 6 902346
3 1 6
3 5 7
3 3 5
1 2 791251
1 5 502214
2 6 7 929048
1 6...

output:

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

result:

ok 16607 lines

Test #34:

score: 0
Accepted
time: 580ms
memory: 26156kb

input:

198392 7 9
1 1 23598910
3 1 2
1 1 25616681
2 1 2 22101090
2 2 3 25455751
3 1 2
3 1 2
1 3 25668120
3 1 3
1 3 23878180
1 4 10885281
1 1 5873751
2 2 7 31608236
3 2 3
3 3 5
2 2 6 37313936
2 1 6 36853293
2 4 7 6773989
2 1 7 19143946
3 2 7
3 3 7
3 1 2
1 1 31756932
3 3 6
2 5 8 39585364
1 2 27162269
3 4 5
2...

output:

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

result:

ok 65758 lines

Subtask #7:

score: 39
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #35:

score: 39
Accepted
time: 806ms
memory: 26352kb

input:

198752 4 12
1 1 8650000
1 2 174624
1 1 0
1 1 174624
3 4 5
2 2 4 8650003
1 4 1
1 3 3
3 1 7
2 5 6 174624
1 6 174627
1 6 12726658
3 2 4
3 1 3
1 6 174624
3 2 8
1 3 8554530
3 3 5
1 9 174627
3 2 10
3 3 6
3 6 11
1 1 8554531
1 1 174627
1 9 3
1 10 174625
1 14 174626
1 12 8397313
3 15 18
1 6 0
3 5 19
3 2 13
3...

output:

0
8476464
95536
95536
95536
95536
95536
95536
95536
0
0
95536
95536
0
0
4241824
0
5770704
95536
0
4320912
0
95536
4320912
0
0
0
5770704
0
4320912
0
5770704
95536
0
0
95536
0
5862080
4320912
4241824
5862080
5770704
4320912
0
4241824
95536
4241824
4241824
95536
0
0
0
4241824
0
0
4288176
4209024
0
5862...

result:

ok 90438 lines

Test #36:

score: 0
Accepted
time: 820ms
memory: 25940kb

input:

199927 6 9
1 1 523516
3 1 2
3 1 2
3 1 2
1 1 0
3 1 2
1 3 8476302
3 2 3
1 4 4500736
1 1 1249924
2 1 2 7070499
1 1 4015096
3 6 7
3 2 6
1 7 1249920
1 3 7312562
3 1 2
3 6 7
3 1 7
3 1 3
3 2 6
3 1 4
1 1 765580
3 9 10
1 9 4500736
1 2 765579
1 5 4500736
3 5 7
1 3 6828221
3 8 14
1 12 1249924
2 4 15 5906542
1 ...

output:

523516
523516
523516
523516
523516
0
523512
523512
0
0
0
523512
1929318
0
1929318
0
523512
523512
0
523512
523512
523512
1929318
0
2171598
0
0
523512
0
523512
523512
523512
2171598
1929318
523512
523512
1929318
523512
336768
336768
0
1984854
1742790
0
0
0
0
1742790
0
1742790
0
0
0
1742790
0
0
0
0
0
...

result:

ok 91009 lines

Test #37:

score: 0
Accepted
time: 768ms
memory: 27428kb

input:

198250 8 8
1 1 1581064
1 2 0
3 2 3
3 1 2
3 1 2
1 3 1065008
3 1 3
1 4 32
3 1 3
3 1 2
1 2 1065008
1 6 32
3 4 7
3 4 6
3 4 6
3 1 6
3 1 6
3 1 2
3 1 3
1 1 835683
3 3 6
2 7 8 1351802
1 8 1065012
1 9 147728
3 5 6
1 6 721317
3 5 7
1 1 721284
1 9 1638565
1 4 1065010
3 4 9
3 2 12
1 6 721318
1 13 606384
1 12 60...

output:

0
548888
548888
548888
548888
548888
0
0
0
548888
548888
548888
548888
0
0
0
319560
90264
0
319560
377024
90264
0
377024
0
377024
0
319560
319560
319560
0
319560
0
0
319560
0
0
90264
319560
90264
0
0
377024
0
319560
0
0
0
319560
90264
0
319560
319560
0
0
90264
90264
319560
0
8344
8344
303448
0
8344
...

result:

ok 90088 lines

Test #38:

score: 0
Accepted
time: 764ms
memory: 27428kb

input:

198177 10 7
1 1 8405060
3 1 2
1 2 4200080
1 3 8400060
3 1 2
1 4 4200080
3 3 5
3 4 5
1 2 8400060
3 2 6
3 5 6
3 3 6
3 2 4
1 5 4200080
1 6 8400060
3 2 4
1 4 0
1 2 4200080
1 5 2600040
1 3 9209575
3 4 11
3 8 11
1 2 2604080
3 3 12
1 7 8402080
3 7 9
3 1 13
3 1 5
3 3 4
1 7 2020
1 6 6808000
3 2 3
3 9 13
1 3 ...

output:

5000
5000
0
0
0
0
0
0
0
0
0
1801535
0
1060
1060
0
0
0
0
0
0
0
0
1801530
1060
1060
0
0
1801530
0
1060
0
1801530
0
0
0
0
0
0
1060
0
0
0
0
0
0
0
0
0
0
1801530
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1801530
0
0
0
0
0
0
1801530
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1801530
0
0
0
1801530
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90051 lines

Test #39:

score: 0
Accepted
time: 764ms
memory: 25988kb

input:

199605 12 7
1 1 439453
1 2 887839
3 2 3
1 1 1504230
1 3 1997572
3 1 5
1 5 134864
1 1 1997576
1 7 0
3 1 4
3 1 5
1 5 1123272
3 1 9
1 2 629930
3 1 3
3 9 10
3 7 8
3 7 10
3 4 9
3 1 5
3 1 10
3 4 8
1 7 1618350
3 2 5
1 1 2627506
3 10 12
3 2 7
3 3 5
3 3 5
3 3 12
1 11 8
1 8 1009156
3 6 11
1 9 1997572
1 4 2492...

output:

257905
67428
0
67428
67428
67428
257905
0
325333
67428
67428
325333
0
257905
325333
325333
0
0
67428
67428
0
0
0
67428
67428
67428
0
0
0
0
67428
67428
325332
67428
0
0
0
0
0
325332
0
67428
67428
325332
0
67428
0
0
0
0
67428
257904
67428
257904
257904
325332
257904
325332
0
257904
314676
257904
0
0
3...

result:

ok 90817 lines

Test #40:

score: 0
Accepted
time: 739ms
memory: 26600kb

input:

199432 18 6
1 1 20865879
1 1 22713696
3 1 3
1 1 0
3 1 3
3 2 4
3 1 3
1 1 30316248
3 2 5
3 1 5
3 2 3
1 1 30316248
1 2 11409336
1 5 9719622
3 6 8
1 7 1263600
1 1 0
2 3 9 32164406
3 4 9
3 3 6
1 7 1053013
1 6 8866158
3 3 8
1 11 4017712
1 11 23339671
3 2 7
1 3 11619944
1 14 16263619
3 9 12
1 11 20170527
1...

output:

0
0
1958967
0
1958967
0
1958967
1906470
1958958
0
1906470
0
1958958
1958958
1958958
1958958
0
1958958
1958958
1958958
1906470
0
1958958
0
1958958
1958958
0
0
1958958
1958958
0
1958958
1958958
0
0
0
0
1958958
0
1958958
1958958
0
0
0
0
0
1958958
52488
0
1958958
52488
0
1958958
1958958
0
0
0
0
0
0
1958...

result:

ok 90696 lines

Test #41:

score: 0
Accepted
time: 688ms
memory: 27280kb

input:

199092 24 5
1 1 6935
2 1 2 7410978
3 1 2
1 2 1449522
1 3 4878867
1 2 1449520
3 3 5
3 3 5
1 2 1994273
1 5 3988518
1 1 1449512
3 5 8
1 4 3988520
1 2 1994273
3 2 9
3 1 6
3 1 7
3 3 9
1 6 890951
3 7 9
1 3 4878879
1 4 1994275
3 12 13
1 2 3429953
3 9 12
1 8 3429951
1 4 1994259
1 12 1449512
1 17 2884608
1 1...

output:

6913
0
0
6913
0
6913
6913
0
0
0
0
0
0
0
0
0
0
0
6912
0
0
0
0
0
0
6912
6912
6912
6912
0
6912
6912
6912
6912
0
6912
0
0
0
0
6912
0
6912
0
0
0
0
0
0
6912
0
0
0
6912
0
6912
0
0
6912
6912
0
0
0
0
0
0
0
6912
0
0
0
0
0
0
6912
0
0
0
0
0
0
0
6912
0
6912
0
6912
0
6912
0
0
0
0
0
0
0
6912
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90353 lines

Test #42:

score: 0
Accepted
time: 650ms
memory: 25828kb

input:

198953 36 4
1 1 31112
3 1 2
1 2 31136
3 1 2
1 2 12
1 2 24
1 4 31124
1 4 15556
1 2 15568
3 5 7
1 8 15556
3 1 8
3 7 8
1 1 917536
1 1 1151284
1 11 485656
1 1 682516
3 5 6
3 9 11
3 10 12
3 5 10
1 3 1226392
3 6 9
3 4 13
1 2 1120184
3 1 7
3 4 11
1 7 1257480
3 11 15
3 13 15
3 8 15
3 11 15
3 7 10
1 12 77316...

output:

0
0
0
0
0
0
0
53752
53752
0
0
0
0
0
0
0
0
53752
0
0
53752
0
0
0
0
0
0
0
0
53752
53752
0
0
0
53748
0
53748
0
0
0
0
53748
0
53748
53748
0
53748
53748
0
0
0
0
0
0
0
53748
53748
0
0
0
0
0
0
53748
0
0
0
0
0
0
0
0
0
0
0
0
0
53748
0
0
53748
0
0
0
0
0
0
0
0
53748
0
53748
0
53748
0
0
0
0
0
53748
0
0
0
0
0
0
...

result:

ok 90667 lines

Test #43:

score: 0
Accepted
time: 655ms
memory: 26768kb

input:

198777 48 4
1 1 2714112
3 1 2
2 1 2 2695727
3 1 2
2 1 2 2750991
3 1 2
1 2 18449
1 3 92179
3 1 3
2 3 4 46090
1 4 55335
1 1 82966
3 1 6
1 5 55335
2 1 3 2658820
1 2 92161
2 2 5 101414
3 5 6
2 1 8 2751006
1 6 5
3 7 9
1 2 101398
2 4 5 64522
1 10 18446
3 3 11
3 7 10
3 6 9
3 2 10
3 2 5
1 7 82946
1 6 64551
...

output:

2658816
2658816
2658816
2658816
0
2658816
2658816
0
0
0
0
0
0
2658816
2658816
2658816
0
0
0
2658816
0
0
0
2658816
2658816
2658816
0
0
2658816
2658816
2658816
2658816
0
2658816
0
0
0
0
2658816
0
0
0
2658816
0
0
2658816
2658816
0
0
2658816
0
0
0
0
2658816
0
0
2658816
2658816
0
0
0
0
2658816
2658816
26...

result:

ok 90278 lines

Test #44:

score: 0
Accepted
time: 639ms
memory: 25936kb

input:

198900 90 3
1 1 194433
3 1 2
3 1 2
3 1 2
2 1 2 437462
3 1 2
1 1 194457
3 1 3
3 1 3
3 1 3
3 1 2
3 2 3
1 1 48605
3 1 3
1 4 48676
3 1 4
3 1 5
1 1 534616
1 1 388830
1 3 243013
1 2 388886
2 4 9 388827
3 2 7
3 2 7
3 1 7
1 2 631865
3 7 9
2 3 9 631827
3 3 5
3 5 7
3 1 3
1 2 48648
3 4 7
3 1 8
1 4 583271
3 2 9...

output:

45
45
45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 90318 lines

Test #45:

score: 0
Accepted
time: 654ms
memory: 26764kb

input:

199379 210 3
1 1 3545430
3 1 2
3 1 2
1 1 7512540
3 1 2
1 1 2240700
2 3 4 1362269
3 1 2
3 2 4
1 3 905201
2 2 5 7938700
3 2 3
1 3 2214380
1 3 7539181
3 1 3
3 1 2
1 3 5324944
3 7 8
3 1 8
3 7 8
1 3 7530204
3 3 7
1 3 3980395
1 6 4867909
3 2 11
1 11 7943173
2 1 12 474687
3 3 12
3 8 10
3 6 7
2 5 10 6212351...

output:

4410
4410
4410
4410
4410
4410
0
4410
0
0
0
0
4410
0
0
0
0
0
0
4410
4410
4410
0
0
0
4410
4410
0
0
0
0
4410
0
0
4410
0
0
0
0
0
0
0
0
0
0
0
0
0
4410
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4410
0
0
0
0
0
0
4410
0
4410
0
4410
0
0
0
4410
0
4410
4410
0
0
0
0
0
4410
0
0
0
0
0
0
0
0
4410
0
0
0
0...

result:

ok 90711 lines

Test #46:

score: 0
Accepted
time: 627ms
memory: 27356kb

input:

198749 2002 2
1 1 1318
1 2 1144
1 2 1052
3 1 4
3 1 3
1 4 1478
3 1 2
3 1 5
3 2 5
1 3 286
3 3 4
3 3 4
3 2 5
1 4 418
3 5 7
1 5 450
1 6 1828
3 1 2
1 4 936
3 2 9
1 1 1642
1 3 1678
1 1 1792
1 3 1246
3 6 9
1 2 1364
3 6 10
3 9 15
3 13 14
3 2 9
1 13 1214
3 7 11
3 8 16
3 12 14
2 6 14 1325
1 9 1526
1 1 1118
3 ...

output:

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

result:

ok 90283 lines

Test #47:

score: 0
Accepted
time: 764ms
memory: 25848kb

input:

198820 12 7
1 1 0
1 1 0
1 2 0
1 3 2488465
3 1 3
2 2 3 11
3 1 4
3 4 5
3 2 3
2 1 2 11
2 2 3 9
3 2 3
1 5 1990944
3 3 5
3 3 5
3 2 5
1 1 9
1 4 869
3 4 6
1 4 1990949
3 4 8
3 1 3
2 1 9 1990948
3 4 6
3 7 8
3 4 7
1 5 996772
3 7 8
2 5 9 1493425
1 3 875
3 1 8
1 11 996774
3 3 4
1 3 1990949
3 7 11
3 2 10
3 4 9
1...

output:

0
0
498384
0
0
498384
498384
498384
498384
0
0
498384
0
0
0
0
0
0
498384
0
498384
0
498384
0
498384
498384
498384
498384
0
0
498384
498384
0
498384
0
0
0
498384
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
498384
0
0
0
498384
0
0
0
498384
0
0
0
498384
498384
0
0
0
0
0
0
0
0
0
0
0
0
0
0
498384
0
0
0
0
0
0
0
0
0
498...

result:

ok 90302 lines

Test #48:

score: 0
Accepted
time: 725ms
memory: 27144kb

input:

199251 18 6
1 1 0
1 2 23336
1 3 35004
1 3 35004
1 2 58322
1 3 93326
3 1 7
3 4 5
1 4 46672
1 8 0
3 2 3
3 1 4
1 9 35004
3 8 10
1 2 11668
1 1 58322
1 9 46672
1 11 0
3 1 5
3 4 5
1 7 46672
2 10 15 58321
1 12 14
3 8 16
3 1 13
3 1 8
1 12 34996
1 14 11679
1 15 69994
3 3 8
3 7 14
1 11 69991
1 1 13
3 1 19
1 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
6088932
0
0
0
0
0
0
0
0
0
6088932
0
0
6088932
0
0
0
0
6088932
0
0
0
0
0
0
0
0
6088932
0
0
0
0
0
0
0
0
0
0
6088932
0
0
0
0
0
0
0
6088932
0
6088932
0
0
0
0
0
6088932
0
0
6088932
0
0
0
0
0
0
0
6088932
0
0
6088932
0
0
0
0
0
0
6088932
0
0
0
6088932
6088932
0
0
6088932
0
608893...

result:

ok 90555 lines

Test #49:

score: 0
Accepted
time: 691ms
memory: 26768kb

input:

199662 24 5
1 1 0
3 1 2
2 1 2 23
2 1 2 17
1 2 9
1 1 17
3 1 2
3 2 4
1 2 20
3 3 5
3 2 5
1 3 9
3 3 6
2 4 6 10
2 4 6 10
3 3 6
1 3 18
1 7 21
3 3 4
1 6 19
1 9 5
1 7 21
3 3 10
1 1 20
1 6 8
3 8 10
1 5 16
1 2 23
1 8 19
2 4 13 8
1 7 5
1 17 8
3 7 9
1 9 5
1 1 20
1 3 6
1 16 5
3 2 4
2 14 20 3
1 5 8
1 12 15
1 10 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15288
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15288
15288
15288
0
0
0
15288
0
0
0
0
15288
0
0
0
0
0
0
0
0
0
0
15288
0
0
0
0
0
15288
0
0
0
0
15288
0
0
0
0
15288
0
15288
15288
1528...

result:

ok 90696 lines

Test #50:

score: 0
Accepted
time: 712ms
memory: 27196kb

input:

199244 30 5
1 1 0
1 1 0
3 2 3
1 1 0
2 1 3 29
1 1 12
1 3 26
2 2 4 5
3 3 4
1 4 19
3 1 3
3 2 4
2 1 7 2
3 2 7
1 7 23
3 6 7
3 2 8
1 4 24
1 6 7
3 1 2
1 1 6
1 10 1
3 2 6
3 1 7
1 4 12
1 9 2
3 3 9
1 11 23
3 9 12
3 4 10
3 1 10
1 11 15
3 2 16
2 3 5 9
2 12 13 23
3 1 7
3 3 10
1 16 19
1 12 23
1 4 23
1 8 1
3 17 18...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4050120
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90915 lines

Test #51:

score: 0
Accepted
time: 673ms
memory: 26732kb

input:

199563 36 4
1 1 21600
1 2 6048
1 1 15552
1 1 15552
3 2 5
2 3 4 31139
3 1 4
3 2 4
2 1 3 10803
3 3 4
2 3 5 25
1 3 21604
1 6 37172
3 1 5
1 2 37160
1 1 41931
1 4 10813
1 1 21622
1 9 15567
1 11 6061
1 1 10809
3 5 14
3 4 7
1 9 21600
3 1 5
3 5 13
1 9 6048
1 16 37177
2 11 17 31119
1 9 37180
3 2 4
3 3 8
1 13...

output:

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

result:

ok 91088 lines

Test #52:

score: 0
Accepted
time: 676ms
memory: 27052kb

input:

199314 48 4
1 1 0
3 1 2
3 1 2
1 1 790272
3 1 2
1 2 3838464
1 4 903168
1 1 225792
3 1 5
1 5 3824640
3 2 4
1 4 930816
1 8 2257920
1 4 5110272
3 3 5
1 10 930816
1 4 760320
3 3 11
3 3 8
3 1 9
1 7 2059776
1 7 2709504
1 3 1410048
3 7 12
1 8 27648
3 4 12
1 7 3386880
3 1 8
3 1 11
1 16 4741632
1 2 2880000
3 ...

output:

0
0
0
0
0
112896
112896
112896
0
13824
0
0
0
112896
126720
0
13824
13824
13824
112896
112896
0
112896
112896
0
126720
0
0
13824
13824
0
0
126720
0
126720
0
13824
0
112896
0
13824
13824
13824
13824
13824
0
13824
13824
0
0
0
13824
13824
0
0
112896
13824
0
13824
13824
0
13824
13824
13824
13824
0
0
0
0
...

result:

ok 90927 lines

Test #53:

score: 0
Accepted
time: 668ms
memory: 26688kb

input:

199298 54 4
1 1 116855
3 1 2
3 1 2
1 1 76192
3 2 3
1 3 118286
3 1 2
2 1 3 141953
1 2 94616
3 1 5
1 2 141936
2 5 6 42159
3 3 6
3 1 3
1 1 8118
2 3 5 43618
2 1 7 76161
2 1 3 31777
1 7 113127
3 7 8
3 3 4
3 1 5
1 4 105027
1 6 18470
1 4 99800
3 4 8
1 1 152313
1 7 27
1 2 42124
1 7 104982
3 12 14
3 1 2
3 6 ...

output:

1485
1485
1485
1485
1458
1458
0
0
0
1458
0
1458
1458
1458
0
0
0
1458
0
0
1458
1458
1458
0
1458
1458
0
0
1458
0
0
0
1458
1458
1458
0
1458
0
0
0
1458
0
1458
1458
0
1458
0
0
0
0
0
1458
0
1458
0
0
0
1458
0
1458
1458
1458
1458
1458
0
1458
0
0
1458
0
1458
1458
0
1458
0
1458
0
1458
1458
0
1458
1458
0
1458
...

result:

ok 90766 lines

Test #54:

score: 0
Accepted
time: 682ms
memory: 25768kb

input:

199468 60 4
1 1 7256940
3 1 2
3 1 2
1 2 9109560
3 1 3
3 1 2
1 2 5184720
3 1 2
2 3 4 1479539
1 1 3999241
3 3 5
3 1 4
3 1 3
2 1 2 12512495
3 1 4
1 4 5184749
3 4 6
3 4 6
1 5 5329970
1 2 6660615
3 1 8
1 4 10369488
3 3 9
3 8 9
2 1 4 4592001
3 1 7
3 1 5
3 2 3
3 1 5
1 5 11845329
3 3 9
3 5 10
3 4 10
3 1 4
1...

output:

667140
667140
667140
667140
667140
667140
667140
667140
667140
0
0
667140
0
0
0
0
0
0
0
0
667140
667140
0
0
667140
667140
667140
667140
667140
0
0
667140
0
0
0
0
667140
667140
0
0
0
667140
667140
0
0
667140
0
667140
0
0
0
0
0
667140
667140
667140
667140
667140
667140
667140
0
0
667140
0
0
667140
667...

result:

ok 90556 lines

Test #55:

score: 0
Accepted
time: 767ms
memory: 25992kb

input:

197994 8 8
1 1 11117696
3 1 2
3 1 2
3 1 2
3 1 2
2 1 2 2860167
1 2 8519684
3 1 3
1 1 5
1 1 8519683
3 3 4
3 2 4
3 2 3
2 1 3 2860165
3 2 5
1 3 8519682
1 1 5458183
1 6 13715716
3 1 5
1 5 5458178
3 2 7
3 4 7
1 5 5
3 3 8
3 6 8
1 2 13715714
1 3 7
3 4 7
1 1 2
1 6 13715717
1 8 13715719
2 4 12 11117703
1 4 85...

output:

2860160
2860160
2860160
2860160
2860160
2860160
2860160
0
2860160
0
2860160
0
0
0
0
2860160
0
0
2860160
2860160
2860160
0
2860160
0
2860160
2860160
2860160
2860160
0
2860160
2860160
0
2860160
2860160
2860160
0
2860160
2860160
0
0
2860160
2860160
0
2860160
0
2860160
0
2860160
2860160
2860160
2860160
...

result:

ok 89932 lines

Test #56:

score: 0
Accepted
time: 730ms
memory: 25944kb

input:

198642 16 6
1 1 8737
2 1 2 8736
1 2 17485
1 2 2
1 4 8
1 4 52429
3 3 6
3 1 2
1 2 15
1 6 34951
1 7 2
3 1 8
1 9 17473
1 4 34959
1 9 34957
3 2 12
3 5 6
1 11 17485
1 9 34947
3 5 12
3 4 5
3 7 14
1 9 17478
1 15 9
1 15 34952
3 10 12
3 3 4
3 9 15
2 1 15 61167
1 12 15
1 8 17476
1 17 52427
3 4 20
3 2 19
3 6 19...

output:

0
8736
8736
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8736
0
0
0
0
0
0
0
8736
0
0
0
0
0
0
0
0
0
0
0
0
8736
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8736
0
8736
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 90458 lines

Test #57:

score: 0
Accepted
time: 644ms
memory: 27136kb

input:

198135 80 4
1 1 332873
3 1 2
1 2 460858
1 3 256050
1 2 60
3 2 5
1 3 256070
1 6 102424
1 6 204868
1 2 358474
1 9 102464
1 1 102444
1 10 204828
1 3 256030
1 12 40
1 3 204828
3 8 11
3 5 9
3 2 10
1 9 256030
3 2 14
3 3 5
1 2 409636
1 4 409636
1 4 51262
3 6 7
3 3 14
3 12 15
3 13 16
3 10 14
3 2 10
3 1 4
2 ...

output:

25601
0
25601
0
0
0
0
0
0
0
0
0
0
25601
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25600
0
25600
0
0
0
0
0
0
25600
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25600
0
0
0
0
0
0
0
25600
0
0
0
0
0
0
0
0
0
0
0
0
0
25600
0
0
0
0
0
0
25600
0
0
0
0
0
0
0
0
0
0
0
0
25600
0
0
25600
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 90194 lines