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 pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

vector<int> pre_kmp(const string& pat) {
	int k;
	vector<int> table((int)pat.size() + 1);
	table[0] = -1;

	for (int i = 1; i <= pat.size(); ++i) {
		k = table[i-1];

		while (k >= 0) {
			if (pat[k] == pat[i-1]) break;
			else k = table[k];
		}

		table[i] = k + 1;
	}

	return table;
}

vector<ll> len;
vector<vector<ll>> num;

vector<ll> calc(ll t, string &S) {
	vector<ll> cnt(26);
	if (t == 0) return cnt;
	for (int i = (int)len.size()-1; i >= 0; --i) {
		if (len[i] <= t) {
			rep(c, 26) cnt[c] += num[i][c];
			t -= len[i];
		}
	}
	if (t > 0) rep(i, t) cnt[S[i] - 'a']++;
	return cnt;
}

int main() {
	string S; ll L, R;
	cin >> S >> L >> R;

	int N = S.size() / 2;

	vi vec = pre_kmp(S);
	int cyc = N - vec[N];

	len.pb(N);
	vector<ll> c0(26);
	rep(i, N) ++c0[S[i] - 'a'];

	num.pb(c0);

	len.pb(N + cyc);
	rep(i, cyc) ++c0[S[i]-'a'];
	num.pb(c0);

	for (int i = 2; ; ++i) {
		ll nl = len[i-2] + len[i-1];
		if (nl > R) break;
		len.pb(nl);
		vector<ll> nx(26);
		rep(c, 26) nx[c] = num[i-1][c] + num[i-2][c];
		num.pb(nx);
	}

	auto vl = calc(L-1, S), vr = calc(R, S);
	rep(i, 26) printf("%lld%c", vr[i] - vl[i], i == 25 ? '\n' : ' ');

	return 0;
}