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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#define SIZE 200005
#define BT 1005
#define ALP 26

using namespace std;
typedef long long int ll;

char str[SIZE];
int KMP[SIZE];
ll len[BT];
ll cnt[BT][ALP];
ll ans[ALP];
ll query[ALP];

void solve(ll L)//[0,L-1]
{
	int n=strlen(str);
	for(int i=0;i<n;i++)
	{
		if(i==0) KMP[i]=-1;
		else
		{
			KMP[i]=KMP[i-1];
			while(1)
			{
				if(str[KMP[i]+1]==str[i])
				{
					KMP[i]++;
					break;
				}
				if(KMP[i]==-1) break;
				KMP[i]=KMP[KMP[i]];
			}
		}
	}
	int add=KMP[n-1];
	while((add+1)*2>=n) add=KMP[add];
	string T="";
	for(int i=0;i<n-(add+1);i++) T+=str[i];
	for(int i=0;i<T.size();i++)
	{
		if(i==0) KMP[i]=-1;
		else
		{
			KMP[i]=KMP[i-1];
			while(1)
			{
				if(T[KMP[i]+1]==T[i])
				{
					KMP[i]++;
					break;
				}
				if(KMP[i]==-1) break;
				KMP[i]=KMP[KMP[i]];
			}
		}
	}
	add=KMP[T.size()-1];
	while((add+1)*2>T.size()) add=KMP[add];
	add++;
	//printf("%s %d\n",T.c_str(),add);
	int sz=0;
	memset(cnt,0,sizeof(cnt));
	memset(len,0,sizeof(len));
	for(int i=add;i<T.size()-add;i++)
	{
		len[sz]++;
		cnt[sz][T[i]-'a']++;
	}
	sz++;
	for(int i=0;i<add;i++)
	{
		len[sz]++;
		cnt[sz][T[i]-'a']++;
	}
	sz++;
	while(len[sz-1]<=L)
	{
		len[sz]=len[sz-1]+len[sz-2];
		for(int i=0;i<ALP;i++)
		{
			cnt[sz][i]=cnt[sz-1][i]+cnt[sz-2][i];
		}
		//printf("%lld\n",len[sz]);
		sz++;
	}
	memset(query,0,sizeof(query));
	for(int i=sz-1;i>=2;i--)
	{
		if(L>=len[i])
		{
			L-=len[i];
			for(int j=0;j<ALP;j++) query[j]+=cnt[i][j];
		}
	}
	for(int i=0;i<L;i++)
	{
		query[T[i]-'a']++;
	}
}
int main()
{
	scanf("%s",&str);
	ll L,R;
	scanf("%lld %lld",&L,&R);
	solve(R);
	for(int i=0;i<ALP;i++) ans[i]=query[i];
	solve(L-1);
	for(int i=0;i<ALP;i++) ans[i]-=query[i];
	for(int i=0;i<ALP;i++)
	{
		if(i!=0) printf(" ");
		printf("%lld",ans[i]);
	}puts("");
	return 0;
}