#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string T, P;

    cin >> T >> P;

    uint64_t ht = 0, hp = 0, b = 1;
    for (uint32_t i = 0; i < P.length(); i++) {
        ht = (ht << 7) + T[i];
        hp = (hp << 7) + P[i];
        b = b << 7;
    }

    for (int32_t i = 0; i <= (int32_t)(T.length() - P.length()); i++) {
        if (ht == hp) if (T.substr(i, P.length()) == P) printf("%d\n", i);
        ht = (ht << 7) + T[i+P.length()] - b * T[i];
    }

    return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string T, P;

    cin >> T >> P;

    uint64_t ht = 0, hp = 0, b = 1;
    for (uint32_t i = 0; i < P.length(); i++) {
        ht = (ht << 7) + T[i];
        hp = (hp << 7) + P[i];
        b = b << 7;
    }

    for (int32_t i = 0; i <= (int32_t)(T.length() - P.length()); i++) {
        if (ht == hp) if (T.substr(i, P.length()) == P) printf("%d\n", i);
        ht = (ht << 7) + T[i+P.length()] - b * T[i];
    }

    return 0;
}
```