#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
const ll B=1e6+7;
const ll mod=1e9+7,mod2=998244353,mod3=1e11+7;
ll t_mod(ll x,ll m){
  if(x>=0) return x%m;
  else{
    ll x2=x*(-1);
    x2/=m;
    x2+=2;
    return (x+m*x2)%m;
  }
}
vector<int> contain(string b,string a){
  int al=a.length(),bl=b.length();

  ll t=1,t2=1,t3=1;
  for(int i=0;i<al;i++) {
    t*=B;
    t%=mod;
    t2*=B;
    t2%=mod2;
    t3*=B;
    t3%=mod3;
  }

  ll ah=0,bh=0,ah2=0,bh2=0,ah3=0,bh3=0;
  for(int i=0;i<al;i++) {
    ah=(ah*B)%mod+a[i];
    ah%=mod;
    ah2=(ah2*B)%mod2+a[i];
    ah2%=mod2;
    ah3=(ah3*B)%mod3+a[i];
    ah3%=mod3;
  }
  for(int i=0;i<al;i++) {
    bh=(bh*B)%mod+b[i];
    bh%=mod;
    bh2=(bh2*B)%mod2+b[i];
    bh2%=mod2;
    bh3=(bh3*B)%mod3+b[i];
    bh3%=mod3;
  }

  vector<int> ret;
  for(int i=0;i+al<=bl;i++){
    if(ah==bh&&ah2==bh2&&ah3==bh3) {
      ret.push_back(i);
    }
    if(i+al<bl){
      bh=(bh*B)%mod+b[i+al]-b[i]*t;
      bh=t_mod(bh,mod);
      bh2=(bh2*B)%mod2+b[i+al]-b[i]*t2;
      bh2=t_mod(bh2,mod2);
      bh3=(bh3*B)%mod3+b[i+al]-b[i]*t3;
      bh3=t_mod(bh3,mod3);
    }
  }
  return ret;
}
int main(){
  string a,b;
  cin>>a>>b;
  if(a.length()<b.length()) return 0;
  vector<int> ans=contain(a,b);
  for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}


### Prompt

Please provide a cpp coded solution to the problem described below:

Find places where a string P is found within a text T. Print all indices of T where P found. The indices of T start with 0.

Constraints

* 1 ≤ length of T ≤ 1000000
* 1 ≤ length of P ≤ 10000
* The input consists of alphabetical characters and digits

Input

In the first line, a text T is given. In the second line, a string P is given.

Output

Print an index of T where P found in a line. Print the indices in ascending order.

Examples

Input

aabaaa
aa


Output

0
3
4


Input

xyzz
yz


Output

1


Input

abc
xyz


Output

### Response

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
const ll B=1e6+7;
const ll mod=1e9+7,mod2=998244353,mod3=1e11+7;
ll t_mod(ll x,ll m){
  if(x>=0) return x%m;
  else{
    ll x2=x*(-1);
    x2/=m;
    x2+=2;
    return (x+m*x2)%m;
  }
}
vector<int> contain(string b,string a){
  int al=a.length(),bl=b.length();

  ll t=1,t2=1,t3=1;
  for(int i=0;i<al;i++) {
    t*=B;
    t%=mod;
    t2*=B;
    t2%=mod2;
    t3*=B;
    t3%=mod3;
  }

  ll ah=0,bh=0,ah2=0,bh2=0,ah3=0,bh3=0;
  for(int i=0;i<al;i++) {
    ah=(ah*B)%mod+a[i];
    ah%=mod;
    ah2=(ah2*B)%mod2+a[i];
    ah2%=mod2;
    ah3=(ah3*B)%mod3+a[i];
    ah3%=mod3;
  }
  for(int i=0;i<al;i++) {
    bh=(bh*B)%mod+b[i];
    bh%=mod;
    bh2=(bh2*B)%mod2+b[i];
    bh2%=mod2;
    bh3=(bh3*B)%mod3+b[i];
    bh3%=mod3;
  }

  vector<int> ret;
  for(int i=0;i+al<=bl;i++){
    if(ah==bh&&ah2==bh2&&ah3==bh3) {
      ret.push_back(i);
    }
    if(i+al<bl){
      bh=(bh*B)%mod+b[i+al]-b[i]*t;
      bh=t_mod(bh,mod);
      bh2=(bh2*B)%mod2+b[i+al]-b[i]*t2;
      bh2=t_mod(bh2,mod2);
      bh3=(bh3*B)%mod3+b[i+al]-b[i]*t3;
      bh3=t_mod(bh3,mod3);
    }
  }
  return ret;
}
int main(){
  string a,b;
  cin>>a>>b;
  if(a.length()<b.length()) return 0;
  vector<int> ans=contain(a,b);
  for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}


```