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<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const llint big=2e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-9;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);}

class alphs{
public:
	array<llint,26> kaz;
	alphs(){for(int i=0;i<26;i++){kaz[i]=0;}}
	alphs& operator +=(alphs other){
		for(int i=0;i<26;i++){this->kaz[i]+=other.kaz[i];}
		return (*this);
	}
	alphs& operator -=(alphs other){
		for(int i=0;i<26;i++){this->kaz[i]-=other.kaz[i];}
		return (*this);
	}
};
vector<llint> retu;
vector<alphs> mowa;
string str;
void retus(void){
	llint k=retu.back();
	alphs a=mowa.back();
	while(-1){
		k+=retu[retu.size()-2];retu.pub(k);
		a+=mowa[mowa.size()-2];mowa.pub(a);
		if(retu.back()>big){return;}
	}
}
alphs solve(llint x,llint fu){
	alphs ans;
	if(fu==0||fu==1){
		for(llint i=0;i<x;i++){ans.kaz[str[i]-'a']++;}
		return ans;
	}
	if(x<retu[fu-1]){return solve(x,fu-1);}
	ans=mowa[fu-1];
	ans+=solve(x-retu[fu-1],fu-2);
	return ans;
}

int main(void){
	llint l,r,n,i,j;//p r p の最初のp
	cin>>str;n=str.size();
	cin>>l>>r;
	alphs it;n/=2;
	for(i=0;i<n;i++){it.kaz[str[i]-'a']++;}
	mowa.pub(it);
	retu.pub(n);
	for(j=0;j<n;j++){str.pob();}
	llint ueha=0;
	llint siha=0;
	const llint ueka=101;
	llint uegen=1;
	llint iti=n;
	for(i=1;i<n;i++){//上と下が良い数
		ueha+=(str[i-1]-'a')*uegen;ueha%=mod;
		uegen*=ueka;uegen%=mod;
		siha*=ueka;
		siha+=(str[n-i]-'a');
		siha%=mod;
		if(ueha==siha){iti=i;}
	}
	for(j=0;j<n-iti;j++){
		str.pub(str[j]);
		it.kaz[str[j]-'a']++;
	}
	mowa.pub(it);
	retu.pub(str.size());
	retus();
	auto ans=solve(r,retu.size());
	ans-=solve(l-1,retu.size());
	for(i=0;i<26;i++){cout<<ans.kaz[i]<<" ";}
	return 0;
}