#include<bits/stdc++.h>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcountll __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << fixed << setprecision(10);
}
typedef unsigned long long ull;

struct RollingHash
{
	vector<ull> hash, pow;
	RollingHash(string s, ull _b = 1000000007)
	{
		_b = _b;
		int sz = s.length();
		hash.assign(sz + 1, 0);
		pow.assign(sz + 1, 0);

		pow[0] = 1;
		for (int i = 0; i<sz; i++) {
			pow[i + 1] = pow[i] * _b;
		}
		for (int i = 0; i<sz; i++) {
			hash[i + 1] = (hash[i] + s[i])*_b;
		}
	}
	// s[l]s[l+1]....s[r-1]のハッシュ値を取得する
	// 半開区間
	ull get(int l, int r) {
		return (hash[r] - hash[l] * pow[r - l]);
	}
};
signed main() {
	my_io();
	vector<int>ans;
	string t, s;
	cin >> t >> s;
	RollingHash t_Roll(t);
	RollingHash s_Roll(s);
	int s_hash=s_Roll.get(0, (int)s.size());
	for (int i = 0; i <=(int)t.size()-(int)s.size(); i++) {
		if (s_hash == t_Roll.get(i, i + s.size())) {
			ans.push_back(i);
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i] << endl;
	}
	return 0;
}



### Prompt

Please create a solution in cpp 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>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcountll __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << fixed << setprecision(10);
}
typedef unsigned long long ull;

struct RollingHash
{
	vector<ull> hash, pow;
	RollingHash(string s, ull _b = 1000000007)
	{
		_b = _b;
		int sz = s.length();
		hash.assign(sz + 1, 0);
		pow.assign(sz + 1, 0);

		pow[0] = 1;
		for (int i = 0; i<sz; i++) {
			pow[i + 1] = pow[i] * _b;
		}
		for (int i = 0; i<sz; i++) {
			hash[i + 1] = (hash[i] + s[i])*_b;
		}
	}
	// s[l]s[l+1]....s[r-1]のハッシュ値を取得する
	// 半開区間
	ull get(int l, int r) {
		return (hash[r] - hash[l] * pow[r - l]);
	}
};
signed main() {
	my_io();
	vector<int>ans;
	string t, s;
	cin >> t >> s;
	RollingHash t_Roll(t);
	RollingHash s_Roll(s);
	int s_hash=s_Roll.get(0, (int)s.size());
	for (int i = 0; i <=(int)t.size()-(int)s.size(); i++) {
		if (s_hash == t_Roll.get(i, i + s.size())) {
			ans.push_back(i);
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i] << endl;
	}
	return 0;
}



```