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:
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
	ll X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200000+10;

int n,lt,lim; char s[N];
int sum[N][26];
ll ans[26],len[100],cnt[100][26];

int nxt[N];
void getnext() {
	for (int i=2,j=0;i<=n;++i) {
		while (j&&s[j+1]!=s[i]) j=nxt[j];
		if (s[j+1]==s[i]) ++j;
		nxt[i]=j;
	}
}

void calc_sp(ll p,int w) {
	if (!p) return;
	for (int i=0;i<26;++i) ans[i]+=w*(p/lt)*sum[lt][i];
	for (int i=0;i<26;++i) ans[i]+=w*sum[p%lt][i];
}

void calc(ll p,int w) {
	if (!p) return;
	for (int i=lim;i;--i) {
		if (p<len[i]) continue;
		p-=len[i];
		for (int j=0;j<26;++j) ans[j]+=w*cnt[i][j];
	}
	for (int i=0;i<26;++i) ans[i]+=w*sum[p][i];
}

int main() {
	scanf("%s",s+1); n=strlen(s+1)>>1;
	ll l=read(),r=read();
	getnext(); lt=n-nxt[n];
	for (int i=1;i<=n;++i) {
		memcpy(sum[i],sum[i-1],sizeof(sum[i]));
		++sum[i][s[i]-'a'];
	}
	if (n%lt==0) calc_sp(r,1),calc_sp(l-1,-1);
	else {
		len[1]=n,len[2]=n+lt;
		for (int i=0;i<26;++i)
			cnt[1][i]=sum[n][i],cnt[2][i]=sum[n][i]+sum[lt][i];
		for (int i=3;;++i) {
			len[i]=len[i-1]+len[i-2];
			for (int j=0;j<26;++j) cnt[i][j]=cnt[i-1][j]+cnt[i-2][j];
			if (len[i]>1e18) { lim=i; break; }
		}
		calc(r,1),calc(l-1,-1);
	}
	for (int i=0;i<26;++i) printf("%lld ",ans[i]); puts("");
	return 0;
}