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<cstdio>
#include<cstring>

char T[1000001],P[10001];
int n,m; // T:text, P:pattern, n:T's length, m:P's length
int F[10001]; // Prefix Function

void Prefix_Table(char P[], int m){
	int i=1,j=0;
	F[0] = 0;
	while(i<m){
		if(P[i] == P[j]){
			F[i] = j+1;
			i++;
			j++;
		}
		else if(j>0)
			j=F[j-1];
		else{ F[i] = 0;
			i++;
		}
	}
}

int KMP(char T[], int n, char P[], int m){
	int i=0,j=0;
	Prefix_Table(P,m);
	while(i<n){
		if(T[i]==P[j]){
			if(j==m-1)
				printf("%d\n",i-j);
			i++;
			j++;
			
		}
		else if(j>0)
			j=F[j-1];
		else i++;
	}
	return -1;
}

int main(){
	scanf("%s",T);
	scanf("%s",P);
	n = strlen(T); m = strlen(P);
	KMP(T,n,P,m);
	return 0;
}