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 <cstdio>
#include <string.h>
#include <iostream>
using namespace std;

#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))

struct C {
	long long sum[26];
	long long s;
	C() {
		memset(sum, 0, sizeof sum);
		s = 0;
	}
} F[1100];

C operator * (C x, long long y) {
	for (int i = 0; i < 26; i++)
		x.sum[i] *= y;
	x.s *= y;
	return x;
}

C operator + (C x, C y) {
	for (int i = 0; i < 26; i++)
		x.sum[i] += y.sum[i];
	x.s += y.s;
	return x;
}

C operator - (C x, C y) {
	for (int i = 0; i < 26; i++)
		x.sum[i] -= y.sum[i];
	x.s -= y.s;
	return x;
}

int len;
int n;
char S[210000];
int ne[210000];

C query(int k, long long l, long long r) {
	// printf("?? %d %lld %lld\n", k, l, r);
	if (k <= 1) {
		if (k == 0) {
			l = max(l, 1);
			r = min(r, n - ne[n]);
		}else {
			l = max(l, 1);
			r = min(r, n);
		}
		C ans;
		memset(ans.sum, 0, sizeof ans.sum);
		ans.s = 0;
		for (int i = l; i <= r; i++)
			ans.sum[S[i] - 'a'] += 1, ans.s += 1;
		return ans;
	}
	if (l <= 1 && r >= F[k].s)
		return F[k];
	if (r <= F[k - 1].s)
		return query(k - 1, l, r);
	else if (l > F[k - 1].s)
		return query(k - 2, l - F[k - 1].s, r - F[k - 1].s);
	else
		return query(k - 1, l, r) + query(k - 2, l - F[k - 1].s, r - F[k - 1].s);
}

int main() {
	scanf("%s", S + 1);
	n = strlen(S + 1) / 2;
	int p = 0;
	ne[1] = 0;
	for (int i = 2; i <= n; i++) {
		for (; p && S[p + 1] != S[i]; p = ne[p]);
		if (S[p + 1] == S[i])
			p ++;
		ne[i] = p;
	}

	long long l, r;
	cin >> l >> r;
	// if (ne[n] * 2 >= n) {
	// 	int c = n - ne[n];
	// 	C pp;
	// 	for (int i = 1; i <= c; i++)
	// 		pp.sum[S[i] - 'a'] += 1, pp.s += 1;
	// 	C ans = pp * (r / c);
	// 	for (int i = 1; i <= r % c; i++)
	// 		ans.sum[S[i] - 'a'] += 1;
	// 	l -= 1;
	// 	ans = ans - (pp * (l / c));
	// 	for (int i = 1; i <= l % c; i++)
	// 		ans.sum[S[i] - 'a'] -= 1;
	// 	for (int i = 0; i < 25; i++)
	// 		printf("%lld ", ans.sum[i]);
	// 	printf("%lld\n", ans.sum[25]);
	// }else {
		len = 1;
		for (int i = 1; i <= n - ne[n]; i++)
			F[0].sum[S[i] - 'a'] += 1, F[0].s += 1;
		for (int i = 1; i <= n; i++)
			F[1].sum[S[i] - 'a'] += 1, F[1].s += 1;
		while (F[len].s <= 1000000000000000000LL) {
			F[len + 1] = F[len] + F[len - 1];
			len += 1;
		}
		C ans = query(len, l, r);
		for (int i = 0; i < 25; i++)
			printf("%lld ", ans.sum[i]);
		printf("%lld\n", ans.sum[25]);
	// }
}