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<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
string s;
in pd;
in n;
VI ssz;
VI cnt;
in aps(char c, in r){
  if(n%pd==0){
    in cr=0;
    forn(i,pd)
      cr+=(s[i]==c);
    in to=0;
    forn(i,r%pd)
      to+=(s[i]==c);
    return (r/pd)*cr+to;
  }
  ssz.clear();
  cnt.clear();
  ssz.PB(pd);
  ssz.PB(n);
  in cr=0;
  forn(i,pd)
    cr+=(s[i]==c);
  cnt.PB(cr);
  for(in i=pd;i<n;++i)
    cr+=(s[i]==c);
  cnt.PB(cr);
  while(ssz.back()<=r){
    ssz.PB(ssz[sz(ssz)-1]+ssz[sz(ssz)-2]);
    cnt.PB(cnt[sz(cnt)-1]+cnt[sz(cnt)-2]);
  }
  in sm=0;
  in nxt=sz(ssz)-1;
  while(nxt>=0){
    if(r>=ssz[nxt]){
      sm+=cnt[nxt];
      r-=ssz[nxt];
    }
    --nxt;
  }
  forn(i,r)
    sm+=(s[i]==c);
  return sm;
}
VI genpref(string& p){
  if(sz(p)==0){
    return {};
  }
  if(sz(p)==1){
    return {1};
  }
  VI mmc;
  in rms=1;
  in rsz=0;
  while(rsz<sz(p)-rms && p[rsz+rms]==p[rsz])
    ++rsz;
  mmc.resize(sz(p));
  mmc[0]=sz(p);
  mmc[1]=rsz;
  for(in i=2;i<sz(p);i++){
    mmc[i]=0;
    if(i<rms+rsz){
      mmc[i]=mmc[i-rms];
      if(mmc[i]+i>=rms+rsz)
	mmc[i]=rms+rsz-i;
    }
    if(i+mmc[i]>=rms+rsz){
      rms=i;
      rsz=mmc[i];
      while(rsz<sz(p)-rms && p[rsz+rms]==p[rsz])
	++rsz;
      mmc[i]=rsz;
    }
  }
  return mmc;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>s;
  s.resize(sz(s)/2);
  n=sz(s);
  VI v=genpref(s);
  pd=n;
  for(in i=1;i<n;++i){
    if(v[i]==n-i){
      pd=i;
      break;
    }
  }
  in l,r;
  cin>>l>>r;
  for(char c='a';c<='z';++c){
    cout<<aps(c,r)-aps(c,l-1)<<" ";
  }
  cout<<endl;
  return 0;
}