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;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

// Z algorithm (length of longest common prefix for s[0:N] & s[i:N] for each i)
// Complexity: O(N)
// <http://snuke.hatenablog.com/entry/2014/12/03/214243>
vector<int> z_algorithm(const string &s) {
    vector<int> ans(s.size());
    ans[0] = s.size();
    int i = 1, j = 0;
    while (i < (int)s.size()) {
        while (i + j < (int)s.size() && s[j] == s[i + j]) ++j;
        ans[i] = j;
        if (!j) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < (int)s.size() && k + ans[k] < j) ans[i + k] = ans[k], ++k;
        i += k;
        j -= k;
    }
    return ans;
}

vector<lint> C2(string S) {
    vector<lint> ret(26);
    for (auto c : S) ret[c - 'a']++;
    for (auto &d : ret) d /= 2;
    return ret;
}

string Next(string S) {
    vector<int> z = z_algorithm(S);
    int r = S.length();
    FOR(i, S.length() / 2 + 1, S.length()) if (z[i] + i == S.length()) r = min(r, i);
    return  S.substr(0, r) + S.substr(0, r);
}

map<lint, vector<lint>> mp;

string S, T;
vector<lint> solve(lint L) {
    vector<lint> ret(26);
    while (L > T.length())
    {
        auto itr = prev(mp.upper_bound(L));
        REP(d, 26) ret[d] += itr->second[d];
        L -= itr->first;
    }
    REP(i, L) ret[T[i] - 'a']++;
    return ret;
}

int main()
{
    lint L, R;
    cin >> S >> L >> R;
    T = Next(S);
    vector<lint> v1 = C2(S), v2 = C2(T);
    lint l1 = S.length() / 2, l2 = T.length() / 2;
    mp[l1] = v1;
    mp[l2] = v2;

    while (l2 < 2e18) {
        swap(l1, l2);
        l2 += l1;
        swap(v1, v2);
        REP(i, 26) v2[i] += v1[i];
        mp[l2] = v2;
    }

    vector<lint> ret1 = solve(L - 1), ret2 = solve(R);
    REP(d, 26) printf("%lld ", ret2[d] - ret1[d]);
    puts("");
}