#include <iostream>
#include <vector>
#include <string>

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

struct RollingHash{
    i64 m1 = 1000000007, m2 = 1000000009;
    i64 b1 = 1009, b2 = 1007;
    vector<i64> h1, h2, p1, p2;
    RollingHash(string s){
        i64 n = s.length();
        h1.resize(n + 1); h2.resize(n + 1); p1.resize(n + 1); p2.resize(n + 1);
        h1[0] = s[0] % m1;
        h2[0] = s[0] % m2;
        p1[0] = p2[0] = 1;
        for(int i = 0; i < n; ++i){
            h1[i + 1] = (h1[i] * b1 % m1 + s[i]) % m1;
            h2[i + 1] = (h2[i] * b2 % m2 + s[i]) % m2;
            p1[i + 1] = p1[i] * b1 % m1;
            p2[i + 1] = p2[i] * b2 % m2;
        }
    };
    P get(i64 l, i64 r){
        i64 hash1 = (h1[r] + m1 - h1[l] * p1[r - l] % m1) % m1;
        i64 hash2 = (h2[r] + m2 - h2[l] * p2[r - l] % m2) % m2;
        return P(hash1, hash2);
    };
};

int main(){
    string t, p;
    cin >> t >> p;
    if(t.length() < p.length()) return 0;
    RollingHash ht(t), hp(p);
    for(int i = 0; i + p.length() <= t.length(); ++i){
        if(ht.get(i, i + p.length()) == hp.get(0, p.length())) cout << i << endl;
    }
}

### Prompt

Create a solution in CPP for 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 <iostream>
#include <vector>
#include <string>

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

struct RollingHash{
    i64 m1 = 1000000007, m2 = 1000000009;
    i64 b1 = 1009, b2 = 1007;
    vector<i64> h1, h2, p1, p2;
    RollingHash(string s){
        i64 n = s.length();
        h1.resize(n + 1); h2.resize(n + 1); p1.resize(n + 1); p2.resize(n + 1);
        h1[0] = s[0] % m1;
        h2[0] = s[0] % m2;
        p1[0] = p2[0] = 1;
        for(int i = 0; i < n; ++i){
            h1[i + 1] = (h1[i] * b1 % m1 + s[i]) % m1;
            h2[i + 1] = (h2[i] * b2 % m2 + s[i]) % m2;
            p1[i + 1] = p1[i] * b1 % m1;
            p2[i + 1] = p2[i] * b2 % m2;
        }
    };
    P get(i64 l, i64 r){
        i64 hash1 = (h1[r] + m1 - h1[l] * p1[r - l] % m1) % m1;
        i64 hash2 = (h2[r] + m2 - h2[l] * p2[r - l] % m2) % m2;
        return P(hash1, hash2);
    };
};

int main(){
    string t, p;
    cin >> t >> p;
    if(t.length() < p.length()) return 0;
    RollingHash ht(t), hp(p);
    for(int i = 0; i + p.length() <= t.length(); ++i){
        if(ht.get(i, i + p.length()) == hp.get(0, p.length())) cout << i << endl;
    }
}

```