#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
#define M 9999991

typedef long long ll;

char S1[1000001],S2[10001];
int N,n;

int pow_mod_S(int n,char s){
    ll x = 1;
    ll m = 128;
    while (n > 0) {
        if (n&1) {
            x = (m*x)%M;
        }
        m = (m*m)%M;
        n >>= 1;
    }
    return (x*s)%M;
}

int make(char S[]){
    ll x = 0;
    for (int i = 0; i < n; i++) {
        x = (x + pow_mod_S(n-i-1,S[i]))%M;
    }
    return x;
}

void RollingHash(){
    ll ORG = make(S2);
    ll comp = make(S1);
    ll n_1 = pow_mod_S(n-1,1);
    
    if (comp == ORG) printf("0\n");
    
    for (int i = 0; i < N-n; i++) {
        comp = (comp + M - (n_1*S1[i])%M)%M;
        comp = (comp*128)%M;
        comp = (comp + S1[i+n])%M;
        
        if (comp == ORG) printf("%d\n",i+1);
    }
}

int main(){
    cin >> S1 >> S2;
    N = strlen(S1);
    n = strlen(S2);
    
    RollingHash();
    
    return 0;
}
### Prompt

Your task is to create 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<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
#define M 9999991

typedef long long ll;

char S1[1000001],S2[10001];
int N,n;

int pow_mod_S(int n,char s){
    ll x = 1;
    ll m = 128;
    while (n > 0) {
        if (n&1) {
            x = (m*x)%M;
        }
        m = (m*m)%M;
        n >>= 1;
    }
    return (x*s)%M;
}

int make(char S[]){
    ll x = 0;
    for (int i = 0; i < n; i++) {
        x = (x + pow_mod_S(n-i-1,S[i]))%M;
    }
    return x;
}

void RollingHash(){
    ll ORG = make(S2);
    ll comp = make(S1);
    ll n_1 = pow_mod_S(n-1,1);
    
    if (comp == ORG) printf("0\n");
    
    for (int i = 0; i < N-n; i++) {
        comp = (comp + M - (n_1*S1[i])%M)%M;
        comp = (comp*128)%M;
        comp = (comp + S1[i+n])%M;
        
        if (comp == ORG) printf("%d\n",i+1);
    }
}

int main(){
    cin >> S1 >> S2;
    N = strlen(S1);
    n = strlen(S2);
    
    RollingHash();
    
    return 0;
}
```