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>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
const int mod = 998244353;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
char s[maxn]; int len;
int h0[maxn], pw[maxn];
inline int sub(int l,int r) {
	return (h0[r] + ll(mod - pw[r - l + 1]) * h0[l - 1]) % mod;
}
struct T { ll a[26]; };
inline T add(T x, T y) {
	for(int i = 0;i < 26;++i) {
		x.a[i] += y.a[i];
	}
	return x;
}
inline T sub(T x, T y) {
	for(int i = 0;i < 26;++i) {
		x.a[i] -= y.a[i];
	}
	return x;
}
typedef std::string str;
T sum[maxn], empty;
ll size[maxn];
str b;
int ok[maxn];
inline void init(str s0, str s1) {
	s1 = s0 + s1;
	size[1] = s0.size(), size[2] = s1.size();
	for(char i : s0) ++ sum[1].a[i - 'a'];
	for(char i : s1) ++ sum[2].a[i - 'a'];
	ok[1] = ok[2] = 1;
	for(int i = 3;i <= 100;++i) {
		size[i] = size[i - 1] + size[i - 2];
		ok[i] = ok[i - 1] && size[i] <= 2e18;
		sum[i] = add(sum[i - 1], sum[i - 2]);
	}
}
inline T pre(ll x) {
	T ans = empty;
	for(int j = 100;j >= 0;--j) if(ok[j] && x >= size[j]) {
		ans = add(ans, sum[j]);
		x -= size[j], --j;
	}
	for(int j = 1;j <= x;++j) ++ ans.a[s[j] - 'a'];
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	*pw = 1;
	for(int i = 1;i < maxn;++i) {
		pw[i] = pw[i - 1] * 233ll % mod;
	}
	cin >> s + 1, len = strlen(s + 1) >> 1;
	for(int i = 1;i <= len;++i) {
		h0[i] = (h0[i - 1] * 233ll + s[i]) % mod;
	}
	int border = len;
	for(int i = 1;i < len;++i) {
		if(sub(1, i) == sub(len - i + 1, len)) {
			border = i;
		}
	}
	if(border << 1 >= len && len % border == 0) {
		init(str(s + 1, s + len + 1), str(s + 1, s + len + 1));
	} else if(border > 0) {
		init(str(s + 1, s + len + 1), str(s + 1, s + len - border + 1));
	}
	ll l, r;
	cin >> l >> r;
	T ans = sub(pre(r), pre(l - 1));
	for(int i = 0;i < 26;++i) {
		cout << ans.a[i] << ' ';
	}
}