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<cstring>
using namespace std;
typedef long long LL;
const int N=100005;
LL A1[26],A2[26],an1[26],an[26],L,R,S,t;
int b[N<<1],next[N],s[N][26],i,j,k,n,m,l,B;
char c;

inline char getc()
{
	#define VV 10000000
	static char s[VV],*l=s,*r=s;
	if (l==r)
		l=s,r=s+fread(s,1,VV,stdin);
	return l==r?0:*l++;
}

LL read(){ LL z=0; do c=getc(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getc(); return z; }

void fib(LL X)
{
	if (X<=n)
	{
		for (register int i=0;i<26;++i)
			an[i]+=s[X][i];
		return;
	}
	if (X<=n<<1)
	{
		for (register int i=0;i<26;++i)
			an[i]+=s[n][i]+s[X-n][i];
		return;
	}
	for (register int i=0;i<26;++i)
		A1[i]=s[n][i],A2[i]=A1[i]+s[B][i];
	LL l1=n,l2=n+B;
	while (X>l1+l2)
	{
		for (register int i=0;i<26;++i)
			t=A1[i],A1[i]=A2[i],A2[i]+=t;
		t=l1,l1=l2,l2+=t;
	}
	for (register int i=0;i<26;++i)
		an[i]+=A2[i];
	fib(X-l2);
}

void solve(LL X)
{
	if (X<=n)
		for (i=0;i<26;++i)
			an[i]=s[X][i];
	else
		if (n%B)
			fib(X);
		else
			for (S=X/n,l=X%n,i=0;i<26;++i)
				an[i]=S*s[n][i]+s[l][i];
}

int main()
{
	do c=getc(); while (c<'a'||c>'z');
	while (c>='a'&&c<='z') b[++n]=c-'a',c=getc();
	n>>=1,L=read(),R=read();
	for (i=2;i<=n;next[i]=j+(b[j+1]==b[i]),++i)
		for (j=next[i-1];j&&b[j+1]!=b[i];j=next[j]);
	B=n-next[n];
	for (i=1;i<=n;++s[i][b[i]],++i)
		for (j=0;j<26;++j)
			s[i][j]=s[i-1][j];
	solve(R);
	for (i=0;i<26;++i) an1[i]=an[i],an[i]=0;
	solve(L-1);
	for (i=0;i<26;++i) printf("%lld ",an1[i]-an[i]);
	return 0;
}