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
/*input
aabaaa
aa
*/
#include <iostream>

  void computeLPSArray(std::string * pattern, int M, int * lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
      if ((*pattern)[i] == (*pattern)[len]) {
        len++;
        lps[i] = len;
        i++;
      } else {
        if (len != 0) {
          len = lps[len - 1];
        } else {
          lps[i] = 0;
          i++;
        }
      }
    }
  }

void KMPSearch(std::string *pattern, std::string *string) {
  int M = pattern->length();
  int N = string->length();
  int lps[M];
  computeLPSArray(pattern, M, lps);
  int i = 0;
  int j = 0;
  while (i < N) {
    if ((*pattern)[j] == (*string)[i]) {
      j++;
      i++;
    }
    if (j == M) {
      std::cout << i - j << std::endl;
      j = lps[j - 1];
    }

    else if (i < N && (*pattern)[j] != (*string)[i]) {
      if (j != 0)
        j = lps[j - 1];
      else
        i = i + 1;
    }
  }
}

int main() {
  std::string pattern, string;
  getline(std::cin, string);
  getline(std::cin, pattern);
  KMPSearch(&pattern, &string);
  return 0;
}
