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;

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ll MAX = 2e18;
const ld inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 200020;
const ll mod = 1e9 + 7;

inline ll power(ll x,ll y){
	y = ((y % (mod - 1)) + (mod - 1)) % (mod - 1);
//	if ( y < 0 ) return power(power(x,-y),mod - 2);
	ll res = 1;
	while ( y ){
		if ( y & 1 ) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

int len,s[maxn],fail[maxn];
int trans[maxn][10];
void getfail(){
	fail[1] = 0;
	int p = 0;
	rep(i,2,len){
		while ( p && s[i] != s[p + 1] ) p = fail[p];
		if ( s[i] == s[p + 1] ) fail[i] = ++p;
		else fail[i] = 0;
	}
}
struct node{
	ll len,cnt[50];
	node() { len = 0 , memset(cnt,0,sizeof(cnt)); }
	node operator + (node a){
		node cur;
		rep(i,0,25) cur.cnt[i] = a.cnt[i] + cnt[i];
		cur.len = len + a.len;
		if ( cur.len > MAX ) cur.len = MAX;
		return cur;
	}
}g[100];
char ch[maxn];
ll l,r;

void init(){
	len /= 2;
	rep(i,1,len) s[i] = ch[i] - 'a';
	getfail();
	g[0].len = len;
	rep(i,1,len) g[0].cnt[s[i]]++;
	g[1] = g[0];
	g[1].len += len - fail[len];
	rep(i,1,len - fail[len]) g[1].cnt[s[i]]++;
	rep(i,2,100){
		g[i] = g[i - 1] + g[i - 2];	
	}
}
node calc(ll n){
	node res;
	if ( !n ) return res;
	repd(i,100,0){
		if ( n >= g[i].len ) res = res + g[i] , n -= g[i].len; //发现这个地方特别好写，因为g[n] = g[n- 1] + g[n - 2],无论n是否大于当前长度，都考虑第n-1项
	}
	rep(i,1,n) res.cnt[s[i]]++;
	return res;
}
int main(){
	scanf("%s",ch + 1);
	cin>>l>>r;
	len = strlen(ch + 1);
	init();
	node ans1 = calc(r),ans2 = calc(l - 1);
	rep(i,0,25) cout<<ans1.cnt[i] - ans2.cnt[i]<<" ";
	cout<<endl;
}