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<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

typedef pair<int, int> pii;

int jt[10001];

int main()
{
	map<char, int> mt;
	string T, P;
	cin >> T >> P;

	jt[0] = -1;
	jt[1] = 0;
	int i = 2, j = 0;
	int k = 0;
	while (i <= P.size()) 
	{
		if (P[i - 1] == P[j])
		{
			jt[i] = j + 1;
			++i;
			++j;
		}
		else if (j > 0)
		{
			j = jt[j];
		}
		else
		{
			jt[i++] = 0;
		}
	}
	
	i = j = 0;
	while (i<T.size()) 
	{
		if (T[i] == P[j]) 
		{
			++i;
			++j;
			if (j == P.size()) 
			{
				cout << i - P.size() << '\n';
				j = jt[j];
			}
		}
		else if (j == 0)
		{
			++i;
		}
		else
		{
			j = jt[j];
		}
	}
	return 0;
}
