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 <string>
#include <map>
#include <vector>
using namespace std;

long long L, R, fib[100], power[100009], hush[100009]; string S, T;

void init() {
	fib[0] = 0; fib[1] = 1; for (int i = 2; i <= 99; i++) fib[i] = fib[i - 1] + fib[i - 2];
	power[0] = 1; for (int i = 1; i <= 100008; i++) power[i] = power[i - 1] * 331LL;
	hush[0] = 0; for (int i = 0; i < T.size(); i++) { hush[i + 1] = hush[i] * 331LL; hush[i + 1] += (T[i] - 'a' + 1); }
}
long long val(long long l, long long r) {
	return hush[r] - hush[l] * power[r - l];
}

long long reps() {
	long long G = 0;
	for (int i = 1; i <= T.size(); i++) {
		if (T.size() % i != 0) continue;
		bool OK = true;
		for (int j = 0; j < T.size(); j += i) {
			if (T.substr(0, i) != T.substr(j, i)) OK = false;
		}
		if (OK == true) { G = T.size() / i; break; }
	}
	return G;
}
vector<long long> solve_1(long long Y, long long Z) {
	vector<long long>rem(26, 0);
	for (int i = 0; i < Y; i++) rem[T[i] - 'a'] += Z / Y;
	for (int i = 0; i < Z%Y; i++) rem[T[i] - 'a']++;
	return rem;
}

long long a, b; map<long long, vector<long long>>M;

vector<long long>solve(long long Z) {
	if (M[Z].size() >= 1) return M[Z];
	if (Z <= a) {
		vector<long long>A1(26, 0);
		for (int i = 0; i < Z; i++) A1[T[i] - 'a']++;
		M[Z] = A1;
		return A1;
	}
	vector<long long>A2(26, 0);
	for (int i = 1; i <= 90; i++) {
		long long G = fib[i] * a + fib[i - 1] * b;
		if (Z <= G) {
			vector<long long>P1 = solve(fib[i - 1] * a + fib[i - 2] * b);
			vector<long long>P2 = solve(Z - (fib[i - 1] * a + fib[i - 2] * b));
			A2 = P1;
			for (int j = 0; j < 26; j++) A2[j] += P2[j];
			break;
		}
	}
	M[Z] = A2;
	return A2;
}

vector<long long>solve_2(long long Z) {
	a = T.size(), b = 0;
	for (int i = 0; i < T.size(); i++) { if (val(0, i) == val(T.size() - i, T.size())) b = T.size() - i; }
	return solve(Z);
}

int main() {
	cin >> S >> L >> R; T = S.substr(0, S.size() / 2);
	init();
	long long V = reps(); vector<long long>ans1, ans2;
	if (V >= 2) { ans1 = solve_1(T.size() / V, R); ans2 = solve_1(T.size() / V, L - 1); }
	else { ans1 = solve_2(R); ans2 = solve_2(L - 1); }
	for (int i = 0; i < ans1.size(); i++) { if (i)cout << " "; cout << ans1[i] - ans2[i]; }cout << endl;
	return 0;
}