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;

const int MAX = 1000010;
int tbl[MAX];

void intialize(const string &str)
{
  int n = str.size();

  tbl[0] = -1;
  int j = -1;
  for (int i = 0; i < n; i++) {
    while (j >= 0 && str[i] != str[j])
      j = tbl[j];
    tbl[i+1] = ++j;
  }

  // for (int i = 0; i <= n; i++)
  // printf("tbl[%d] = %d\n", i, tbl[i]);
}

void kmp(const string &str, const string &ptn)
{
  intialize(ptn);
  int m = 0, i = 0, n = str.size();

  while (m+i < n) {
    if (ptn[i] == str[m+i]) {
      if (++i == ptn.size()) {
        cout << m << endl;
        m += i - tbl[i];
        i = tbl[i];
      }
    } else {
      m += i - tbl[i];
      i = (i==0?0:tbl[i]);
    }
  }
}

int main()
{
  string s1, s2;

  cin >> s1 >> s2;
  kmp(s1, s2);

  return EXIT_SUCCESS;
}


