#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    string s; cin >> s;
    string t; cin >> t;
    int n = s.size();
    int m = t.size();

    vector<int> ans;
    rep(i,n - m + 1){
        int ans_ = s.find(t, i);
        if(ans_ == std::string::npos){
            i = n;
        }else{
            ans.push_back(ans_);
            i = ans_;
        }
    }

    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    
    return 0;
}
 
 


### Prompt

Create a solution in cpp for 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>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    string s; cin >> s;
    string t; cin >> t;
    int n = s.size();
    int m = t.size();

    vector<int> ans;
    rep(i,n - m + 1){
        int ans_ = s.find(t, i);
        if(ans_ == std::string::npos){
            i = n;
        }else{
            ans.push_back(ans_);
            i = ans_;
        }
    }

    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    
    return 0;
}
 
 


```