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.io.*;
import java.util.*;

public class Main{
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args){
		char[] S = sc.next().toCharArray();
		char[] P = sc.next().toCharArray();
		int n = S.length;
		int m = P.length;

		int[] T = new int[m+1];
		T[0] = -1;
		T[1] = 0;
		int i = 2;
		int j = 0;
		while(i <= m){
			if(P[i-1] == P[j]){
				T[i] = j + 1;
				i++;
				j++;
			}else if(j > 0){
				j = T[j];
			}else{
				T[i] = 0;
				i++;
			}
		}

		i = 0;
		j = 0;
		StringBuilder ans = new StringBuilder();
		while(i + j < n){
			if(P[j] == S[i + j]){
				j++;
				if(j == m){
					ans.append(i);
					ans.append("\n");
				}else{
					continue;
				}
			}
			i = i + j - T[j];
			if(j > 0){
				j = T[j];
			}
		}

		System.out.print(ans);
	}

	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next(){
			while(st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
	}
}