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<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

void KMP(string T, string P){
	int t=T.size();
	int p=P.size();
	int i,j,k;
	
	//?????????????????????
	vector<int> next(p);
	int nex;
	i=2;
	j=0;
	if(p==1){
		next[0]=-1;
		nex=0;
	}else{
		next[0]=-1;
		next[1]=0;
		while(i<p+1){
			if(P[i-1]==P[j]){
				if(i==p){
					nex=j+1;
				}else{
					next[i]=j+1;
				}
				i++;
				j++;
			}else if(j>0){
				j=next[j];
			}else{
				if(i==p){
					nex=0;
				}else{
					next[i]=0;
				}
				i++;
			}
		}
	}
	i=0;
	j=0;
	while(i<t){
		//cout << i << " "<< j<<endl;
		if(T[i+j]==P[j]){
			j++;
			if(j==p) {
				printf("%d\n",i);
				i++;
				j=nex;
			}
		}else{
			i=i+j-next[j];
			if(j>0){j=next[j];}
		}
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string T,P;
	cin >> T >> P;
	KMP(T,P);
	return 0;
}