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
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <list>
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<int, ll> i_ll;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define pb push_back
 
int INF = INT_MAX / 10;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

vector<int> z_algorithm(string s) {
	int N = s.length();
	vector<int> a(N + 1); a[0] = N;
	int j = 0;
	for (int i = 1; i <= N;) {
		for (; i + j < N && s[i + j] == s[j]; j++);
		if (a[i] = j) {
			int k;
			for (k = 1; k + a[k] < a[i]; k++)
				a[i + k] = a[k];
			i += k; j -= k;
		}
		else i++;
	}
	return a;
}

int main() {
	string t; cin >> t;
	string s; cin >> s;
	int N = s.length(), M = t.length();
	string st = s + '$' + t;
	vector<int> a = z_algorithm(st);
	for (int j = 0; j <= M; j++)
		if (a[N + 1 + j] == N)
			printf("%d\n", j);
}