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;
typedef long long ll;
const int N = 300000;

int n, kmp[N], T; char s[N];
ll l, r, num[N][30];

ll fib(ll len, int c){
    if(len <= n) return num[len][c];
    if(len <= n * 2) return num[n][c] + num[len-n][c];
    ll f1 = num[n][c], f2 = num[n][c] + num[T][c], l1 = n, l2 = n + T;
    // 1 : S, 2 : ST;
    while(len > l1 + l2){
        ll tmp = f2;
        f2 += f1; f1 = tmp;
        tmp = l2;
        l2 += l1; l1 = tmp;
        //2 --> 1 + 2; 1 --> 2
        //exp: STSST --> STSSTSTS; STS --> STSST 
    }
    return f2 + fib(len - l2, c);
}

ll calc(ll len, int c){ // 计算前 len 位 c 出现的次数
    if(len <= n) return num[len][c];
    if(n % T == 0){ // 形如 TTT TTT 的字符串
        ll ret = 1ll * (len-n) / T * num[T][c] + num[n][c]; // T 出现了(len-n)/T次, n出现了1次
        len -= n; len %= T;
        return ret + num[len][c];
    }
    return fib(len, c);
}

int main(){
    scanf("%s%lld%lld", s+1, &l, &r);
    n = strlen(s+1) / 2;
    kmp[0] = kmp[1] = 0; int p = 0;
    for(int i=2; i<=n; i++){
        while(p && s[i] != s[p+1]) p = kmp[p];
        kmp[i] = (s[i] == s[p+1]) ? ++p : p;
    }

    for(int i=1; i<=n; i++){
        for(int j=0; j< 26; j++)
            num[i][j] = num[i-1][j];
        num[i][s[i] - 'a'] ++;
    } // num[i][j] : 第i位和之前字符j出现的次数
    T = n - kmp[n]; // T:最长的等于一个前缀的后缀的起始位置的前一位 
    //printf("%d\n", T);
    for(int i=0; i< 26; i++)
        printf("%lld%c", calc(r, i) - calc(l-1, i), (i == 25) ? 10 : 32);
    //printf("%d\n", calc(5, 1));

    return 0;
}