#include<iostream>
using namespace std;
#include<string>
#include<stdio.h>

#define A 1995455101 // large prime number.
#define B 1995455447 // large prime number, bigger than A.

int main()
{
    string T; cin >> T; int len_T = T.size();
    string P; cin >> P; int len_P = P.size();
    long long *has_T, *has_P;
    has_T = new long long [len_T];
    has_P = new long long [len_P];

    long long h = 0; int i;  // hash coding.
    // has_T[i] = (T[0]A^{i-1} + T[1]A^{i-2} + ... + T[i-1]A + T[i]) % B.
    for(i = 0; i < len_T; i++){ h = (h * A + T[i]) % B; has_T[i] = h; }
    h = 0;
    // has_P[i] = (P[0]A^{i-1} + P[1]A^{i-2} + ... + P[i-1]A + P[i]) % B.
    for(i = 0; i < len_P; i++){ h = (h * A + P[i]) % B; has_P[i] = h; }

    // last_has = (P[0]A^{len_P-1} + P[1]A^{len_P-2} + ... + P[len_P-1]) % B.
    long long last_has = has_P[len_P - 1];
    // A^{len_P} Mod B.
    long long power, x, y, z;
    x = A, y = len_P, z = 1;
    for( ; y; y /= 2){
        if((y & 1) != 0){ z = (z * x) % B; }
        x = (x * x) % B;
    }
    power = z;

    for(i = len_P - 1; i < len_T; i++){
        if(has_T[i] == ((i >= len_P ? has_T[i - len_P] : 0) * power + last_has) % B){
			printf("%d\n", i - len_P + 1);
        }
    }
    return 0;
}
### Prompt

Develop a solution in Cpp 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;
#include<string>
#include<stdio.h>

#define A 1995455101 // large prime number.
#define B 1995455447 // large prime number, bigger than A.

int main()
{
    string T; cin >> T; int len_T = T.size();
    string P; cin >> P; int len_P = P.size();
    long long *has_T, *has_P;
    has_T = new long long [len_T];
    has_P = new long long [len_P];

    long long h = 0; int i;  // hash coding.
    // has_T[i] = (T[0]A^{i-1} + T[1]A^{i-2} + ... + T[i-1]A + T[i]) % B.
    for(i = 0; i < len_T; i++){ h = (h * A + T[i]) % B; has_T[i] = h; }
    h = 0;
    // has_P[i] = (P[0]A^{i-1} + P[1]A^{i-2} + ... + P[i-1]A + P[i]) % B.
    for(i = 0; i < len_P; i++){ h = (h * A + P[i]) % B; has_P[i] = h; }

    // last_has = (P[0]A^{len_P-1} + P[1]A^{len_P-2} + ... + P[len_P-1]) % B.
    long long last_has = has_P[len_P - 1];
    // A^{len_P} Mod B.
    long long power, x, y, z;
    x = A, y = len_P, z = 1;
    for( ; y; y /= 2){
        if((y & 1) != 0){ z = (z * x) % B; }
        x = (x * x) % B;
    }
    power = z;

    for(i = len_P - 1; i < len_T; i++){
        if(has_T[i] == ((i >= len_P ? has_T[i - len_P] : 0) * power + last_has) % B){
			printf("%d\n", i - len_P + 1);
        }
    }
    return 0;
}
```