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>

typedef long long LL;
typedef std::valarray<LL> data;

const int N = 200005, M = 100;

std::string s, t;
LL l, r; int p;

void solve() {
	static int nxt[N], n = s.size();
	for (int i = 1, p = nxt[0] = -1; i <= n; nxt[i++] = ++p)
		while (p >= 0 && s[p] != s[i - 1]) p = nxt[p];
	int p = n; while (p << 1 > n) p = nxt[p];
	n -= p, s.resize(n), t = s.substr(0, n - nxt[n]);
}

LL len[M];
data sum[M];

data count(const std::string &s, int n = 0x3f3f3f3f) {
	data ret(26);
	for (int i = 0; i < n && i < s.size(); ++i) ++ret[s[i] - 'a'];
	return ret;
}

data dfs(int dep, LL n) {
	if (dep <= 1) return count(dep ? s : t, n);
	if (n <= len[dep - 1]) return dfs(dep - 1, n);
	else return sum[dep - 1] + dfs(dep - 2, n - len[dep - 1]);
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> s >> l >> r, solve();
	len[1] = s.size(), len[0] = t.size();
	sum[1] = count(s), sum[0] = count(t);
	for (p = 1; len[p] < 1e18; ++p)
		len[p + 1] = len[p] + len[p - 1], sum[p + 1].resize(26), sum[p + 1] = sum[p] + sum[p - 1];
	data ret = dfs(p, r) - dfs(p, l - 1);
	for (int i = 0; i < 26; ++i) std::cout << ret[i] << ' '; std::cout << '\n';
	return 0;
}