#include "bits/stdc++.h"
using namespace std;
int *compute_table(const string &t) {
	int m = t.size();
	int *table = new int[m + 1];
	table[0] = -1;
	int j = -1;
	for (int i = 0; i < m; i++) {
		while (j >= 0 && t[i] != t[j]) j = table[j];
		j++;
		table[i + 1] = j;
	}
	return table;
}
vector<int> string_match(const string &s, const string &t) {
	int n = s.size();
	int m = t.size();
	int *table = compute_table(t);
	vector<int> ans;
	int i = 0, j = 0;
	while (i < n) {
		if (s[i] == t[j]) {
			i++; j++;
			if (j == m) {
				ans.push_back(i - m);
				j = table[j];
			}
		}
		else if (j > 0) j = table[j];
		else i++;
	}
	delete[] table;
	return ans;
}
int main() {
	string S, T;
	cin >> S >> T;
	vector<int> ans = string_match(S, T);
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}
}
### Prompt

Your challenge is to write 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;
int *compute_table(const string &t) {
	int m = t.size();
	int *table = new int[m + 1];
	table[0] = -1;
	int j = -1;
	for (int i = 0; i < m; i++) {
		while (j >= 0 && t[i] != t[j]) j = table[j];
		j++;
		table[i + 1] = j;
	}
	return table;
}
vector<int> string_match(const string &s, const string &t) {
	int n = s.size();
	int m = t.size();
	int *table = compute_table(t);
	vector<int> ans;
	int i = 0, j = 0;
	while (i < n) {
		if (s[i] == t[j]) {
			i++; j++;
			if (j == m) {
				ans.push_back(i - m);
				j = table[j];
			}
		}
		else if (j > 0) j = table[j];
		else i++;
	}
	delete[] table;
	return ans;
}
int main() {
	string S, T;
	cin >> S >> T;
	vector<int> ans = string_match(S, T);
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}
}
```