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>
#define b 31ll
#define mod 1004535809ll
#define ll long long
using namespace std;
char s[400005];
ll l[1005],fib[1005][27],ans[27];
ll has[400005],m[400005],lo,hi;
int len,t;
inline ll get(int l,int r)
{if (l>r) return 0;
ll ret=(has[r]-has[l-1]*m[r-l+1])%mod;
return (ret<0?ret+mod:ret);
}
inline void add(ll p,int pos)
{if (pos<=1)
{for (int i=1;i<=p;i++)
{ans[s[(i-1)%len+1]-'a']++;}
return;
}
if (p>=l[pos-1])
{for (int i=0;i<26;i++) ans[i]+=fib[pos-1][i];
add(p-l[pos-1],pos-2);
return;
}
add(p,pos-1);
}
inline void del(ll p,int pos)
{if (pos<=1)
{for (int i=1;i<=p;i++)
{ans[s[(i-1)%len+1]-'a']--;}
return;
}
if (p>=l[pos-1])
{for (int i=0;i<26;i++) ans[i]-=fib[pos-1][i];
del(p-l[pos-1],pos-2);
return;
}
del(p,pos-1);
}
int main (){
	int i,j,las;
	scanf ("%s",s+1);len=strlen(s+1);
	scanf ("%lld%lld",&lo,&hi);
	m[0]=1ll;len>>=1;
	for (i=1;i<=len;i++)
	{m[i]=m[i-1]*b%mod;
	has[i]=has[i-1]*b+(s[i]-'0');
	has[i]%=mod;
	}
	for (i=1;i<=len;i++)
	{if (get(1,len-i)==get(i+1,len))
	{t=i;break;}
	}
	l[0]=len;l[1]=len+t;
	for (i=1;i<=len;i++)
	{fib[0][s[i]-'a']++;
	fib[1][s[i]-'a']++;
	}
	for (i=1;i<=t;i++)
	{fib[1][s[i]-'a']++;}
	for (i=2;l[i-2]+l[i-1]<=2ll*hi;i++)
	{for (j=0;j<26;j++)
	{fib[i][j]=fib[i-1][j]+fib[i-2][j];}
	l[i]=l[i-1]+l[i-2];
	las=i;
	}
	add(hi,las);del(lo-1,las);
	for (i=0;i<26;i++)
	{printf ("%lld ",ans[i]);}
	return 0;
}