#include<bits/stdc++.h>
using namespace std;
using UL=unsigned int;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

int main(){
 string S,T; cin>>S>>T;
 vector<UL> AM(T.size()+1); AM[0]=~0u;
 UL q = ~0u;
 rep(p,T.size()){
  while(q!=~0u){ if(T[p]==T[q]) break; else q=AM[q]; }
  AM[p+1] = ++q;
 }
 vector<UL> X(S.size());
 q = 0;
 rep(p,S.size()){
  while(q!=~0u){ if(S[p]==T[q]) break; else q=AM[q]; }
  X[p] = ++q;
  if(q==T.size()){ printf("%u\n",p-q+1); q=AM[q]; }
 }
 return 0;
}


### Prompt

Please create a solution in Cpp 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;
using UL=unsigned int;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

int main(){
 string S,T; cin>>S>>T;
 vector<UL> AM(T.size()+1); AM[0]=~0u;
 UL q = ~0u;
 rep(p,T.size()){
  while(q!=~0u){ if(T[p]==T[q]) break; else q=AM[q]; }
  AM[p+1] = ++q;
 }
 vector<UL> X(S.size());
 q = 0;
 rep(p,S.size()){
  while(q!=~0u){ if(S[p]==T[q]) break; else q=AM[q]; }
  X[p] = ++q;
  if(q==T.size()){ printf("%u\n",p-q+1); q=AM[q]; }
 }
 return 0;
}


```