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:
//https://atcoder.jp/contests/arc077/tasks/arc077_d

#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;

string s;
int Z[N], n;
long long l, r, cnt[1000], ch[1000][26], ans[26];

void cal(long long x, int v){
    int cur = 0;
    while (cnt[cur] < x) cur++;
    while (x){
        while (cnt[cur-1] >= x) cur--;
        if (x <= cnt[0]){
            for (int i = 0; i < x; i++) ans[s[i] - 'a'] += v;
            break;
        }
        if (cnt[cur] == x){
            for (int i = 0; i < 26; i++) ans[i] += ch[cur][i] * v;
            x = 0;
        }
        else{
            for (int i = 0; i < 26; i++) ans[i] += ch[cur-1][i] * v;
            x -= cnt[cur-1];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s >> l >> r; n = s.size();
    for (int i = 1, l = 0, r = 0; i < n; i++){
        if (i <= r) Z[i] = min(r-i+1, Z[i-l]);
        while (i + Z[i] < n && s[Z[i]] == s[i+Z[i]]) Z[i]++;
        if (i + Z[i] - 1 > r) l = i, r = i + Z[i] - 1;
    }
    for (int i = 1; i < n; i++) if (i > n/2 && i + Z[i] == n){
        s.resize(i); n = i; break;
    }
    cnt[0] = n;
    for (int i = 1; i < n; i++) if (i + Z[i] >= n){
        cnt[1] = cnt[0] + i;
        break;
    }
    if (!cnt[1]) cnt[1] = 2 * cnt[0];
    if (cnt[0] % (cnt[1] - cnt[0]) == 0){
        int siz = cnt[1] - cnt[0];
        for (int i = 0; i < siz; i++) ans[s[i] - 'a'] += (r+siz-i-1) / siz - (l-1+siz-i-1) / siz;
        for (int i = 0; i < 26; i++) cout << ans[i] << " ";
        return 0;
    }

    for (int i = 0; i < n; i++) ch[0][s[i] - 'a']++, ch[1][s[i] - 'a']++;
    for (int i = 0; i < (cnt[1] - cnt[0]); i++) ch[1][s[i] - 'a']++;

    for (int i = 2; cnt[i-1] <= r; i++) {
        cnt[i] = cnt[i-1] + cnt[i-2];
        for (int j = 0; j < 26; j++) ch[i][j] = ch[i-1][j] + ch[i-2][j];
    }
    cal(r, 1); cal(l-1, -1);

    for (int i = 0; i < 26; i++) cout << ans[i] << " ";
}