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;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;
const ll    inf = 2e18;

ll  add(ll  x,ll  y)    {   x += y; if (x > inf)    x = inf;    return  x;  }
ll  mul(ll  x,ll  y)    {
    if (x == 0) return  0;
    if (y == 0) return  0;
    if (x >= inf / y)
        return  inf;
    else
        return  x * y;
}

string S;
ll  l, r;
int kmp[N];

vector<ll>  fib;
vector<ll>  calc()  {
    if (r == 0) return  vector<ll>(26,0);
    int n = sz(S);

    int len1 = n - kmp[n];
    int len2 = n - len1;

    ll  cnt1 = 0;
    ll  cnt2 = 0;

    for(int i = sz(fib) - 1 ; i > 1 ; --i)
        if (add(mul(fib[i - 1],len1),mul(fib[i - 2],len2)) <= r)    {
            cnt1 += fib[i - 1];
            cnt2 += fib[i - 2];

            r -= fib[i - 1] * len1;
            r -= fib[i - 2] * len2;
        }
    vector<ll>  res(26,0);

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

    for(int i = 0 ; i < len1 ; ++i) res[S[i] - 'a'] += cnt1;
    for(int i = len1 ; i < n ; ++i) res[S[i] - 'a'] += cnt2;

    return  res;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    fib.pb(0);
    fib.pb(1);

    while (fib.back() < inf)
        fib.pb(0),
        fib.back() += fib[sz(fib) - 2],
        fib.back() += fib[sz(fib) - 3];

    cin >> S;       S.resize(sz(S) / 2);
    cin >> l >> r;

    kmp[1] = 0;
    kmp[0] = -1;

    for(int i = 2 ; i <= sz(S) ; ++i)
    for(int j = kmp[i - 1] ; j >= 0 ; j = kmp[j])
        if (S[j] == S[i - 1])   {
            kmp[i] = j + 1;
            break;
        }    
    vector<ll>  cnt1 = calc();  r = l - 1;
    vector<ll>  cnt2 = calc();

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