#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; (i) < (n); ++ (i))
#define loop(i,a,n) for (int i = (a); (i) < (n); ++ (i))
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 0
//#define int ll
using namespace std;

typedef vector<int> vi;
typedef unsigned long long ull;

signed main(){
    string T,P;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> T >> P;
    ull nhash=0;
    ull _b=1000000007;
    for(int i=0;i<(int)P.size();i++){
        nhash=(nhash+P[i])*_b;
    }
    vector<ull> hash,pow;
    int sz = T.length();
    hash.assign(sz+1,0);
    pow.assign(sz+1,0);
    pow[0]=1;
    for(int i=0;i<sz;i++){
        pow[i+1]=pow[i]*_b;
    }
    for(int i=0;i<sz;i++){
        hash[i+1]=(hash[i]+T[i])*_b;
    }
    rep(i,(int)T.size()-(int)P.size()+1) {
        if((hash[i+(int)P.size()]-hash[i]*pow[(int)P.size()]) == nhash) {
            cout << 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 <bits/stdc++.h>
#define rep(i,n) for (int i = 0; (i) < (n); ++ (i))
#define loop(i,a,n) for (int i = (a); (i) < (n); ++ (i))
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 0
//#define int ll
using namespace std;

typedef vector<int> vi;
typedef unsigned long long ull;

signed main(){
    string T,P;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> T >> P;
    ull nhash=0;
    ull _b=1000000007;
    for(int i=0;i<(int)P.size();i++){
        nhash=(nhash+P[i])*_b;
    }
    vector<ull> hash,pow;
    int sz = T.length();
    hash.assign(sz+1,0);
    pow.assign(sz+1,0);
    pow[0]=1;
    for(int i=0;i<sz;i++){
        pow[i+1]=pow[i]*_b;
    }
    for(int i=0;i<sz;i++){
        hash[i+1]=(hash[i]+T[i])*_b;
    }
    rep(i,(int)T.size()-(int)P.size()+1) {
        if((hash[i+(int)P.size()]-hash[i]*pow[(int)P.size()]) == nhash) {
            cout << i << endl;
        }
    }
}

```