#include<bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;

typedef unsigned long long ull;

const ull B=10007;

void RollingHash(string T, string P){
	int t=T.size();
	int p=P.size();
	
	ull x=1;
	for (int i=0;i<p;i++) x*=B;
	
	ull th=0,ph=0;
	for (int i=0;i<p;i++) th=th*B+T[i];
	for (int i=0;i<p;i++) ph=ph*B+P[i];
	
	for (int i=0;i+p<=t;i++){
		if(th==ph) printf("%d\n",i);
		if(i+p<t) th=th*B+T[i+p]-T[i]*x;
	}
}

int main(){
	string T,P;
	cin >> T >> P;
	RollingHash(T,P);
	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>
#include<iostream>
#include<string>
using namespace std;

typedef unsigned long long ull;

const ull B=10007;

void RollingHash(string T, string P){
	int t=T.size();
	int p=P.size();
	
	ull x=1;
	for (int i=0;i<p;i++) x*=B;
	
	ull th=0,ph=0;
	for (int i=0;i<p;i++) th=th*B+T[i];
	for (int i=0;i<p;i++) ph=ph*B+P[i];
	
	for (int i=0;i+p<=t;i++){
		if(th==ph) printf("%d\n",i);
		if(i+p<t) th=th*B+T[i+p]-T[i]*x;
	}
}

int main(){
	string T,P;
	cin >> T >> P;
	RollingHash(T,P);
	return 0;
}
```