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>
#include<algorithm>
#define N 200010
#define ll long long
using namespace std;

int n, nxt[N], d, len[2];
ll L, R, ans[26], D[1010][2], s[2], s1[2][26];
char S[N];

inline void kmp(){
	nxt[0]=nxt[1]=0; int j;
	for(int i=2; i<=n; i++){
		j=nxt[i-1]; while(j&&S[i]!=S[j+1])j=nxt[j];
		if(S[i]==S[j+1])j++; nxt[i]=j;
	}
}

inline void solve(ll m, int f){
	len[0]=n; len[1]=d;
	memset(D, 0, sizeof(D)); D[1][0]=1; D[2][1]=1;
	if(m<=n+d){
		for(int i=1; i<=n; i++)if(i<=m)ans[S[i]-'a']+=f;
		for(int i=1; i<=d; i++)if(n+i<=m)ans[S[i]-'a']+=f;
		return;
	}
	memset(s1, 0, sizeof(s1));
	for(int i=1; i<=n; i++)s1[0][S[i]-'a']++;
	for(int i=1; i<=d; i++)s1[1][S[i]-'a']++;
	
	s[0]=1; s[1]=0; ll now=n+d; int p;
	for(int i=3; i<=1000; i++){
		D[i][0]=s[0]; D[i][1]=s[1];
		now+=D[i][0]*len[0]+D[i][1]*len[1];
		s[0]+=D[i-1][0]; s[1]+=D[i-1][1];
		if(now>=m){
			while(m>n+d){
				for(int j=1; j<=i; j++)if(m>=D[j][0]*len[0]+D[j][1]*len[1]){
					for(int k=0; k<=25; k++)ans[k]+=s1[0][k]*D[j][0]*f;
					for(int k=0; k<=25; k++)ans[k]+=s1[1][k]*D[j][1]*f;
					m-=D[j][0]*len[0]+D[j][1]*len[1];
				}
			}
			for(int j=1; j<=n; j++)if(j<=m)ans[S[j]-'a']+=f;
			for(int j=1; j<=d; j++)if(n+j<=m)ans[S[j]-'a']+=f;
			return;
		}
	}
}

int main(){
	scanf("%s", S+1); n=strlen(S+1); n>>=1;
	scanf("%lld%lld", &L, &R);
	kmp(); d=n-nxt[n];
	memset(ans, 0, sizeof(ans)); solve(R, 1); solve(L-1, -1);
	for(int i=0; i<=24; i++)printf("%lld ", ans[i]); printf("%lld", ans[25]);
}