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;

template <typename _tp> inline void read(_tp&x) {
	char ch=getchar(),ob=0;x=0;
	while(ch!='-'&&!isdigit(ch))ch=getchar();if(ch=='-')ob=1,ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(ob)x=-x;
}

const int N = 201000;
char str[N];
int f[26][N], n;
int nxt[N], t;

ll calc(int*a, ll p) {
	if(p <= n) return a[p];
	if(p <= (n<<1)) return a[n] + a[p-n];
	ll t0 = n, t1 = n + t;
	ll r0 = a[n], r1 = a[n] + a[t];
	while(t0 + t1 <= p) {
		t0 += t1, r0 += r1;
		swap(t0, t1), swap(r0, r1);
	}
	return r1 + calc(a, p - t1);
}

bool fac;

ll work(int*a, ll p) {
	if(p <= n) return a[p];
	if(p <= (n<<1)) return a[n] + a[p-n];
	if(fac) {
		p -= n;
		return a[n] + (p/t) * a[t] + a[p%t];
	}
	return calc(a, p);
}

int main() {
	scanf("%s", str+1);
	n = strlen(str+1) >> 1;
	for(int i=0;i<26;++i) {
		int*arr = f[i];
		for(int j=1;j<=n;++j)
			arr[j] = arr[j-1] + (str[j] == (i+'a'));
	}
	
	for(int i=2,k=0;i<=n;++i) {
		while(k and str[k+1] != str[i]) k = nxt[k];
		if(str[k+1] == str[i]) ++k;
		nxt[i] = k;
	}
	
	t = n - nxt[n];
	fac = (n%t == 0);
	
	ll l, r; scanf("%lld%lld",&l,&r);
	for(int i=0;i<26;++i)
		printf("%lld ", work(f[i], r) - work(f[i], l-1));
	putchar(10);
	return 0;
}