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

#define iter(i, n) forw(i, 1, n)
#define forw(i, a, b) for (int i = a; i <= b; ++i)

typedef long long i64;
typedef unsigned long long u64;
typedef vector<i64> Info;

const int NR = 2e5 + 100;

i64 f[200];
int p[NR];
string s, t;
i64 L, R;
int n;

Info c[200];

Info add(Info a, Info b) {
	Info c(26);
	for (int i = 0; i < 26; ++i) c[i] = a[i] + b[i];
	return c;
}

Info count(string s) {
	Info a(26);
	for (char c : s) ++a[c - 'a'];
	return a;
}

Info print(int n, i64 L, i64 R) {
//	printf("%d %lld %lld\n", n, L, R);
	if (L == 1 && R == f[n]) {
		return c[n];
	}

	if (n < 2) {
		return count((n == 0 ? s : s + t).substr(L - 1, R - L + 1));
	}

	i64 t = f[n - 1];
	if (R <= t) return print(n - 1, L, R);
	else if (L > t) return print(n - 2, L - t, R - t);
	else {
		return add(print(n - 1, L, t), print(n - 2, 1, R - t));
	}
}

string per(string s) {
	int j = -1, n = s.length();
	p[0] = -1;
	for (int i = 1; i < n; ++i) {
		for (; j >= 0 && s[i] != s[j + 1]; j = p[j]);
		if (s[i] == s[j + 1]) ++j;
		p[i] = j;
	}
	return s.substr(0, n - 1 - p[n - 1]);
}



int main() {
	//freopen("77F.in", "r", stdin);
	cin >> s >> L >> R;
	s = s.substr(0, s.length() / 2);
	t = per(s);
	f[0] = s.length();
	c[0] = count(s);
	f[1] = f[0] + t.length();
	c[1] = add(c[0], count(t));
	for (n = 2; (u64) f[n - 1] + f[n - 2] <= 1e18; ++n)
		f[n] = f[n - 1] + f[n - 2], 
		c[n] = add(c[n - 1], c[n - 2]);
	Info tmp = print(n, L, R);
	for (int i = 0; i < 26; ++i) printf("%lld ", tmp[i]);
	puts("");
	return 0;
}