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 "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <time.h>
#include <stdio.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mpa make_pair
#define all(a) a.begin(), a.end()

template<typename T>
void vdeb(vector<T> &da) {
	int size = da.size();
	for (int i = 0;i < size;i++) {
		if (i == size - 1) {
			cout << da[i] << endl;
		}
		else {
			cout << da[i] << ' ';
		}
	}
}
template<typename T>
void vvdeb(vector<T> &da) {
	int size = da.size();
	for (int i = 0;i < size;i++) {
		vdeb(da[i]);
	}
}

int da[1010000];

void zalgo(string &s, int le, int ri){
	da[le] = ri - le;
	int i = le + 1, j = 0;
	while(ri > i){
		while(i + j < ri && s[le + j] == s[i + j]){
			j++;
		}
		da[i] = j;
		if(j == 0){
            i++;
            continue;
        }
		int k = 1;
		while(ri > i + k && k + da[k + le] < j){
			da[i + k] = da[le + k]; ++k;
		}
		i += k; j -= k;
	}
	return;
}


int main(){
	string t,p,s;
	cin >> t >> p;
	s = p+t;
	int n = s.size();
	zalgo(s, 0, n);
	//vdeb(da);
	rip(i,n,p.size()){
		if(da[i] >= p.size()){
			printf("%d\n",int(i-p.size()));
		}
	}
}
