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 L long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define aa first
#define bb second
#define xx aa.aa
#define yy aa.bb
#define zz bb
#define mp make_pair
#define mpp(a,b,c) mp(mp(a,b),c)
using namespace std;
int n,m,x[200010],a[200010];
char s[200010];
L l,r,f[200],g[200];
inline L count(L r,int i)
{
	int j;
	L k=0;
	for(j=1;j<=n;j++)
	  a[j]=a[j-1]+(s[j]=='a'+i);
	if(n%m==0)
	  if(r<=n)
	    return a[r];
	  else
	    return a[n]+(r-n)/m*a[m]+a[(r-n)%m];
	else
	  {
	   f[1]=a[m];
	   g[1]=m;
	   f[2]=a[n];
	   g[2]=n;
	   for(j=3;g[j-1]<r;j++)
	     {
		  f[j]=f[j-1]+f[j-2];
		  g[j]=g[j-1]+g[j-2];
		 }
	   for(j--;j;j--)
	     if(r>=g[j])
	       {
			r-=g[j];
			k+=f[j];
		   }
	   k+=a[r];
	   return k;
	  }
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j;
	scanf("%s%lld%lld",&s[0]+1,&l,&r);
	n=strlen(&s[0]+1);
	for(i=2;i<=n;i++)
	  {
	   for(j=x[i-1];j;j=x[j])
	     if(s[j+1]==s[i])
	       break;
	   if(s[j+1]==s[i])
	     x[i]=j+1;
	  }
	for(i=x[n];i>n/2;i=x[i]);
	n-=i;
	m=n-x[n];
	for(i=0;i<26;i++)
	  printf("%lld ",count(r,i)-count(l-1,i));
	return 0;
}