#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B = 1000000007ULL;

int main(){
  int N; // N is the size of string s
  string s,P;
  cin >> s >> P;
  N=s.size();
  vector<ull> p(N+1); // p is power (base B)
  vector<ull> hash(N+1); // hash values
  p[0] = 1; hash[0] = 0;
  for (int i = 0; i < N; i++) {
    hash[i+1] = hash[i]*B + s[i];
    p[i+1] = p[i]*B;
  }
  /*
    s?????¨????????????s[L,R]??????????????\????????\?????????????????????.
    hash[L,R] := hash[R+1]-hash[L]*p[R-L+1];
  */
  ull base=0,ans=0;
  for(int i=0;i<P.size();i++){
    base=base*B+P[i];
  }
  for(int i=0;i+P.size()<=N;i++){
    int L=i,R=i+P.size()-1;
    if(hash[R+1]-hash[L]*p[R-L+1]==base) cout<<i<<endl;
  }
  return 0;
}
### Prompt

Your challenge is to write a cpp solution to the following problem:

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<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B = 1000000007ULL;

int main(){
  int N; // N is the size of string s
  string s,P;
  cin >> s >> P;
  N=s.size();
  vector<ull> p(N+1); // p is power (base B)
  vector<ull> hash(N+1); // hash values
  p[0] = 1; hash[0] = 0;
  for (int i = 0; i < N; i++) {
    hash[i+1] = hash[i]*B + s[i];
    p[i+1] = p[i]*B;
  }
  /*
    s?????¨????????????s[L,R]??????????????\????????\?????????????????????.
    hash[L,R] := hash[R+1]-hash[L]*p[R-L+1];
  */
  ull base=0,ans=0;
  for(int i=0;i<P.size();i++){
    base=base*B+P[i];
  }
  for(int i=0;i+P.size()<=N;i++){
    int L=i,R=i+P.size()-1;
    if(hash[R+1]-hash[L]*p[R-L+1]==base) cout<<i<<endl;
  }
  return 0;
}
```