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>

typedef long long ll;
const int N = 200054;
constexpr long double phi = 0.61803398874989484820458683436564l,
	hz = 0.49723029647758477079258462177973l, lz = phi;

int n, T;
int f[N];
ll ans[N];
char s[N];

ll phi_n(ll n) {
	unsigned int hi = n >> 32, lo = n & 0xffffffff;
	return 2654435769ll * hi + floorl(hi * hz + lo * lz);
}

void solve(ll x, int coef) {
	int i, u = T, v = n - T;
	if (n % T) {
		ll p, Lu = -1, Lv = -1, Cu, Cv, estimate = x / (u * phi + v * (1 - phi));
		for (p = std::max<ll>(estimate - 100, 1); ; ++p) {
			Cu = phi_n(p), Cv = p - 1 - Cu;
			if (u * Cu + v * Cv > x) break;
			Lu = Cu, Lv = Cv;
		}
		assert(~Lu && ~Lv);
		for (i = 0; i < u; ++i) ans[s[i]] += Lu * coef;
		for (i = 0; i < v; ++i) ans[s[i]] += Lv * coef;
		p = x - (u * Lu + v * Lv);
		for (i = 0; i < p; ++i) ans[s[i]] += coef;
	} else {
		lldiv_t info = lldiv(x, T);
		for (i = 0; i < T; ++i) ans[s[i]] += info.quot * coef;
		for (i = 0; i < info.rem; ++i) ans[s[i]] += coef;
	}
}

int main() {
	int i, j = 0; ll l, r;
	scanf("%s%lld%lld", s, &l, &r), s[n = strlen(s) / 2] = 0;
	for (j = *f = -1, i = 0; i < n; f[++i] = ++j)
		for (; ~j && s[j] != s[i]; j = f[j]);
	T = n - f[n];
	solve(r, 1), solve(l - 1, -1);
	for (i = 97; i < 123; ++i) printf("%lld%c", ans[i], i == 122 ? 10 : 32);
	return 0;
}