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;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
ll len[1001], cnt[1001][26];
int cntS[200001][26], cntX[400001][26];
vector<int> Z_algo(string &s) {
	int n = s.size();
	vector<int> z(n);
	int L = 0, R = 0;
	for (int i = 1; i < n; i++) {
		if (i > R) {
			L = R = i;
			while (R < n && s[R - L] == s[R]) R++;
			z[i] = R - L; R--;
		}
		else {
			int k = i - L;
			if (z[k] < R - i + 1) z[i] = z[k];
			else {
				L = i;
				while (R < n && s[R - L] == s[R]) R++;
				z[i] = R - L; R--;
			}
		}
	}
	return z;
}
ll solve(int k, int ch, ll L) {
	if (L > len[k]) return cnt[k][ch] + solve(k, ch, L - len[k]);
	if (L == len[k]) return cnt[k][ch];
	if (k == 0) return cntS[L][ch];
	if (k == 1) return cntX[L][ch];
	if (L > len[k - 1]) return cnt[k - 1][ch] + solve(k - 2, ch, L - len[k - 1]);
	return solve(k - 1, ch, L);
}
int main() {
	string S;
	cin >> S;
	ll l, r;
	cin >> l >> r;
	S = S.substr(0, S.size() / 2);
	vector<int> z = Z_algo(S);
	int k = 1;
	while (k < S.size()) {
		if (S.size() - k == z[k]) break;
		k++;
	}
	if (k == 0) k = S.size();
	string T = S.substr(0, k);
	string X = S + T;
	len[0] = S.size();
	len[1] = X.size();
	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j < 26; j++) cntS[i + 1][j] += cntS[i][j];
		cntS[i + 1][S[i] - 'a']++;
	}
	for (int i = 0; i < X.size(); i++) {
		for (int j = 0; j < 26; j++) cntX[i + 1][j] += cntX[i][j];
		cntX[i + 1][X[i] - 'a']++;
	}
	for (int i = 0; i < 26; i++) {
		cnt[0][i] = cntS[S.size()][i];
		cnt[1][i] = cntX[X.size()][i];
	}
	k = 0;
	while (len[k] * 2 < r) {
		if (k > 0) {
			len[k + 1] = len[k] + len[k - 1];
			for (int i = 0; i < 26; i++) cnt[k + 1][i] = cnt[k][i] + cnt[k - 1][i];
		}
		k++;
	}
	for (int i = 0; i < 26; i++) {
		cout << solve(k, i, r) - solve(k, i, l - 1) << " ";
	}
	cout << endl;
}