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>
int N, kmp[200001], G = 1;
char s[200002];
long long L, R, len[666], ans[666][26], O[26];
void Calc(long long x, int f)
{
	for (int i = G; i; i--)
		if (len[i] <= x)
		{
			x -= len[i];
			for (int j = 0; j < 26; j++)
				O[j] += f * ans[i][j];
		}
	for (int i = 1; i <= x; i++)
		O[s[i] - 'a'] += f;
}
int main()
{
	scanf("%s", s + 1);
	while (s[N + 1])
		N++;
	scanf("%lld%lld", &L, &R);
	for (int i = 2; i <= N; i++)
	{
		int ans = kmp[i - 1];
		while (ans && s[ans + 1] != s[i])
			ans = kmp[ans];
		if (s[ans + 1] == s[i])
			kmp[i] = ans + 1;
		else
			kmp[i] = 0;
	}
	int E = N;
	while (E + E >= N)
		E = kmp[E];
	N -= E;
	if (kmp[N] << 1 >= N || kmp[N] == 0)
	{
		int T = N - kmp[N];
		for (int i = 1; i <= T; i++)
			O[s[i] - 'a'] += (R + T - i) / T - (L - 1 + T - i) / T;
		for (int i = 0; i < 26; i++)
			printf("%lld%c", O[i], " \n"[i == 25]);
		return 0;
	}
	len[0] = N - kmp[N];
	len[1] = N;
	for (int i = 1; i <= N - kmp[N]; i++)
		ans[0][s[i] - 'a']++;
	for (int i = 1; i <= N; i++)
		ans[1][s[i] - 'a']++;
	while (len[G - 1] + len[G] <= R)
	{
		len[G + 1] = len[G - 1] + len[G];
		for (int i = 0; i < 26; i++)
			ans[G + 1][i] = ans[G - 1][i] + ans[G][i];
		G++;
	}
	Calc(R, 1);
	Calc(L - 1, -1);
	for (int i = 0; i < 26; i++)
		printf("%lld%c", O[i], " \n"[i == 25]);
	return 0;
}