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 <cstdio>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

int n;
char s[200001];
int z[200001];
long long ans[26];

void calc(long long c, long long g, long long f) {
    int i;
    
    for (i = 0; i < g; i++) ans[s[i] - 'a'] += c / g * f;
    for (i = 0; i < c % g; i++) ans[s[i] - 'a'] += f;
}

void calc2(long long c, long long x, long long y, int f) {
    int i;
    vector <long long> v;
    map <long long, long long> mp;
    map <long long, long long>::reverse_iterator it;
    
    v.push_back(x);
    v.push_back(y);
    
    while (v.back() < c) {
        v.push_back(v[v.size() - 1] + v[v.size() - 2]);
    }
    
    mp[c] += f;
    
    for (it = mp.rbegin(); it != mp.rend(); it++) {
        long long x = it->first;
        
        for (i = 0; ; i++) {
            if (v[i] >= x) break;
        }
        
        if (v[i] <= n) {
            calc(x, v[i], it->second);
        } else {
            mp[v[i - 1]] += it->second;
            mp[x - v[i - 1]] += it->second;
        }
    }
}

int main() {
    int x, y, i, j, k;
    long long l, r;
    
    scanf("%s", s);
    scanf("%lld %lld", &l, &r);
    
    n = strlen(s);
    
    i = 1, j = 0;
    z[0] = n;
    
    while (i < n) {
        while (i + j < n && s[j] == s[i + j]) j++;
        
        z[i] = j;
        
        if (j == 0) {
            i++;
            
            continue;
        }
        
        k = 1;
        
        while (i + k < n && k + z[k] < j) {
            z[i + k] = z[k];
            k++;
        }
        
        i += k;
        j -= k;
    }
    
    x = n / 2;
    y = n;
    
    for (i = n - 1; i > n / 2; i--) {
        if (i + z[i] == n) y = i;
    }
    
    calc2(r, x, y, 1);
    calc2(l - 1, x, y, -1);
    
    for (i = 0; i < 26; i++) {
        if (i > 0) putchar(' ');
        
        printf("%lld", ans[i]);
    }
    puts("");
    
    return 0;
}