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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
vector<int>zalgo(string s)
{
	vector<int>r;
	r.resize(s.size());
	r[0] = s.size();
	s.push_back('$');
	int pt = 1, kn = 0;
	for (;;)
	{
		if (pt == s.size() - 1)break;
		for (;;)
		{
			if (s[pt + kn] != s[kn])break;
			else kn++;
		}
		r[pt] = kn;
		int t = 1;
		for (;;)
		{
			if (r[t] < kn - t)r[pt + t] = r[t], t++;
			else break;
		}
		pt += t;
		kn = max(0, kn - t);
	}
	return r;
}
typedef long long ll;
vector<ll>get1(ll a, string s)
{
	vector<ll>r;
	r.resize(26);
	for (int i = 0; i < s.size(); i++)r[s[i] - 'a'] += a / s.size();
	for (int i = 0; i < a%s.size(); i++)r[s[i] - 'a']++;
	return r;
}
vector<ll>fib[1000];
ll len[1000];
vector<ll>get2(ll a, string x, string y)
{
	if (a <= x.size() + y.size())
	{
		vector<ll>r;
		r.resize(26);
		for (int i = 0; i < min(a, (ll)(x.size())); i++)r[x[i] - 'a']++;
		for (int i = x.size(); i < a; i++)r[y[i - x.size()] - 'a']++;
		return r;
	}
	int rr;
	for (int i = 0;; i++)
	{
		if (len[i] <= a)rr = i;
		else break;
	}
	vector<ll>r = fib[rr];
	vector<ll>s = get2(a - len[rr], x, y);
	for (int i = 0; i < 26; i++)r[i] += s[i];
	return r;
}
int main()
{
	string zs;
	cin >> zs;
	ll lb, ub;
	scanf("%lld%lld", &lb, &ub);
	string s;
	for (int i = 0; i < zs.size() / 2; i++)s.push_back(zs[i]);
	vector<int>v = zalgo(s);
	int rr = -1;
	for (int i = 1; i < v.size(); i++)
	{
		if (v[i] == s.size() - i)
		{
			rr = i;
			break;
		}
	}
	if (rr == -1 || s.size() % rr == 0)
	{
		vector<ll>a = get1(ub, s), b = get1(lb - 1, s);
		for (int i = 0; i < 26; i++)printf("%lld ", a[i] - b[i]);
		printf("\n");
	}
	else
	{
		string x, y;
		for (int i = 0; i < rr; i++)x.push_back(s[i]);
		for (int i = rr; i < s.size(); i++)y.push_back(s[i]);
		for (int i = 0; i < 200; i++)fib[i].resize(26);
		for (int i = 0; i < x.size(); i++)fib[0][x[i] - 'a']++, fib[1][x[i] - 'a'] += 2;
		for (int i = 0; i < y.size(); i++)fib[0][y[i] - 'a']++, fib[1][y[i] - 'a']++;
		for (int i = 2; i < 200; i++)for (int j = 0; j < 26; j++)fib[i][j] = fib[i - 1][j] + fib[i - 2][j];
		len[0] = x.size() + y.size(), len[1] = x.size() + y.size() + x.size();
		for (int i = 2; i < 200; i++)len[i] = len[i - 1] + len[i - 2];
		vector<ll>a = get2(ub, x, y), b = get2(lb - 1, x, y);
		for (int i = 0; i < 26; i++)printf("%lld ", a[i] - b[i]);
		printf("\n");
	}
}