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 <algorithm>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;


//BEGIN
template <unsigned long long MOD = 1000000007, unsigned long long base = 2009>
struct RollingHash {
	vector<unsigned long long> hash, power;

	RollingHash() {}
	RollingHash(const string& s) {
		int n = s.size();
		hash.assign(n + 1, 0);
		power.assign(n + 1, 1);
		for (int i = 0; i < n; ++i) {
			hash[i + 1] = (hash[i] * base + s[i]) % MOD;
			power[i + 1] = power[i] * base % MOD;
		}
	}
	
	unsigned long long get(int l, int r) {
		unsigned long long res = hash[r] + MOD - (hash[l] * power[r - l] % MOD);
		return res - (res >= MOD ? MOD : 0);
	}

	int LCP(const RollingHash<MOD, base>& b, int l1, int r1, int l2, int r2) {
		int len = min(r1 - l1, r2 - l2);
		int low = -1, high = len + 1;
		while (high - low > 1) {
			int mid = (low + high) / 2;
			if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
			else high = mid;
		}
		return low;
	}
};
//END


int main() {
	string T, P; cin >> T >> P;
	RollingHash<> rht(T), rhp(P);
	auto pval = rhp.get(0, P.size());
	for (int i = 0; i + P.size() <= T.size(); ++i)
		if (rht.get(i, i + P.size()) == pval)
			printf("%d\n",i);

	return 0;
}
/*
	created: 2019-11-12
	https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B
*/
