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>

const int MAXN = 200010;
typedef long long LL;
typedef std::vector<LL> V;
V operator + (V a, V b) {
	for (int i = 0; i != 26; ++i) a[i] += b[i];
	return a;
}
struct item {
	V a; char * s;
	item * l, * r; LL L;
	item() { a = V(26, 0); s = NULL, l = r = NULL; L = 0; }
	V qry(LL rr) {
		assert(rr <= L);
		if (s != NULL) {
			V res(26, 0);
			for (int i = 0; i != rr; ++i) ++res[s[i] - 'a'];
			return res;
		} else {
			if (rr <= l->L) return l->qry(rr);
			return l->a + r->qry(rr - l->L);
		}
	}
} is[100];
char buf[MAXN]; int n, fail[MAXN];
char s1[MAXN], s2[MAXN];
LL ansl[MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> buf + 1; n = strlen(buf + 1) / 2;
	for (int i = 1; i <= n; ++i) {
		int now = fail[i - 1];
		while (now && buf[now + 1] != buf[i]) now = fail[now];
		++now, fail[i] = now != i && buf[now] == buf[i] ? now : 0;
	}
	int tl = n - fail[n];
	std::copy(buf + 1, buf + 1 + n, s2);
	std::copy(buf + 1, buf + 1 + tl, s1);
	is[0].L = tl, is[0].s = s1, is[1].L = n, is[1].s = s2;
	is[0].a = is[0].qry(is[0].L);
	is[1].a = is[1].qry(is[1].L);
	LL L, R; std::cin >> L >> R;
	int cur = 1;
	while (is[cur].L < R) {
		++cur;
		is[cur].a = is[cur - 1].a + is[cur - 2].a;
		is[cur].L = is[cur - 1].L + is[cur - 2].L;
		is[cur].l = &is[cur - 1], is[cur].r = &is[cur - 2];
	}
	V aa = is[cur].qry(R);
	V ab = L > 1 ? is[cur].qry(L - 1) : V(26, 0);
	for (int i = 0; i < 26; ++i) std::cout << aa[i] - ab[i] << ' ';
	return 0;
}