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;
using Int = long long;

vector<Int> zalgorithm(string s){
  Int n=s.size();
  vector<Int> a(n,0);
  a[0]=n;
  Int i=1,j=0;
  while(i<n){
    while(i+j<n&&s[j]==s[i+j]) j++;
    a[i]=j;
    if(j==0){
      i++;
      continue;
    }
    Int k=1;
    while(i+k<n&&k+a[k]<j) a[i+k]=a[k],k++;
    i+=k;
    j-=k;
  }
  return a;
}

//INSERT ABOVE HERE
using vint = vector<Int>;
void print(const vint &v){
  for(Int i=0;i<(Int)v.size();i++){
    if(i) cout<<" ";
    cout<<v[i];
  }
  cout<<endl;
}

vint add(const vint &a,const vint &b){
  vint c(26,0);
  for(Int i=0;i<26;i++) c[i]=a[i]+b[i];
  return c;
}
vint sub(const vint &a,const vint &b){
  vint c(26,0);
  for(Int i=0;i<26;i++) c[i]=a[i]-b[i];
  return c;
}

signed main(){
  string s;
  cin>>s;
  Int l,r;
  cin>>l>>r;
  l--;
  {
    string t(s);
    t.erase(unique(t.begin(),t.end()),t.end());
    if(t.size()==1u){
      vint ans(26,0);
      ans[t[0]-'a']=r-l;
      print(ans);
      return 0;
    }
  }
  
  Int n=s.size(),k=n/2+1;
  vector<Int> z=zalgorithm(s);
  while(k<n&&k+z[k]<n) k++;
  if(k==n){
    s=s+s;
    z=zalgorithm(s);
    k=n+1;
    n=n+n;
    while(k<n&&k+z[k]<n) k++;
  }
  
  vector<Int> x;
  x.emplace_back(n);
  x.emplace_back((n-z[k])*2);
  //cout<<n<<":"<<k<<":"<<z[k]<<endl;
  for(Int i=0;x.back()<=r;i++)
    x.emplace_back(Int(x[i]+x[i+1]));

  vector<vint> a(n+1,vint(26,0));
  for(Int i=0;i<n;i++)
    for(Int j=0;j<26;j++)
      a[i+1][j]=a[i][j]+(s[i]=='a'+j);
  
  using P = pair<Int, Int>;
  map<P, vint> dp;
  function<vint(Int, Int)> dfs=
    [&](Int l,Int r){
      //cout<<l<<" "<<r<<":"<<endl;
      //if(dp.count(P(l,r))) print(dp[P(l,r)]);
      if(dp.count(P(l,r))) return dp[P(l,r)];
      vint &res=dp[P(l,r)];
      if(r<=n) return res=sub(a[r],a[l]);
      Int p=0;
      while(r>x[p]) p++;
      Int y=x[p]/2;
      if(y<=l) return res=dfs(l-y,r-y);
      return res=add(dfs(l,y),dfs(0,r-y));
    };
  
  print(dfs(l,r));
  return 0;
}