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 <bits/stdc++.h>

std::vector<int> MPAlgorithm(const std::string& str)
{
	std::vector<int> ret(str.size() + 1);
	ret[0] = -1;
	for (int i{}; i < (int)str.size(); i++)
	{
		int prev{ret[i]};
		while (prev >= 0 && str[prev] != str[i]) prev = ret[prev];
		ret[i + 1] = prev + 1;
	}
	return std::move(ret);
}

int main()
{
	std::string T, P;
	std::cin >> T >> P;
	auto mp{MPAlgorithm(P)};
	for (int i{}, length{}; i < (int)T.size(); i++)
	{
		while (length >= 0 && T[i] != P[length]) length = mp[length];
		length++;
		if (length != (int)P.size()) continue;
		printf("%d\n", i - length + 1);
		length = mp[length];
	}

	return 0;
}
