#include<iostream>
#include<string>
#include<vector>

using namespace std;

void Knuth_Morris_Pratt(string &T, string &P, vector<int> &res){
	vector<int> pat(P.size()+1);
	pat[0] = -1;
	
	for(int i = 0, j = -1; i < P.size(); i++){
		while(j >= 0 && P[i] != P[j]) j = pat[j];
		j++;
		if(P[i+1] == P[j]) pat[i+1] = pat[j];
		else pat[i+1] = j;
	}
	
	for(int i = 0, j = 0; i < T.size(); i++){
		while(j >= 0 && T[i] != P[j]) j = pat[j];
		j++;
		if(j == P.size()){
			res.push_back(i-P.size()+1);
			j = pat[P.size()];
		}
	}
}

signed main(){
	
	vector<int> ans;
	string T, P;
	
	cin>>T>>P;
	
	Knuth_Morris_Pratt(T,P,ans);
	
	for(int y : ans){
		cout<<y<<endl;
	}
	
	return 0;
}


### Prompt

Please create a solution in Cpp to the following problem:

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

### Response

```cpp
#include<iostream>
#include<string>
#include<vector>

using namespace std;

void Knuth_Morris_Pratt(string &T, string &P, vector<int> &res){
	vector<int> pat(P.size()+1);
	pat[0] = -1;
	
	for(int i = 0, j = -1; i < P.size(); i++){
		while(j >= 0 && P[i] != P[j]) j = pat[j];
		j++;
		if(P[i+1] == P[j]) pat[i+1] = pat[j];
		else pat[i+1] = j;
	}
	
	for(int i = 0, j = 0; i < T.size(); i++){
		while(j >= 0 && T[i] != P[j]) j = pat[j];
		j++;
		if(j == P.size()){
			res.push_back(i-P.size()+1);
			j = pat[P.size()];
		}
	}
}

signed main(){
	
	vector<int> ans;
	string T, P;
	
	cin>>T>>P;
	
	Knuth_Morris_Pratt(T,P,ans);
	
	for(int y : ans){
		cout<<y<<endl;
	}
	
	return 0;
}


```