#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;

template <typename T> inline bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> inline bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

vector<int> rollingHash(const string &s, const string &key) {
    using u64 = unsigned long long;
    u64 m = mod;
    int sl = s.size(), kl = key.size();
    vector<int> ret;
    u64 t = 1;
    u64 sh = 0, kh = 0;
    rep(i, kl) {
        t *= m;
        sh = sh * m + s[i];
        kh = kh * m + key[i];
    }
    rep(i, sl - kl + 1) {
        if(kh == sh) ret.push_back(i);
        if(i + kl < sl) sh = sh * m + s[i + kl] - s[i] * t;
    }
    return ret;
}

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

    string s, key;
    cin >> s >> key;
    vector<int> ret = rollingHash(s, key);
    rep(i, ret.size()) cout << ret[i] << endl;
}

### Prompt

Generate a CPP solution to 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>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;

template <typename T> inline bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> inline bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

vector<int> rollingHash(const string &s, const string &key) {
    using u64 = unsigned long long;
    u64 m = mod;
    int sl = s.size(), kl = key.size();
    vector<int> ret;
    u64 t = 1;
    u64 sh = 0, kh = 0;
    rep(i, kl) {
        t *= m;
        sh = sh * m + s[i];
        kh = kh * m + key[i];
    }
    rep(i, sl - kl + 1) {
        if(kh == sh) ret.push_back(i);
        if(i + kl < sl) sh = sh * m + s[i + kl] - s[i] * t;
    }
    return ret;
}

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

    string s, key;
    cin >> s >> key;
    vector<int> ret = rollingHash(s, key);
    rep(i, ret.size()) cout << ret[i] << endl;
}

```