//be naame khodaa
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cassert>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <complex>
#define pb push_back

using namespace std;
typedef long long ll;

const int N = 1000*1000 + 5;

int f[N];

void calcf(string s, int n){
	f[0] = -1;
	for (int i = 1; i <= n; i++){
		f[i] = f[i-1];
		while (f[i] >= 0 && s[i-1] != s[f[i]])
			f[i] = f[f[i]];
		f[i]++;
	}
}

int patMatch(string t, string s, int n){
	int cur = 0, ans = 0;
	for (int i = 0; i < t.size(); i++){
		while (cur >= 0 && t[i] != s[cur])
			cur = f[cur];
		cur++;
		if (cur == n) cout << i-n+1 << '\n', cur = f[n], ans++;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	string t, s;
	cin >> t >> s;
	int n = s.length();
	calcf(s, n);
	patMatch(t, s, n);
}

### 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
//be naame khodaa
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cassert>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <complex>
#define pb push_back

using namespace std;
typedef long long ll;

const int N = 1000*1000 + 5;

int f[N];

void calcf(string s, int n){
	f[0] = -1;
	for (int i = 1; i <= n; i++){
		f[i] = f[i-1];
		while (f[i] >= 0 && s[i-1] != s[f[i]])
			f[i] = f[f[i]];
		f[i]++;
	}
}

int patMatch(string t, string s, int n){
	int cur = 0, ans = 0;
	for (int i = 0; i < t.size(); i++){
		while (cur >= 0 && t[i] != s[cur])
			cur = f[cur];
		cur++;
		if (cur == n) cout << i-n+1 << '\n', cur = f[n], ans++;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	string t, s;
	cin >> t >> s;
	int n = s.length();
	calcf(s, n);
	patMatch(t, s, n);
}

```