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;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef pair<int, int> P;

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  string t, p;
  cin >> t >> p;

  int ts = t.size();
  int ps = p.size();
  vector<int> a(ps+1);
  int j = a[0] = -1;
  rep(i,ps) {
    while (j >= 0 && p[i] != p[j]) j = a[j];
    ++j;
    if (p[i+1] == p[j])
      a[i+1] = a[j];
    else 
      a[i+1] = j;
  }

  vector<int> ans;
  int pi = 0;
  rep(ti,ts) {
    while (pi > -1 && p[pi] != t[ti])
      pi = a[pi];
    pi++;
    if (pi >= ps) {
      ans.push_back(ti - pi + 1);
      pi = a[pi];
    }
  }

  for (auto a : ans) cout << a << endl;

  return 0;
}

