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 <cstdio>
#include <string>
#include <vector>

using namespace std;

const long long MOD=1e9+7;
const long long BASE=0x234567;

struct RollingHash {
    string s;
    long long mod, base;
    vector<long long> hash, pow;
    RollingHash() {}
    RollingHash(string s, long long m, long long b): s(s), mod(m), base(b) {
        pow.resize(s.length()+1); pow[0]=1;
        for (size_t i=0; i<s.length(); ++i)
            (pow[i+1] = pow[i]*base) %= mod;

        hash.assign(s.length()+1, 0);
        for (size_t i=0; i<s.length(); ++i)
            (hash[i+1] = hash[i]+pow[i]*s[i]) %= mod;
    }
    long long get_hash(size_t first, size_t last) {
        return (hash[last]-hash[first]+mod) % mod;
    }
    long long make_hash(string t) {
        long long h=0;
        for (size_t i=0; i<t.length(); ++i)
            (h += pow[i]*t[i]) %= mod;

        return h;
    }
    long long diff(long long h, size_t pos, size_t len) {
        return (h*pow[pos]-get_hash(pos, pos+len))%mod;
    }
    bool is_equiv(long long h, size_t pos, size_t len) {
        return !diff(h, pos, len);
    }
};

int main() {
    char buf[1<<20];
    scanf("%s", buf);
    string T(buf);

    RollingHash rhash(T, MOD, BASE);

    scanf("%s", buf);
    string P(buf);

    long long h=rhash.make_hash(P);
    for (size_t i=0; i+P.length()<=T.length(); ++i)
        if (rhash.is_equiv(h, i, P.length()))
            printf("%zd\n", i);

    return 0;
}