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 "bits/stdc++.h"
using namespace std;
#define LL long long
int a[100010];
char s[100010];
const int maxn = 400010;
const int logn = 19;
vector <int> vc[maxn];
set<int>st;
list<int>li;
map<string,int>m;
pair<int,int>p;
bool mark[maxn];
int n, k;

void join() {
   string s,t;
   cin>>s>>t;
   for(int i=0;i<s.size();i++){
       string k=s.substr(i,t.size());
       if(k==t)cout<<i<<"\n";
   }
}

void solve() {
    LL n;
    cin >> n;
    long long x=n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(&a[0],&a[n]);
    for(int i=0;i<n-1;i++){
        if(a[i]==a[i+1]) --x;
    }
    cout<<x<<"\n";
}

int main()
{
    //int tc;
	//scanf("%d", &tc);
	//while(tc-->0) {
	    //solve();
	    join();
	//}
    return 0; 
}
