#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

class KnuthMorrisPratt{
	public:
		vector<int> fail;
		string t; // 探す文字列
		KnuthMorrisPratt(string& t) {
			this->t = t;
			int m = t.size();
			fail = vector<int>(m + 1);
			int j = fail[0] = -1;
			for (int i = 1; i <= m; ++i) {
				while (j >= 0 && t[j] != t[i - 1]) j = fail[j];
				fail[i] = ++j;
			}
		}
		vector<int> match(string& s){ // s に含まれる連続する部分文字列 t のインデックスを返す
			int n = s.size(), m = t.size();
			vector<int> res;
			for (int i = 0, k = 0; i < n; ++i) {
				while (k >= 0 && t[k] != s[i]) k = fail[k];
				if (++k >= m) {
					res.emplace_back(i - m + 1); // match at s[i-m+1 .. i]
					k = fail[k];
				}
			}
			return res;
		}
};

int main(){
	string s, t;
	cin >> s >> t;
	KnuthMorrisPratt kmp(t);
	for(auto i : kmp.match(s)){
		cout << i << endl;
	}
}


### Prompt

Develop a solution in cpp to the problem described below:

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>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

class KnuthMorrisPratt{
	public:
		vector<int> fail;
		string t; // 探す文字列
		KnuthMorrisPratt(string& t) {
			this->t = t;
			int m = t.size();
			fail = vector<int>(m + 1);
			int j = fail[0] = -1;
			for (int i = 1; i <= m; ++i) {
				while (j >= 0 && t[j] != t[i - 1]) j = fail[j];
				fail[i] = ++j;
			}
		}
		vector<int> match(string& s){ // s に含まれる連続する部分文字列 t のインデックスを返す
			int n = s.size(), m = t.size();
			vector<int> res;
			for (int i = 0, k = 0; i < n; ++i) {
				while (k >= 0 && t[k] != s[i]) k = fail[k];
				if (++k >= m) {
					res.emplace_back(i - m + 1); // match at s[i-m+1 .. i]
					k = fail[k];
				}
			}
			return res;
		}
};

int main(){
	string s, t;
	cin >> s >> t;
	KnuthMorrisPratt kmp(t);
	for(auto i : kmp.match(s)){
		cout << i << endl;
	}
}


```