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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    string t, s;
    cin >> s >> t;
    int nt = t.size(), ns = s.size();
    if(nt > ns) return 0;
    
    vi sen;
    rep(i, nt-1) {
        if(t.substr(i+1, nt-1-i) == t.substr(0, nt-1-i)) sen.push_back(i+1);
    }

    vi ans;
    rep(i, ns-nt+1) {
        if(s[i] == t[0]) {
            if(s.substr(i, nt) == t) {
                ans.push_back(i);
                while(true) {
                    bool x = false;
                    rep(j, sen.size()) {
                        if(i+nt+sen[j] > ns) break;
                        if(s.substr(i+nt, sen[j]) == t.substr(nt-sen[j], sen[j])) {
                            x = true;
                            i += sen[j];
                            ans.push_back(i);
                            break;
                        }
                    }
                    if(!x) break;
                }
                i += nt;
            }
        }
    }


    rep(i, ans.size()) {
        cout << ans[i] << '\n';
    }
}
