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
#ifdef BUILT_LOCAL

#include "niklib.h"

#endif

#include <iostream>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <list>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
constexpr ll mod = 1000000007;
constexpr ll base = 32984971;

long long dpow[10001];

long long mpow(int n) {
    if (n == 0)return 1;
    if (dpow[n] == 0) {
        dpow[n] = (mpow(n - 1) * base) % mod;
    }
    return dpow[n];
}

ll rh_b(ll c, char s) {
    return (c * base + s) % mod;
}

ll rh_f(ll c, char s, int len) {
    return ((c - (s * mpow(len - 1))) % mod + mod) % mod;
}

long long mhash(string s) {
    ll ret = 0;
    for (auto &e:s) {
        ret = rh_b(ret, e);
    }
    return ret;
}


int main() {
    string t, p;
    cin >> t >> p;
    ll v = mhash(p);
    int n = p.length(), m = t.length();
    ll u = mhash(t.substr(0, n));
    if (v == u) cout << 0 << '\n';
    for (int i = 0; i < m - n; i++) {
        u = rh_f(u, t[i], n);
        u = rh_b(u, t[i + n]);
        if (u == v)cout << i + 1 << '\n';
    }
}

