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 <vector>
#include<set>
using namespace std;


vector<int> arregloPatron(string patron){
	int i= 0, j = 1;
	vector<int> arr(patron.size());
	
	while( j < patron.size() ) {
		if( patron[i] != patron[j] ){
			if( i != 0){
				i = arr[i-1];
			}
			else {
				arr[j] = 0;
				j++;
			}
			
		}
		else if( patron[i] == patron[j] ){
			arr[j] = i+1;
			i++; j++;
		}
	}
	
	return arr;
	
}

void kmp(string texto, string patron, set<int> &res ){
	vector<int> lps;
	lps = arregloPatron(patron);
	
	int i = 0, j = 0;
	
	while( i < texto.length() ){
		if( texto[i] == patron[j] ){
			i++;
			j++;
		}
		else {
			if( j != 0 ){
				j = lps[j-1];
			}
			else {
				i++;
			}
		}
		
		//cout << i << " " << j << endl;
		if( j == patron.size() ){
			cout << i-patron.size() << endl;
			//res.insert(i-patron.size());
		}
	}
	
	//cout << j << endl;
	
	
	//return false;
}


int main(){
	
	
	string original, patron;
	cin >> original >> patron;
	set<int> res;
	kmp(original, patron, res);
	//for(set<int> i: res)
	//	cout << i << endl;
	//set <int> :: iterator it; 
	//for(it = res.begin(); it != res.end(); it++)
	//	cout << *it << endl;
	
	
	return 0;
}
