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>
using namespace std;

#define ll long long
const int MAXN=3e5+5;

int len,anc[30][MAXN],S,T,num,p[MAXN];
ll l,r;
char s[MAXN];

ll calc(ll lt,int n){
	if(lt<=len)return anc[n][lt];
	if(lt<=2*len)return anc[n][len]+anc[n][lt-len];
	ll f1=anc[n][S],f2=anc[n][len],lenf1=S,lenf2=len;
	while(lt>lenf1+lenf2){
		ll tem2=f2,lentem2=lenf2;
		f2+=f1;lenf2+=lenf1;
		f1=tem2;lenf1=lentem2;
	}
	return f2+calc(lt-lenf2,n);
}

int main(){
	scanf("%s",s+1);
	scanf("%lld%lld",&l,&r);
	len=strlen(s+1)/2;
/*	bool ok=0;
	for(int i=2*len;;i--){
		int tmp=i;num=1;
		while(s[num]==s[tmp]){
			num++;tmp++;
			if(tmp==2*len+1){
				ok=1;
				break;	
			}
		}
		if(ok){num--;break;}
	}	*/
	p[1] = 0;
    for (int j = 0, i = 2; i <= len; i ++) {
        for (; j && s[j + 1] != s[i];) j = p[j];
        if (s[j + 1] == s[i]) j ++;
        p[i] = j;
    }
//	T=num;
//	S=len-num;
	S=len-p[len];
	for(int i=1;i<=26;i++){
		for(int j=1;j<=len;j++){
			anc[i][j]=anc[i][j-1];
			if((int)s[j]-96==i)anc[i][j]++;
		}
	}
//	cout<<calc(43200,1);
	for(int i=1;i<=26;i++){
		printf("%lld ",calc(r,i)-calc(l-1,i));
	}
	return 0;
}