#include <bits/stdc++.h>
using namespace std;

#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define per(i,n) for (int i=(int)(n)-1;i>=0;i--)
#define For(i,n) for (int i=1;i<=(int)(n);i++)
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define vi vector <int>
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define pb push_back
#define re return
#define se second
#define fi first
const int INF=0x7fffffff;
const int MAXN=10000+3;

string s,t;
int f[MAXN];

void init_fail(const string &t,int f[]){
	int k=f[0]=-1;
	for (int i=1;i<t.size();i++){
		while (k>-1 && t[k+1]!=t[i]) k=f[k];
		f[i]=k+=t[k+1]==t[i];
	}
//	dea(f,t.size());
}

void kmp(const string &s,const string &t){
	init_fail(t,f);
	int k=-1;
	for (int i=0;i<s.size();i++){
		while (k>-1 && t[k+1]!=s[i]) k=f[k];
		k+=t[k+1]==s[i];
		if (k==t.size()-1){
			cout<<i-t.size()+1<<endl;
			k=f[k];
		}
	}
}

int main(){
	fio;
	cin>>s>>t;
	kmp(s,t);
	re 0;
}

### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;

#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define per(i,n) for (int i=(int)(n)-1;i>=0;i--)
#define For(i,n) for (int i=1;i<=(int)(n);i++)
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define vi vector <int>
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define pb push_back
#define re return
#define se second
#define fi first
const int INF=0x7fffffff;
const int MAXN=10000+3;

string s,t;
int f[MAXN];

void init_fail(const string &t,int f[]){
	int k=f[0]=-1;
	for (int i=1;i<t.size();i++){
		while (k>-1 && t[k+1]!=t[i]) k=f[k];
		f[i]=k+=t[k+1]==t[i];
	}
//	dea(f,t.size());
}

void kmp(const string &s,const string &t){
	init_fail(t,f);
	int k=-1;
	for (int i=0;i<s.size();i++){
		while (k>-1 && t[k+1]!=s[i]) k=f[k];
		k+=t[k+1]==s[i];
		if (k==t.size()-1){
			cout<<i-t.size()+1<<endl;
			k=f[k];
		}
	}
}

int main(){
	fio;
	cin>>s>>t;
	kmp(s,t);
	re 0;
}

```