QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119796#5659. Watching Cowflixpandapythoner#25 546ms40676kbC++145.9kb2023-07-05 19:38:212024-07-04 00:19:02

Judging History

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

  • [2024-07-04 00:19:02]
  • 评测
  • 测评结果:25
  • 用时:546ms
  • 内存:40676kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 19:38:21]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


mt19937 rnd(234);
const ll inf = 1e18;


int n;
vector<int> s;
vector<vector<int>> g;
vector<ll> rs;
vector<int> usd;
vector<ll> dp_clrd, dp_not_clrd;
int dfs_usdc;
vector<int> dfs_usd;
vector<int> prnt;


void dfs0(int v, int p, ll k){
    prnt[v] = p;
    dfs_usd[v] = dfs_usdc;
    dp_clrd[v] = -1 - k;
    dp_not_clrd[v] = 0;
    for(auto to: g[v]){
        if(dfs_usd[to] != dfs_usdc && to != p && usd[to] == 0){
            dfs0(to, v, k);
            dp_not_clrd[v] += max(dp_clrd[to], dp_not_clrd[to]);
            if(dp_clrd[to] + k > dp_not_clrd[to]){
                dp_clrd[v] += dp_clrd[to] + k;
            } else{
                dp_clrd[v] += dp_not_clrd[to];
            }
        }
        if(usd[to] == 2){
            dp_clrd[v] += k;
        }
    }
}


void dfs1(int v, int p, ll k, bool clrd, ll &dsm, ll &dcmps){
    if(clrd){
        usd[v] = 1;
        dsm += -1 - k;
        dcmps -= 1;
        for(auto to: g[v]){
            if(to != p && usd[to] == 0){
                if(dp_clrd[to] + k > dp_not_clrd[to]){
                    dcmps += 1;
                    dsm += k;
                    dfs1(to, v, k, true, dsm, dcmps);
                } else{
                    dfs1(to, v, k, false, dsm, dcmps);
                }
            }
            if(usd[to] == 2){
                dsm += k;
                dcmps += 1;
            }
        }
    } else{
        for(auto to: g[v]){
            if(to != p && usd[to] == 0){
                if(dp_clrd[to] > dp_not_clrd[to]){
                    dfs1(to, v, k, true, dsm, dcmps);
                } else{
                    dfs1(to, v, k, false, dsm, dcmps);
                }
            }
        }
    }
}



void solve_slow(){
    rs.resize(n + 1);
    usd.resize(n);
    for(int i = 0; i < n; i += 1){
        if(s[i] == 0){
            usd[i] = 0;
        } else{
            usd[i] = 2;
        }
    }
    dfs_usdc = 10;
    dfs_usd.assign(n, 0);
    prnt.resize(n);
    dp_clrd.resize(n);
    dp_not_clrd.resize(n);
    ll sm = 0;
    ll components = 0;
    for(int i = 0; i < n; i += 1){
        if(s[i] == 1){
            sm += 1;
            components += 1;
        }
    }
    for(int v = 0; v < n; v += 1){
        for(auto to: g[v]){
            if(v < to && usd[v] == 2 && usd[to] == 2){
                components -= 1;
            }
        }
    }
    for(int k = 1; k <= n; k += 1){
        dfs_usdc += 1;
        sm += components;
        vector<int> not_usd;
        not_usd.reserve(n);
        for(int i = 0; i < n; i += 1){
            if(usd[i] == 0){
                not_usd.push_back(i);
            }
        }
        for(auto v: not_usd){
            if(dfs_usd[v] != dfs_usdc){
                dfs0(v, -1, k);
                ll dsm = 0;
                ll dcmps = 0;
                if(dp_clrd[v] > dp_not_clrd[v]){
                    dfs1(v, -1, k, true, dsm, dcmps);
                } else{
                    dfs1(v, -1, k, false, dsm, dcmps);
                }
                sm -= dsm;
                components -= dcmps;
            }
        }
        for(auto v: not_usd){
            if(usd[v] == 1){
                usd[v] = 2;
            }
        }
        rs[k] = sm;
    }
}


void solve(ll tl, ll tr, ll sm, ll cmps, vector<int> &vrtcs){
    if(tl > tr){
        return;
    }
    ll k = (tl + tr) / 2;
    vector<int> lft_vrtcs, rght_vrtcs;
    ll my_sm = sm + cmps * (k - tl + 1);
    ll my_cmps = cmps;
    dfs_usdc += 1;
    for(auto v: vrtcs){
        if(dfs_usd[v] != dfs_usdc){
            dfs0(v, -1, k);
            ll dsm = 0;
            ll dcmps = 0;
            if(dp_clrd[v] > dp_not_clrd[v]){
                dfs1(v, -1, k, true, dsm, dcmps);
            } else{
                dfs1(v, -1, k, false, dsm, dcmps);
            }
            my_sm -= dsm;
            my_cmps -= dcmps;
        }
    }
    rs[k] = my_sm;
    for(auto v: vrtcs){
        if(usd[v] == 1){
            lft_vrtcs.push_back(v);
        } else{
            rght_vrtcs.push_back(v);
        }
    }
    solve(k + 1, tr, my_sm, my_cmps, rght_vrtcs);
    for(auto v: rght_vrtcs){
        usd[v] = 1;
    }
    for(auto v: lft_vrtcs){
        usd[v] = 0;
    }
    solve(tl, k - 1, sm, cmps, lft_vrtcs);
}


void solve(){
    rs.resize(n + 1);
    usd.resize(n);
    for(int i = 0; i < n; i += 1){
        if(s[i] == 0){
            usd[i] = 0;
        } else{
            usd[i] = 2;
        }
    }
    dfs_usdc = 10;
    dfs_usd.assign(n, 0);
    prnt.resize(n);
    dp_clrd.resize(n);
    dp_not_clrd.resize(n);
    ll sm = 0;
    ll components = 0;
    for(int i = 0; i < n; i += 1){
        if(s[i] == 1){
            sm += 1;
            components += 1;
        }
    }
    for(int v = 0; v < n; v += 1){
        for(auto to: g[v]){
            if(v < to && usd[v] == 2 && usd[to] == 2){
                components -= 1;
            }
        }
    }
    vector<int> vrtcs;
    for(int i = 0; i < n; i += 1){
        if(usd[i] == 0){
            vrtcs.push_back(i);
        }
    }
    solve(1, n, sm, components, vrtcs);
}


int32_t main(){
    if(1){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    // assert(n <= 1e4);
    s.resize(n);
    for(int i = 0; i < n; i += 1){
        char c;
        cin >> c;
        s[i] = c - '0';
    }
    g.assign(n, vector<int>());
    for(int i = 0; i < n - 1; i += 1){
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    solve();
    for(int k = 1; k <= n; k += 1){
        cout << rs[k] << "\n";
    }
    return 0;
}

詳細信息

Test #1:

score: 4.16667
Accepted
time: 0ms
memory: 3668kb

input:

5
10001
1 2
2 3
3 4
4 5

output:

4
6
8
9
10

result:

ok 5 number(s): "4 6 8 9 10"

Test #2:

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

input:

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

output:

4
6
8
9
10
11
12

result:

ok 7 numbers

Test #3:

score: 0
Wrong Answer
time: 3ms
memory: 4316kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...

output:

711
837
957
1040
1124
1203
1277
1349
1352
1401
1449
1496
1541
1586
1631
1675
1718
1760
1742
1776
1809
1842
1875
1907
1938
1968
1998
2027
2056
2084
2111
2138
2164
2189
2213
2237
2260
2283
2286
2308
2329
2349
2368
2386
2404
2422
2439
2456
2472
2487
2502
2516
2529
2541
2552
2563
2573
2583
2593
2603
261...

result:

wrong answer 3rd numbers differ - expected: '944', found: '957'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 4500kb

input:

5000
0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...

output:

890
1226
1472
1547
1649
1748
1845
1940
1821
1866
1910
1953
1995
2036
2076
2115
2154
2192
2206
2240
2273
2305
2336
2366
2395
2424
2452
2479
2506
2532
2557
2581
2604
2626
2648
2670
2691
2711
2730
2749
2768
2786
2804
2821
2837
2853
2869
2884
2898
2911
2923
2934
2944
2953
2962
2971
2980
2988
2995
3001
3...

result:

wrong answer 3rd numbers differ - expected: '1433', found: '1472'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 4240kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...

output:

794
1025
1199
1284
1382
1475
1561
1641
1559
1600
1640
1679
1717
1754
1790
1826
1861
1895
1928
1960
1992
2024
2056
2088
2119
2150
2181
2211
2241
2270
2298
2325
2351
2376
2401
2425
2448
2471
2493
2515
2536
2556
2575
2594
2612
2629
2645
2660
2674
2688
2701
2713
2724
2734
2743
2751
2759
2766
2772
2777
2...

result:

wrong answer 3rd numbers differ - expected: '1178', found: '1199'

Test #6:

score: 4.16667
Accepted
time: 148ms
memory: 32012kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30804
41189
48182
51855
52223
52591
52958
53324
53690
54055
54419
54782
55144
55505
55865
56224
56582
56939
57295
57650
58004
58357
58709
59061
59412
59762
60111
60459
60806
61152
61497
61841
62184
62526
62867
63207
63546
63884
64222
64559
64895
65230
65564
65898
66231
66563
66894
67224
67554
67883
...

result:

ok 200000 numbers

Test #7:

score: 4.16667
Accepted
time: 144ms
memory: 32248kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30644
41023
48123
51892
52268
52643
53017
53390
53763
54135
54506
54876
55245
55613
55980
56346
56712
57077
57441
57804
58166
58528
58889
59249
59608
59966
60323
60679
61034
61388
61741
62093
62445
62796
63146
63495
63843
64190
64536
64881
65225
65568
65910
66251
66591
66931
67270
67608
67945
68281
...

result:

ok 200000 numbers

Test #8:

score: 4.16667
Accepted
time: 132ms
memory: 31996kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30736
41111
48167
51868
52239
52609
52978
53346
53714
54081
54447
54812
55176
55539
55902
56264
56625
56985
57344
57702
58060
58417
58774
59130
59485
59839
60192
60544
60895
61245
61594
61942
62289
62635
62980
63324
63668
64011
64353
64695
65036
65377
65717
66057
66396
66734
67071
67408
67744
68079
...

result:

ok 200000 numbers

Test #9:

score: 0
Wrong Answer
time: 65ms
memory: 16532kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12231
15712
15163
16300
17331
17762
18418
19056
19668
20270
20860
20243
20535
20827
21118
21409
21699
21989
22277
22564
22850
23136
23420
22900
23090
23279
23467
23655
23842
24028
24213
24398
24582
24765
24948
25131
25313
25495
25676
25856
26036
26215
26393
26571
26748
26925
27102
27029
27192
27355
...

result:

wrong answer 2nd numbers differ - expected: '13861', found: '15712'

Test #10:

score: 0
Wrong Answer
time: 93ms
memory: 17072kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15993
21937
25281
27931
30360
28313
28818
29322
29823
30323
30822
29846
30047
30247
30446
30645
30844
31042
31239
31436
31633
31829
32024
32099
32281
32462
32642
32821
33000
33178
33355
33531
33706
33880
34053
34225
34396
34566
34735
34904
35073
35242
35410
35578
35745
35912
36078
36243
36408
36573
...

result:

wrong answer 2nd numbers differ - expected: '21877', found: '21937'

Test #11:

score: 0
Wrong Answer
time: 106ms
memory: 16768kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14608
18567
21252
23670
25846
24472
24916
25358
25796
26233
26666
25807
25993
26179
26365
26550
26735
26920
27104
27288
27472
27656
27839
28010
28191
28372
28552
28732
28912
29091
29269
29447
29624
29801
29977
30152
30327
30502
30677
30851
31024
31196
31368
31539
31710
31881
32051
32220
32388
32556
...

result:

wrong answer 2nd numbers differ - expected: '18481', found: '18567'

Test #12:

score: 0
Wrong Answer
time: 69ms
memory: 17300kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12198
15655
15093
16220
17244
17738
18418
19082
19731
20375
21007
20361
20691
21020
21348
21675
22001
22325
22649
22972
23293
23613
23932
23363
23585
23806
24026
24246
24465
24683
24901
25119
25336
25553
25769
25984
26198
26412
26625
26838
27051
27264
27477
27689
27900
28111
28321
28251
28445
28639
...

result:

wrong answer 2nd numbers differ - expected: '13815', found: '15655'

Test #13:

score: 0
Wrong Answer
time: 91ms
memory: 17024kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16072
22021
25331
27983
30406
28439
28947
29453
29957
30460
30959
30031
30237
30442
30646
30850
31054
31257
31460
31662
31863
32063
32262
32343
32530
32716
32902
33087
33271
33455
33638
33820
34001
34181
34361
34540
34718
34895
35071
35246
35421
35595
35769
35943
36117
36290
36462
36633
36803
36972
...

result:

wrong answer 2nd numbers differ - expected: '21956', found: '22021'

Test #14:

score: 0
Wrong Answer
time: 93ms
memory: 16684kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14721
18772
21526
24003
26239
25022
25543
26060
26576
27091
27604
26556
26770
26984
27197
27409
27620
27831
28041
28250
28458
28666
28873
29068
29273
29477
29680
29882
30083
30283
30482
30680
30877
31073
31269
31465
31661
31856
32050
32243
32436
32628
32819
33010
33200
33390
33579
33767
33954
34141
...

result:

wrong answer 2nd numbers differ - expected: '18698', found: '18772'

Test #15:

score: 0
Wrong Answer
time: 72ms
memory: 16552kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12121
15560
15063
16211
17253
17644
18303
18939
19559
20171
20777
20159
20466
20771
21076
21380
21682
21983
22282
22580
22877
23173
23468
22881
23076
23270
23464
23657
23850
24042
24233
24423
24612
24801
24990
25179
25367
25554
25740
25925
26109
26292
26475
26658
26840
27021
27202
27104
27271
27437
...

result:

wrong answer 2nd numbers differ - expected: '13753', found: '15560'

Test #16:

score: 0
Wrong Answer
time: 97ms
memory: 17072kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16192
22165
25455
28069
30465
28532
29039
29545
30049
30548
31046
30066
30267
30468
30668
30867
31065
31263
31461
31659
31856
32052
32247
32316
32497
32677
32856
33034
33212
33389
33566
33743
33920
34096
34272
34447
34621
34794
34966
35137
35308
35479
35649
35818
35986
36153
36319
36484
36648
36811
...

result:

wrong answer 2nd numbers differ - expected: '22112', found: '22165'

Test #17:

score: 0
Wrong Answer
time: 104ms
memory: 16808kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14705
18734
21466
23893
26084
24932
25456
25978
26498
27009
27508
26586
26827
27067
27307
27546
27785
28023
28260
28496
28731
28966
29200
29433
29666
29898
30129
30359
30589
30818
31047
31275
31502
31728
31953
32177
32401
32624
32846
33067
33287
33507
33726
33945
34163
34381
34598
34814
35029
35243
...

result:

wrong answer 2nd numbers differ - expected: '18667', found: '18734'

Test #18:

score: 0
Wrong Answer
time: 73ms
memory: 16584kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12282
15668
15142
16281
17293
17756
18416
19063
19694
20306
20907
20273
20577
20880
21181
21482
21782
22081
22379
22676
22972
23267
23562
22938
23131
23323
23514
23704
23893
24082
24270
24457
24643
24829
25014
25198
25381
25563
25745
25927
26109
26290
26470
26649
26827
27004
27180
27116
27279
27441
...

result:

wrong answer 2nd numbers differ - expected: '13869', found: '15668'

Test #19:

score: 4.16667
Accepted
time: 165ms
memory: 19088kb

input:

100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111
114
117
120
123
126
129
132
135
138
141
144
147
150
153
156
159
162
165
168
171
174
177
180
183
186
189
192
195
198
201
204
207
210
213
216
219
222
225
228
231
234
237
240
243
246
249
252
25...

result:

ok 100000 numbers

Test #20:

score: 0
Wrong Answer
time: 203ms
memory: 31172kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

32208
43929
50276
55340
59958
56024
56926
57826
58719
59610
60498
58476
58768
59059
59350
59640
59930
60220
60510
60800
61090
61379
61667
61691
61953
62214
62474
62733
62991
63248
63504
63759
64013
64267
64520
64772
65023
65273
65522
65771
66019
66266
66513
66760
67006
67251
67495
67738
67980
68221
...

result:

wrong answer 2nd numbers differ - expected: '43788', found: '43929'

Test #21:

score: 0
Wrong Answer
time: 235ms
memory: 30528kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

29187
37186
42486
47196
51413
48729
49593
50453
51303
52144
52979
50856
51133
51409
51684
51959
52233
52506
52779
53052
53325
53597
53869
54119
54389
54659
54928
55197
55465
55732
55998
56263
56528
56792
57055
57317
57579
57841
58103
58364
58624
58884
59143
59401
59658
59915
60171
60426
60681
60936
...

result:

wrong answer 2nd numbers differ - expected: '37057', found: '37186'

Test #22:

score: 0
Wrong Answer
time: 162ms
memory: 32152kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

24124
30874
29594
31671
33553
34385
35586
36758
37888
38997
40095
38868
39367
39866
40364
40861
41358
41854
42348
42842
43335
43827
44318
43101
43392
43683
43973
44262
44550
44837
45124
45410
45695
45979
46263
46546
46829
47111
47393
47674
47955
48235
48514
48793
49071
49349
49626
49478
49734
49989
...

result:

wrong answer 2nd numbers differ - expected: '27220', found: '30874'

Test #23:

score: 0
Wrong Answer
time: 215ms
memory: 31076kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

32229
44105
50557
55650
60343
56305
57185
58062
58934
59802
60667
58701
58996
59290
59583
59876
60169
60462
60755
61047
61338
61628
61917
61927
62191
62455
62718
62980
63242
63503
63764
64024
64283
64542
64800
65057
65314
65570
65826
66081
66335
66588
66840
67091
67341
67590
67838
68085
68332
68578
...

result:

wrong answer 2nd numbers differ - expected: '44001', found: '44105'

Test #24:

score: 0
Wrong Answer
time: 546ms
memory: 40676kb

input:

200000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111
114
117
120
123
126
129
132
135
138
141
144
147
150
153
156
159
162
165
168
171
174
177
180
183
186
189
192
195
198
201
204
207
210
213
216
219
222
225
228
231
234
237
240
243
246
249
252
25...

result:

wrong answer 18425th numbers differ - expected: '43404', found: '43405'