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>

typedef long long LL;
const int N=2e5+10;

LL l,r,ans[26],g[110],sum[N][26],sm[110][26];
int len,plen,nxt[N];
char s[N];

void Init() {
	scanf("%s",s);
	scanf("%lld%lld",&l,&r);
}

void Getnext(char *s,int len) {
	nxt[0]=0;nxt[1]=0;
	for (int i=1,k=0;i<len;++i) {
		while (k && s[i]!=s[k]) k=nxt[k];
		if (s[i]==s[k]) ++k;
		nxt[i+1]=k;
	}
}

void Calc(int dep,LL *ans,LL _l,LL _r,int op) {
	if (_r==g[dep] && _l==1) {
		for (int j=0;j<26;++j) ans[j]=ans[j]+op*sm[dep][j];
		return ;
	}
	if (dep==0 || dep==1) {
		for (int j=0;j<26;++j) ans[j]=ans[j]+op*(sum[_r][j]-sum[_l-1][j]);
		return ;
	}
	if (_r>g[dep-1] && _l<=g[dep-1]) {
		Calc(dep-1,ans,_l,g[dep-1],op);
		Calc(dep-2,ans,1,_r-g[dep-1],op);
	}else if (_r<=g[dep-1]) Calc(dep-1,ans,_l,_r,op);
	 else Calc(dep-2,ans,_l-g[dep-1],_r-g[dep-1],op);
}

void Solve() {
	len=strlen(s);len/=2;
	Getnext(s,len);
	for (int i=1;i<=len;++i) {
		for (int j=0;j<26;++j) sum[i][j]=sum[i-1][j];
		sum[i][s[i-1]-'a']++;
	}
	plen=len-nxt[len];
	g[0]=plen; for (int j=0;j<26;++j) sm[0][j]=sum[plen][j];
	g[1]=len; for (int j=0;j<26;++j) sm[1][j]=sum[len][j];
	for (int i=2;i<=100;++i) {
		g[i]=g[i-1]+g[i-2];
		for (int j=0;j<26;++j) sm[i][j]=sm[i-1][j]+sm[i-2][j];
	}
	
	for (int i=1;i<=100;++i) 
		if (g[i]>r) { Calc(i,ans,l,r,1); break; }
	for (int i=0;i<26;++i) printf("%lld%c",ans[i],(i==25)?'\n':' ');
}

int main() {
	Init();
	Solve();
	return 0;
}