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 N=200005;

struct node{
	ll v[26];
	node(bool f=0){if(f)memset(v,0,26<<3);}
	ll&operator[](char c){return v[c-'a'];}
	node friend operator+(const node&a,const node&b){
		node c=a;
		for(int i=0;i<26;i++)c.v[i]+=b.v[i];
		return c;
	}
	node friend operator-(const node&a,const node&b){
		node c=a;
		for(int i=0;i<26;i++)c.v[i]-=b.v[i];
		return c;
	}
	node friend operator*(const node&a,ll b){
		node c=a;
		for(int i=0;i<26;i++)c.v[i]*=b;
		return c;
	}
	void print(){
		for(int i=0;i<26;i++)
			printf("%lld%c",v[i]," \n"[i==25]);
	}
}ch[N];

char S[N];
ll l,r,f[105];
int n,fail[N],m,k;
node g[105];

void mk(){
	g[0]=ch[m];f[0]=m;
	g[1]=ch[n];f[1]=n;
	for(k=2;(g[k]=g[k-1]+g[k-2],f[k]=f[k-1]+f[k-2])<=r;k++);
}
node chk1(ll len){
	if(len<=n)return ch[len];
	node ret=ch[n];len-=n;
	ret=ret+ch[m]*(len/m)+ch[len%m];
	return ret;
}
node chk2(ll len){
	node ret(true);
	for(int i=k;i>=1;i--)
		if(len>=f[i])ret=ret+g[i],len-=f[i];
	ret=ret+ch[len];len=0;
	return ret;
}

int main(){
	scanf("%s",S+1);
	n=strlen(S+1)>>1;
	scanf("%lld%lld",&l,&r);
	fail[1]=0;ch[1][S[1]]++;
	for(int i=2;i<=n;i++){
		int p=fail[i-1];
		while(p&&S[p+1]!=S[i])p=fail[p];
		fail[i]=p+(S[p+1]==S[i]);
		ch[i]=ch[i-1];ch[i][S[i]]++;
	}
	m=n-fail[n];
	if(n%m==0)(chk1(r)-chk1(l-1)).print();
	else mk(),(chk2(r)-chk2(l-1)).print();
	return 0;
}