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 <string>
#include <cmath>
using namespace std;

//typedef unsigned long long ull;

void RabinCarp(string T, string P, int d){ 
    int n = T.size();
    int m = P.size();
    int h = 1;
    int p = 0;
    int t[n];
    t[0] = 0;
  
    for(int i=0; i<m-1; i++){
      h = h * d;
    }
    for(int i=0; i<m; i++){                                                                                                                              
        p = d*p + P[i];
        t[0] = d*t[0] + T[i];
    }

    for(int s=0; s<n-m+1; s++){
        if(p==t[s]) {
          cout << s << endl;
        }
        if(s<n-m){
            t[s+1]=d*(t[s]-T[s]*h) + T[s+m];
        }
    }
}

int main(){
    int d = 167;
    string T, P;
    cin>>T>>P;

    RabinCarp(T, P, d);

    return 0;
}
