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 MAXN = 200100;
const ll MOD = 1e9 + 7;
const ll P = 2413;

string S, T;
ll phash[MAXN];
ll pmult[MAXN];
ll sz[100];
ll cc[100][26];

string get_nv ()
{
    int N = S.length();
    phash[0] = 0;
    pmult[0] = 1;
    for (int i = 0; i < N; i++)
    {
        phash[i+1] = (phash[i] * P + S[i]) % MOD;
        pmult[i+1] = (pmult[i] * P) % MOD;
    }

    for (int i = N + 2; ; i += 2)
    {
        int cchunk = i / 2;
        ll lhs = phash[N-cchunk];
        ll rhs = phash[N] - phash[cchunk] * pmult[N-cchunk];
        if ((lhs - rhs) % MOD == 0)
        {
            return S + S.substr(N - cchunk, i - N);
        }
    }
}

vector <ll> gogo (ll x)
{
    if (x < sz[0])
    {
        vector <ll> res;
        for (int i = 0; i < 26; i++)
            res.push_back(0);

        for (int i = 0; i < x; i++)
            res[S[i]-'a']++;
        return res;
    }

    int chi = 0;
    while (x >= sz[chi+1])
        chi++;

    vector <ll> res;
    for (int i = 0; i < 26; i++)
        res.push_back(cc[chi][i]);

    vector <ll> nleft = gogo (x - sz[chi]);
    for (int i = 0; i < 26; i++)
        res[i] += nleft[i];
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> S;
    T = get_nv ();

    //cout << T << "\n";

    sz[0] = S.length() / 2;
    for (int i = 0; i < S.length() / 2; i++)
    {
        int nv = S[i] - 'a';
        cc[0][nv]++;
    }
    sz[1] = T.length() / 2;
    for (int i = 0; i < T.length() / 2; i++)
    {
        int nv = T[i] - 'a';
        cc[1][nv]++;
    }
    
    int chi = 2;
    while (true)
    {
        sz[chi] = sz[chi-1] + sz[chi-2];
        for (int i = 0; i < 26; i++)
        {
            cc[chi][i] = cc[chi-1][i] + cc[chi-2][i];
        }

        if (sz[chi] > 2e18)
            break;
        chi++;
    }

    ll L, R;
    cin >> L >> R;
    vector <ll> res1 = gogo (R), res2 = gogo (L - 1);
    for (int i = 0; i < 26; i++)
        res1[i] -= res2[i];

    for (int i = 0; i < 26; i++)
    {
        if (i) cout << " ";
        cout << res1[i];
    }
    cout << "\n";
}