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
// ALDS1_14_A/B: String search (DFA)

import java.io.PrintWriter;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    char[] T = sc.next().toCharArray();
    char[] P = sc.next().toCharArray();
    PrintWriter pw = new PrintWriter(System.out);

    // preprocess
    int[] pi = new int[P.length + 1];
    pi[0] = -1;
    int k = -1;
    for (int i = 1; i <= P.length; ++i) {
      while (k >= 0 && P[k] != P[i - 1]) k = pi[k];
      pi[i] = ++k;
    }

    // search
    int j = 0;
    for (int i = 1; i <= T.length; ++i) {
      while (j >= 0 && P[j] != T[i - 1]) j = pi[j];
      ++j;
      if (j == P.length) {
        pw.println(i - P.length);
        j = pi[j];
      }
    }
    pw.flush();
  }
}
