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>
using namespace std;
using ll = long long;

const __int128 rh_mod = 10000000000000061;
const ll rh_b = 1009;

class rolling_hash {
	const int n;
	vector<ll> R, H;
public:
	rolling_hash(const string& s)
		: n(s.size()), R(n + 1), H(n + 1) {
		R[0] = 1;
		for (int i = 0; i < n; i++) {
			R[i + 1] = (__int128)R[i] * rh_b % rh_mod;
			H[i + 1] = ((__int128)H[i] * rh_b + s[i]) % rh_mod;
		}
	}
	ll get(int l, int r) {
		assert(0 <= l && l <= r && r <= n);
		return (H[r] - (__int128)H[l] * R[r - l] % rh_mod + rh_mod) % rh_mod;
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	string T, P;
	cin >> T >> P;
	int n = T.size(), m = P.size();
	rolling_hash rh(T);
	ll h = rolling_hash(P).get(0, m);
	for (int i = 0; i + m <= n; i++) if (rh.get(i, i + m) == h) {
		printf("%d\n", i);
	}
	return 0;
}

