#include <cstdio>
#include <cstring>
#pragma warning(disable : 4996)
char s[1000009], t[10009];
int main() {
	scanf("%s%s", s, t);
	unsigned long long hs = 0, ht = 0, pw = 1;
	int sl = strlen(s), tl = strlen(t);
	for (int i = 0; i < tl; i++) {
		hs = hs * 257 + s[i];
		ht = ht * 257 + t[i];
		pw *= 257;
	}
	for (int i = tl; i <= sl; i++) {
		if (hs == ht) printf("%d\n", i - tl);
		hs = hs * 257 + s[i] - s[i - tl] * pw;
	}
	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 <cstdio>
#include <cstring>
#pragma warning(disable : 4996)
char s[1000009], t[10009];
int main() {
	scanf("%s%s", s, t);
	unsigned long long hs = 0, ht = 0, pw = 1;
	int sl = strlen(s), tl = strlen(t);
	for (int i = 0; i < tl; i++) {
		hs = hs * 257 + s[i];
		ht = ht * 257 + t[i];
		pw *= 257;
	}
	for (int i = tl; i <= sl; i++) {
		if (hs == ht) printf("%d\n", i - tl);
		hs = hs * 257 + s[i] - s[i - tl] * pw;
	}
	return 0;
}
```