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;
typedef long long LL;
const int MaxN = 2e5+3;
char s[MaxN];
LL l,r;
int cnt[MaxN][26];
struct Statu{
	LL s[26];
	Statu() {memset(s,0,sizeof s);}
	template<typename T>
	Statu(const T* x) {
		for (LL* p=s;p<s+26;++p,++x) *p=*x;
	}
	inline LL& operator [](const char& ch) {
		return *(s+(int)ch-'a');
	}
	inline LL& operator [] (const int& x) {
		return *(s+x);
	}
	inline Statu& operator +=(const Statu& o) {
		for (int i=0;i<26;++i) s[i]+=o.s[i];
		return *this;
	}
	inline Statu operator +(const Statu& b) const {
		Statu ret;
		for (int i=0;i<26;++i) ret.s[i]=s[i]+b.s[i];
		return ret;
	}
	inline void print() const {
		for (int i=0;i<26;++i) printf("%I64d ",s[i]);
		putchar('\n');
	}
};

inline int* Z_box(const char* str,int* z) {
	int r=-1,p=-1,l=strlen(str);
	z[0]=l-1;
	for (int i=1;i<l;++i) {
		z[i]=-1;
		if (r>=i) z[i]=min(z[i-p],r-i);
		while (i+z[i]+1<l && str[i+z[i]+1]==str[z[i]+1]) z[i]++;
		if (i+z[i]>r) r=i+z[i],p=i;
	}
	return z;
}

LL solve(LL llen,Statu L,LL rlen,Statu R,LL last,Statu& ans) {
	if (llen+rlen<=last) {
		LL t=solve(llen+rlen,L+R,llen,L,last,ans);
		last=t;
	}
	if (llen<=last) {
		ans+=L;
		last-=llen;
	}
	return last;
} 
char s2[MaxN];int z[MaxN];
int main() {
	scanf("%s",s);
	cin >> l >> r;
	l--,r--;
	int len=strlen(s);
	for (int i=0;i<len/2;++i) s2[i]=s[i];
	int l2=strlen(s2);
	Z_box(s2,z);
	memset(cnt,0,sizeof cnt);
	cnt[0][s[0]-'a']=1;
	for (int i=1;i<l2;++i) {
		for (int j=0;j<26;++j) cnt[i][j]=cnt[i-1][j];
		cnt[i][s[i]-'a']++;
	}
	int pre=0x7fffffff; 
	for (int i=1;i<l2;++i) {
		if (z[i]!=-1 && i+z[i]==l2-1) pre=min(pre,i); 
	}
	if (pre==0x7fffffff) {
		Statu ans;
		for (int i=0;i<26;++i) {
			ans[i]+=(LL)cnt[l2-1][i]*(r/l2)+cnt[r%l2][i];
			if (l>=1) ans[i]-=(LL)cnt[l2-1][i]*((l-1)/l2)+cnt[(l-1)%l2][i];
		}
		for (int i=0;i<26;++i) cout << ans[i] << " ";
	} else {
		Statu L,R,ans1,ans2,ans;
		for (int i=0;i<26;++i) 
			L[i]=cnt[pre-1][i],
			R[i]=cnt[l2-1][i]-cnt[pre-1][i];
		LL x1=solve(pre,L,l2-pre,R,r+1,ans1),x2=solve(pre,L,l2-pre,R,l,ans2);
		for (int i=0;i<26;++i) {
			ans[i]=ans1[i]-ans2[i]; 
			if (x1>=1) ans[i]+=cnt[x1-1][i];
			if (x2>=1) ans[i]-=cnt[x2-1][i];
		}
		for (int i=0;i<26;++i) cout << ans[i] << " ";
	}
	return 0;
}