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<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int oto[10100000];
long long L[500];
char p[10100000];
map<long long, long long>Map[500];
int Do(int n) {
	int i;
	p[n] = 0;
	oto[0] = -1;
	for (i = 1; i <= n; i++) {
		int t = oto[i - 1];
		while (t != -1 && p[i - 1] != p[t])t = oto[t];
		oto[i] = t + 1;
	}
	for (int TT = 0; TT < 3; TT++) {
		int t = n;
		while (t * 2 >= n)t = oto[t];
		L[TT] = n;
		int tn = n * 2 - t * 2;
		for (i = n + 1; i <= tn; i++) {
			p[i - 1] = p[t - 1 + i - n];
			int tt = oto[i - 1];
			while (tt != -1 && p[i - 1] != p[tt])tt = oto[tt];
			oto[i] = tt + 1;
		}
		n = tn;
		L[TT + 1] = n;
	}
	if (L[3] - L[2] == L[2] - L[1]) return 1;
	return 2;
}
long long C[26], C2[26], T[26];
void Get1(long long n) {
	int i;
	for (i = 0; i < 26; i++)T[i] = C[i] = 0;
	for (i = 0; i < min(L[1], n); i++)C[p[i] - 'a']++;
	for (i = L[1]; i < L[2]; i++)T[p[i] - 'a']++;
	if (n <= L[1])return;
	for (i = 0; i < 26; i++)C[i] += ((n - L[1]) / (L[2] - L[1])) * T[i] ;
	for (i = 0; i < (n - L[1]) % (L[2] - L[1]); i++)C[p[L[1] + i] - 'a']++;
}
int main() {
	int i;
	long long b, e;
	scanf("%s", p);
	scanf("%lld%lld", &b, &e);
	for (i = 0; p[i]; i++);
	int n = i;
	if (Do(n) == 1) {
		Get1(b-1);
		for (i = 0; i < 26; i++)C2[i] = C[i];
		Get1(e);
		for (i = 0; i < 26; i++)printf("%lld ", C[i] - C2[i]);
		return 0;
	}
	else {
		int i;
		for (i = 4;; i++) {
			L[i] = L[i - 1] + L[i - 2];
			if (L[i] >= e)break;
		}
		int pv = i;
		Map[pv][e]++;
		Map[pv][b - 1]--;
		for (i = pv; i >= 2; i--) {
			for (auto &tp : Map[i]) {
				if (tp.first <= L[i - 1])Map[i - 1][tp.first] += tp.second;
				else {
					Map[i - 1][L[i - 1]]+=tp.second;
					Map[i - 1][tp.first - L[i] / 2]+=tp.second;
					Map[i - 1][L[i - 1] - L[i] / 2]-=tp.second;
				}
			}
		}
		long long s = 0;
		for (i = L[1]; i >= 1; i--) {
			s += Map[1][i];
			C[(p[i - 1] - 'a')] += s;
		}
		for (i = 0; i < 26; i++)printf("%lld ", C[i]);
	}
}