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<cctype>
#include<algorithm>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1600010;
char s[maxn];
int n,f[maxn],cnt[30];
ll ans[30],g[1000][30];
int get_next() {
	f[0]=f[1]=0;
	rep(i,1,n-1) {
		int j=f[i];
		while(j&&s[j]!=s[i]) j=f[j];
		f[i+1]=(s[i]==s[j]?j+1:0);
	}
	int j=f[n];
	while(j&&j>=(n+1)/2) j=f[j];
	int m=n;
	rep(i,j,n-j-1) s[m++]=s[i];
	return n=m;
}
int K;
void init() {
	f[0]=f[1]=0;
	rep(i,1,n-1) {
		int j=f[i];
		while(j&&s[j]!=s[i]) j=f[j];
		f[i+1]=(s[i]==s[j]?j+1:0);
	}
	int j=f[n];
	while(j&&j>=(n+1)/2) j=f[j];
	if(j) K=n/2;
	else K=n;
	n-=j;
}
int main() {
	ll l,r;
	scanf("%s%lld%lld",s,&l,&r);
	n=strlen(s);
	init();s[n]='\0';
//	printf("%s\n",s);
	int st=n;
	int a=get_next();
	int b=get_next();
	int c=get_next();
	if(b*2==a+c) { // equal
		rep(i,1,n) if(i>=l&&i<=r) ans[s[i-1]-'a']++;
		rep(i,b,c-1) cnt[s[i]-'a']++;
		r-=n;l-=n+1;
		rep(x,0,25) {
			ll k=r/(c-b);if(r<0) k=0;
			ans[x]+=k*cnt[x];
			ll k2=l/(c-b);if(l<0) k2=0;
			ans[x]-=k2*cnt[x];
			if(x==25) {
				r-=k*(c-b);l-=k2*(c-b);
				rep(i,1,r) ans[s[i-1]-'a']++;
				rep(i,1,l) ans[s[i-1]-'a']--;
			}
		}
	}
	else { // fib
		g[1][26]=K;g[2][26]=st;
		rep(i,0,K-1) g[1][s[i]-'a']++;
		rep(i,0,st-1) g[2][s[i]-'a']++;
		int m;
		rep(i,3,1000) {
			rep(x,0,26) g[i][x]=g[i-1][x]+g[i-2][x];
			if(g[i][26]>=r) {m=i;break;}
		}
	//	rep(i,1,m) printf("%lld ",g[i][26]);puts("");
		dwn(j,m,1) if(r>=g[j][26]) {
			rep(x,0,25) ans[x]+=g[j][x];
			r-=g[j][26];
		}
		rep(i,1,r) ans[s[i-1]-'a']++;
		l--;
		dwn(j,m,1) if(l>=g[j][26]) {
			rep(x,0,25) ans[x]-=g[j][x];
			l-=g[j][26];
		}
		rep(i,1,l) ans[s[i-1]-'a']--;
	//	printf("%d %d\n",l,r);
	}
	rep(i,0,25) printf("%lld%c",ans[i],i==25?'\n':' ');
	return 0;
}
/*
abbaabba
3 52523523
*/