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 <bits/stdc++.h>

using namespace std;

int main()
{
  string T[2];
  cin >> T[0] >> T[1];
  
  typedef unsigned int int_type;
  const int_type base = 9973;

  vector<int_type> hashed[2], power[2];  

  for(int i = 0; i < 2; i++){
    int sz = T[i].size();
    hashed[i].assign(sz + 1, 0);
    power[i].assign(sz + 1, 0);
          
    hashed[i][0] = 0;
    power[i][0] = 1;
    for(int j = 0; j < sz; j++){
      power[i][j+1] = power[i][j] * base;
      hashed[i][j+1] = (hashed[i][j]+T[i][j])*base;
    }
  }

  for(int i = 0; i <= (int)(T[0].size()-T[1].size()); i++){
    if(hashed[0][i+T[1].size()] - hashed[0][i]*power[0][T[1].size()] == 
       hashed[1][T[1].size()] - hashed[1][0]*power[0][T[1].size()]){
      printf("%d\n", i);
    }
  }

  return 0;
}