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
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

vector<int> compute_lps(string s,int m,vector<int> lps){
	int len = 0;
	lps[0] = 0;
	int i = 1;
	while(i < m){
		if(s[i] == s[len]){
			len++;
			lps[i] = len;
			i++;
		}else{
			if(len != 0) len = lps[len-1];
			else{
				lps[i] = 0;
				i++;
			}
		}
	}

	return lps;
}

void kmp_search(string pat,string txt){
	int m = pat.length();
	int n = txt.length();

	vector<int> lps(m);
	lps = compute_lps(pat,m,lps);

	int i = 0,j = 0;
	while(i < n){
		if(pat[j] == txt[i]){
			i++;
			j++;
		}

		if(j == m){
			cout << i - j << endl;
			j = lps[j-1];
		}else if(i < n & pat[j] != txt[i]){
			if(j != 0) j = lps[j-1];
			else i++;
		}
	}
}

int main()
{
	string t,p;
	cin >> t >> p;
	kmp_search(p,t);

	return 0;
}
