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<iostream>
#include<cstring>
#define DIM 200005
using namespace std;
//ifstream cin("date.in");
//ofstream cout("date.out");
int n, L, i, j, ok, k;
char s[DIM], a[DIM];
int p[DIM];
long long st, dr, fib[10000], sol[200], sn[200], sk[200];
void solve(int m, long long x, int semn){
    if(m <= 2){
        if(x <= n){
            for(int i = 1; i <= x; i++){
                sol[ s[i] ] += semn;
            }
        }
        else{
            for(int i = 1; i <= n; i++){
                sol[ s[i] ] += semn;
            }
            for(int i = 1; i <= x - n; i++){
                sol[ s[i] ] += semn;
            }
        }
        return;
    }
    if(fib[m - 1] * n + fib[m - 2] * k >= x){
        solve(m - 1, x, semn);
    }
    else{
        x -= fib[m - 1] * n + fib[m - 2] * k;
        for(int i = 'a'; i <= 'z'; i++){
            sol[i] += sn[i] * fib[m - 1] * semn;
            sol[i] += sk[i] * fib[m - 2] * semn;
        }
        solve(m - 2, x, semn);
    }
}
int main(){
    cin>> s + 1;
    n = strlen(s + 1);
    cin>> st >> dr;
    n /= 2;
    for(i = 2; i <= n; i++){
        while(L > 0 && s[i] != s[L + 1]){
            L = p[L];
        }
        if(s[i] == s[L + 1]){
            L++;
        }
        p[i] = L;
    }
    for(i = 1; i <= n; i++){
        ok = 1;
        for(j = i + i; j <= n; j += i){
            if(p[j] != j - i){
                ok = 0;
            }
        }
        L = 1;
        for(j = j - i + 1; j <= n; j++){
            if(s[j] != s[L]){
                ok = 0;
            }
            L++;
        }
        if(ok == 1){
            k = i;
            break;
        }
    }
    for(i = 1; i <= n; i++){
        sn[ s[i] ]++;
    }
    for(i = 1; i <= k; i++){
        sk[ s[i] ]++;
    }
    fib[1] = fib[2] = 1;
    for(i = 3; ; i++){
        fib[i] = fib[i - 1] + fib[i - 2];
        if(fib[i] * n >= dr || fib[i] * n + fib[i - 1] * k >= dr){
            solve(i, dr, 1);
            solve(i, st - 1, -1);
            break;
        }
    }
    for(i = 'a'; i <= 'z'; i++){
        cout<< sol[i] <<" ";
    }
}