QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211829#7400. Digital RootSolitaryDreamTL 4455ms318492kbC++174.1kb2023-10-12 21:36:202023-10-12 21:36:20

Judging History

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

  • [2023-10-12 21:36:20]
  • 评测
  • 测评结果:TL
  • 用时:4455ms
  • 内存:318492kb
  • [2023-10-12 21:36:20]
  • 提交

answer

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

#define int long long

using pii=pair<int,int>;

const int N=1e6+1e5+7;

int cnt[16][1<<16];

int n,m,B;

char S[N];

int a[N],s[N];

vector<int> pos[16];

int dp[N][2],F[2];

signed g[N][2][16][2];

int G[2][16][2];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // scanf("%lld%lld%lld",&n,&m,&B);
    cin>>n>>m>>B;
    // scanf("%s",S+1);
    cin>>(S+1);
    int cz=0,sz=0,nz=0,bz=0;
    int W=B-1;
    for(int i=1;i<=n;i++)
    {
        if(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                dp[i][j]=dp[i-1][j];
        }
        else
        {
            dp[i][1]=dp[i-1][0];
        }
        dp[i][S[i]!='0']++;
        for(int j=0;j<2;j++)
            F[j]+=dp[i][j];


        if(S[i]=='0')
            sz++;
        else
            sz=0;
        cz+=sz;
        a[i]=islower(S[i])?S[i]-'a'+10:S[i]-'0';
        bz+=a[i]==B-1;
        a[i]%=(B-1);

        
            
        if(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                for(int k=0;k<W;k++)
                    g[i][j][(k+a[i])%W][1]=g[i-1][j][k][0]+g[i-1][j][k][1];
        }
        else if(a[i]!=0)
        {
            for(int j=0;j<W;j++)
                g[i][1][(j+a[i])%W][1]=g[i-1][0][j][0]+g[i-1][0][j][1];
        }
        if(S[i]=='0'||a[i]!=0)
            g[i][a[i]!=0][a[i]][0]++;
        for(int j=0;j<2;j++)
            for(int k=0;k<W;k++)
                for(int t=0;t<2;t++)
                G[j][k][t]+=g[i][j][k][t];
        nz+=S[i]!='0';
    }
    vector<pii>st;
    pos[0].push_back(0);
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%W;
        pos[s[i]].push_back(i);
        st.push_back({1<<a[i],i});
        for(auto &[x,y]:st)
            x|=1<<a[i];
        vector<pii> nst;
        reverse(st.begin(),st.end());
        for(auto [x,y]:st)
        {
            if(nst.empty()||x!=nst.back().first)
                nst.push_back({x,y});
        }
        st.swap(nst);
        reverse(st.begin(),st.end());
        for(int y=(int)st.size()-1;y>=0;y--)
        {
            int R=st[y].second,L=y>0?st[y-1].second+1:1;
            for(int j=0;j<W;j++)
            {
                int v=(s[i]-j+W)%(W);
                int A=upper_bound(pos[v].begin(),pos[v].end(),R-1)-lower_bound(pos[v].begin(),pos[v].end(),L-1);
                // if(j==2&&A)n
                cnt[j][st[y].first]+=A;
            }
        }
    }
    for(int t=0;t<W;t++)
        for(int i=0;i<W;i++)
            for(int S=0;S<(1<<W);S++)
                if(!(S>>i&1))
                    cnt[t][S^(1<<i)]+=cnt[t][S];
    while(m--)
    {
        cin>>S;
        int x=islower(S[0])?S[0]-'a'+10:S[0]-'0';
        int bx=x;
        x%=W;
        cin>>S;
        if(bx==0)
        {
            int p=strlen(S);
            bool ok=0;
            for(int j=0;j<p;j++)
                if(S[j]=='0')
                    ok=1;
            cout<<F[0]+ok*F[1]<<"\n";
            // printf("%lld\n",F[0]+ok*(F[1]));
            continue;
        }
        int p=strlen(S);
        int E=0;
        for(int i=0;i<p;i++)
            E|=1<<(islower(S[i])?S[i]-'a'+10:S[i]-'0');
        long long ans=0;
            ans+=cnt[x][(1<<W)-1];
        if(x==0&&!(E&(1<<W)))
            ans-=F[0];
        if(E&(1<<W))
        {
            E^=(1<<W);
            E|=1;
        }
        else if((E&1))
        {
            if(x==0)
            {
                for(int t=0;t<W;t++)
                {
                    if(!(E>>t&1))
                    {
                        // assert(!G[1][0][1]);
                        ans-=G[1][(W-t)%W][1];
                    }
                    ans-=G[1][t][0];
                }
            }
        }
        for(int j=0;j<W;j++)
        {
            if(j==x)
                continue;
            int s=(x-j+W)%(W);
            int nS=E>>s|((E<<(W)>>s)&((1<<W)-1));
            nS^=(1<<W)-1;
            ans+=cnt[j][(1<<W)-1]-cnt[j][nS];
        }
        cout<<ans<<"\n";
    }
}

详细

Test #1:

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

input:

9 2 10
123456789
9 12
8 123456789

output:

24
45

result:

ok 2 tokens

Test #2:

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

input:

5 10 5
01234
0 1
1 1
2 1
3 1
4 1
0 1
1 0
2 0
3 0
4 0

output:

1
13
9
9
9
1
10
9
10
6

result:

ok 10 tokens

Test #3:

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

input:

19 6 2
0010111001010011111
0 0
0 1
0 01
1 0
1 1
1 01

output:

42
11
42
179
190
190

result:

ok 6 tokens

Test #4:

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

input:

13 21 3
1010011001002
0 0
0 1
0 10
0 2
0 20
0 21
0 012
1 0
1 1
1 01
1 2
1 20
1 12
1 021
2 0
2 1
2 01
2 2
2 02
2 12
2 102

output:

36
10
36
10
36
10
36
78
90
91
78
78
91
91
58
76
76
91
91
91
91

result:

ok 21 tokens

Test #5:

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

input:

15 60 4
313213200103021
0 0
0 1
0 01
0 2
0 20
0 21
0 021
0 3
0 30
0 31
0 103
0 23
0 032
0 321
0 0132
1 0
1 1
1 10
1 2
1 02
1 12
1 021
1 3
1 30
1 13
1 310
1 23
1 203
1 312
1 1302
2 0
2 1
2 01
2 2
2 02
2 21
2 120
2 3
2 03
2 13
2 031
2 32
2 320
2 213
2 0321
3 0
3 1
3 01
3 2
3 20
3 12
3 201
3 3
3 30
3 1...

output:

27
5
27
5
27
5
27
5
27
5
27
5
27
5
27
96
118
120
105
105
120
120
96
96
120
120
105
105
120
120
89
104
104
118
120
120
120
89
89
104
104
120
120
120
120
100
93
103
99
105
108
108
120
120
120
120
120
120
120
120

result:

ok 60 tokens

Test #6:

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

input:

14 155 5
03033201040331
0 0
0 1
0 10
0 2
0 20
0 21
0 210
0 3
0 03
0 13
0 130
0 23
0 302
0 312
0 3201
0 4
0 40
0 14
0 140
0 42
0 042
0 421
0 0421
0 43
0 043
0 341
0 0143
0 423
0 3240
0 2314
0 30214
1 0
1 1
1 01
1 2
1 20
1 12
1 012
1 3
1 30
1 13
1 103
1 32
1 203
1 213
1 1302
1 4
1 40
1 41
1 041
1 24
1...

output:

26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
5
26
68
91
97
84
88
104
105
72
81
102
103
90
90
105
105
68
68
97
97
88
88
105
105
81
81
103
103
90
90
105
105
66
75
82
95
104
104
105
75
82
88
89
102
105
105
105
66
66
82
82
104
104
105
105
82
82
89
89
105
105
105
105
79
79
86
...

result:

ok 155 tokens

Test #7:

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

input:

11 378 6
34155331452
0 0
0 1
0 10
0 2
0 20
0 21
0 201
0 3
0 03
0 13
0 301
0 32
0 203
0 231
0 2301
0 4
0 04
0 14
0 401
0 42
0 402
0 412
0 0214
0 34
0 340
0 143
0 1340
0 234
0 4032
0 1243
0 03412
0 5
0 50
0 51
0 051
0 25
0 520
0 512
0 2015
0 35
0 053
0 513
0 5301
0 352
0 5320
0 5123
0 51302
0 45
0 054...

output:

11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
0
11
44
54
65
50
52
65
66
42
52
60
66
55
55
66
66
41
52
60
65
53
54
65
66
49
55
63
66
56
56
66
66
44
44
65
65
52
52
66
66
52
52
66
66
55
55
66
66
5...

result:

ok 378 tokens

Test #8:

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

input:

10 889 7
2433333441
0 0
0 1
0 01
0 2
0 20
0 21
0 210
0 3
0 03
0 13
0 301
0 32
0 032
0 123
0 3201
0 4
0 40
0 41
0 104
0 24
0 240
0 412
0 4102
0 34
0 304
0 143
0 1340
0 342
0 4320
0 2134
0 43210
0 5
0 05
0 51
0 051
0 52
0 502
0 251
0 2510
0 35
0 530
0 315
0 3510
0 253
0 0532
0 3521
0 05231
0 54
0 504
...

output:

10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
10
0
...

result:

ok 889 tokens

Test #9:

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

input:

12 2040 8
512641272172
0 0
0 1
0 10
0 2
0 02
0 12
0 120
0 3
0 30
0 13
0 310
0 23
0 203
0 132
0 1203
0 4
0 04
0 41
0 140
0 42
0 042
0 421
0 4102
0 43
0 043
0 143
0 0341
0 342
0 3402
0 3142
0 23410
0 5
0 05
0 51
0 501
0 25
0 502
0 251
0 1502
0 35
0 035
0 153
0 1350
0 253
0 2350
0 3125
0 31205
0 45
0 4...

output:

12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
...

result:

ok 2040 tokens

Test #10:

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

input:

17 4599 9
05628257863606468
0 0
0 1
0 10
0 2
0 02
0 21
0 210
0 3
0 03
0 13
0 013
0 23
0 032
0 231
0 0321
0 4
0 40
0 14
0 401
0 24
0 402
0 421
0 0124
0 34
0 043
0 134
0 1403
0 243
0 2043
0 3241
0 32140
0 5
0 50
0 15
0 501
0 52
0 205
0 215
0 5210
0 35
0 350
0 153
0 0351
0 523
0 0235
0 2135
0 05321
0 5...

output:

20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
20
2
...

result:

ok 4599 tokens

Test #11:

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

input:

12 10230 10
544253693210
0 0
0 1
0 01
0 2
0 02
0 21
0 102
0 3
0 30
0 13
0 130
0 32
0 023
0 213
0 0132
0 4
0 40
0 14
0 410
0 24
0 402
0 214
0 2014
0 43
0 043
0 431
0 4130
0 234
0 3420
0 3124
0 10423
0 5
0 05
0 15
0 105
0 52
0 250
0 251
0 1520
0 53
0 305
0 531
0 5013
0 352
0 3205
0 3251
0 12305
0 45
0...

output:

13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
...

result:

ok 10230 tokens

Test #12:

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

input:

11 22517 11
88902812271
0 0
0 1
0 01
0 2
0 02
0 21
0 102
0 3
0 03
0 31
0 013
0 32
0 230
0 213
0 2310
0 4
0 40
0 14
0 014
0 42
0 042
0 241
0 1402
0 43
0 034
0 341
0 4031
0 432
0 3024
0 2413
0 13204
0 5
0 05
0 51
0 015
0 25
0 520
0 512
0 2051
0 53
0 035
0 351
0 0531
0 523
0 2305
0 5321
0 51302
0 45
0 ...

output:

13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
13
1
...

result:

ok 22517 tokens

Test #13:

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

input:

20 49140 12
4106a58ba660082b59b8
0 0
0 1
0 01
0 2
0 20
0 21
0 021
0 3
0 30
0 13
0 310
0 32
0 320
0 321
0 0312
0 4
0 40
0 14
0 410
0 42
0 420
0 241
0 0124
0 34
0 043
0 134
0 0314
0 243
0 3420
0 3421
0 40231
0 5
0 05
0 51
0 105
0 52
0 502
0 512
0 2501
0 53
0 053
0 513
0 1035
0 523
0 0325
0 2531
0 3250...

output:

27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
27
4
...

result:

ok 49140 tokens

Test #14:

score: 0
Accepted
time: 19ms
memory: 16124kb

input:

18 106483 13
7766a43b68bc24b4ca
0 0
0 1
0 01
0 2
0 20
0 21
0 021
0 3
0 30
0 13
0 301
0 23
0 023
0 132
0 3210
0 4
0 04
0 41
0 401
0 24
0 024
0 421
0 0241
0 43
0 304
0 314
0 0413
0 432
0 3042
0 1342
0 10324
0 5
0 50
0 15
0 150
0 52
0 205
0 215
0 0251
0 35
0 305
0 315
0 5301
0 523
0 2053
0 3512
0 32150...

output:

18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
18
0
...

result:

ok 106483 tokens

Test #15:

score: 0
Accepted
time: 37ms
memory: 18000kb

input:

20 229362 14
adcb1876a0dbb2a7a99a
0 0
0 1
0 01
0 2
0 02
0 21
0 021
0 3
0 30
0 13
0 103
0 23
0 320
0 213
0 2031
0 4
0 40
0 41
0 014
0 42
0 420
0 142
0 2140
0 43
0 430
0 134
0 0314
0 342
0 4032
0 4213
0 32041
0 5
0 05
0 15
0 051
0 52
0 052
0 215
0 1250
0 35
0 035
0 135
0 1035
0 253
0 0253
0 5123
0 510...

output:

22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
...

result:

ok 229362 tokens

Test #16:

score: 0
Accepted
time: 92ms
memory: 16088kb

input:

15 491505 15
8263921c51e6584
0 0
0 1
0 10
0 2
0 20
0 21
0 201
0 3
0 30
0 13
0 013
0 32
0 203
0 231
0 2031
0 4
0 04
0 41
0 014
0 42
0 024
0 421
0 0241
0 43
0 430
0 134
0 0431
0 342
0 2403
0 1432
0 30421
0 5
0 05
0 15
0 510
0 25
0 502
0 152
0 2150
0 53
0 053
0 531
0 5310
0 235
0 3025
0 3152
0 01235
0 ...

output:

15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
15
0
...

result:

ok 491505 tokens

Test #17:

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

input:

12 1048560 16
9fc1425c5f63
0 0
0 1
0 01
0 2
0 02
0 12
0 210
0 3
0 30
0 31
0 130
0 23
0 203
0 213
0 0312
0 4
0 04
0 14
0 140
0 42
0 042
0 412
0 4120
0 43
0 304
0 134
0 0413
0 342
0 0324
0 4312
0 10243
0 5
0 05
0 51
0 015
0 52
0 250
0 125
0 0521
0 53
0 530
0 135
0 0315
0 253
0 5302
0 1235
0 10523
0 54...

output:

12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
12
0
...

result:

ok 1048560 tokens

Test #18:

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

input:

1982 6 2
010111111001001011101100000100010111001101000011111001101101110011010100011001001011100100101001001011000001000001111110101101000011000001101100111100011011110001000111001111001001110100010101010000011110000010100110010010110111110101100100010110110110001001101001111010000001100011011001111...

output:

5976
1971
5976
1963182
1965153
1965153

result:

ok 6 tokens

Test #19:

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

input:

2039 21 3
22220221120002121202011212010100111220020002010022122001002120100122221211201211102012220102122020202202100101221110122201001111110202212110222001002202102221012102011022102222121222021001002122020111121212221010012110200101121022211212201002101011001112201001112120211211220112100022210201...

output:

4038
974
4038
974
4038
974
4038
2075674
2079527
2079780
2075674
2075674
2079780
2079780
2077273
2078044
2078131
2079780
2079780
2079780
2079780

result:

ok 21 tokens

Test #20:

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

input:

1068 60 4
33020210210223103321310231022103220332211022303312210003312223213010221220122312131202311021222212131232203010010221210113211310101203303310231210102103022002203302000330013002302312230101112120101321322231013030311300031020321001302211121112200212332002221202323231212222330231121213013003...

output:

1718
324
1718
324
1718
324
1718
324
1718
324
1718
324
1718
324
1718
568133
569963
570826
568943
569460
570763
570846
568133
568133
570826
570826
569460
569460
570846
570846
568222
568952
569471
569844
570831
570750
570846
568222
568222
569471
569471
570831
570831
570846
570846
568214
568869
569716
5...

result:

ok 60 tokens

Test #21:

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

input:

1122 155 5
0021110301024201000400341203412441220102111314142032320440243011003003131001211233321423142221323444344411041104023303431244112013131331322024423112103103144013043321000310144143412133431424014024414044021312444134330302321132240102401204240331422124334211213343331144240040340034243041343...

output:

1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
258
1652
626291
628102
629647
626921
627968
629593
629964
627044
628248
629772
629954
628688
628792
629959
630003
626291
626291
629647
629647
627968
627968
629964
629964...

result:

ok 155 tokens

Test #22:

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

input:

1183 378 6
1415204434012241052000240203054131453051210111123022021123405155144451402250333331033425144000523344214531204401435153513553020334413011214033043440120434145125251421502135511101415352443134143353320330032213202052004201053440351545125524254230135004142223403130551252252222401224511031204...

output:

1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
236
1651
695265
697386
69...

result:

ok 378 tokens

Test #23:

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

input:

1237 889 7
1121342321660200421023315322044550233643153244212253616302462023225410300202343201252021061242511523353562200232011316056316443365661100545303521542225521625560524526112532043130245651666426464464600061242205423605223510156241661546533253206503321026005665354112454102222016364342464264264...

output:

1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
1643
206
164...

result:

ok 889 tokens

Test #24:

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

input:

1294 2040 8
026411045150646273325374632226173702567514623511720727727765307424101647201200600272110337016404467561327730111550237670426702731274421274224011045703217171412126361452143443063171110051520021275314102534570456044130473254730564376040423302721307660706176724614400663741254370734504610006...

output:

1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
1661
187
166...

result:

ok 2040 tokens

Test #25:

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

input:

1348 4599 9
627507035301570811820702868133837817046438650147834015260000807002352727462067880473762536552186325310780543283023662520545480440445227783801326342512282233112487461310230748034766247785884185187886284243568764434276845880764283737644185703266544287187644547705758688756145643875874727454...

output:

1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
1684
166
168...

result:

ok 4599 tokens

Test #26:

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

input:

1513 10230 10
5603703864301311206779292028516992100589964852896339173178554865649469514330152239200017334889577010262779210747424573311360519027352871180380154577227190516159175799329410093389121861223913998174833733348505301706410486919308845960301517027295031702990777539303082398188769208019085414...

output:

1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
1844
167
184...

result:

ok 10230 tokens

Test #27:

score: 0
Accepted
time: 10ms
memory: 18300kb

input:

1567 22517 11
365a0567848841292324694a195823738aa41829056853995674736097079486a661525829a25a45a61a617882758050345480335902460a10337313a4a461a592656245a75279254104751682177460184a7213202883a76781324110445a7346a7a29928a828852820a26862021909a88a57a461718a0225978499a7080630934743894a2107a920403a20415941...

output:

1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
1849
139
184...

result:

ok 22517 tokens

Test #28:

score: 0
Accepted
time: 11ms
memory: 16588kb

input:

1628 49140 12
02468824977303a577b2740744860616a7ba671a75899b079290b6baaa1484430966506650058b014a7314a168366342623780425412833a15b2634694578407730bb34016045253467a122b707757861131b092a52831509911aa8a03572b1223a778b27195648283779399893611653971ba85a2733a1b4a77b011a6958905370738179467181b68b53a96763bb3...

output:

1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
1906
138
190...

result:

ok 49140 tokens

Test #29:

score: 0
Accepted
time: 22ms
memory: 18428kb

input:

1682 106483 13
875069b05833a22ab4c89394c636512a2ba1003b2cc04a225167ac8815184c9b942b05690521447cbbba247579a4c671bc13466b1b793904421a4723b0b0a165aa665cc40a66690c3a8a3c3235c3858477c469953a72509610334460498152590c308969c835820459128a84123c468c83aa264589a3928ab884788b39ac64a3293a83178127697660919455cbaac...

output:

1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
1951
131
195...

result:

ok 106483 tokens

Test #30:

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

input:

1735 229362 14
5b132465a7177aaccc67ad14625a0357c9d5c27d270384bb3cc68ab3b14b72b98d8bd5b12c269003946b2291b9cc9b095883204d8957b937c289d2abc220446a117a2963c2c358531113b6124cb4d712c50bc4c181494428641170aa30b1c8b7254abd4887b3110402c1b673514c26a2958da4a84b857a2d7ca3c8bb84113d6c864a3418a73069db318cbda344482...

output:

1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
1981
123
198...

result:

ok 229362 tokens

Test #31:

score: 0
Accepted
time: 99ms
memory: 18512kb

input:

1797 491505 15
b5006949e66d7974b076dc0cb7174de851e17548eee458d117b0ee0cee4a29246c51dcc63ac8bd8ed62de31704aabd3e06505b758c3009e01265cd3eeead164214773dd3737a024154a7927c272941514b30dce13d2c02db2340d3c7ddc169da5d8b902c0279db9becba99ceb8ed93e40d480d367c7c952cbb16045324c76c23c0968c785a6c23259e92717933e66...

output:

2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
2055
130
205...

result:

ok 491505 tokens

Test #32:

score: 0
Accepted
time: 211ms
memory: 16972kb

input:

1851 1048560 16
c4d5309856a42c01bb6a6b1550e11a7700d5a0543bfa06c44b4d870f2e070cf7d2b2314727c8423a8a7b2d8b1eac3681061a6b053c1271f7b3b7aef1fc22c5ca210ca9dde0cb1f8742c5e64fe47e02b3a3b8c0a1c2dc3256602a2494f03fe1cdd75e4fa3063c2c57f022163459614305665840e1b870f3622ee3ef8d31ac5ebf71649da71e51bdcfe75d0562198a...

output:

2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
2119
137
211...

result:

ok 1048560 tokens

Test #33:

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

input:

1048576 6 2
011001011010111011100010101100110000101110011011111000000101111000011011110101101101000010000001100101110000011011111110000101001110100110111110101000101110010111101111111100010101001100100110010101001111010011000111011100110010000011011011000000100001100111100001000011101100100101001010...

output:

3139199
1044615
3139199
549755293561
549756338176
549756338176

result:

ok 6 tokens

Test #34:

score: 0
Accepted
time: 249ms
memory: 314568kb

input:

1048576 21 3
01021122000000002202002200201211020102022110120021202111222221000110120211122102201011022210212210201100111101000122222022012111202211000211221021212211110201101221121212002212012100011211110021111211202100111020022110011020022222020201112110001100200101100022120121102221202221211100222...

output:

2096803
524419
2096803
524419
2096803
524419
2096803
549754247468
549756207864
549756338176
549754247468
549754247468
549756338176
549756338176
549755026700
549755421096
549755464160
549756338176
549756338176
549756338176
549756338176

result:

ok 21 tokens

Test #35:

score: 0
Accepted
time: 495ms
memory: 311512kb

input:

1048576 60 4
00333131003222001111130212313102033201223233213001203211132312301222010302303233231132003101000132223003220012210312131100102333000300121223233122133313032021123013003010303201230302222232233022231011203311322202002210022232230123003323323002312021112202002223120322333222200031132012300...

output:

1748102
349392
1748102
349392
1748102
349392
1748102
349392
1748102
349392
1748102
349392
1748102
349392
1748102
549753788655
549755530707
549756321646
549754569803
549755024491
549756254736
549756338176
549753788655
549753788655
549756321646
549756321646
549755024491
549755024491
549756338176
54975...

result:

ok 60 tokens

Test #36:

score: 0
Accepted
time: 880ms
memory: 314520kb

input:

1048576 155 5
1123214323021214403121343410321013311410242404110020131214001332314023413423012443442124130233141412334042343200330024342104244200301111140220344012422033213430031414131311313042244303244413123123000203221204213244434121010400313324122411344222220121303013232402331140234334124241130320...

output:

1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
260924
1571414
549752845960
549754653536
549756001512
549753456100
549754517533
54...

result:

ok 155 tokens

Test #37:

score: 0
Accepted
time: 1316ms
memory: 309556kb

input:

1048576 378 6
2155453551353024055521330433044005411251011430024113155300421323151442525241315130253021231533145442304323411311023112410424225515545445415234101545310543311335430300142120004114550225145200544052031435544305035510052000340340143332434110345003250503042135544221113413055430053504451004...

output:

1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
1467332
209238
...

result:

ok 378 tokens

Test #38:

score: 0
Accepted
time: 1792ms
memory: 310940kb

input:

1048576 889 7
6636122465046336103251406624402256020100012561520346634400466460361655552433455503346416023661241566320661352026445113246410012102341060024106015100001400645231043431324200014005106310045625643040516062544143400361324314661554044305043443640216502054143552565636613514621143230363316355...

output:

1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
1398016
174477
...

result:

ok 889 tokens

Test #39:

score: 0
Accepted
time: 2365ms
memory: 309276kb

input:

1048576 2040 8
737420715301240711234450435777063151100117330676674405135172244246067067505542035631122011354630327326775664157705475426531120113205121600237633671220636000034044523232423277671055633124627056207600374154473456534461622501214676050647252163452316562634720051511014253241654257142566627...

output:

1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
1348686
149920
...

result:

ok 2040 tokens

Test #40:

score: 0
Accepted
time: 2984ms
memory: 311620kb

input:

1048576 4599 9
344458120645036517162572154767410155306046711672242363184782618888557646170614231611687773656786264623830541848664620606858755312287811761854060150702821802158718560053400825200360280537606282314346681868318263603434031480651173156155100505827407157705264148385311801175773787205540448...

output:

1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
1310951
131273
...

result:

ok 4599 tokens

Test #41:

score: 0
Accepted
time: 3676ms
memory: 309176kb

input:

1048576 10230 10
7681540484342598883918091536761088189926496811318985890017247805542526795406464694484812033460539722550784224919205743780114226712129951336788975559744859095331949306521987552425440422028960277456521125685589849943511442431782794177783375002300826757289527135176839414837661569001946...

output:

1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
1281771
116567
...

result:

ok 10230 tokens

Test #42:

score: 0
Accepted
time: 4455ms
memory: 310624kb

input:

1048576 22517 11
633397639a3a938818217a401a680394797a977962946709236958584a562a031830428934763302583a29360950821601676a4a32215062218138513404a410506211757aa060206395650a8560930731aa718765581639185176537aa809424381816a79055388833519a7a15a4961aa45969717821705aa968a04340259998a825452157a62856983a009825...

output:

1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
1257918
104769
...

result:

ok 22517 tokens

Test #43:

score: -100
Time Limit Exceeded

input:

1048576 49140 12
69b3771990a156834107249a3344775141ba3175b9b6a98626b23490b7807122253657b23054134216937b603aa5005b56b5182735171081025616486204bb784589128a99640381048034760aab33a8a4a1b94102567482a51b2a779265973054823200455194b2b286137259b250a8922779b913697b7b1126a811452b613084849506825b5427a8256172795...

output:


result: