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
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define M0 1599937
#define M1 1599977

typedef long long ll;
ll mh_[2];
char S1[1000001];
char S2[10001];
int n,N;

ll mod_pow_s(ll m, int n, ll mod, char s){//
    ll x = 1;
    while (n > 0) {
        if (n&1) {
            x = (x*m)%mod;
        }
        m = (m*m)%mod;
        n >>= 1;
    }
    x = (x*s)%mod;
    return x;
}

ll makeMH(char S[],int n, ll m){//
    ll mh = 0;
    for (int i = 1; i <= n; i++) {
        mh = (mh + mod_pow_s(128,n-i,m,S[i-1]) )%m;
    }
    return mh;
}

bool CHECK(ll o[], ll s[]){//
    if (o[0] == s[0] && o[1] == s[1]) {
        return true;
    }else{
        return false;
    }
}

ll moding(ll h,ll m, int i){//
    h = (h - mod_pow_s(128,n-1,m,S1[i]) + m)%m;
    h = (h*128)%m;
    h = (h + S1[n+i])%m;
    return h;
}

void rolling(int N, int n){
    ll ORG[2];
    ORG[0] = makeMH(S2,n,M0);
    ORG[1] = makeMH(S2,n,M1);
    
    mh_[0] = makeMH(S1,n,M0);
    mh_[1] = makeMH(S1,n,M1);
    
    if(CHECK(ORG,mh_)){
        printf("0\n");
    }
    
    for (int i = 0; i < N - n; i++) {
        mh_[0] = moding(mh_[0],M0,i);
        mh_[1] = moding(mh_[1],M1,i);
        if (CHECK(ORG,mh_)) {
            printf("%d\n",i+1);
        }
    }
}

int main(){
    cin >> S1 >> S2;
    N = strlen(S1);
    n = strlen(S2);

    rolling(N,n);
    
    return 0;
}