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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	string text, pat;
	cin >> text >> pat;

	int n = text.size();
	int k = pat.size();
	vector<int> failure(k + 1);

	failure[0] = 0;
	for(int i = 1; i <= k; i++) {
		int v = i - 1;
		while(v > 0) {
			v = failure[v];
			if(pat[v] == pat[i - 1]) {
				failure[i] = v + 1;
				v = -1;
				break;
			}
		}
		if(v == 0) {
			failure[i] = 0;
		}
		//printf("failure[%d] = %d\n", i, failure[i]);
	}

	int state = 0;
	vector<int> ans;

	for(int pos = 0; pos < n; pos++) {

		if(state < k && pat[state] == text[pos]) {
			state += 1;
			if(state == k) {
				ans.push_back(pos + 1 - k);
			}
			continue;
		}

		if(state > 0) {
			state = failure[state];
			pos -= 1;
		}
	}

	ios::sync_with_stdio(false);

	for(auto a : ans) {
		cout << a << "\n";
	}

	return 0;
}

