Problem: We will call a string that can be obtained by concatenating two equal strings an even string. For example, `xyzxyz` and `aaaaaa` are even, while `ababab` and `xyzxy` are not.

For a non-empty string S, we will define f(S) as the shortest even string that can be obtained by appending one or more characters to the end of S. For example, f(`abaaba`)=`abaababaab`. It can be shown that f(S) is uniquely determined for a non-empty string S.

You are given an even string S consisting of lowercase English letters. For each letter in the lowercase English alphabet, find the number of its occurrences from the l-th character through the r-th character of f^{10^{100}} (S).

Here, f^{10^{100}} (S) is the string f(f(f( ... f(S) ... ))) obtained by applying f to S 10^{100} times.

Constraints

* 2 \leq |S| \leq 2\times 10^5
* 1 \leq l \leq r \leq 10^{18}
* S is an even string consisting of lowercase English letters.
* l and r are integers.

Input

Input is given from Standard Input in the following format:


S
l r


Output

Print 26 integers in a line with spaces in between. The i-th integer should be the number of the occurrences of the i-th letter in the lowercase English alphabet from the l-th character through the r-th character of f^{10^{100}} (S).

Examples

Input

abaaba
6 10


Output

3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Input

xx
1 1000000000000000000


Output

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0


Input

vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000


Output

87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0

Solution (in CPP):

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

vector<int>zalgorithm(string s){
    vector<int>a(s.size());
    a[0]=s.size();
    int i=1,j=0;
    while(i<s.size()){
        while(i+j<s.size()&&s[j]==s[i+j])j++;
        a[i]=j;
        if(j==0){i++;continue;}
        int k=1;
        while(i+k<s.size()&&k+a[k]<j)a[i+k]=a[k],k++;
        i+=k;j-=k;
    }
    return a;
}

string S;
int L;

map<int,int>calc(int a,int b){
    if(a+b>=L){
        map<int,int>ret;
        ret[L]++;
        return ret;
    }

    auto m=calc(a+b,a);
    map<int,int>ret;

    for(auto p:m){
        if(p.fi>a+b){
            ret[a+b]+=p.se;
            ret[p.fi-a-b]+=p.se;
        }
        else{
            ret[p.fi]+=p.se;
        }
    }
    return ret;
}

vint solve(){
    vint z=zalgorithm(S);

    int b=0;
    for(int i=S.size()-1;i>0;i--){
        if(z[i]==S.size()-i)b=S.size()-i;
    }

    int a=S.size()-b;

    auto m=calc(a,b);
    vint ret(26);
    for(auto p:m){
        rep(i,p.fi)ret[S[i]-'a']+=p.se;
    }
    return ret;
}

signed main(){
    cin>>S;
    S=S.substr(0,S.size()/2);
    int l,r;
    cin>>l>>r;
    l--;

    L=r;
    vint y=solve();

    L=l;
    vint x=solve();
    rep(i,26){
        if(i)cout<<" ";
        cout<<y[i]-x[i];
    }cout<<endl;
    return 0;
}