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:
/*input
vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000


*/

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <array>
#include <cassert>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 7;
vector<int64_t> fib;

int64_t add(int64_t a, int64_t b) { return min(a + b, INF); }
int64_t mul(int64_t a, int64_t b)
{
	if (!a || !b) return 0;
	return (INF / b >= a) ? a * b : INF;
}

vector<int> kmp(string S)
{
	int N = (int) S.size();
	vector<int> lps(N + 1, 0);
	lps[1] = 0;
	for (int i = 2; i <= N; ++i) {
		for (lps[i] = lps[i - 1]; lps[i] != 0 && S[i - 1] != S[lps[i]]; lps[i] = lps[lps[i]]);
		if (S[i - 1] == S[lps[i]]) ++lps[i];
	}
	return lps;	
}

array<int64_t, 26> solve(string S, int64_t R)
{
	if (R == 0) return {};
	int N = (int) S.size() / 2;
	S.resize(N);

	auto lps = kmp(S);

	int len1 = N - lps[N], len2 = lps[N];
	int64_t cnt1 = 0, cnt2 = 0;
	for (int i = (int) fib.size() - 1; i >= 2; --i) {
		// cout << add(mul(fib[i - 1], len1), mul(fib[i - 2], len2)) << endl;
		if (add(mul(fib[i - 1], len1), mul(fib[i - 2], len2)) <= R) {
			cnt1 += fib[i - 1], cnt2 += fib[i - 2];
			R -= fib[i - 1] * len1 + fib[i - 2] * len2;
		}
		// cout << i << ": " << R << endl;
	}

	array<int64_t, 26> ans = {};
	for (int i = 0; i < 26; ++i) ans[i] = 0;
	assert(R <= N);
	// for (int i = 0; i < N; ++i) cout << (S[i] - 'a'); cout << endl;
	for (int i = 0; i < R; ++i) ++ans[S[i] - 'a'];

	// cout << cnt1 << ' ' << cnt2 << endl;
	for (int i = 0; i < N - lps[N]; ++i) ans[S[i] - 'a'] += cnt1;
	for (int i = N - lps[N]; i < N; ++i) ans[S[i] - 'a'] += cnt2;
	return ans;
}

int main()
{
	fib = {0, 1};
	while (fib.back() < INF) fib.push_back(*fib.rbegin() + *next(fib.rbegin()));

	ios_base::sync_with_stdio(0); cin.tie(0);
	string S;
	cin >> S;
	int64_t L, R;
	cin >> L >> R;

	auto x = solve(S, R), y = solve(S, L - 1);
	for (int i = 0; i < 26; ++i) cout << x[i] - y[i] << ' ';
	cout << endl;
	return 0;
}