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 <iostream>
#include <string>

int max(int x, int y)
{
	 return x>y? x : y;
}

int main()
{
	std::string T, P;
	getline(std::cin, T);
	getline(std::cin, P);
	
	int n = T.length();
	int m = P.length();
	
	// construct KMP table
	int* KMPtable = new int[m+1];
	KMPtable[0] = -1;
	KMPtable[1] = 0;
	int i = 2, j = 0;
	for (; i<m+1; i++) {
		if (P[i-1] == P[j]) {
			j++; KMPtable[i] = j; 
		}
		else if (j>0) {
			j = KMPtable[j]; i--;
		}
		else KMPtable[i] = 0;
	}
	
	// for (int i=0; i<m; i++) std::cout << KMPtable[i] << " ";
	// std::cout << std::endl;
	
	// search by KMP
	i=0, j=0;
	while (i<n && j<m) {
		if (T[i+j] == P[j]) {
			if (j == m-1) {
				std::cout << i << std::endl;
				// std::cout << i << ": pattern match succeeded" << std::endl; 
				i += m - KMPtable[m];
				j = KMPtable[m];
			}
			else { j++; }
		}
		else {
			// std::cout << i << ": pattern match failed at index " << j << std::endl; 
			i += j - KMPtable[j];
			j = max(0, KMPtable[j]);
		}
	}
	
	delete[] KMPtable;
	
	return 0;
}
		

