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;

typedef unsigned long long ull;

int main()
{
  string t, p;
  ull data = 0, hash = 0;
  ull b = 10007, mul = 1;

  cin >> t >> p;
  
  if(t.size() < p.size()) return (0);
  
  for(int i = p.size() - 1; i >= 0; i--) {
    data += mul * t[i];
    hash += mul * p[i];
    mul *= b;
  }
  
  if(data == hash) cout << 0 << endl;
  
  for(int i = 0; i < t.size() - p.size(); i++) {
    data = data * b - t[i] * mul + t[i + p.size()];
    if(data == hash) cout << i + 1 << endl;
  }
  
  return (0);
}
  