#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long; 
const ull MOD{(1ull<<61)-1};

long long modpow(long long a, long long b){
	long long c = 1;
	while(b > 0){
		if(b & 1) c = c * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return c;
}

struct RollingHash{
	const ull m30{(1ull<<30)-1};
	const ull m31{(1ull<<31)-1};
	const ull MOD{(1ull<<61)-1};
	const ull pos{MOD*7};
	ull base;
	vector<ull> powmemo;
	vector<ull> hash;
	
	RollingHash(string s, ull b) : base(b), powmemo(s.size()+1), hash(s.size()+1){
		powmemo.at(0) = 1;
		for(int i=1; i<powmemo.size(); i++){
			powmemo.at(i) = calmod(mul(powmemo.at(i-1),base));
		}
		for(int i=0; i<s.size(); i++){
			hash.at(i+1) = calmod(mul(hash.at(i),base)+s.at(i));
		}
	}
	ull slice(int begin, int length){
		return calmod( hash.at(begin+length) + pos - mul( hash.at(begin),powmemo.at(length) ) );
	}
	ull mul(ull l, ull r){
		ull lu{l>>31};
		ull ld{l&m31};
		ull ru{r>>31};
		ull rd{r&m31};
		ull mid{ld*ru + lu*rd};
		return ( ((lu*ru)<<1) + ld*rd + ((mid&m30)<<31) + (mid>>30) );
	}
	ull calmod(ull val){
		val = (val&MOD) + (val>>61);
		if(val>=MOD) val -= MOD;
		return val;
	}
};

int main(){
	string t,p; cin>>t>>p;
	ull base{};
	RollingHash rht(t,257);
	RollingHash rhp(p,257);
	for(int i=0; i+p.size()<=t.size(); i++){
		if(rht.slice(i,p.size())==rhp.hash.back()) cout << i << endl;
	}
	
}

### Prompt

Create a solution in cpp for 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>
using namespace std;
using ll = long long; 
using ull = unsigned long long; 
const ull MOD{(1ull<<61)-1};

long long modpow(long long a, long long b){
	long long c = 1;
	while(b > 0){
		if(b & 1) c = c * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return c;
}

struct RollingHash{
	const ull m30{(1ull<<30)-1};
	const ull m31{(1ull<<31)-1};
	const ull MOD{(1ull<<61)-1};
	const ull pos{MOD*7};
	ull base;
	vector<ull> powmemo;
	vector<ull> hash;
	
	RollingHash(string s, ull b) : base(b), powmemo(s.size()+1), hash(s.size()+1){
		powmemo.at(0) = 1;
		for(int i=1; i<powmemo.size(); i++){
			powmemo.at(i) = calmod(mul(powmemo.at(i-1),base));
		}
		for(int i=0; i<s.size(); i++){
			hash.at(i+1) = calmod(mul(hash.at(i),base)+s.at(i));
		}
	}
	ull slice(int begin, int length){
		return calmod( hash.at(begin+length) + pos - mul( hash.at(begin),powmemo.at(length) ) );
	}
	ull mul(ull l, ull r){
		ull lu{l>>31};
		ull ld{l&m31};
		ull ru{r>>31};
		ull rd{r&m31};
		ull mid{ld*ru + lu*rd};
		return ( ((lu*ru)<<1) + ld*rd + ((mid&m30)<<31) + (mid>>30) );
	}
	ull calmod(ull val){
		val = (val&MOD) + (val>>61);
		if(val>=MOD) val -= MOD;
		return val;
	}
};

int main(){
	string t,p; cin>>t>>p;
	ull base{};
	RollingHash rht(t,257);
	RollingHash rhp(p,257);
	for(int i=0; i+p.size()<=t.size(); i++){
		if(rht.slice(i,p.size())==rhp.hash.back()) cout << i << endl;
	}
	
}

```