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;
const int N = 300000;
#define LL long long
LL l, r;
char st[N];
int par[N], n, k;
LL solve(int c, LL r)
{
    LL res = 0;
    if (r <= n)
    {
        for (int i = 1; i <= r; ++ i) if (st[i] == c) res ++;
        return res;
    }
    LL ca = 0, cb = 0;
    for (int i = 1; i <= n - k; ++ i) if (st[i] == c) ca ++;
    for (int i = n - k + 1; i <= n; ++ i) if (st[i] == c) cb ++;
    if (k % (n - k) == 0)
    {
        LL cc = 0;
        for (int i = n - k + 1; i <= n - k + (r - (n - k)) % k; ++ i) if (st[i] == c) cc ++;
        return ca + cb * ((r - (n - k)) / k) + cc;
    }
    else
    {
        LL a = n - k, b = k, cca = ca, ccb = cb;
        for (; a + b <= r; b += a, swap(a, b), cb += ca, swap(ca, cb));
        return ca + solve(c, r - a);
    }
}
int main()
{
    scanf("%s", st + 1);
    n = strlen(st + 1) / 2;
    for (int i = 2; i <= n; ++ i)
    {
        int p = par[i - 1];
        while (p && st[p + 1] != st[i]) p = par[p];
        if (st[p + 1] != st[i]) par[i] = 0; else par[i] = p + 1;
    }
    // printf("%d\n", par[n]);
    k = par[n];
    if (k == 0) k = n, n += n;
    scanf("%lld%lld", &l, &r);
    for (int i = 0; i < 26; ++ i)
        printf("%lld ", solve(i + 'a', r) - solve(i + 'a', l - 1));
}