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
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	final boolean DEBUG = true;
	long d = 1000000007l;
	void run() {
		Scanner scan = new Scanner(System.in);
		StringBuffer sb = new StringBuffer();
		char[] txt = scan.next().toCharArray();
		char[] pat = scan.next().toCharArray();
		int tl = txt.length;
		int pl = pat.length;
		if (tl < pl)
			return;
		
		long h = 1, p = 0, t = 0;
		for (int i = 0; i < pl; i++) {
			h = h * d;
			p = d * p + pat[i];
			t = d * t + txt[i];
		}
		
		for (int i = 0; i <= tl - pl; i++) {
			if (p == t)
				sb.append(i + "\n");
			if (i + pl < tl)
				t = t * d + txt[i + pl] - txt[i] * h;
		}
		System.out.print(sb.toString());
	}
	public static void main(String[] args) {
		new Main().run();
	}
}

