#include <bits/stdc++.h>
using namespace std;

vector<int> knuth_morris_pratt(const string &s){
    int n=s.size();
    //vector<int> kmp(n+1,-1),mp(n+1,-1);
    vector<int>kmp(n+1,-1);
    for(int i=0,j=-1;i<n;i++){
        while(~j&&s[i]!=s[j]) j=kmp[j];
        //kmp[i+1]=mp[i+1]=++j;
        j++;
        if(i+1<n&&s[i+1]==s[j]) kmp[i+1]=kmp[j];
        else kmp[i+1]=j;
    }
    //return mp;
    return kmp;
}
// smallest d s.t. s[x] == s[x + d] for all x
vector<int> minimum_period(const string &s){
    auto mp=knuth_morris_pratt(s);
    for(int i=1;i<(int)mp.size();i++) mp[i]=i-mp[i];
    return mp;
}
// positions for t that match s
vector<int> pattern_match(string s,string t){
    int n=s.size(),m=t.size();
    vector<int> kmp=knuth_morris_pratt(s);

    vector<int> res;
    int i=0,j=0;
    while(i+j<m){
        if(s[j]==t[i+j]){
            if(++j!=n) continue;
            res.emplace_back(i);
        }
        i+=j-kmp[j];
        j=max(kmp[j],0);
    }
    return res;
}

int main() {
    string s, t;
    cin >> s >> t;

    auto idxs = pattern_match(t, s);
    for (auto idx: idxs) cout << idx << endl;
}


### Prompt

In CPP, your task is to solve 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;

vector<int> knuth_morris_pratt(const string &s){
    int n=s.size();
    //vector<int> kmp(n+1,-1),mp(n+1,-1);
    vector<int>kmp(n+1,-1);
    for(int i=0,j=-1;i<n;i++){
        while(~j&&s[i]!=s[j]) j=kmp[j];
        //kmp[i+1]=mp[i+1]=++j;
        j++;
        if(i+1<n&&s[i+1]==s[j]) kmp[i+1]=kmp[j];
        else kmp[i+1]=j;
    }
    //return mp;
    return kmp;
}
// smallest d s.t. s[x] == s[x + d] for all x
vector<int> minimum_period(const string &s){
    auto mp=knuth_morris_pratt(s);
    for(int i=1;i<(int)mp.size();i++) mp[i]=i-mp[i];
    return mp;
}
// positions for t that match s
vector<int> pattern_match(string s,string t){
    int n=s.size(),m=t.size();
    vector<int> kmp=knuth_morris_pratt(s);

    vector<int> res;
    int i=0,j=0;
    while(i+j<m){
        if(s[j]==t[i+j]){
            if(++j!=n) continue;
            res.emplace_back(i);
        }
        i+=j-kmp[j];
        j=max(kmp[j],0);
    }
    return res;
}

int main() {
    string s, t;
    cin >> s >> t;

    auto idxs = pattern_match(t, s);
    for (auto idx: idxs) cout << idx << endl;
}


```