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 {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 2e5 + 10;
char s[N];
int nxt[N],n;
ll l,r,cnt[26],sum[N][26];
vector<ll> len;
vector<vector<ll> > S;

vector<ll> solve(ll x){
    if(x <= n) return vector<ll>(sum[x],sum[x]+26);
    int p = upper_bound(all(len) , x) - len.begin() - 1;
    vector<ll> res = S[p] , gt = solve(x - len[p]);
    rep(i,0,26) res[i] += gt[i];
    return res;
}

int main(){
    scanf("%s%lld%lld",s+1,&l,&r);
    n=strlen(s+1) / 2;
    nxt[1]=0;
    for(int i=2,j=0;i<=n;++i){
        while(j&&s[j+1]!=s[i]) j=nxt[j];
        nxt[i]=s[j+1]==s[i]?++j:j;
    }
    rep(i,1,n+1) rep(j,0,26) sum[i][j]=sum[i-1][j]+(s[i]-'a'==j);
    int period = n - nxt[n];
    if(n % period == 0) {
        rep(i,1,period+1) {
            cnt[s[i] - 'a'] += (r + period - i) / period - (l - 1 + period - i) / period;
        }
    } else {
        vector<ll> A(sum[n],sum[n]+26);
        len.pb(n);S.pb(A);
        rep(i,0,26) A[i]+=sum[period][i];
        len.pb(n+period);S.pb(A);
        while(len[sz(len)-1]<r) {
            len.pb(len[sz(len)-1]+len[sz(len)-2]);
            A=*S.rbegin();
            rep(i,0,26) A[i]+=S[sz(S)-2][i];
            S.pb(A);
        }
        vector<ll> L = solve(l - 1) , R = solve(r);
        rep(i,0,26) cnt[i] = R[i] - L[i];
    }
    rep(i,0,26) printf("%lld%c",cnt[i]," \n"[i==25]);
    return 0;
}