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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

const int N = 2e+5+5;

int n;
char s[N*2];
LL l,r;
LL cnt[30],ans[30];
int nxt[N*2];

void prepare(){
	fo(i,1,n)nxt[i]=0;
	int w=0;
	fo(i,2,n){
		if (w+nxt[w]-1>=i)nxt[i]=min(nxt[i-w+1],w+nxt[w]-i);
		while(i+nxt[i]<=n&&s[i+nxt[i]]==s[nxt[i]+1])nxt[i]++;
		if (i+nxt[i]-1>=w+nxt[w]-1)w=i;
	}
}

void trs(){
	prepare();
	fo(i,n/2+2,n)
	if(i+nxt[i]-1==n){n=i-1;break;}
}

struct number{
	LL x,y,val;
	number(const LL x_=0,const LL y_=0,const LL val_=0){x=x_;y=y_;val=val_;}
}a[100];
number operator + (number a,number b){return number(a.x+b.x,a.y+b.y,a.val+b.val);}

int key,k;

void add(LL lim){
	if (lim<=n){
		fo(i,1,lim)cnt[s[i]-'a']++;
		return;
	}
	int w;
	fd(i,key,1)
	if(lim>=a[i].val){w=i;break;}
	fo(i,1,n)cnt[s[i]-'a']+=a[w].x;
	fo(i,1,k)cnt[s[i]-'a']+=a[w].y;
	add(lim-a[w].val);
}

void solve(LL lim){
	fo(i,0,25)cnt[i]=0;
	k=n;
	fo(i,1,n)
	if (i+nxt[i]-1==n){k=i-1;break;}
	if (n%k==0){
		LL tim=lim/k;
		fo(i,1,k)cnt[s[i]-'a']+=tim;
		fo(i,1,lim%k)cnt[s[i]-'a']++;
	}
	else{
		a[0]=number(0,1,k);
		a[1]=number(1,0,n);
		key=0;
		fo(i,2,100){
			a[i]=a[i-1]+a[i-2];
			if (a[i].val>lim){key=i-1;break;}
		}
		add(lim);
	}
}

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%lld%lld",&l,&r);
	trs();
	prepare();
	solve(r);
	fo(i,0,25)ans[i]=cnt[i];
	solve(l-1);
	fo(i,0,25)ans[i]-=cnt[i];
	fo(i,0,25)printf("%lld ",ans[i]);
	putchar('\n');
	return 0;
}