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:
//15:53-17:33
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define mod 1000000007
string s;
ll L,R;
ll hhash[200005];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll calc(int l,int r){
	ll ret = hhash[r]-(l?hhash[l-1]:0LL); //cout << ret << endl;
	return (ret%mod+mod)%mod * modpow(modpow(37LL,1LL*l),mod-2) % mod;
}
vector<vector<ll> >vec;
vector<ll>num;
vector<ll>cnt[200005];
vector<ll>C(ll idx){
	if(idx <= s.size()) return idx<=0?vector<ll>(26,0LL):cnt[idx-1];
	int x = upper_bound(num.begin(),num.end(),idx)-num.begin();
	x--;
	vector<ll>V = C(idx-num[x]);
	for(int i=0;i<26;i++) V[i] += vec[x][i];
	return V;
}
int main(){
	cin >> s >> L >> R;
	ll seed = 1;
	for(int i=0;i<s.size();i++){
		hhash[i] += (1+s[i]-'a') * seed % mod;
		seed *= 37LL; seed %= mod;
		if(i){
			hhash[i] = (hhash[i]+hhash[i-1])%mod;
			cnt[i] = cnt[i-1]; cnt[i][s[i]-'a']++;
		}
		else{
			cnt[i].resize(26,0LL); cnt[i][s[i]-'a']++;
		}
	}
	int n = s.size(); n /= 2; //cout << n<< endl;
	ll beg = n,nex = 2*n;
	for(int i=n+1;i<2*n;i++){
	    //if(i==22) cout << hhash[2*n-1-i] << " " << calc(i,2*n-1) << endl;
		if(hhash[2*n-1-i] == calc(i,2*n-1)){
			nex = i; break;
		}
	}
	vector<ll>hoge(26,0ll);
	for(int i=0;i<beg;i++){
		hoge[s[i]-'a']++;
	}
	vector<ll>hoge2(26,0ll);
	for(int i=0;i<nex;i++){
		hoge2[s[i]-'a']++;
	}
	vec.pb(hoge); vec.pb(hoge2);
	num.pb(beg); num.pb(nex); //cout << beg << " " << nex << endl;
	while(1){
		vector<ll>hoge3(26,0LL);
		ll S = 0;
		for(int i=0;i<26;i++){
			hoge3[i] = vec[vec.size()-1][i]+vec[vec.size()-2][i];
			S += hoge3[i];
		}
		if(S > R) break;
		else{
			vec.pb(hoge3);
			num.pb(num[num.size()-1]+num[num.size()-2]); //cout << num[num.size()-1] << endl;
		}
	}
	vector<ll>B = C(R);
	vector<ll>S = C(L-1);
	for(int i=0;i<26;i++) cout << B[i]-S[i] << (i==25?'\n':' ');
}