#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
long long B = 1717171;
int main(){
        string t,p;
        cin>>t>>p;
        long long hash[t.size()+1];
        long long pow[t.size()+1];
        hash[0]=0;
        pow[0]=1;
        for(int i=0;i<t.size();i++){
                hash[i+1] = hash[i]*B + t[i];
                pow[i+1] = pow[i]*B;
        }
        long long base=0, ans=0;
        for(int i=0;i<p.size();i++) base = base*B+p[i];

        for(int i=0;i+p.size()<=t.size();i++){
                int left=i, right=i+p.size()-1;
                if(hash[right+1]-hash[left]*pow[right-left+1]==base) printf("%d\n", i);
        }
        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<iostream>
#include<cstdio>
#include<string>
using namespace std;
long long B = 1717171;
int main(){
        string t,p;
        cin>>t>>p;
        long long hash[t.size()+1];
        long long pow[t.size()+1];
        hash[0]=0;
        pow[0]=1;
        for(int i=0;i<t.size();i++){
                hash[i+1] = hash[i]*B + t[i];
                pow[i+1] = pow[i]*B;
        }
        long long base=0, ans=0;
        for(int i=0;i<p.size();i++) base = base*B+p[i];

        for(int i=0;i+p.size()<=t.size();i++){
                int left=i, right=i+p.size()-1;
                if(hash[right+1]-hash[left]*pow[right-left+1]==base) printf("%d\n", i);
        }
        return 0;
}

```