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
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

ll polyhash(string S, ll x, ll p) {
    int slen = S.size();
    ll hash = 0;
    for (int i = slen - 1; i >= 0; i--) {
        hash = (hash * x + (ll)S[i]) % p;
    }
    return hash;
}

void preComputeHashes(string S, ll x, ll p, int len, vector<ll>& res) {
    int slen = S.size();
    string sub = S.substr(slen - len, len);
    res[res.size() - 1] = polyhash(sub, x, p);
    ll y = 1;
    rep(i, len) y = (y * x) % p;

    for (int i = slen - len - 1; i >= 0; i--) {
        res[i] = (((x * res[i + 1] + S[i] - y * S[i + len]) % p) + p) % p;
    }
}

void findSubStr(string S, string P, vector<int>& res) {
    ll p = 1000000009;
    ll x = 263;
    ll phash = polyhash(P, x, p);
    int slen = S.size();
    int plen = P.size();
    vector<ll> thashes(slen - plen + 1);
    preComputeHashes(S, x, p, plen, thashes);

    rep(i, slen - plen + 1) {
        if (phash == thashes[i]) res.push_back(i);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string T, P;
    cin>>T>>P;
    vector<int> res;
    if (T.size() >= P.size()) {
        findSubStr(T, P, res);
    }
    rep(i, res.size()) cout<<res[i]<<endl;
}
