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>
using namespace std;

int main(){
	 ios::sync_with_stdio(false);
	string a, b;
	int x, i = 0;
	cin >> a >> b;
	for(int i = 0;a[i];i++){
		i = a.find(b, i);
		if(i == -1)break;
		cout << i << endl;
	}
	while((x = a.find(b, i)) != -1){
		cout << x << endl;
		i = x + 1;
	}
	return 0;
}*/

#include <iostream>
#include <string>
using namespace std;
string t,p;
int main(){
	ios::sync_with_stdio(false);
	cin>>t>>p;
	for(int i=0;t[i];i++){
		i=t.find(p, i);
		if(i==string::npos)break;
		cout<<i<<'\n';
	}
	return 0;
}