#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin>>s;
	string q;
	cin>>q;

	vector<int>a;
	a.push_back(-1);
	for(int i=1,k=-1;i<=q.size();i++){
		for(;k>=0&&q[i-1]!=q[k];)k=a[k];
		a.push_back(++k);
	}

	vector<int>r;
	for(int i=0,k=0;i<s.size();i++){
		for(;k>=0&&(k==q.size()||q[k]!=s[i]);)k=a[k];
		if(++k==q.size())r.push_back(i+1-k);
	}
	for(int i=0;i<r.size();i++)printf("%d\n",r[i]);
}
### Prompt

Please formulate a CPP solution 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>
#include <cstdio>
using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin>>s;
	string q;
	cin>>q;

	vector<int>a;
	a.push_back(-1);
	for(int i=1,k=-1;i<=q.size();i++){
		for(;k>=0&&q[i-1]!=q[k];)k=a[k];
		a.push_back(++k);
	}

	vector<int>r;
	for(int i=0,k=0;i<s.size();i++){
		for(;k>=0&&(k==q.size()||q[k]!=s[i]);)k=a[k];
		if(++k==q.size())r.push_back(i+1-k);
	}
	for(int i=0;i<r.size();i++)printf("%d\n",r[i]);
}
```