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:
//#pragma GCC optimize(2)
#include<set>    
#include<map>    
#include<stack>    
#include<ctime>    
#include<cstdio>    
#include<queue>    
#include<cmath>    
#include<vector>    
#include<cstring>   
#include<climits>    
#include<iostream>   
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
LL read(){
    LL f=1,x=0;char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f*x;
}
#define INF (LL)(1e18)
#define MAXN 2000000
LL f[100],g[100][26],s0[MAXN+5][26],s1[MAXN+5][26],sum[26];
char S[MAXN+5];
int nxt[MAXN+5],siz=1;
void Climb(LL m,int s){
	int p=siz;
	while(p>1){
		if(f[p-1]<=m){//&&m<=f[p]
			m-=f[p-1];
			for(int c=0;c<26;c++)
				sum[c]+=s*g[p-1][c];
			p-=2;
		}
		else
			p--;
	}
	if(f==0){
		for(int c=0;c<26;c++)
			sum[c]+=s*s0[m][c];
	}
	else{
		for(int c=0;c<26;c++)
			sum[c]+=s*s1[m][c];
	}
	return ;
}
int main(){
	scanf("%s",S+1);
	int n=strlen(S+1)/2;
	f[0]=n;
	LL L=read(),R=read();
	for(int i=1;i<=n;i++){
		memcpy(s0[i],s0[i-1],sizeof(s0[i-1])),s0[i][S[i]-'a']++;
		memcpy(s1[i],s1[i-1],sizeof(s1[i-1])),s1[i][S[i]-'a']++;
		g[0][S[i]-'a']++,g[1][S[i]-'a']++;
	}
	for(int i=2,j=0;i<=n;i++){
		while(j!=0&&S[i]!=S[j+1])
			j=nxt[j];
		if(S[i]==S[j+1])
			j++;
		nxt[i]=j;
	}
	if(n%(n-nxt[n])==0){
		for(int c=0;c<26;c++)
			sum[c]=(R/n*s0[n][c]+s0[R%n][c])-((L-1)/n*s0[n][c]+s0[(L-1)%n][c]);
		for(int c=0;c<26;c++)
			printf("%lld",sum[c]),putchar(c==25?'\n':' ');
		return 0;
	}
	f[1]=f[0]+n-nxt[n];
	for(int i=1;i<=n-nxt[n];i++){
		memcpy(s1[i+n],s1[i+n-1],sizeof(s1[i+n-1])),s1[i+n][S[i]-'a']++;
		g[1][S[i]-'a']++;
	}
	while(f[siz]<=INF){
		++siz;
		f[siz]=f[siz-1]+f[siz-2];
		for(int c=0;c<26;c++)
			g[siz][c]=g[siz-1][c]+g[siz-2][c];
	}
	Climb(R,1),Climb(L-1,-1);
	for(int c=0;c<26;c++)
		printf("%lld",sum[c]),putchar(c==25?'\n':' ');
	return 0;
}